RSA的公钥是怎样计算出来的?

时间:2023-01-08 19:02:47
第一步,随机选择两个不相等的质数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)。
RSA的公钥是怎样计算出来的?
 证书公钥见下面的抓包
RSA的公钥是怎样计算出来的?
 
  • RSA的公钥是怎样计算出来的?
  • 大小: 31.1 KB
0
0
分享到: RSA的公钥是怎样计算出来的? RSA的公钥是怎样计算出来的?
参考知识库
RSA的公钥是怎样计算出来的?
语音识别与合成知识库 294  关注 | 256  收录
RSA的公钥是怎样计算出来的?
计算机视觉知识库 780  关注 | 203  收录
RSA的公钥是怎样计算出来的?
自然语言理解和处理知识库 296  关注 | 87  收录
RSA的公钥是怎样计算出来的?
知识工程知识库 90  关注 | 69  收录
评论