RSA 256

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)

vals.txt

We’re provided the following values:

1
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
2
e = 65537
3
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!

1
from Crypto.Util.number import *
2

3
N = 77483692467084448965814418730866278616923517800664484047176015901835675610073
4
e = 65537
5
c = 43711206624343807006656378470987868686365943634542525258065694164173101323321
6

7
# https://www.alpertron.com.ar/ECM.HTM
8
p = 1025252665848145091840062845209085931
9
q = 75575216771551332467177108987001026743883
10

11
assert p*q == N
12
phi = (p-1)*(q-1) # calculate phi
13
d = inverse(e, phi) # the multiplicative inverse of e (mod phi)
14
m = pow(c, d, N) # decryption
15
print(m)
16
print(long_to_bytes(m)) # convert the message to bytes (characters)

Run the script to get the flag!

1
utflag{just_send_plaintext}