UT CTF 2024
Rsa 256 [100 pts]
Based on the military-grade encryption offered by AES-256, RSA-256 will usher in a new era of cutting-edge security… or at least, better security than RSA-128.
By Jeriah (@jyu on discord)
We’re provided the following values:
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
e = 65537
c = 43711206624343807006656378470987868686365943634542525258065694164173101323321
For those of you who don’t know how RSA works, here’s a short explanation:
First, primes \(p\) and \(q\) are selected at random. These need to be rather large, and are typically 128, 256, or 512 bits. These primes are kept secret.
Then, \(N=pq\) is calculated. This is our modulus, and is publicly known. Because of how large \(p\) and \(q\) are, this should be infeasible to calculate on classical computers (quantum computers are a whole different story, but they’re not quite there yet). We also calculate \(\phi (N)=(p-1)(q-1)\). This is Euler’s totient. This is kept private, and, importantly can only be calculated by those who know the factorization of \(N\).
We can choose a public exponent value, \(e\), at this point. It is most commonly 65537. Importantly, e must be coprime to \(\phi (N)\), because it is used to calculate the private exponent value, \(d\).
Essentially, it must hold true that \(ed \equiv 1\;(mod\; \phi (N))\). In other words, \(d\) is the multiplicative inverse of \(e\) over the modulus \(\phi (N)\). We can find \(d\) via the Extended Euclidean Algorithm. I won’t include it here, but if you’re interested, look it up!
Then, encryption and decryption occur as follows, respectively:
\(m^e \equiv c\; (mod\; N)\)
Where c is the ciphertext.
\(c^d \equiv m\; (mod\; N)\)
Here’s a quick explanation on why decryption works:
\(c^d \equiv m^{ed}\;(mod\;N)\)
Note that \(ed = k\phi (N) + 1\) because \(ed \equiv 1\;(mod\; \phi (N))\)
Therefore,
\(m^{ed}\;(mod\;N) \equiv m^{k\phi (N) + 1}\;(mod\;N)\)
According to Euler’s Theorem,
\(m^{k\phi (N)} \equiv 1\;(mod\;N)\)
Thus,
\(m^{k\phi (N) + 1} \equiv m^{k\phi (N)} \cdot m \equiv m\;(mod\;N)\)
Knowing all this, we can now take a look at provided source code. RSA relies on the inability of an attacker to feasibly factor \(N\). However, in this example, N seems rather small…
We can use this site to factor it in ~2 minutes. This provides us \(p\) and \(q\), and through the same process I just described for encryption and decryption, we can do this easily in Python, utilizing the Pycryptodome module!
from Crypto.Util.number import *
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
e = 65537
c = 43711206624343807006656378470987868686365943634542525258065694164173101323321
# https://www.alpertron.com.ar/ECM.HTM
p = 1025252665848145091840062845209085931
q = 75575216771551332467177108987001026743883
assert p*q == N
phi = (p-1)*(q-1) # calculate phi
d = inverse(e, phi) # the multiplicative inverse of e (mod phi)
m = pow(c, d, N) # decryption
print(m)
print(long_to_bytes(m)) # convert the message to bytes (characters)
Run the script to get the flag!
utflag{just_send_plaintext}