RSA
Abstract
RSA 加密算法是一种非对称加密算法。
加密步骤
- 一对不相等且足够大的质数
p q - 计算p，q的乘积
n = p * q - 计算n的欧拉函数
phi(n) = (p - 1)*(q - 1) - 选一个和phi(n)互质的整数e
1 < e < phi(n) - 计算出e对于phi(n)的模反元素d
de mod phi(n) = 1 - 公钥
KU = (e, n) - 私钥
KR = (d, n) - 明文M 加密
M^e mod n = C - 密文C 解密
C^d mod n = M
特性
e d在模意义下互逆e常取65537
模数攻击
- 共模攻击
公钥指数e攻击
- e = 2, e = 3 可以直接尝试开方
私钥d攻击
威尔逊定理
- 对于素数p有 (p - 1)! = -1 (mod p)