cscg20-rsa

solve.py (2526B)

#!/usr/bin/env python3

from pwn import process, context
from Crypto.PublicKey import RSA
from OpenSSL.crypto import load_privatekey, FILETYPE_PEM
from sympy.ntheory.modular import crt
from sympy.ntheory import discrete_log
from sympy import nextprime, isprime, prod, sieve
from math import isqrt, gcd
import random

# We can split the decryption into two discrete logarithm problems:
# m1^((p-1)*j+dp) = m2 (mod p)    and    m1^((q-1)*k+dq) = m2 (mod q)
# If we construct p and q in a way that the factors of phi(n) are small,
# we can use the Pohlig-Hellman algorithm for finding dp and dq quickly.
# To construct d from dp and dq we use the Chinese-Remainder-Theorem.
# CRT requires the moduli to be coprime, so we use sp = p and sq = q/gcd(p-1,q-1)
# as moduli instead. To expand the resulting solution di to the (p-1)*(q-1)
# ring again, we need to try all solutions di + i * sp * sq * gcd(p-1,q-1)
# for i in [0,gcd(p-1,q-1)[.

# P.S: Some players solved this by trial, choosing d and factoring
#      m1**d - m2 using FactorDB, but that solution seems less intended.

m1 = int.from_bytes(b"Quack! Quack!", "big")
m2 = int.from_bytes(b"Hello! Can you give me the flag, please? I would really appreciate it!", "big")

def build_prime(primes, limit):
    while True:
        ps = []
        while prod(ps) < limit:
            ps += [random.choice(primes),] * random.randint(1, 10)
        if isprime(prod(ps) * 2 + 1):
            return ps, prod(ps), prod(ps) * 2 + 1

def build_params(primes):
    while True:
        pp, sp, p = build_prime(list(primes), isqrt(m2)+1)
        _, sq, q = build_prime(list(primes - set(pp)), isqrt(m2)+1)
        try:
            dp = int(discrete_log(p, m2, m1))
            dq = int(discrete_log(q, m2, m1))
        except:
            continue # m2 not in group m1^x mod ..
        gcdpq = gcd(p, q) # = 2 by construction
        di = int(crt([sp * gcdpq, sq], [dp % (sp * gcdpq), dq % sq])[0])
        for i in range(gcdpq):
            d = di + i * sp * sq * gcdpq
            if pow(m1, d, p*q) != m2:
                continue # wrong i
            if gcd(d, (p-1)*(q-1)) != 1:
                continue # unlucky
            e = pow(d, -1, (p-1)*(q-1))
            return p*q, e, d

params = build_params(set(sieve[1:100]))
key = RSA.construct(params, consistency_check=False)

io = process(["python", "server.py"])
io.sendlineafter(b"PEM format:", key.exportKey("PEM") + b"\n")
io.sendlineafter(b"your message:", b"Quack! :D")
io.readline().decode()
print(io.readline().decode())