rsa加密相关基础知识(1)

RSA 基本原理：

选取两个不同的大素数p、q，并计算N=p*q，选取小素数d，并计算e，使d*e % (p-1)(q-1)=1，
对于任意A若B=A**d % N
则A=B**e % N

可见d、e形成了非对称秘钥关系，加密者用公钥d加密，解密者可用私钥e解密，第三者即使拦截了密文B、公钥d和N，在不知道p、q的前提下，无法推算出e，从而无法获得明文A。当N取非常大的值时，将其因式分解成p、q是非常困难的，例如当N为1024 bit时，据分析，需动用价值数千万美金的大型计算机系统并耗费一年的时间。

质数与互质关系：

质数又称素数，指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

互质关系：两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）

　　1.任意两个质数构成互质关系，比如13和61。

　　2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

　　3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

　　4. 1和任意一个自然数是都是互质关系，比如1和99。

　　5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。

　　6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

欧拉函数：任意给定正整数n,计算在小于等于n的正整数之中，有多少个与n构成互质关系。计算这个值的方法叫做欧拉函数。以φ(n)表示。如φ(6)=2，因为在1到6之中，与6形成互质关系的有1，5。

欧拉函数的计算分为5种情况：

　　1. n=1，φ(1)=1

　　2.n是质数，φ(n)=n-1.质数与每个小于它的数都构成互质关系

　　3.n是质数的k次方，比如n=p^k, p是质数。φ(n)=p^k-p^(k-1)。在小于等于n的数字中，只有不包含因数p的数字才能与n互质。包含p的数字为 1*p，2*p，3*p。。。p^(k-1)*p 一共有p^(k-1)个。

　　4. n是两个质数的乘积，n=a*b， φ(n)=φ(a)*φ(b)

　　5.任意大于1的整数都可以拆成一系列质数的乘积。此时φ(n)=n*(1- p₁^-1)(1-p₂^-1)...(1-p_n^-1). 可通过情况3与情况4推导出来。

欧拉定理：

两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的式子成立： a^φ(n)≡1 (mod n)

如果n为质数则 a^n-1≡1(modn). 此为费马小定理

模反元素：

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除。即 ab≡1(modn) .可用欧拉定理证明b一定存在