Low Public Exponent

If $e$ is small, it is possible to get the flag by brute-forcing. Suppose we have $e = 3$ . In this case, we can try to compute $c + k * N$ (where $k$ 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)

PreviousMultiple Ciphertexts NextLow Private Exponent

Last updated 2 years ago

Was this helpful?

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)