JuleCTF: RSA...W?

Challenge

JULENISSEN er på oppdrag i julen og må kunne levere gaver til alle snille barn. Selv om gaven er stor eller liten, skal den komme trygt frem til barna.

Med en liten modifikasjon på krypteringsalgoritmen kan JULENISSEN endelig sende selv de aller største gavene! Har du vært snill og kan få en gave?

  • Source: rsa-w.py
  • Category: crypto
  • Difficulty: beginner
  • Flag: JUL{st0re_g4ver_0g_st0re_s1kkerhetshull}

The server chats with you, appends your answer to a message, and encrypts it with a slightly modified RSA. I made this for Cyberlandslaget’s JuleCTF in 2025.

m = bytes_to_long(message.encode("utf-8"))

p = getPrime(1024)
q = getPrime(1024)
N = p * q
e = 2**16 + 1

w = m // N
m = m % N
c = pow(m, e, N)

print(f"{N=}\n{e=}\n{w=}\n{c=}")

Vulnerability

The quotient w = m // N is printed alongside the ciphertext. Since m = w * N + (m % N), knowing w reveals the top part of the plaintext: w * N is the message rounded down to a multiple of N. With small numbers:

N = 1000
m = 1234567          # the message as an integer
w = m // N           # 1234
m = m % N            # 567

recovered = w * N    # 1234000
# m == recovered + (m % N), so recovered is m with the low part stripped

For short messages w is 0 and nothing leaks. But the message grows with your answer, the flag is at the start of it, so send enough text and the flag ends up in the part w reveals.

Exploit

Send a long answer so the message is comfortably bigger than N (256 bytes), then multiply back:

# Input: "a" * 400 (or anything long)
from Crypto.Util.number import long_to_bytes

N = int(input("N = "))
w = int(input("w = "))

print(long_to_bytes(w * N).decode("utf-8", errors="ignore"))

The output starts with the beginning of JULENISSEN’s message, including the flag:

Jeg vil ha flagget (JUL{st0re_g4ver_0g_st0re_s1kkerhetshull}) fordi ...