【性价之王】	【线路之王】	【价格之王】	【配置之王】
【免费之王】	【香港首推】	【梯子之王】	【独服之王】

一、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 gmpy2n = 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 = """7047967927522111522747041641841402236827083548329523526307290545978847648329523545978847666355179247520680445978847642831337447520680445978847642539213770479679245826567734152224652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148"""result = ""c_list = c.split()#print(c_list)for i in c_list: result += chr(pow(int(i),d,n))print(result)import gmpy2n = 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 = """7047967927522111522747041641841402236827083548329523526307290545978847648329523545978847666355179247520680445978847642831337447520680445978847642539213770479679245826567734152224652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148"""result = ""c_list = c.split()#print(c_list)for i in c_list: result += chr(pow(int(i),d,n))print(result)import gmpy2n = 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 = """7047967927522111522747041641841402236827083548329523526307290545978847648329523545978847666355179247520680445978847642831337447520680445978847642539213770479679245826567734152224652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148"""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 gmpy2from Crypto.PublicKey import RSAimport rsapublic_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 = 285960468890451637935629440372639283459q = 304008741604601924494328155975272418463phin = (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))import gmpy2from Crypto.PublicKey import RSAimport rsapublic_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 = 285960468890451637935629440372639283459q = 304008741604601924494328155975272418463phin = (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))import gmpy2from Crypto.PublicKey import RSAimport rsapublic_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 = 285960468890451637935629440372639283459q = 304008741604601924494328155975272418463phin = (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))