TSG Live! 12 CTF | Large Enough

tsg_live_ctf_12 rsa small_public_exponent_attack

#TSG_LIVE_CTF_12

from Crypto.Util.number import getStrongPrime

p = getStrongPrime(1024)
q = getStrongPrime(1024)
N = p * q

phi = (p - 1) * (q - 1)
e = phi - 3
d = pow(e, -1, phi)

with open('flag.txt', 'rb') as flag:
    m = int.from_bytes(flag.read(), 'big')

assert(m.bit_length() < 1000)

c = pow(m, e, N)

print(f'N = {N}')
print(f'c = {c}')

e = \phi - 3のRSA だが、 e自体は与えられていない。

c^{-1} = m^{-1*(\phi - 3)} = m ^3 となるので、small public exponent attackが有効そう

from gmpy2 import iroot

N = 24326...
c = 82434...

m, _ = iroot(pow(c, -1, N), 3)
print(bytes.fromhex(hex(m)[2:]))

（厳密には m &lt; 2^{1000} の条件しか与えられてないのでこれで解けるとは限らない。この解法で解けるためには m^3 &lt; nである必要があって、それには m &lt; 2^{682} が必要）