RSA简介：

RSA加密算法使用不同的加密密钥与解密密钥，且由已知加密密钥推导出解密密钥在计算上是不可行的，以此来保障安全。
RSA算法通常是先生成一对RSA密钥，公钥和私钥，私钥由用户保存，公钥可对外公开。
为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位或2048位 。
RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。

前置技能（数论知识）

在讲解原理之前，需要掌握一些数论知识才行。

互质：如果整数 a，b 的最大公因数为 1，即：gcd(a, b) == 1，称 a, b互质。

欧拉函数
定义：对于正整数 x，$\varphi (x):=从1至x中，与x互质的整数的个数$
例如：$\varphi (1)=1,\varphi (2)=1,\varphi (8)=4$

欧拉函数有以下性质：

• 若 p 为质数，则 $\varphi (p)=p-1$
• 若 a, b 互质，则 $\varphi (ab)=\varphi (a)\ast \varphi (b)$
• 若 a, n 互质，则 $a^{\varphi (n)}\equiv 1(modn)$

证明过程，请阅读 《初等数论及其应用·第五版》p174 - p177，提取密码2233

RSA加密原理

1. 选取两个大素数，p, q
2. 令 n = p * q，则 $\varphi (n)=(p-1)\ast (q-1)$
3. 选取一个与 $\varphi (n)$ 互质的数 E
4. 计算 E 模 $\varphi (n)$ 的逆元 D, 即 $E\ast D\equiv 1(mod\varphi (n))$

现在，公钥就是（E, n），私钥就是 （D，n）
假设待加密数据为 a，（a必须与n互质，只需要保证a < min(p,q) 就行了）

加密： $m=Encrypt(a)=a^E(modn)$
解密：$a=Decrypt(m)=m^D(modn)$

证明一下：
$$m^D=a^{ED}=a^{k\varphi (n)+1}=a^{k\varphi (n)}\ast a=(a^{\varphi (n)}{)}^k\ast a=(k^{\prime }n+1{)}^k\ast a=1^k\ast a=a(modn)$$