一、RSA基本原理
（1）独立地选择两个大的素数p和q(100~200位十进制数)。
（2）计算出模数 N = p * q，计算欧拉函数值 φ = (p-1) * (q-1)。
（3）然后选择一个e(1<e<φ)，（φ，e）=1（即e和φ互质）（互质：公约数只有1的两个整数）。
（4）取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)。）。
（5）得到公钥（n,e）和私钥（n,d）。
（6）对明文m进行加密：c = pow(m, e, N),可以得到密文c。
（7）对密文c进行解密：m = pow(c, d, N),可以得到明文m。
二、CTF中的RSA
1、直接分解模数N
（1）原理
由RSA的基本原理可知，通过分解N，得到p和q是最直接的攻击方法，但也是最难的攻击方法，RSA在设计时就已通过数学方法的证明，只要p和q选取的当，N不可能被分解（这里不能被分解指的是在有限的时间内，一般来说破解所花的时间要在该信息存在价值的时间范围内），当然目前量子计算机是破解RSA的一种有力工具了。 在CTF中，如果是考察分解N来解题，则意味着题目中的N是简单的，通过工具就可以分解的出来。常用的工具是windows平台的RSATool和在线分解（http://factordb.com），在线分解的原理是该网站存储了一些N及N的分解值p和q
（2）例题，直接给出n和e
import gmpy2
n = 920139713
# p 和 q通过在线网站http://factordb.com/index.php分解
p = gmpy2.mpz(18443)
q = gmpy2.mpz(49891)
e = gmpy2.mpz(19)
phi_n = (p-1)*(q-1)
d = gmpy2.invert(e, phi_n)
c = """
704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
34152224652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148
"""
result = ""
c_list = c.split()
#print(c_list)
for i in c_list:
result += chr(pow(int(i),d,n))
print(result)
（3）例题，给出key和flan.enc
import gmpy2
from Crypto.PublicKey import RSA
import rsa
public_key = "./file/pub.key"
cipher_file = "./file/flag.enc"
#读入公钥
with open(public_key, "r") as f:
key = RSA.importKey(f)
n = key.n
e = key.e
print(key.n) #86934482296048119190666062003494800588905656017203025617216654058378322103517
print(key.e) #65537
#大数分解得到
p = 285960468890451637935629440372639283459
q = 304008741604601924494328155975272418463
phin = (q-1)*(p-1)
d = gmpy2.invert(e, phin)
key = rsa.PrivateKey(n, e, int(d), p, q)
with open("./file/flag.enc", "rb+") as f:
f = f.read()
print(rsa.decrypt(f, key))
