A Minimal Intro to RSA

Here’s a quick intro to RSA I made for a friend a long time ago. My new friend (Claude 4.5 Opus) found it in my notes archive and published it here on my behalf.

RSA solves a seemingly impossible problem: how can two parties exchange secret messages without a pre-existing secure channel? Before asymmetric encryption, they couldn’t. Someone had to physically transport a shared secret. Thanks to RSA, now anyone with an internet connection can exchange private messages with anyone else. This simple mathematical trick changed the world, and the core idea is elegant enough to explain concisely.

High-Level Scheme

• Everyone has a key pair: a public key (share widely) and a private key (keep secret).
• To send Alice a secret, Bob encrypts with Alice’s public key. Only Alice can decrypt with her private key.

Preliminaries

RSA is built on a trapdoor function: an operation that’s easy to perform but hard to reverse without knowing a secret. In RSA, the trapdoor is multiplication vs. factoring.

Prime Factorization

Every number can be uniquely decomposed into a product of prime numbers (fundamental theorem of arithmetic).

Some examples:

• \(6 = 2 \times 3\)
• \(7 = 7\) (prime)
• \(12 = 2 \times 2 \times 3\)

Multiplication is Easy, Factoring is Hard

For large numbers, computing \(p \times q = n\) is easy, but finding \(p\) and \(q\) from \(n\) is hard. The best known factoring algorithms take roughly exponential time in the number of digits of \(n\).

We always use prime \(p\) and \(q\), in which case they are the only factors of \(n\). The secret key will be related to \(p\) and \(q\), and the public key will include \(n\).

Coprimality

Two numbers are coprime if their greatest common divisor (gcd) is 1. This means they share no factors.

Examples:

• 4 and 15 are coprime (gcd = 1)
• 3 and 12 are not coprime (common factor of \(3\))

Euler’s Totient Function

\(\phi(n)\) = the number of integers less than \(n\) that are coprime to \(n\).

Note that \(\phi(p) = p - 1\) if \(p\) is prime.

Key insight (this is RSA’s trapdoor): Computing \(\phi(n)\) from \(n\) requires factoring \(n\). But given the factors \(p\) and \(q\), it’s trivial: \(\phi(p \times q) = (p-1)(q-1)\).

Example: \(\phi(15) = 8\) because exactly 8 integers less than 15 are coprime to 15: {1, 2, 4, 7, 8, 11, 13, 14}. Using the formula: \(\phi(3 \times 5) = (3-1)(5-1) = 8\).

Euler’s Theorem

For coprime integers \(a\) and \(n\): ¹

\[a^{\phi(n)} \equiv 1 \pmod{n}\]

Example: for \(a = 2\) and \(n = 15\): \[2^{\phi(15)} = 2^{8} = 256 \equiv 1 \pmod{15}\]

Minimal RSA Algorithm

Key Generation

Each person first generates public and private key information:

1. Choose prime numbers \(p\) and \(q\)
2. Compute \(n = p \times q\)
3. Choose \(e\) that is coprime to \(\phi(n)\)
4. Compute \(d\), the modular inverse of \(e\): the unique value where \(e \times d \equiv 1 \pmod{\phi(n)}\)

Public key: \((n, e)\)

Private key: \(d\)

Calculating \(d\) from \((n, e)\) requires first computing \(\phi(n)\). As long as \(p\) and \(q\) are large secret primes, this is computationally infeasible.

from math import gcd

def rsa_keygen(p, q):
    n = p * q
    phi = (p - 1) * (q - 1)
    e = 3  # small e is fast, 65537 is standard [fn:2]
    while gcd(e, phi) != 1:
        e += 2
    d = pow(e, -1, phi)  # modular inverse
    return (n, e, d)

(n, e, d) = rsa_keygen(53, 59)  # toy primes
# => (3127, 3, 2011)

Encryption

The message \(m\) is the raw bytes of the message interpreted as an integer. In practice, \(m\) is typically a symmetric key used to encrypt the actual message.

For \(1 < m < n\):

\[c \equiv m^e \pmod{n}\]

def rsa_encrypt(m, n, e):
    assert 1 < m < n
    return pow(m, e, n)

rsa_encrypt(89, 3127, 3)
# => 1394

Decryption

To decrypt ciphertext \(c\), compute \(c^d \bmod n\):

\[c^d \equiv (m^e)^d \equiv m^{ed} \equiv m \pmod{n}\]

The last step follows from Euler’s Theorem. Since \(ed \equiv 1 \pmod{\phi(n)}\), we have \(ed = k\phi(n) + 1\) so:

\[m^{ed} = m^{k\phi(n) + 1} = m \cdot (m^{\phi(n)})^k = m \cdot 1^k = m\]

def rsa_decrypt(c, n, d):
    assert 1 < c < n
    return pow(c, d, n)

rsa_decrypt(1394, 3127, 2011)
# => 89

Putting It Together

Alice wants to send Bob the secret number \(m = 89\). (This is a toy example. Real-world RSA uses much larger numbers.)

1. Bob generates keys: public \((n, e) = (3127, 3)\), private \(d = 2011\)
2. Bob shares his public key \((3127, 3)\) with Alice
3. Alice encrypts: \(89^3 \bmod 3127 = 1394\). She sends \(c = 1394\) to Bob.
4. Bob decrypts: \(1394^{2011} \bmod 3127 = 89\)

Eve (an eavesdropper) sees 3127, 3, and 1394. She cannot recover 89 without factoring 3127. Alice and Bob can now use 89 as a shared key for fast symmetric encryption of future messages.

Caveats

Real-world RSA requires large primes (2048+ bits for \(n\)), proper padding (OAEP), and many other implementation details not covered here. Never implement your own RSA for production use.

References

• Public Key Cryptography: RSA Encryption Algorithm (video)
• Prime Number Hide-and-Seek: How the RSA Cipher Works
• RSA algorithm – Simple English Wikipedia