RSA算法原理（二）

RSA算法原理（二）2014-10-16 阮一峰上一次，我介绍了一些数论知识。

有了这些知识，我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。

六、密钥生成的步骤

我们通过一个例子，来理解RSA算法。假设爱丽丝要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？

第一步，随机选择两个不相等的质数p和q。

爱丽丝选择了61和53。（实际应用中，这两个质数越大，就越难破解。）

第二步，计算p和q的乘积n。

爱丽丝就把61和53相乘。

n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

第三步，计算n的欧拉函数φ（n）。

根据公式：

φ（n） = （p-1）（q-1）

爱丽丝算出φ（3233）等于60×52，即3120。

第四步，随机选择一个整数e，条件是1< e < φ（n），且e与φ（n）互质。

爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）

第五步，计算e对于φ（n）的模反元素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

URL：http://www.bianceng.cn/Programming/sjjg/201410/45910.htm

这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。总之，爱丽丝算出一组整数解为（x,y）=（2753,-15），即 d=2753。

至此所有计算完成。