CTF 中的 RSA 算法详解

之前做题经常遇上RSA算法，每次都翻博客去查询感觉有点不便，于是想自己总结一下，背景啊总结啊这些就不说了，网上一抓一大把，直接说步骤

设：

明文信息m(message)，加密后的信息c(cipher)，公钥对（nnumber, eencrypt），私钥对（nnumber, ddecrypt）

加密公式

$$
c=m^e\ mod\ n
$$

解密公式

$$
m = c^d\ mod\ n
$$

加密过程

首先选取两个大质数p, q
$$
n = p \cdot q\
$$
e 应该和$\phi(n)$互质，一般取65537，也就是0x10001

然后按照加密公式做着走就是了

解密过程

由于公钥对我们已知，c已知，只需要求d，我们来推一下逻辑链

p, q 相乘生成 n —-> n 生成phi(n) —-> phi(n) 和 e 生成 d

所以我们只需要求到p, q就能够按照上述逻辑生成d用于解密了

p, q 是两个大质数相乘生成的n ，所以只要对n 进行因式分解 就能求到p， q

所以步骤如下

1. 求p, q

上factordb.com直接生成p，q

2. 求phi(n)

$\phi(n)$被称为欧拉函数，这里我们用到的性质直接就是

若n=p*q，且p,q为质数，phi(n) = (p-1)(q-1)

3. 求d

这就要用到gmpy库了，直接m = gmpy2.invert(e, phi(n))就有了

4. 解密

m = c ^ d mod n，所以直接m = pow(c, d, n)出结果的16进制

然后找个16进制解密网站，或者是自己写一个脚本就出来了

binascii.a2b_hex(hex(m)[2:])