RSA

Every time you visit a website over HTTPS, authenticate with an SSH key, or verify a software signature, RSA is likely doing the heavy lifting. Invented by Rivest, Shamir, and Adleman in 1978 — and honoured with the 2002 ACM Turing Award — it remains the most widely deployed public-key cryptosystem in existence. Understanding how it works, why it works, and where it fails is essential for anyone building or auditing secure systems.

Background: modular arithmetic

RSA lives entirely in modular arithmetic. a mod n is the remainder after dividing a by n. The key property you need is that modulo distributes over multiplication and exponentiation:

(a * b) mod n = [(a mod n) * (b mod n)] mod n
a^x   mod n = (a mod n)^x mod n

This means you can reduce intermediate results at each step when computing a huge exponentiation — no need to evaluate the full number before taking the remainder.

Background: Euler's theorem

Euler's totient function φ(n) counts the positive integers less than n that share no common factor with n.

• If p is prime, φ(p) = p - 1 (every integer from 1 to p-1 is coprime to p).
• If n = p * q for distinct primes p and q, then φ(n) = φ(p) * φ(q) = (p-1)(q-1).

Euler's theorem states: for any a coprime to n,

a^φ(n) mod n = 1

This is the engine that makes RSA correct.

Key generation

1. Choose two large distinct primes p and q. Keep them secret.
2. Compute the modulus n = p * q. This is published.
3. Compute φ(n) = (p - 1)(q - 1). Keep this secret.
4. Choose a public exponent e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1 (i.e. e is coprime to φ(n)). The value 65537 is the standard choice in practice.
5. Compute the private exponent d as the modular inverse of e modulo φ(n):

   e * d mod φ(n) = 1
   

   This is solved with the extended Euclidean algorithm.

Public key: (e, n) — share freely.
Private key: d — keep secret. Also discard p, q, and φ(n) after key generation; they must not be recoverable.

Encryption and decryption

Given a message m represented as an integer with 0 < m < n:

Encrypt (anyone with the public key can do this):

c = m^e mod n

Decrypt (only the private-key holder can do this):

m = c^d mod n

That's the complete textbook cipher. The asymmetry comes from the fact that computing d from e and n alone requires factoring n — which is believed to be computationally infeasible for large n.

Why correctness works (Euler's theorem)

Decryption recovers the original message because:

c^d mod n
= (m^e)^d mod n
= m^(ed) mod n

Since e * d ≡ 1 (mod φ(n)), we can write ed = k * φ(n) + 1 for some integer k. Then:

m^(ed) mod n
= m^(k*φ(n)+1) mod n
= (m^φ(n))^k * m mod n
= 1^k * m mod n   ← Euler's theorem: m^φ(n) mod n = 1
= m

The exponent "wraps around" in a cycle of length φ(n), landing back on m.

Worked example

Use the values from the lecture: p = 11, q = 7.

Encrypt message m = 15:

c = 15^37 mod 77 = 71

Decrypt ciphertext c = 71:

m = 71^13 mod 77 = 15  ✓

You can verify small steps by reducing modulo 77 at each multiplication — the distributive property of mod keeps numbers manageable.

Digital signatures

RSA naturally supports signing by inverting the roles of the keys:

• Sign (private key holder): σ = m^d mod n
• Verify (anyone with the public key): compute σ^e mod n; if it equals m, the signature is valid.

The same Euler's theorem argument guarantees (m^d)^e mod n = m, so verification recovers the original value.

Why you must hash before signing

Signing the raw message directly has two fatal problems:

1. Size: RSA can only operate on values smaller than n. A document of arbitrary length cannot be directly exponentiated.
2. Malleability: An attacker who has signatures σ₁ on m₁ and σ₂ on m₂ can trivially forge a signature σ₁ * σ₂ mod n on m₁ * m₂ mod n without knowing d.

The fix is to sign a hash of the message: σ = H(m)^d mod n. A cryptographic hash (SHA-256 or better) produces a fixed-size digest, making both problems disappear. The standard scheme for signature padding is RSA-PSS.

Security foundation: factoring is hard

The security of RSA rests on the integer factorization assumption: given n = p * q, there is no efficient algorithm to recover p and q when they are large (≥ 1024 bits each).

If an attacker could factor n, they would compute φ(n) = (p-1)(q-1) and then recover d = e⁻¹ mod φ(n) — breaking the scheme completely. After more than 45 years of sustained cryptanalytic effort, no polynomial-time classical algorithm for factoring is known. (Note: Shor's algorithm on a sufficiently large quantum computer would break RSA, which is why post-quantum cryptography is an active area.)

Practical considerations

Textbook RSA pitfall

Textbook (plain) RSA is deterministic: encrypting the same message twice gives the same ciphertext. An attacker who can make encryption queries can build a dictionary of (m, c) pairs and look up any observed ciphertext. OAEP adds randomness so every encryption is different, eliminating this attack.

Hybrid encryption in practice

Because RSA is orders of magnitude slower than symmetric ciphers, real protocols (TLS, SSH, PGP) use RSA only to securely exchange a random AES key. All subsequent data is encrypted with AES. This gives you the key-distribution convenience of RSA at the bulk speed of AES.

RSA in SSH

Running ssh-keygen generates an RSA key pair. The public key goes to the server (~/.ssh/authorized_keys); the private key stays on your machine (~/.ssh/id_rsa). During login, the server challenges you to prove you hold the private key — no password ever crosses the network.

Key takeaways

• RSA key generation: pick primes p, q; compute n = pq, φ(n) = (p-1)(q-1); choose e coprime to φ(n); find d = e⁻¹ mod φ(n). Public key is (e, n), private key is d.
• Encrypt with the public key: c = m^e mod n. Decrypt with the private key: m = c^d mod n.
• Correctness follows from Euler's theorem: because ed ≡ 1 mod φ(n), raising m^e to the power d cycles back to m.
• Signing inverts the key roles: sign with d, verify with e. Always sign a hash, never the raw message.
• Security rests on the hardness of factoring n. There is no known efficient classical algorithm.
• Never deploy textbook RSA. Use OAEP for encryption, PSS for signatures, and at least 2048-bit keys.
• In practice, RSA encrypts a symmetric session key (hybrid encryption); bulk data is encrypted with AES.