在CTF比赛中，往往会涉及到RSA解密类的题目，有了这个工具(基于python3.x)做起来就得心应手了。
这个也可以作为安全工具来使用，检查密钥的安全性。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
$ 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