writeup for the picoctf 2023 crypto challenge: SRA

sra.py

'''
Script to solve SRA in picoCTF 2023

The challenge provides a broken version of RSA that gives the user the cipher text
and d (e^-1) for the private key. n is not given. Below is the original script
with some annotations I added.

    from Crypto.Util.number import getPrime, inverse, bytes_to_long
    from string import ascii_letters, digits
    from random import choice

    pride = "".join(choice(ascii_letters + digits) for _ in range(16)) # plaintext
    gluttony = getPrime(128) # p
    greed = getPrime(128) # q
    lust = gluttony * greed # n
    sloth = 65537 # e
    envy = inverse(sloth, (gluttony - 1) * (greed - 1)) # d

    anger = pow(bytes_to_long(pride.encode()), sloth, lust) # ciphertext

    print(f"{anger = }")
    print(f"{envy = }")

    print("vainglory?")
    vainglory = input("> ").strip()

    if vainglory == pride:
        print("Conquered!")
        with open("/challenge/flag.txt") as f:
            print(f.read())
    else:
        print("Hubris!")


After banging my head against the wall for a day and a half, I found this post:

https://crypto.stackexchange.com/questions/81615/calculating-rsa-public-modulus-from-private-exponent-and-public-exponent

Basically, we need to compute φ(n) then factorize it into p and q:

    n = p * q

    φ(x) = (x-1) when x is prime

    φ(n) = φ(pq)
         = φ(p)φ(q)   NB. φ is a multiplicative when p and q are relatively prime (which they are since they're both prime)
         = (p-1)(q-1)

    (see https://en.wikipedia.org/wiki/Euler%27s_totient_function)

Then d is computed like so,

    ed = 1 mod φ(n)

Which can be rewritten as (for some integer h):

    ed - 1 = hφ(n)
    ed - 1 = h(p-1)(q-1)

Since we have e and d, we can compute ed - 1, then factorize it.

Then combine those factors to form h, p, q until we bruteforce the plaintext.
'''

from Crypto.Util.number import long_to_bytes, bytes_to_long, size, inverse
from math import gcd, prod
import operator
from functools import reduce
import itertools


e = 65537
ct = 18523758736583695550806419568487204346852993574834760315747295068312729905773
d = 2803958435858717407506428640902731003813503817015389113998091540609016712673

# encrypt(m) = m**e mod n = c
# d = e**-1 mod φ(n)
# decrypt(c) = c**d mod n = m

kφ = e * d - 1

def parse_pow(x):
    r = x.split('^')
    if len(r) == 1:
        return [int(r[0])]
    else:
        return [int(r[0])] * int(r[1])

print(kφ)

print('insert factors (use https://www.alpertron.com.ar/ECM.HTM) -- make sure to replace powers with "^":')
factors_in = input()

factors = sum([parse_pow(x.strip().replace(' ', '')) for x in factors_in.split('×')], [])

# remove some low hanging fruit
pfac = factors[-1] # biggest prime factor goes to p
qfac = factors[-2] # second biggest prime factor goes to q
factors = factors[:-2] # remove the top two factors since we've already assigned them
factors.remove(2) # used in p - 1 (since it's even)
factors.remove(2) # used by q - 1 (since it's even)

print('computing factors', len(factors))
T127 = 2**127
T129 = 2**129
ITERS = 3 ** len(factors)
steps = 0
pts = set()
for c in itertools.product([0,1,2], repeat=len(factors)):
    steps += 1
    h     =            prod(factors[i] for i, x in enumerate(c) if x == 0)
    psub1 = 2 * pfac * prod(factors[i] for i, x in enumerate(c) if x == 1)
    qsub1 = 2 * qfac * prod(factors[i] for i, x in enumerate(c) if x == 2)
    if h < e and T127 < psub1 < T129 and T127 < qsub1 < T129 and max(psub1+1, qsub1+1) < 2 * min(psub1+1, qsub1+1):
        n = (psub1 + 1) * (qsub1 + 1)
        pt = long_to_bytes(pow(ct, d, n))
        # there's no deduplication of the factors so we end up with multiple ways of computing p and q
        if len(pt) == 16:
            pts.add(pt)
            print(pt)
    if steps % 10000 == 0:
        print(steps, '/', ITERS, steps / ITERS)

print(pts)