# RSA Algorithms: Key Generation, Encryption & Decryption
> [!Note]
> **RSA** secures messages by marrying three arithmetic procedures—**key generation**, **encryption** and **decryption**—whose correctness follows from modular exponentiation while their security leans on the practical impossibility of factoring the modulus n.
A robust RSA deployment begins with **key generation**: two secret primes _p_ and _q_ yield the modulus **n = pq**, Euler’s totient **φ(n) = (p − 1)(q − 1)**, a public exponent _e_ coprime with φ(n) and its modular inverse _d_, the **private exponent**. Possessing **(n, e)** lets anyone encrypt, yet only knowledge of **d** allows reversal.
> [!Algorithm] **Key Generation**
>
> - Choose random strong primes **p**, **q**
>
> - Compute **n = p · q**
>
> - Compute **φ(n) = (p − 1)(q − 1)**
>
> - Select **e** such that **gcd(e, φ(n)) = 1**
>
> - Compute **d = e⁻¹ (mod φ(n))**
>
> - Publish **kpub = (n, e)** and keep **kpriv = d** (plus φ(n), p, q) strictly secret
>
After keys exist, the **encryption algorithm** transforms any integer plaintext _m_ with 0 ≤ _m_ < _n_ into ciphertext **c = mᵉ (mod n)**, while the **decryption algorithm** recovers the original by **m = cᵈ (mod n)**.
> [!Algorithm] **Encryption**
>
> - Accept **plaintext m** and recipient’s **(n, e)**
>
> - Calculate **c = mᵉ (mod n)**
>
> - Transmit **ciphertext c** to recipient
>
> [!Algorithm] **Decryption**
>
> - Accept **ciphertext c** and owner’s **d** with the same **n**
>
> - Compute **m = cᵈ (mod n)**
>
> - Output the recovered **plaintext m**
>
> [!Example]
> With the slide’s 32-bit toy values: **n = 284 829 9073**, **e = 1 535 231 195**, **d = 1 437 751 395**.
> • Alice encrypts **m = 424 242** as **c = 191 459 7261**.
> • Bob decrypts by **m = cᵈ (mod n)** and regains **424 242**, affirming that encryption and decryption are mathematical inverses when _d·e ≡ 1 (mod φ(n))_.
Because only the **private exponent** unlocks ciphertext, RSA naturally extends to **digital signatures** when the data are instead exponentiated with _d_ and verified with _e_. Although **elliptic-curve cryptography** now offers similar security with shorter keys, RSA at **2048 bits or above** still underpins TLS handshakes, software updates and secure e-mail.
``` mermaid
sequenceDiagram
participant KG as Key Generation
participant Alice
participant Bob
%% ---------- KEY GENERATION ----------
KG->>KG: choose p, q
KG->>KG: n = p·q, φ(n) = (p−1)(q−1)
KG->>KG: select e ⟂ φ(n)
KG->>KG: d = e⁻¹ mod φ(n)
KG-->>Alice: k_pub = (n, e)
KG-->>Bob: k_priv = d (kept secret)
%% ---------- ENCRYPTION ----------
Alice->>Alice: c = mᵉ mod n
Alice-->>Bob: ciphertext c
%% ---------- DECRYPTION ----------
Bob->>Bob: m = cᵈ mod n
```
### Python Code
``` python
import random
from math import gcd
def is_prime(n: int) -> bool:
"""Return True if n is a prime (naïve trial division, fine for small demo)."""
if n < 2:
return False
if n % 2 == 0:
return n == 2
r = int(n ** 0.5) + 1
for i in range(3, r, 2):
if n % i == 0:
return False
return True
def generate_prime(low: int = 100, high: int = 300) -> int:
"""Pick a random prime in [low, high]."""
while True:
candidate = random.randint(low, high)
if is_prime(candidate):
return candidate
def egcd(a: int, b: int):
"""Extended Euclidean algorithm: returns (g, x, y) such that ax + by = g = gcd(a,b)."""
if b == 0:
return (a, 1, 0)
g, x1, y1 = egcd(b, a % b)
return (g, y1, x1 - (a // b) * y1)
def modinv(e: int, phi: int) -> int:
"""Modular inverse of e modulo phi."""
g, x, _ = egcd(e, phi)
if g != 1:
raise ValueError("e and phi are not coprime, inverse doesn't exist")
return x % phi
def rsa_keygen():
"""Generate a very small RSA key pair (demo purposes only!)."""
p = generate_prime()
q = generate_prime()
while q == p: # ensure p ≠ q
q = generate_prime()
n = p * q
phi = (p - 1) * (q - 1)
# common choice; if it clashes we fall back to searching for an odd e
e = 65537
if gcd(e, phi) != 1:
e = 3
while gcd(e, phi) != 1:
e += 2
d = modinv(e, phi)
return {"p": p, "q": q, "n": n, "phi": phi, "e": e, "d": d}
def rsa_encrypt(m: int, n: int, e: int) -> int:
"""Encrypt integer message m with public key (n, e)."""
return pow(m, e, n)
def rsa_decrypt(c: int, n: int, d: int) -> int:
"""Decrypt ciphertext c with private exponent d and modulus n."""
return pow(c, d, n)
# --- Demo run --------------------------------------------------------------
key = rsa_keygen()
p, q, n, phi, e, d = key.values()
# choose a random plaintext that is smaller than n
m = random.randint(2, n - 2)
c = rsa_encrypt(m, n, e)
m_recovered = rsa_decrypt(c, n, d)
print("=== RSA DEMONSTRATION (toy-size parameters) ===")
print(f"Prime factors (secret): p = {p}, q = {q}")
print(f"Modulus: n = {n}")
print(f"Public exponent: e = {e}")
print(f"Private exponent (secret): d = {d}")
print(f"\nOriginal plaintext m = {m}")
print(f"Ciphertext c = {c}")
print(f"Recovered plaintext = {m_recovered}")
print("\nSuccess:", m == m_recovered)
```
---
## References