🔐 RSA CTF Writeups

A collection of RSA cryptography write-ups from PicoCTF/CyLab Security Academy

📖 About

This repository contains detailed write-ups for various RSA focused cryptography challenges from the CyLab Security Academy. Each write-up walks through the challenge set-up, steps to solve, and technical explanation on the mathematical vulnerability exploited.

🚩 Challenges (My Difficulty Ranking)

Rank	Challenge	Difficulty Score (0-100)	Tier
1	rsa_oracle	77	Hard
2	Sum-O-Primes	72	Hard
3	b00tl3gRSA3	68	Hard
4	rsa-pop-quiz	65	Hard
5	ClusterRSA	60	Hard
6	college-rowing-team	50	Medium
7	miniRSA	46	Medium
8	Crack the Power	46	Medium
9	b00tl3gRSA2	40	Medium
10	StegoRSA	30	Easy
11	EVEN RSA CAN BE BROKEN???	28	Easy

🧮 RSA Mathematics Basics

The security of the RSA cryptosystem lies in the difficulty of factoring a large modulus into its original prime factors. RSA keys are generated using large prime factors, and utilizing modular arithmetic to encrypt and decrypt messages.

Key Generation

First, two large distinct prime numbers must be chosen, $p$ and $q$

Then the modulus $n$ can be constructed:

$$n = p \cdot q$$

Euler's Totient $\phi (n)$ is then calculated using the shortcut:

$$\phi (n) = (p - 1)(q - 1)$$

Next, the public exponent $e$ must be chosen so that:

$$1 < e < \phi (n) \land \gcd(e, \phi (n)) = 1$$

Finally, the private exponent $d$, used for decryption, is calculated as follows:

$$d = e^{-1} \mod \phi (n) $$

Encryption & Decryption

A plaintext message $m$ is encrypted into the ciphertext $c$ using the public exponent $e$, and the modulus $n$:

$$c = m^e \mod n$$

Conversely, the ciphertext is decrypted using the private exponent $d$ and the modulus $n$:

$$m = c^d \mod n$$

Why It Works

Since the private exponent $d$ is the modular inverse of the public exponent $e \mod \phi(n)$, we have:

$$e \cdot d \equiv 1 \pmod{\phi(n)}$$

Following Euler's theorem:

$$m^{\phi(n)} \equiv 1 \pmod{n}$$

For any $m$ coprime to $n$, which gives us:

$$c^d = (m^e)^d = m^{e \cdot d} = m^{k \cdot \phi(n) + 1} \equiv m \pmod{n}$$