TSG Live CTF 6 | Broken RSA - crypto-writeup-public

#tsglivectf6

class key:
    def __init__(self, p, q):
        self.N = p * q
        self.phi = (p - 1) * (q - 1)
        self.e = 65537
        self.d = pow(self.e, -1, self.phi)

    def gen_private_key(self):
        return (self.N, self.d)

    def gen_public_key(self):
        return (self.N, self.e)

def encrypt(msg, public):
    N, e = public
    return pow(msg, e, N)

def decrypt(c, private):
    N, d = private
    return pow(c, d, N)


from private_key import p, q
from FLAG import FLAG


msg = int.from_bytes(FLAG, byteorder='big')
keys = key(p, q)
encrypted = encrypt(msg, keys.gen_public_key())

assert(msg < p * q)

print(f'N, e = {keys.gen_public_key()}')
print(f'c = {encrypted}')

if pow(msg, keys.phi, keys.N) != 1:
    raise Exception('Oops! RSA is broken!')

overview

RSA だが $m^{\phi} \not\equiv \mod N$ らしい

solution

そのようなケースは $p, q$ が素数でないか、もしくは $\gcd(m, N) \ne 1$ かである（オイラーの定理は $\gcd(m, N) = 1$ を前提としている）
前者は解けなさそうなので後者と仮定して $\gcd(m^e \pmod N, N)$ も引き続き $\ne 1$ であろうから、これで $p$ を求める
$q$ だけでは $m$ は求まらない感じなので、普通に $\phi$ を計算しても復号できるが、こんかいはちょっと怖いので例えば RSA-CRT による方法で $\phi$ を回避しつつ復号、とかやるといいらしい