六、密钥生成的步骤

前面我介绍了一些数论知识。 有了这些知识，我们就可以看懂RSA算法。这是目前地球上最重要的加密算法。 我们通过一个例子，来理解RSA算法。假设[爱丽丝](http://zh.wikipedia.org/wiki/%E7%88%B1%E4%B8%BD%E4%B8%9D%E4%B8%8E%E9%B2%8D%E4%BC%AF)要与鲍勃进行加密通信，她该怎么生成公钥和私钥呢？  第一步，随机选择两个不相等的质数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 爱丽丝就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。） 第五步，计算e对于φ(n)的模反元素d。 所谓["模反元素"](http://zh.wikipedia.org/wiki/%E6%A8%A1%E5%8F%8D%E5%85%83%E7%B4%A0)就是指有一个整数d，可以使得ed被φ(n)除的余数为1。 > 　　ed ≡ 1 (mod φ(n)) 这个式子等价于 > 　　ed - 1 = kφ(n) 于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。 > 　　ex + φ(n)y = 1 已知 e=17, φ(n)=3120， > 　　17x + 3120y = 1 这个方程可以用["扩展欧几里得算法"](http://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95)求解，此处省略具体过程。总之，爱丽丝算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。 至此所有计算完成。 第六步，将n和e封装成公钥，n和d封装成私钥。 在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。 实际应用中，公钥和私钥的数据都采用[ASN.1](http://zh.wikipedia.org/zh-cn/ASN.1)格式表达（[实例](http://hi.baidu.com/mathack/item/d0ad4cc1514a3663f7c95da2)）。