Understand RSA key generation, encryption, decryption, and the math behind it for CTF crypto.

RSA

RSA(Rivest-Shamir-Adleman) Algorithm is an asymmetric or public-key cryptography algorithm which means it works on two different keys: Public Key and Private Key. The Public Key is used for encryption and is known to everyone, while the Private Key is used for decryption and must be kept secret by the receiver.

How it works: Generate two large primes (p, q); modulus n = p × q; public exponent e (typically 65537); private exponent d computed using Euler's totient φ(n) = (p-1)(q-1); encryption uses C = M^e mod n; decryption uses M = C^d mod n.

Why it matters: RSA security relies entirely on factorization difficulty; small primes, shared factors, or improper padding create exploitable weaknesses; CTF challenges test prime factorization, Chinese Remainder Theorem, and Coppersmith's attack; most common asymmetric algorithm in real-world systems.

RSA Overview

RSA (Rivest–Shamir–Adleman) works on the principle that:

Public key (n, e) is known to everyone → encrypts
Private key d is secret → decrypts
Computing d from n and e is computationally hard (depends on factoring n)

Component	Who knows	Purpose
n (modulus)	Public	Shared by all
e (public exponent)	Public	Encryption
d (private exponent)	Secret	Decryption
p, q (primes)	Secret	Only owner knows

Mathematical Foundations

Modular Arithmetic

Concept	Definition
$a \bmod n$	Remainder when $a$ is divided by $n$ (e.g. $17 \bmod 5 = 2$ )
Modular inverse	$a^{-1} \bmod n$ : an integer $x$ with $ax \equiv 1 \pmod{n}$ ; exists iff $\gcd(a,n)=1$

Euler's Totient Function

Case	Formula
Prime $p$	$\varphi(p) = p-1$
$n = pq$ (distinct primes)	$\varphi(n) = (p-1)(q-1)$

Carmichael's Lambda

For $n = pq$ , $\lambda(n) = \mathrm{lcm}(p-1,q-1)$ . Some RSA implementations use $\lambda$ instead of $\varphi$ when computing $d$ .

RSA Algorithm

Key Generation

Choose two primes

Choose two large distinct prime numbers: p, q.

Compute modulus

Compute: n = p * q (this modulus is public).

Compute totient

Compute Euler's totient $\varphi(n) = (p-1)(q-1)$ (or Carmichael $\lambda(n) = \mathrm{lcm}(p-1,q-1)$ ).

Choose public exponent

Choose $e$ with $1 < e < \varphi(n)$ and $\gcd(e, \varphi(n)) = 1$ (commonly $e = 65537 = 2^{16}+1$ ).

Compute private exponent

Compute $d \equiv e^{-1} \pmod{\varphi(n)}$ . This is the private exponent.

Distribute keys

Public key: (n, e) Private key: (n, d) or (p, q, d, e)

Encryption

c \equiv m^e \pmod{n}

Decryption

m \equiv c^d \pmod{n}

This works because $(m^e)^d \equiv m^{ed} \equiv m \pmod{n}$ by Euler's theorem.

Python RSA from Scratch

Explanation: Generates a small RSA keypair, encrypts a short message, then decrypts it to demonstrate end-to-end RSA.

from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes, GCD
from math import lcm

# Key generation
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
phi = (p - 1) * (q - 1)

# Verify e and phi are coprime
assert GCD(e, phi) == 1

# Private exponent
d = pow(e, -1, phi)  # Python 3.8+ built-in modular inverse

# Encrypt
m = bytes_to_long(b"Hello CTF!")
c = pow(m, e, n)

# Decrypt
m_decrypted = pow(c, d, n)
print(long_to_bytes(m_decrypted))  # → b"Hello CTF!"

When You Have p and q

Explanation: Given the prime factors p and q, compute d and decrypt ciphertext c.

from Crypto.Util.number import long_to_bytes

p = ...
q = ...
e = 65537
c = ...

n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

Common RSA Parameters in CTF

CTF challenges often give you some or all of:

Given	Typical next step
$n$ , $e$ , $c$	Standard scenario - look for small $e$ , factorable $n$ , or known attacks
$p$ , $q$ , $e$ , $c$	Compute $\varphi$ and $d$ , then decrypt
$n$ , $e$ , $d$ , $c$	Recover factors from $d$ (see below)
Multiple moduli	$\gcd(n_1, n_2)$ may reveal a shared prime

Factoring n Given d

If you know d (private exponent) and want p, q:

Explanation: Uses a randomized method to recover `p` and `q` from `n`, `e`, and `d` by exploiting the relation ed − 1 = k·φ(n).

import random
from math import gcd

def factor_with_d(n, e, d):
    """Recover p and q from n, e, d."""
    # ed - 1 = k * phi(n)
    k = e * d - 1

    while True:
        g = random.randint(2, n - 2)
        t = k

        while t % 2 == 0:
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gcd(x - 1, n) > 1:
                p = gcd(x - 1, n)
                return p, n // p

p, q = factor_with_d(n, e, d)
print(f"p = {p}\nq = {q}")

Reading PEM Files

Loads RSA keys from PEM files and prints the key components (public n, e; private d, p, q).

from Crypto.PublicKey import RSA

# Load public key from PEM file
with open('public.pem', 'r') as f:
    pub = RSA.import_key(f.read())
    n = pub.n
    e = pub.e
    print(f"n = {n}")
    print(f"e = {e}")
    print(f"key size = {pub.size_in_bits()} bits")

# Load private key
with open('private.pem', 'r') as f:
    priv = RSA.import_key(f.read())
    d = priv.d
    p = priv.p
    q = priv.q

See also

ECC Basics - Elliptic Curve Cryptography overview and attacks.
Hash Functions - Hashing concepts used in signatures and protocols.
RSA Attacks - The full RSA attack catalogue (Wiener, Håstad, Coppersmith, common modulus, and more).

Last updated on Aug 1, 2025

RSA Basics

RSA