Low Public Exponent

If ee is small, it is possible to get the flag by brute-forcing. Suppose we have e=3e = 3. In this case, we can try to compute c+kNc + k * N (where kk is an natural number) until we find a perfect cube. If a perfect cube is found, simply take cubic root on it and we would get the flag:

from Crypto.Util.number import long_to_bytes, bytes_to_long
from sympy import integer_nthroot

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Cubic root--------#

while True:
    # Example: integer_nthroot(16, 2) => (4, True)
    # Note that the True or False here is boolean value
    result = integer_nthroot(c, 3)
    if result[1]:
        m = result[0]
        break
    c += N

flag = long_to_bytes(m).decode()

print(flag)

Last updated