baby modulus — Small RSA

Platform: spbctf | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: NA | Author: XESXOR | Date: 2026-03-08 | Status: Solved Techniques: rsa_small_modulus_factorization

Summary

Task: RSA with small 128-bit modulus. Solution: Factor n via factordb.com and compute private key d to decrypt.

baby modulus — Crypto Kids 2.0

Description

RSA with small 128-bit modulus.

• n = 127515183131859395739078505442605447613
• e = 31337
• c = 33403920388615840326926465556447601348

Analysis

The modulus n is only 128 bits — easily factorizable via factordb.com or yafu.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes

n = 127515183131859395739078505442605447613
e = 31337
c = 33403920388615840326926465556447601348

# Factorization via factordb.com:
p = 11192001222936284809
q = 11393421122090001557
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

assert p * q == n

# Calculate phi(n) and d
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)

# Decrypt
m = pow(c, d, n)
flag = long_to_bytes(m)
print(flag.decode())
# Output: spbctf{REDACTED}

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