RSA算法原理（二）
作者:阮一峰
上次，我介绍了一些数论知识。
有了这些知识，我们就能理解RSA算法。这是目前地球上最重要的加密算法。
六、密钥生成步骤我们通过一个例子，来了解RSA算法。假设爱丽丝想与鲍勃进行加密通信，她应该如何生成公钥和私钥？
在第一步中，随机选择两个不相等的素数P和Q。
爱丽丝选择了61和53。(在实际应用中，这两个素数越大，就越难破解。)
第二步是计算p和q的乘积n。
爱丽丝把61和53相乘。
n = 61×53 = 3233
n的长度是密钥长度。3233被写成一个二进制数1100100010001，总共12位，所以这个密钥是12位。在实际应用中，RSA密钥一般为1024位，重要场合为2048位。
第三步是计算欧拉函数φ(n)
根据公式:
φ(n) = (p-1)(q-1)
爱丽丝计算出φ(3233)等于60×52，或3120。
第四步是随机选择一个整数e，条件是1
爱丽丝在1到3120之间，随机选择了17个。(在实际应用中，经常选择65537。)
在第五步中，计算φ(n)的e的模逆元素d。
所谓的“模逆元素”是指有一个整数d，它使ed的余数除以φ(n) 1。
ed ≡ 1 (mod φ(n))
这个公式相当于
ed - 1 = kφ(n)
因此，求模逆元素D本质上就是求解下面的二元一阶方程。
ex + φ(n)y = 1
已知e=17，φ(n)=3120，
17x + 3120y = 1
这个方程可以用“扩展欧几里德算法”来求解，这里省略了具体的过程。简而言之，爱丽丝计算出一组整数解为(x，y)=(2753，-15)，即d=2753。
到目前为止，所有的计算都已完成。
步骤6:将N和E封装成公钥，将N和D封装成私钥。
在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥是(3233，17)，私钥是(3233，2753)。
在实际应用中，公钥和私钥的数据以ASN.1格式表示(例如)。
七、RSA算法可靠性审查上述关键生成步骤，共六个数字:
pqnφ(n)ed
在这六个数字中，两个(n和e)用于公钥，其他四个数字不公开。密钥是D，因为N和D构成了私钥。一旦D泄露，就等于私钥泄露。
那么，有没有可能用已知的n和e来推导d？
(1)ed≡1 (mod φ(n)).只有当e和φ(n)已知时，才能计算d。
(2)φ(n)=(p-1)(q-1).只有当p和q已知时，才能计算φ(n)。
(3)n=pq .只有通过分解n因子才能计算p和q。
结论:如果n可以分解，d可以计算，这意味着私钥被破解了。
然而，大整数的因式分解非常困难。目前，除了暴力破解之外，还没有找到其他有效的方法。*写道:
RSA算法的可靠性取决于分解最大整数的难度。换句话说，分解最大整数越困难，RSA算法就越可靠。
如果有人找到一个快速的因式分解算法，RSA的可靠性将大大降低。但是找到这样一个算法的可能性非常小。今天只有一个短的RSA密钥可以被猛烈破解。直到2008年，世界上还没有可靠的方法来攻击RSA算法。
只要密钥的长度足够长，用RSA加密的信息实际上就无法解密。"
例如，您可以考虑3233 (61×53)，但不能考虑以下整数。
1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507 917026122142913461670429214311602221240479274737794080665351419597459856902143413
它等于两个质数的乘积:
33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489×3674604360436043478071694949498373713771377781467999489489×36
事实上，这可能是人类分解的最大整数(232位十进制，768位二进制)。比这更大的因式分解还没有报道过，所以迄今为止破解的最长的RSA密钥是768位。
八、用公钥和密钥加密和解密，可以加密和解密。
(1)加密需要公钥(n，e)
假设鲍勃想把加密消息M发送给爱丽丝，他将用爱丽丝的公钥(n，e)加密M。请注意，m必须是整数(字符串可以是ascii码或unicode码)，m必须小于n。
所谓“加密”就是计算下面的公式C:
me≡ c (mod n)
爱丽丝的公钥是(3233，17)，鲍勃的M假设为65，那么可以计算出下面的等式:
6517≡ 2790 (mod 3233)
所以，C等于2790，鲍勃给爱丽丝发了2790。
(2)要解密的私钥(n，d)
爱丽丝从鲍勃那里得到2790英镑后，她用自己的私钥(3233，2753)解密了它。可以证明下面的等式一定是正确的:
cd≡ m (mod n)
也就是说，C的d次方除以n的余数是m。现在，C等于2790，私钥是(3233，2753)，所以爱丽丝计算
27902753≡ 65 (mod 3233)
因此，爱丽丝知道鲍勃加密前的原始文本是65。
到目前为止，“加密-解密”的整个过程已经完成。
我们可以看到，如果我们不知道D，就没有办法从c中找到M。如前所述，要知道D，N必须分解，这是极其困难的，所以RSA算法保证了通信的安全性。
你可能会问，公钥(n，e)只能加密小于n的整数，所以如果我想加密大于n的整数，我应该怎么做？有两种解决方案:一种是将长信息分成几条短消息，每条短消息分别加密；另一种是先选择一种“对称加密算法”(如DES)，用该算法的密钥加密信息，然后用RSA公钥加密DES密钥。
九.私钥解密的证明最后，让我们证明为什么用私钥解密可以正确地得到M。那就是证明下面的公式:
cd≡ m (mod n)
因为根据加密规则
me≡ c (mod n)
因此，C可以写成以下形式:
c = me- kn
将C代入我们需要证明的解密规则:
(me- kn)d≡ m (mod n)
这相当于证明
med≡ m(模n)
由于
ed ≡ 1 (mod φ(n))
因此
ed = hφ(n)+1
插入:
mhφ(n)+1≡ m (mod n)
接下来，分为两个案例来证明上述公式。
(1)m和n是质数。
根据欧拉定理，此时
mφ(n)1(mod n)
得到
(mφ(n))h× m ≡ m (mod n)
原始公式已被证明。
(2)m和n不是互素的。
此时，因为n等于素数p和q的乘积，所以m必须等于kp或kq。
以m = kp为例，考虑到此时K和Q必须互为质数，根据欧拉定理，下列公式成立:
(kp)q-1≡ 1(模q)
走得更远
[(kp)q-1]h(p-1)× kp ≡ kp (mod q)
也就是说，
(kp)ed≡ kp (mod q)
将其改写成以下等式
(kp)ed= tq + kp
此时，t必须能被p整除，即t=tp。
(kp)ed= tpq + kp
因为m=kp，n=pq，所以
med≡ m(模n)
原始公式已被证明。
(结束)