RSA

The Story Behind the Math

In 1976, Whitfield Diffie and Martin Hellman proposed a revolutionary idea: what if encryption and decryption used different keys? One key could be made public for anyone to encrypt messages, while only the owner of the private key could decrypt them. But they didn't have a concrete system to implement this idea.

The challenge was picked up by three researchers at MIT: Ron Rivest, Adi Shamir, and Leonard Adleman. After months of failed attempts (Rivest and Shamir would propose schemes, Adleman would break them), Rivest had a breakthrough one night in April 1977 after a Passover celebration. By morning, he had a complete system written up. He listed the authors alphabetically: RSA.

The key insight: Multiplying two large prime numbers is trivial — a computer can do it in microseconds. But given only the product, finding the original primes is extraordinarily hard. A number that takes microseconds to create could take billions of years to factor. This asymmetry between multiplication (easy) and factoring (hard) is the foundation of RSA.

What Rivest, Shamir, and Adleman didn't know was that a British mathematician, Clifford Cocks, had independently discovered the same algorithm in 1973 while working at GCHQ (the UK's signals intelligence agency). But his work was classified and wouldn't be declassified until 1997.

RSA went on to become the backbone of internet security. Every time you see the padlock icon in your browser, RSA (or its descendants) is likely involved. Rivest, Shamir, and Adleman received the 2002 Turing Award for their contribution.

Why It Matters

• HTTPS/TLS — RSA secures web traffic, online banking, and e-commerce
• Digital signatures — Verifying software updates, legal documents, and email authenticity
• SSH — Secure remote server access uses RSA key pairs
• PGP/GPG — Email encryption relies on RSA
• Cryptocurrency — Early Bitcoin implementations used RSA-related mathematics
• Government and military — Classified communication relies on public-key infrastructure

Prerequisites

• Modular arithmetic (remainders, \(a \mod n\))
• Prime numbers and factoring
• Euler's totient function \(\phi(n)\)
• Exponentiation and logarithms

The Formula

Key Generation

1. Choose two large distinct primes \(p\) and \(q\)
2. Compute \(n = pq\)
3. Compute \(\phi(n) = (p-1)(q-1)\)
4. Choose \(e\) such that \(1 < e < \phi(n)\) and \(\gcd(e, \phi(n)) = 1\)
5. Compute \(d \equiv e^{-1} \pmod{\phi(n)}\) (i.e., \(ed \equiv 1 \pmod{\phi(n)}\))

Public key: \((n, e)\). Private key: \((n, d)\).

Encryption

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

Decryption

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

The fundamental identity that makes RSA work:

\[ m^{ed} \equiv m \pmod{n} \]

Derivation

Step 1: Euler's Theorem — The Mathematical Foundation

Euler's theorem states that for any integer \(a\) coprime to \(n\):

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

where \(\phi(n)\) is Euler's totient function — the count of integers from 1 to \(n\) that are coprime to \(n\).

Why does this work? Consider the set of integers coprime to \(n\): \(\{a_1, a_2, \ldots, a_{\phi(n)}\}\). Multiplying each by \(a\) (coprime to \(n\)) just permutes this set. So:

\[ \prod_{i} (a \cdot a_i) \equiv \prod_{i} a_i \pmod{n} \]

\[ a^{\phi(n)} \prod_{i} a_i \equiv \prod_{i} a_i \pmod{n} \]

Since \(\prod a_i\) is coprime to \(n\), we can cancel it:

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

Step 2: Computing \(\phi(n)\) for \(n = pq\)

For two distinct primes \(p\) and \(q\), the integers from 1 to \(n = pq\) that are not coprime to \(n\) are the multiples of \(p\) (there are \(q\) of them) and the multiples of \(q\) (there are \(p\) of them). Since \(p\) and \(q\) are distinct primes, the only number that's a multiple of both is \(pq = n\) itself. By inclusion-exclusion:

\[ \phi(n) = n - p - q + 1 = pq - p - q + 1 = (p-1)(q-1) \]

Step 3: Why Decryption Recovers the Message

We chose \(e\) and \(d\) such that:

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

This means \(ed = 1 + k\phi(n)\) for some integer \(k\). Now consider decryption:

\[ c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \pmod{n} \]

By Euler's theorem (when \(\gcd(m, n) = 1\)):

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

Therefore:

\[ c^d \equiv m \cdot 1^k \equiv m \pmod{n} \]

We get back the original message \(m\).

Edge case: What if \(\gcd(m, n) \neq 1\)? This means \(m\) is divisible by \(p\) or \(q\) (but not both, since \(m < n = pq\)). In this case, a more careful argument using the Chinese Remainder Theorem shows that \(m^{ed} \equiv m \pmod{n}\) still holds.

Step 4: Finding the Private Key \(d\)

We need \(d\) such that \(ed \equiv 1 \pmod{\phi(n)}\). This is computed using the Extended Euclidean Algorithm.

Given \(\gcd(e, \phi(n)) = 1\), the algorithm finds integers \(d\) and \(y\) such that:

\[ ed + y \cdot \phi(n) = 1 \]

Reducing modulo \(\phi(n)\):

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

This \(d\) is the multiplicative inverse of \(e\) modulo \(\phi(n)\).

Step 5: Why It's Secure

