RaRCTF 2021 | babycrypt

#rarctf2021

from Crypto.Util.number import getPrime, bytes_to_long

flag = bytes_to_long(open("/challenge/flag.txt", "rb").read())

def genkey():
    e = 0x10001
    p, q = getPrime(256), getPrime(256)
    if p <= q:
      p, q = q, p
    n = p * q
    pubkey = (e, n)
    privkey = (p, q)
    return pubkey, privkey

def encrypt(m, pubkey):
    e, n = pubkey
    c = pow(m, e, n)
    return c

pubkey, privkey = genkey()
c = encrypt(flag, pubkey)

hint = pubkey[1] % (privkey[1] - 1)
print('pubkey:', pubkey)
print('hint:', hint)
print('c:', c)

RSA。がもらえる。連立方程式たてるだけ。sympyを使った

from sympy.solvers import solve
from sympy import symbols
from ptrlib import Socket

sock = Socket("193.57.159.27", 60123)
n = int(sock.recvlineafter("65537, ")[:-1])
x = int(sock.recvlineafter("hint: "))
c = int(sock.recvlineafter("c: "))

p, q = symbols("p, q", integer=True)
solutions = solve([n - p * q, x - (p - q + 1)])
for s in solutions:
    p, q = abs(int(s[p])), abs(int(s[q]))

    print(p, q)
    assert n % p == 0

    d = pow(65537, -1, (p-1)*(q-1))
    m = pow(c, d, n)
    print(m.to_bytes(100, "big"))
    quit()