Overview#

You’re given RSA parameters and a ciphertext. Factoring n via FactorDB yields a very small prime p = 101 and a large prime q. Standard RSA decryption m = c^d mod n returns a number that doesn’t decode to ASCII.

The twist: the original message M was larger than the modulus n, so encryption implicitly reduced it modulo n. After decryption, you get M mod n; to recover M, you add back (a multiple of) n.

Given Parameters#

• p = 101
• q = 313846144900241708687128313929756784551
• n = 31698460634924412577399959706905435239651
• e = 65537
• c = 23648999580642514140599125257944114844209

Math#

• phi(n) = (p - 1)(q - 1)
• d = e^-1 mod phi(n)
• m_dec = c^d mod n
• If original M >= n, encryption sent M mod n. After decryption we get m_dec = M mod n.
• Recover M by testing M = m_dec + k*n for small k >= 0 until bytes decode. Here k = 1 works.

Solution Script#

1
import sympy as sp
2

3
p = 101
4
q = 313846144900241708687128313929756784551
5
n = 31698460634924412577399959706905435239651
6
e = 65537
7
c = 23648999580642514140599125257944114844209
8

9
# Sanity checks
10
assert p * q == n
11
assert sp.isprime(p) and sp.isprime(q)
12

13
phi = (p - 1) * (q - 1)
14
d = pow(e, -1, phi)
15

16
m_dec = pow(c, d, n)
17
print("m_dec =", m_dec)
18

19
# Try adding multiples of n until it decodes
20
def try_decode(x: int):
21
    try:
22
        h = hex(x)[2:]
23
        if len(h) % 2:
24
            h = "0" + h
25
        return bytes.fromhex(h).decode()
26
    except Exception:
27
        return None
28

29
flag = None
30
for k in range(0, 5):
31
    candidate = m_dec + k * n
32
    s = try_decode(candidate)
33
    if s and s.startswith("v1t{") and s.endswith("}"):
34
        flag = s
35
        print("k =", k, "->", flag)
36
        break
37

38
assert flag is not None

Why This Works#

• RSA encrypts modulo n. If the original message M is larger than n, the actual encrypted value is based on M mod n.
• Decryption returns the reduced message. Adding one modulus (or a few) reconstructs a valid preimage that maps to ASCII.

Flag#

1
v1t{RSA_101_b4by}