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)

爱丽丝算出φ(n)等于60×52=3120。

 

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

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

 

第五步，计算e对于φ(n)的模反元素d。

所谓"模反元素"就是指有一个整数d，可以使得ed被φ(n)除的余数为1。

ed ≡ 1 (mod φ(n))

这个式子等价于

ed - 1 = kφ(n)

实质上就是对下面这个二元一次方程求解。

ed + φ(n)k = 1

已知 e=17, φ(n)=3120，

17d + 3120k = 1

这个方程可以用"扩展欧几里得算法"求解，此处省略具体过程。

总之，爱丽丝算出一组整数解为 (d,k)=(2753,-15)，即 d=2753。

至此所有计算完成。

 

第六步，将n和e封装成公钥，n和d封装成私钥。

在爱丽丝的例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。

 

第七步：发送公钥，保留私钥。此消息在centificate中。

爱丽丝将公钥（3233,17）发给Bob，自己保留私钥就是（3233, 2753）。

 证书公钥见下面的抓包