random_RSA
from gmpy2 import next_prime, invert as inverse_mod
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from math import lcm
from sys import exit
global_bits = 1024
BANNER = rb"""
...
"""
def generate_prime(bits: int):
p = (getrandbits(bits - 32) << 32)
return next_prime(p)
def generate_private_key(bits: int):
p, q = generate_prime(bits), generate_prime(bits)
n, phi = p * q, lcm(p-1, q - 1)
d = inverse_mod(0x10001, phi)
privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
return privateKey, p > q
if __name__ == "__main__":
print(BANNER.decode())
print("Welcome to the world of random RSA.")
print("Please make your choice.")
for _ in range(8):
choice = input()
if choice == '1':
p, q = generate_prime(global_bits), generate_prime(global_bits)
N = p*q
d = generate_prime(global_bits-32)
e = inverse_mod(d, (p * p - 1) * (q * q - 1))
print(f"{int(N)}")
print(f"{int(e)}")
elif choice == '2':
privateKey, signal = generate_private_key(global_bits)
Cipher = PKCS1_v1_5.new(privateKey)
c = (Cipher.encrypt(flag.encode()))
print(c)
exit()
else:
exit()
八次交互机会，输入1可通过生成随机数生成p、q、d，且有e的生成规则：$ed \equiv 1\pmod {(p^2-1)\cdot (q^2-1)}$,最后给出N、e，属于RSA的变体，有论文可参考：CiteSeerX (psu.edu)，想看懂属实费劲，记住是通过找$\frac{e}{N^2-\frac{9}{4}\cdot N+1}$的连分数可恢复d，从而恢复p、q。输入2构造基础RSA加密flag。
显然最后加密flag中生成的p、q需要通过菜单1的随机数预测得到，8次交互，可以让前7次选择菜单1，最后一次选择菜单2，如此便得到：((1024-32) / 32 * 2+ (1024-32-32) / 32) * 7 = 644个32位的随机数，接着就能恢复菜单2中的p、q。
恢复p、q、d：
先交互得到7组N、e
def contfrac_attack(n,e):
convergents = continued_fraction(ZZ(e) / ZZ(int(n^2 -9/4*n +1))).convergents()
for c in convergents:
k = c.numerator()
d = c.denominator()
if pow(pow(2,int(e),int(n)),int(d),n) == 2:
phi = (e*d - 1)//k
p_add_q = iroot(n^2+1 -phi +2*n,2)[0]
p_sub_q = iroot(n^2+1 -phi -2*n,2)[0]
p = (p_add_q + p_sub_q)//2
q = n//p
#if p<q:
# p,q = q,p
#print('[',p,',',q,',',d,'],')
return int(p),int(q),int(d)
N = [...]
E = [...]
pqd = []
for n,e in zip(N,E):
p,q,d = contfrac_attack(n,e)
pqd.append([p,q,d])
接着调用MT19937的模板即可得到p、q来，要注意的是因为p、q的顺序不知道，需要进行爆破：
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from extend_mt19937_predictor import ExtendMT19937Predictor
from gmpy2 import invert,next_prime
from math import lcm
import itertools
c = b'...'
def get_random(bits):
p = predictor.predict_getrandbits(bits - 32) << 32
return next_prime(p)
for o in itertools.product([0,1],repeat=7):
try:
predictor = ExtendMT19937Predictor()
for i,v in enumerate(pqd):
predictor.setrandbits(v[o[i]]>>32, 992)
predictor.setrandbits(v[1-o[i]]>>32, 992)
predictor.setrandbits(v[2]>>32, 960)
except:
continue
p,q = get_random(1024),get_random(1024)
n = p*q
phi = lcm(p-1,q-1)
d = inverse(e,phi)
privateKey = RSA.construct((int(n), int(0x10001), int(d), int(p), int(q)))
Cipher = PKCS1_v1_5.new(privateKey)
flag = (Cipher.decrypt(c,'\x00'))
if b'NepCTF' in flag:
print(flag)
break
其他题可参考：
NepCTF2023 Crypto wp_无趣的浅的博客-CSDN博客
[NepCTF 2023] crypto 复现_石氏是时试的博客-CSDN博客
2023 NepCTF | CTF导航 (ctfiot.com)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1666739907@qq.com