macOS Catalina(10.15.4)下RsaCtfTool的安装及使用

在CTF比赛中,往往会涉及到RSA解密类的题目,有了这个工具(基于python3.x)做起来就得心应手了。

这个也可以作为安全工具来使用,检查密钥的安全性。

RSA简介

为了方便理解,先对RSA密钥体制做个简略的介绍。

  1. 选择两个大的参数,计算出模数 N = p * q
  2. 计算欧拉函数 φ = (p-1) * (q-1),然后选择一个e(1<e<φ),并且e和φ互质(互质:公约数只有1的两个整数)
  3. 取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)。)
  4. 对明文m进行加密:c = pow(m, e, N),可以得到密文c。
  5. 对密文c进行解密:m = pow(c, d, N),可以得到明文m。
整理:

pq:两个大的质数,是另一个参数N的的两个因子。
N:大整数,可以称之为模数
ed:互为无反数的两个指数
cm:密文和明文
(N, e):公钥
(N, d):私钥
pow(x, y, z):效果等效pow(x, y)% z, 先计算xy次方,如果存在另一个参数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

参考链接


发布者

发表评论

您的电子邮箱地址不会被公开。