UIUCTF2017 – OldTV

Not many people solved this despite the author and I believing that this should have been an easy challenge. We were given the following program:

from binascii import hexlify
from fractions import gcd
import rsa

pub, priv = rsa.newkeys(2048)

with open('flag.txt') as f: flag = f.read()

signme = 1337

q = priv.q
p = priv.p
d = priv.d
e = priv.e
n = priv.n

# RSA signatures are way too slow I'm gonna go sanic

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

s1 = pow(signme, d % (p - 1), p)
s2 = pow(signme, d % (p - 1), q)
qinv = modinv(q, p)
h = (qinv * (s1 - s2)) % p
s = s2 + h * q

print "parameters:"
print e
print n
print "signed 1337 with"
print s
print "encrypted flag"
print hexlify(rsa.encrypt(flag, pub))

Initially, you should try to verify the signature and compute s^e \pmod{n}, and realize that it is not 1337. We eventually notice that d_q \equiv d \pmod{p - 1}, which is incorrect, so we pull out a pencil and paper and calculate.

    \[ \begin{aligned} s_1 &\equiv m^{d_p} \pmod{p} \implies c_1 p + s_1 = m^{d_p} \\ s_2 &\equiv m^{d_p} \pmod{q} \implies c_2 q + s_2 = m^{d_p} \\ s_1 - s_2 &= c_2 q - c_1 p \\ h &\equiv q^{-1} (c_2 q - c_1 p) \pmod{p} \implies h \equiv c_2 \pmod{p} \\ s &\equiv m^{d_p} - c_2 q + hq \equiv m^{d_p} \pmod{p} \\ ed_p &\equiv 1 \pmod{p - 1} \implies s^e \equiv m \pmod{p} \\ \end{aligned} \]

We can then just compute \gcd(s^e - m, n) to get p, where s^e - m is taken modulo n. The chances of s^e - m \equiv 0 \pmod{n} are really small, so this works most of the time.

This entry was posted in CTF, Math. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *