RSA Algorithm

The key-distribution problem

Every cipher so far, from Caesar to AES, is symmetric: the same key locks and unlocks. So before two people can talk secretly they must already share a secret key. How do you agree on a key with a website you have never visited?

In 1977 Ron Rivest, Adi Shamir and Leonard Adleman published RSA, the first practical public-key (asymmetric) cipher. Bob creates two keys:

• a public key (e, n) that he gives to everyone, used to encrypt,
• a private key (d, n) that he never shares, used to decrypt.

Think of it as an open padlock: anyone can snap it shut on a box, but only Bob has the key that opens it.

Key generation

1. Choose two different large primes p and q. Keep them secret.
2. Compute n = p × q. It is public.
3. Compute φ(n) = (p − 1)(q − 1), Euler’s totient. It is secret.
4. Choose e with 1 < e < φ(n) and gcd(e, φ(n)) = 1. Real systems use e = 65537.
5. Compute d = e⁻¹ mod φ(n), the number with e × d mod φ(n) = 1, using the extended Euclidean algorithm.

The public key is (e, n) and the private key is (d, n).

Encryption and decryption

The message is turned into a number m with 0 ≤ m < n. Then:

• Encrypt (anyone, with the public key): c = mᵉ mod n
• Decrypt (Bob, with the private key): m = cᵈ mod n

It works because e × d = 1 + k·φ(n) for some k, and by Euler’s theorem m^φ(n) = 1 (mod n). So cᵈ = m^(ed) = m · (m^φ(n))ᵏ = m (mod n).

Worked example (p = 17, q = 11, e = 7)

This is the classic textbook example.

Step	Calculation	Result
n	17 × 11	187
φ(n)	16 × 10	160
e	gcd(7, 160) = 1 ✓	7
d	7⁻¹ mod 160	23
Public key	(e, n)	(7, 187)
Private key	(d, n)	(23, 187)
Encrypt m = 88	88⁷ mod 187	c = 11
Decrypt c = 11	11²³ mod 187	m = 88

Finding d with the extended Euclid table

Start with r₁ = φ(n) = 160, r₂ = e = 7, t₁ = 0 and t₂ = 1. In each row, q = ⌊r₁ / r₂⌋, r = r₁ − q·r₂ and t = t₁ − q·t₂. Then shift everything one place left and repeat until r₂ = 0:

q	r₁	r₂	r	t₁	t₂	t
22	160	7	6	0	1	−22
1	7	6	1	1	−22	23
6	6	1	0	−22	23	−160

When r₂ reaches 0, r₁ = 1 (the gcd) and t₁ = 23 = d. If t₁ were negative you would add φ(n). Check: 7 × 23 = 161 = 160 + 1 ✓.

Square-and-multiply

88⁷ has 14 digits, and real exponents have 600 digits, so nobody computes mᵉ first. Instead, write the exponent in binary and, for each bit from the left, square the running result and then multiply by m if the bit is 1, reducing mod n every time. e = 7 = 111₂:

Bit	Square	Multiply	Result
1	1² = 1	1 × 88 = 88	88
1	88² mod 187 = 77	77 × 88 mod 187 = 44	44
1	44² mod 187 = 66	66 × 88 mod 187 = 11	11

A 2048-bit exponent takes about 2048 squarings, not 2²⁰⁴⁸ multiplications.

Digital signatures

Swap the roles of the keys and RSA proves who sent a message:

• Sign with the private key: s = mᵈ mod n.
• Verify with the public key: check that sᵉ mod n = m.

Only Bob knows d, so only he can make s, yet everyone can check it. In practice Bob signs a hash of the message (for example SHA-256), not the message itself, because the hash is short and fixed-size.

Why is RSA secure?

Eve sees n, e and c. To decrypt she needs d, which needs φ(n), which needs p and q. So breaking RSA is (as far as anyone knows) as hard as factoring n.

