RSA介绍
- RSA是一种非对称加密算法，即加密和解密时用到的密钥不同。
- 加密密钥是公钥，可以公开；解密密钥是私钥，必须保密保存。
- 基于一个简单的数论事实：两个大质数相乘很容易，但想要对其乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥，即公钥；而两个大质数组合成私钥。
RSA步骤
取两个大质数p和q，相乘得到n
p
q
n = p * q
根据(p-1)*(q-1)得到加密密钥e
1 < e < (p-1)*(q-1)
gcd(e, (p-1)*(q-1)) = 1
根据e和(p-1)*(q-1)得到解密密钥d
1 < d < (p-1)*(q-1)
d = e^-1 mod((p-1)*(q-1))
# e*d ≡ 1 mod((p-1)*(q-1))
# e*d % (p-1)*(q-1) = 1
对A加密
B = A^e mod n
对B解密
A = B^d mod n
RSA基础题型
| # | 题型关键点 | 条件 | 解法/思路 | 工具 |
|---|---|---|---|---|
| 1 | 分解 n | n 较小或能查到 | 用 factordb 分解 n，求 φ(n) 再求 d | factordb.com |
| 2 | e很小 且 m^e < n | 明文较小 | 暴力求 m，使 m^e ≡ c mod n 成立 | gmpy2.iroot() |
| 3 | 多人广播攻击 | e 相同，n 不同，m 相同，且 e 组数 ≥ 接收者数量 | 中国剩余定理合并 ci，开 e 次方得 m | sympy.crt(), gmpy2.iroot() |
| 4 | 共模攻击 | 多个 c，e 不同但 n 相同 | 扩展欧几里得解 x, y，构造 m = c1^x * c2^y mod n | 自写 exgcd |
| 5 | 公因数攻击 | 多个 n 之间有公因子 | 求 gcd(n1, n2) 得 p，进而算 d | gmpy2.gcd() |
| 6 | 小 d 攻击（Wiener） | d 非常小（d < n^0.25） | 使用连续分数收敛逼近求 d | RSAwienerHacker.py |
| 7 | dp 泄露 | 给出 dp，知道 e | 利用 e*dp ≡ 1 mod (p-1)，爆破 p | 自写爆破脚本 |
| 8 | dp, dq, p, q 已知 | 通常与 dp 泄露同现 | 利用 CRT 构造 m_p, m_q 再还原 m | Crypto.Util.number, CRT |
| 9 | 低加密指数 + Padding | e 小，但 m 较大 | 需分析 padding，若模式已知可逆推 m | 结合特征推测补位 |