在CTF比赛中，往往会涉及到RSA解密类的题目，有了这个工具(基于python3.x)做起来就得心应手了。
这个也可以作为安全工具来使用，检查密钥的安全性。
$ git clone https://github.com/Ganapati/RsaCtfTool.git $ cd RsaCtfTool $ pip3 install -r "requirements.txt" # 安装辅助数学计算库sagemath，提高计算效率 $ brew cask install sage # 暴力破解RSA公钥，输出私钥 $ python3 RsaCtfTool.py --publickey certificate.crt --private # 公钥中提取 N,e $ python3 RsaCtfTool.py --publickey ~/certificate.crt --dumpkey
RSA简介
为了方便理解，先对RSA密钥体制做个简略的介绍。
- 选择两个大的参数，计算出模数 N = p * q
- 计算欧拉函数 φ = (p-1) * (q-1)，然后选择一个e(1<e<φ)，并且e和φ互质（互质：公约数只有1的两个整数）
- 取e的模反数d，计算方法为:e * d ≡ 1 (mod φ) （模反元素：如果两个正整数e和n互质，那么一定可以找到整数d，使得 e * d - 1 被n整除，或者说e * d被n除的余数是1。这时，d就叫做e的“模反元素”。欧拉定理可以用来证明模反元素必然存在。两个整数a,b，它们除以整数M所得的余数相等：a ≡ b(mod m)，比如说5除3余数为2，11除3余数也为2，于是可写成11 ≡ 5(mod 3)。）
- 对明文m进行加密：c = pow(m, e, N),可以得到密文c。
- 对密文c进行解密：m = pow(c, d, N),可以得到明文m。
整理：
`p` 和 `q`：两个大的质数，是另一个参数N的的两个因子。
`N`：大整数，可以称之为模数
`e` 和 `d`：互为无反数的两个指数
`c` 和 `m`：密文和明文
`(N, e)`：公钥
`(N, d)`：私钥
`pow(x, y, z)`：效果等效`pow(x, y)% z`， 先计算`x`的`y`次方，如果存在另一个参数`z`，需要再对结果进行取模。
密钥长度：`n`以二进制表示的的位数，例如密钥长度为`512`代表`n`用二进制表示的长度为`512bit`。
RSA安全性分析
对于RSA加密算法，公钥`(N, e)`为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数`N`，然后计算`欧拉函数φ(n)=(p-1) * (q-1)`,再通过`d * e ≡ 1 mod φ(N)`，即可计算出 `d`，然后就可以使用私钥`(N, d)`通过`m = pow(c,d,N)`解密明文。
保障RSA的安全性
1. 定期更换密钥
2. 不同的用户不可以使用相同的模数N
3. p与q的差值要大，最好是差几个比特
4. p-1与q-1都应该有大的素因子，一般建议选择的两个大素数p、q使得p=2p+1和q=2q+1也是素数
5. e的选择不要太小
6. d的选择也是不可以太小，最好满足d>=n的4分之1