1.随机取大质数 p、q
2.设 n = p x q, n 的二进制位数就是密钥长度,一般为1024,2048.
3.计算n的欧拉函数 φ(n) = (p - 1)(q - 1)
4.从 1 - φ(n) 之间选择一个整数,且 e 与 φ(n) 互质,计作 e
5.计算 e 对于 φ(n) 的模反元素d
ed ≡ 1 (mod φ(n))
意思就是 ed / φ(n) 余数 1
等价于 ed - 1 = k * φ(n), 由于d 和 k 未知,相当于二元一次方程求解
- (n,e) 作为公钥, (n,d) 作为私钥
7.加密: me ≡ c (mod n) ,其中m (密文,整数)二进制长度不可超过n m:明文 c:密文
8.解密: cd ≡ m (mod n) 欧拉定理可证
9.暴力破解:
- 因为解密需要私钥(n,d).
- 根据
ed ≡ 1 (mod φ(n)) - e 已经是公钥提供了,所以只要知道φ(n)就可以破解
- 问题转化为求 φ(n):
- 求 φ(n), 根据
φ(n) = (p - 1)(q - 1)
- 求 φ(n), 根据
- 所以转求 p - 1 和 q - 1, 根据
n = p * q
- 所以转求 p - 1 和 q - 1, 根据
- 只要因数分解 n 得出p 和 q 就可以计算
φ(n) = (p - 1)(q - 1)
- 只要因数分解 n 得出p 和 q 就可以计算
- 但是,想要因数分解n为两个大质数的乘积,只能从最小的质数一点点循环的试,目前貌似只有768位的二进制被质因数分解了.再长还未公布.
