准备知识

除了1和自身外，没法被其他自然数整除的大于1的整数

质数

除了1和自身外，没法被其他自然数整除的大于1的整数
如：2，3，5，7，11，13

互质数

公因数只有1的两个非零自然数，叫做互质数。
如 5，12

欧拉函数

小于n的正整数中与n互质的数的数目。
如:1到7中，与8互质的整数为1，3，5，7，所以φ(8)=4

性质：

1. 给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)
   如：3≡5 （mod 2)
2. 若n为质数则 φ(n)=n-1(注：n为质数，n的因数只有1和n,前n-1个数与n的公因数只有1，所以 φ(n)=n-1 即1，2，3，...，n-1)
3. 若m,n互质， φ(m * n)=φ(m) * φ(n) (当m,n都为质数时，φ(m*n)=φ(m) * φ(n) = (m-1) * (n-1) ,因为m, n 为质数，所以m*n只与m或n的倍数不是互质数，一共有m * n -1 个数， m的倍数有n-1个， n的倍数m-1个，所以φ(m * n)=(m * n-1) - (m-1) - (n-1)=(m-1) * (n-1)）
4. 若m,n 互质，则 ` m ** φ(n) ≡ 1 (mod n) 4.1 模反元素：若m,n 互质，一定存在一个整数a, 使得：m * a ≡ 1 (mod n)。称a为m对于n`的模反元素

RSA生成过程

1. 随机选择两个极大的不相等质数p, q；
   1.1 为方便计算取p = 13, q = 17

2. 计算p与q的乘积n；
   2.1 n = 13 * 17 = 221

3. 计算n的欧拉函数φ(n)；
   3.1 φ(n) = （13 - 1） * （17 - 1） = 192

4. 随机选择一个整数e，1<e<φ(n)且e与φ(n)互质；
   4.1 例如取e = 5

5. 计算e对于φ(n)的模反元素d， ed ≡ 1 (mod φ(n)) e * d = k * φ(n) + 1 d = (k * φ(n) + 1)/e 取k=0,1,2...计算d的数值，直到d为整数 5.1 求得 d = 77，此时k=2

6. 将n和e封装为公钥， n和d封装为私钥;
   6.1 即以上步骤生成的公钥为 221，5 私钥为 221，77

加密过程

1. 有待加密信息m(m必须为整数，字符串取ascii值或unicode值, 且m < n)；
   1.1 例如取m = 10

2. 根据加密公式m ** e ≡ c (mod n) ，使用公钥加密,生成密文 c;
   2.1 10 ** 5 % 221 = 108 即c = 108

3.根据解密公式 c ** d ≡ m (mod n) 使用私钥解密,生成明文 m为;
3.1 108 ** 77 % 221 = 10 即m = 10

RSA加密安全性探讨：

1. 基于已知的公钥，是否能计算出私钥：即已知n,e 求 d
2. 因为 d = (k * φ(n) + 1)/e， 所以只需计算出n的欧拉函数值φ(n), 已知n是两个质数p、q的乘积 φ(n) = φ(p * q) = φ(p) * φ(q) = (p-1) * (q-1)
3. RSA加密安全强度就是在于n的因数分解的难度，n越大越安全，目前n为1024或2048位，普通计算机无法对其进行因式分解