RSA 101

Recon

We are given a file containing a ciphertext, as well as the RSA parameters N and E:

n = 31698460634924412577399959706905435239651
e = 65537
c = 23648999580642514140599125257944114844209

At first glance, this appears to be a straightforward RSA challenge: we need to factor N. Fortunately, FactorDB provides us with the factors without much effort, and we realize that the challenge title was itself a clue.

p = 101
q = 313846144900241708687128313929756784551

However, the situation is not as straightforward as it initially seems. When we attempt to decrypt the ciphertext using these values, we only obtain seemingly meaningless binary data:

$ RsaCtfTool \
    -p 101 \
    -q 313846144900241708687128313929756784551 \
    -e 65537 \
    --decrypt 23648999580642514140599125257944114844209
Decrypted data :
HEX : 0x190a2f07690f57386bce37c08e09f1849a
INT (big endian) : 8520595641234233889906203467245297960090
INT (little endian) : 52580194138662613259523171555239621757465
STR : b'\x19\n/\x07i\x0fW8k\xce7\xc0\x8e\t\xf1\x84\x9a'

Exploitation

One important rule to keep in mind is that decrypting an RSA ciphertext does not always recover the original message M, but rather M mod N. If the original message is larger than N, RSA encryption reduces it modulo N.

As a result, the decrypted output represents only the remainder, not the complete original message. In such cases, we need to add N to the decrypted integer repeatedly until the resulting bytes form a meaningful message. Since N is relatively small in this challenge, this situation is highly likely.

We can use a simple Python script to add both values and verify whether the result reveals the flag:

from Crypto.Util.number import long_to_bytes

m = 0x190a2f07690f57386bce37c08e09f1849a
n = 31698460634924412577399959706905435239651
m_sum_n = m + n

print(long_to_bytes(m_sum_n))

Flag capture

Let’s execute the script to obtain the flag:

$ python extract_flag.py
v1t{RSA_101_b4by}