EntryLevel RSA
2600 training · Crypto
From the chall.py:
from Crypto.Util.number import *
from flag import FLAG
FLAG = bytes_to_long(FLAG)
e = 11
nbits = 2048
p = getPrime(nbits)
q = getPrime(nbits)
n = p*q
ct = pow(FLAG, e, n)
print(f"{ct=}")Known infos
Goal: The flag has been encrypted using RSA with an exponent .
Our goal is to decrypt the ciphertext, but given the ciphertext size, we need
to consider a specific attack vector.
Informations from chall.py:
e = 11
n = p*q # where p and q are 2048-bit primes
ct = FLAG**11 % nThe challenge involves RSA encryption where the modulus is approximately 4096 bits. The encrypted flag is
, but the ciphertext
length gives a critical clue for solving this challenge.
Analyse
Key Points
1. Ciphertext Length: The ciphertext is significantly smaller than
expected—about 2351 bits, while the modulus
is around 4096 bits. This
difference in size suggests something important: the value of
is
smaller than
, meaning the encryption did not “wrap around” modulo
.
2. Unlikely Probability: If were truly wrapped, the high
bits of the ciphertext would not be zero. The fact that the ciphertext is only
2351 bits implies that the most significant 1745 bits of the result are zero,
which is extremely improbable in a random RSA scenario. The probability
of this occurring, assuming uniform distribution, is roughly
, which
is virtually impossible. This strongly suggests that
, meaning
that the encryption did not involve modular reduction.
3. Direct Root Extraction: Since , the ciphertext is simply
, and no modular arithmetic has affected the result. This allows us
to directly compute the 11th root of the ciphertext to recover the flag.
How to solve
Recovering the Flag
To solve this challenge, we just need to compute the 11th root of the ciphertext:
1. Given that , we know that no wrapping occurred during the
encryption, so the ciphertext is simply
.
2. By computing the 11th root of the ciphertext, we can recover the original
value of the flag, as .
Solve script
from Crypto.Util.number import *
from libnum import nroot
e = 11
ct = int(open("output.txt", "r").read().strip().split("=")[1])
assert ct.bit_length() < 3000
print(long_to_bytes(nroot(ct, e)))Explanation
Ciphertext Size: The key insight is that the ciphertext size is much
smaller than the modulus , suggesting that
. This allows us
to avoid dealing with the modulus and directly compute the 11th root of
the ciphertext to retrieve the flag.
Root Calculation: By using the function nroot(ct, 11), we can efficiently
compute the 11th root of the ciphertext and convert the result back into
bytes to retrieve the flag.
Conclusion
This challenge illustrates a case where the RSA encryption process did not
involve modular wrapping. By carefully analyzing the size of the ciphertext
and understanding the implications, we were able to directly extract the
flag by computing the 11th root of the ciphertext without needing to factor
or perform more complex RSA attacks.