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:

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 ϕ(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 ϕ(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}