To break RSA, an attacker who knows the public key \((n, e)\) needs to find \(d\). To find \(d\), they need \(\phi(n) = (p-1)(q-1)\). To find \(\phi(n)\), they need \(p\) and \(q\). To find \(p\) and \(q\), they must factor \(n\).

The best known classical factoring algorithms (e.g., the General Number Field Sieve) run in sub-exponential time:

\[ O\!\left(\exp\!\left(c \cdot (\ln n)^{1/3} (\ln \ln n)^{2/3}\right)\right) \]

For a 2048-bit key (\(n \approx 2^{2048}\)), this is computationally infeasible with current technology.

Warning: Shor's algorithm on a quantum computer could factor in polynomial time \(O((\log n)^3)\). This is why post-quantum cryptography is an active research area.

Variables Explained

Symbol	Name	Description
\(p, q\)	Primes	Two large, distinct prime numbers (kept secret)
\(n\)	Modulus	\(pq\), part of both public and private keys
\(\phi(n)\)	Euler's totient	\((p-1)(q-1)\), count of integers coprime to \(n\)
\(e\)	Public exponent	Typically 65537; must be coprime to \(\phi(n)\)
\(d\)	Private exponent	\(e^{-1} \mod \phi(n)\), kept secret
\(m\)	Plaintext	The message as an integer, \(0 \leq m < n\)
\(c\)	Ciphertext	The encrypted message, \(c = m^e \mod n\)

Worked Examples

Example 1: Small RSA (Toy Example)

Key generation:

Choose \(p = 61\), \(q = 53\).

\[ n = 61 \times 53 = 3233 \]

\[ \phi(n) = 60 \times 52 = 3120 \]

Choose \(e = 17\) (coprime to 3120, since \(\gcd(17, 3120) = 1\)).

Find \(d\) such that \(17d \equiv 1 \pmod{3120}\).

Using the Extended Euclidean Algorithm: \(d = 2753\) (since \(17 \times 2753 = 46801 = 15 \times 3120 + 1\)).

Public key: \((3233, 17)\). Private key: \((3233, 2753)\).

Encryption of \(m = 65\) (ASCII for 'A'):

\[ c = 65^{17} \mod 3233 = 2790 \]

Decryption:

\[ m = 2790^{2753} \mod 3233 = 65 \]

We recover the original message.

Example 2: Why Factoring Is the Bottleneck

Suppose an attacker intercepts the public key \((n = 3233, e = 17)\). To find \(d\), they need \(\phi(n)\).

For \(n = 3233\), trial division quickly reveals \(3233 = 61 \times 53\). But for a 2048-bit number (about 617 digits), the best algorithms would take longer than the age of the universe on current hardware.

Example 3: Digital Signature

Alice wants to sign a document with hash \(h = 100\). She computes the signature with her private key:

\[ s = 100^{2753} \mod 3233 = 2726 \]

Anyone can verify with her public key:

\[ h' = 2726^{17} \mod 3233 = 100 \]

Since \(h' = h\), the signature is valid. Only Alice (who knows \(d\)) could have produced this signature — it proves authenticity and non-repudiation.

Common Mistakes

• Using small primes: RSA with small primes is trivially breakable. In practice, \(p\) and \(q\) should be at least 1024 bits each (for a 2048-bit \(n\)).

• Reusing primes: If two RSA moduli share a prime factor (\(n_1 = pq_1\), \(n_2 = pq_2\)), computing \(\gcd(n_1, n_2) = p\) immediately breaks both keys.

• Encrypting without padding: Raw RSA (\(c = m^e \mod n\)) is deterministic — the same message always produces the same ciphertext. In practice, randomized padding schemes like OAEP are essential.

• Confusing \(\phi(n)\) with \(n\): The exponents work modulo \(\phi(n)\), not modulo \(n\). The message arithmetic is modulo \(n\), but the key relationship \(ed \equiv 1\) is modulo \(\phi(n)\).

• Thinking RSA is quantum-safe: Shor's algorithm breaks RSA. Post-quantum alternatives like lattice-based cryptography are being standardized.

Related Formulas

• Diffie-Hellman Key Exchange — The key exchange protocol that inspired RSA
• Elliptic Curve Cryptography — A more efficient alternative to RSA

History

• 1874 — William Stanley Jevons notes the asymmetry between multiplication and factoring
• 1973 — Clifford Cocks at GCHQ secretly discovers the RSA algorithm (classified until 1997)
• 1976 — Diffie and Hellman publish the concept of public-key cryptography
• 1977 — Rivest, Shamir, and Adleman publish the RSA algorithm
• 1978 — RSA paper appears in Communications of the ACM
• 1983 — RSA patented in the US (patent expired in 2000)
• 1991 — RSA Laboratories publishes the RSA Factoring Challenge
• 1994 — Peter Shor discovers quantum factoring algorithm, threatening RSA
• 2002 — Rivest, Shamir, and Adleman receive the Turing Award
• 2020 — RSA-250 (829 bits) factored; 2048-bit keys remain secure

References

• Rivest, R. L., Shamir, A., & Adleman, L. (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 21(2), 120–126.
• Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644–654.
• Shor, P. W. (1994). Algorithms for Quantum Computation. Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 124–134.
• Boneh, D. (1999). Twenty Years of Attacks on the RSA Cryptosystem. Notices of the AMS, 46(2), 203–213.