Crypto: RSA Small Exponent

Background

RSA encryption: c = m^e mod n, where (n, e) is the public key and m is the plaintext message as an integer.

This cryptographer chose e = 3 to speed up encryption and sent a short message. When the message is short enough that m^e < n, the modular reduction never occurs — meaning c = m^e exactly. Recover m with a single integer operation.

Public Key & Ciphertext (1024-bit modulus)

e 3

n 0xb7a7119d1fc113ba28bbae7f021d243ec072d864f9cc4cd04a4a950f12a0b817ab5b6887703fb536331ace8561edfabcc288fa5a41126f773f5cd56d04859924d328452e07f00696216d10dd3b988c300844ee270326c81f5b8f6bc49c2225b6522071546a79996f54e79559ce0d2b5b86d001b15aa45a6a675c32029060cde3

c 0x10652cdfaa8a3da40da185438b2d1a1605add1f479cbff6dc37a9932564746ebbbe8f28e52132238ed1b1ee1fc86092f6fa25f23e4eb4ca37e25f3d2958a8bcd6d5e1b60ae4c8fb11ba931ead3a30f1aa6fb4832637b5988b1023d4a762dddf6aadb5b161665

⬇ Download challenge.txt

Solve Skeleton (Python)

# Option A — gmpy2 (exact integer cube root)
from gmpy2 import iroot
c = int("0x10652cdfaa8a3da40da185438b2d1a1605add1f479cbff6dc37a9932564746ebbbe8f28e52132238ed1b1ee1fc86092f6fa25f23e4eb4ca37e25f3d2958a8bcd6d5e1b60ae4c8fb11ba931ead3a30f1aa6fb4832637b5988b1023d4a762dddf6aadb5b161665", 16)
m, is_perfect = iroot(c, 3)
flag = m.to_bytes((m.bit_length() + 7) // 8, "big").decode()
print(flag)

# Option B — Newton's method (no extra libraries)
def icbrt(n):
    # Bit-based seed avoids floating-point precision loss on large numbers
    x = 1 << ((n.bit_length() + 2) // 3)
    while True:
        x1 = (2*x + n // (x*x)) // 3
        if x1 >= x:
            return x
        x = x1

m = icbrt(c)
flag = m.to_bytes((m.bit_length() + 7) // 8, "big").decode()
print(flag)