博客

RSA算法和证明

  • Post author:
  • Post category:其他


1977 年由罗纳德·李维斯特（Ron


R


ivest）、阿迪·萨莫尔（Adi


S


hamir）和伦纳德·阿德曼 （Leonard


A


dleman）一起提出，因此名为 RSA 算法。

RSA 算法中公私钥的产生

1 随机选择两个不相等的质数 p 和 q p = 11, q = 29
2 计算 p 和 q 的乘积 n（明文小于 n） n = p× q = 11 * 29 = 319
3 计算 n 的欧拉函数 v=φ(n) 欧拉函数是小于或等于n的正整数中与n互质的数的数目。所谓的互质，就是最大公约数为1。

  • φ(8)，中1~8与8互质的数由1,3,5,7，因此 φ(8)=4。
  • 欧拉函数是积性函数：若m,n互质，φ(mn) =φ(m)φ(n) 。
  • 由于p、q都是质数，φ(p)=p-1，φ(q)=q-1，那么，φ(n)=φ(pq)=φ(p)φ(q)=(p-1)(q-1)

v=φ(319)=(11-1)(29-1) = 280

4 随机选择一个整数 k

  • 1< k < v，且 k 与 v 互质
例子选择 k = 187
5 计算 k 对于 v 的模反元素 d (d × k）%v = 1。也就是在模 v 中的 d ≡ k-1 (mod v)

例子结果为3 （3*187）% 280 = 561%280 = 1

6 公钥：(k,n) （187,319）
7 私钥：(d,n) （3,319）

RSA 算法加解密流程

1 加密 c ≡ m^k (mod n)，m 为明文，c为密文 明文123。

  • 以公钥加密：c≡123^187≡161（mod 319)
  • 以私钥加密：c≡123^3≡140（mod 319)
2 解密 m ≡ c^d (mod n) 以私钥加密，用公钥解密；以公钥加密，用私钥解密

  • 以公钥加密，以私钥解密：m≡161^3≡123（mod 319)
  • 以私钥加密，以公钥解密：m≡140^187≡123（mod 319)

证明


条件和相关的定理


推导

网上不少资料在推导中，只是给出了第一种情况，即明文m和n=qp互质的情况，如果q和p的数值远大于m是没有问题，但是不见得这个条件成立，而且也无需这个条件。第二种情况，对于我这种数学渣渣来讲，是很精巧的计算，参考自

https://wenku.baidu.com/view/5200777565ce05087732133e.html


版权声明：本文为flowingflying原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。