• Factoring 187 takes a moment: try dividing by 2, 3, 5, … up to √187.
• The largest RSA number ever factored, RSA-250 (829 bits), took about 2,700 CPU core-years in 2020.
• Real keys use n of 2048 or 4096 bits (617 or 1233 decimal digits).

A large quantum computer running Shor’s algorithm could factor n quickly. That is why new “post-quantum” algorithms are being rolled out.

RSA in practice

• RSA is about 1000× slower than AES, so it is never used to encrypt whole files. It encrypts or agrees on a short AES key, and AES does the rest (hybrid encryption).
• “Textbook” RSA as shown here is deterministic: the same m always gives the same c, so an attacker can test guesses. Real RSA adds random padding (OAEP) before encrypting.
• Today, HTTPS mostly uses RSA for signatures (in certificates) and Diffie–Hellman for agreeing on keys.

Code

from math import gcd

def make_keys(p: int, q: int, e: int = 65537):
    n, phi = p * q, (p - 1) * (q - 1)
    assert gcd(e, phi) == 1, "e must share no factor with phi(n)"
    d = pow(e, -1, phi)                 # modular inverse (Python 3.8+)
    return (e, n), (d, n)

def egcd_inverse(e: int, phi: int) -> int:
    """The extended Euclid table, as worked by hand."""
    r1, r2, t1, t2 = phi, e, 0, 1
    while r2:
        q = r1 // r2
        r1, r2 = r2, r1 - q * r2
        t1, t2 = t2, t1 - q * t2
    return t1 % phi                     # r1 is now gcd = 1

def power(m: int, e: int, n: int) -> int:
    """Square-and-multiply, reading the bits of e from the left."""
    result = 1
    for bit in bin(e)[2:]:
        result = result * result % n
        if bit == "1":
            result = result * m % n
    return result

public, private = make_keys(17, 11, e=7)
print(public, private)                  # (7, 187) (23, 187)
print(egcd_inverse(7, 160))             # 23
c = power(88, *public)
print(c)                                # 11
print(power(c, *private))               # 88
s = power(88, *private)                 # sign with the private key
print(power(s, *public) == 88)          # True: the signature checks out

#include <cstdint>
#include <iostream>
using namespace std;
using u64 = uint64_t;

u64 power(u64 m, u64 e, u64 n) {        // square-and-multiply (right-to-left bits)
    u64 result = 1;
    m %= n;
    while (e) {
        if (e & 1) result = result * m % n;
        m = m * m % n;
        e >>= 1;
    }
    return result;                      // fine while n < 2^32
}

long long inverse(long long e, long long phi) {    // extended Euclid table
    long long r1 = phi, r2 = e, t1 = 0, t2 = 1;
    while (r2) {
        long long q = r1 / r2, r = r1 - q * r2, t = t1 - q * t2;
        r1 = r2; r2 = r;
        t1 = t2; t2 = t;
    }
    return (t1 % phi + phi) % phi;
}

int main() {
    u64 p = 17, q = 11, n = p * q, phi = (p - 1) * (q - 1), e = 7;
    u64 d = inverse(e, phi);
    u64 c = power(88, e, n);
    cout << "d = " << d << ", c = " << c << ", m = " << power(c, d, n) << '\n';   // d = 23, c = 11, m = 88
}

Common mistakes

• Using n instead of φ(n) when computing d. d is the inverse of e modulo φ(n), not modulo n.
• Choosing e that shares a factor with φ(n). With φ(n) = 160, e = 5 fails because gcd(5, 160) = 5, so no inverse exists.
• Forgetting to make d positive. The table can end with a negative t₁; add φ(n).
• Computing mᵉ in full before taking mod n. Reduce after every multiplication, as square-and-multiply does.
• Swapping the keys. Encrypt with the receiver’s public key; sign with the sender’s private key.
• Picking m ≥ n. The message must be smaller than n, or it cannot be recovered.