2024 SAINTSEC招新赛 babyXor

题目源码

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"""
.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.--------.
| N.--.  | E.--.  | P.--.  | C.--.  | T.--.  | F.--.  | H.--.  | A.--.  | P.--.  | P.--.  | Y.--.  |
|  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  :/\:  |  (\/)  |  :():  |  :/\:  |  :/\:  |  (\/)  |
|  :\/:  |  :\/:  |  ()()  |  (__)  |  :\/:  |  (__)  |  :\/:  |  ()()  |  :\/:  |  :\/:  |  :\/:  |
|  '--'n |  '--'e |  '--'p |  '--'c | '--'t  |  '--'f |  '--'h |  '--'a |  '--'p |  '--'p |  '--'y |
`--------`--------`--------`--------'--------`--------`--------`--------`--------`--------`--------`
"""


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()

分析

MT19937 PRNG预测

观察choice，发现choice=1和choice=2好像并没有直接的关系，但是都用到了getrandbits函数，联想到MT19937 PRNG预测

mersenne-twister-predictor

import random
from mt19937predictor import MT19937Predictor

predictor = MT19937Predictor()
for _ in range(624):
    x = random.getrandbits(32)
    predictor.setrandbits(x, 32)

assert random.getrandbits(32) == predictor.getrandbits(32)

题目一共有8次交互机会，当choice=1，pq都是getrandbits(1024-32)，d是getrandbits(1024-32-32)，所以前7轮可以获得(992*2+960)*7=20608bits，满足MT19937所需要的624*32=19968bits

然后根据每一轮的N、e用连分数恢复p、q、d，就可以预测了

连分数

比赛的时候没找到题目对应的论文，只找到了X-NUCA weird这个比较相似的，但是不会构造成题目e=inverse_mod(d, (p*p-1)*(q*q-1))的形式，论文提到这种形式可以找e / (N^2-9/4*N+1)的连分数

注意：题目没有输出每一轮p和q的顺序，所以需要爆破互换pq的，复现为了方便验证，手动加上一个signal值

本地复现

from sage.all import *
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from random import getrandbits
from mt19937predictor import MT19937Predictor

flag = "NepCTF{c4e4356067fb3bedc53dde7af59beb1c}"
global_bits = 1024

def generate_prime(bits: int):
    p = (getrandbits(bits - 32) << 32)
    return int(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 = int(inverse_mod(0x10001, phi))
    privateKey = RSA.construct((n, 0x10001, d, p, q))
    return privateKey, p > q

NN = []
ee = []
signal = []

for i in range(7):
    p, q = generate_prime(global_bits), generate_prime(global_bits)
    if p > q:
        signal.append(1)
    else:
        signal.append(0)
    N = p * q
    d = generate_prime(global_bits - 32)
    e = int(inverse_mod(d, (p * p - 1) * (q * q - 1)))
    NN.append(N)
    ee.append(e)

privateKey = generate_private_key(global_bits)[0]
Cipher = PKCS1_v1_5.new(privateKey)
c = Cipher.encrypt(flag.encode())
# print(c)

# 连分数解 pqd
def attack(N, e):
    convergents = continued_fraction(e / (N ** 2 - Integer(9) / Integer(4) * N + 1)).convergents()
    for c in convergents:
        k = c.numerator()
        d = c.denominator()
        if pow(pow(2, e, N), d, N) == 2:
            phi = (e * d - 1) // k
            p_a_q = int(sqrt(N ** 2 + 1 - phi + 2 * N))
            p_s_q = int(sqrt(N ** 2 + 1 - phi - 2 * N))
            p = (p_a_q - p_s_q) // 2
            assert N % p == 0
            q = N // p
            d = int(inverse_mod(e, (p * p - 1) * (q * q - 1)))
            return p, q, d

predictor = MT19937Predictor()

for i in range(7):
    print(i)
    p, q, d = attack(NN[i], ee[i])
    # 根据 signal 调整 pq 顺序
    if signal[i] == 0:
        if p > q:
            p, q = q, p
    else:
        if p < q:
            p, q = q, p

    predictor.setrandbits(p >> 32, 992)
    predictor.setrandbits(q >> 32, 992)
    predictor.setrandbits(d >> 32, 960)

p = int(next_prime(predictor.getrandbits(992) << 32))
q = int(next_prime(predictor.getrandbits(992) << 32))
n, phi = p * q, lcm(p-1, q-1)
d = int(inverse_mod(0x10001, phi))
privateKey = RSA.construct((n, 0x10001, d, p, q))
Cipher = PKCS1_v1_5.new(privateKey)
flag = Cipher.decrypt(c, '\x00')
print(flag)
# b'NepCTF{c4e4356067fb3bedc53dde7af59beb1c}'

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com