RSA Cryptography and Diffie-Hellman

⚡ Key Takeaways

RSA and Diffie-Hellman are the foundational public-key cryptosystems of modern security. RSA enables encryption and digital signatures based on the difficulty of factoring large integers; Diffie-Hellman enables two parties to agree on a shared secret over a public channel based on the difficulty of the discrete logarithm problem. Both rely on modular arithmetic and the existence of computationally one-way functions. Invented publicly in 1976 (Diffie-Hellman) and 1977 (RSA), they underpin HTTPS, TLS, SSH, and secure messaging worldwide.

💡 The Core Insight

A one-way function is easy to compute but hard to invert. Modular exponentiation $x \mapsto g^x \bmod p$ is fast (by repeated squaring), but recovering $x$ from $g^x$ — the discrete logarithm — is believed infeasible for large $p$ . Symmetrically, multiplying primes $p \cdot q = n$ is fast, but factoring $n$ is believed infeasible. Public-key cryptography exploits a trapdoor: a secret (the factorization, or a private exponent) that makes inversion easy for the legitimate holder but hard for everyone else.

DefinitionModular Arithmetic Foundations

Work in the ring $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$ with addition and multiplication modulo $n$ . The multiplicative group $\mathbb{Z}_n^* = \{a : \gcd(a,n)=1\}$ has order $\varphi(n)$ , where $\varphi$ is Euler's totient function. For $n = pq$ with distinct primes:

1

\quad \varphi(n) = \varphi(p)\,\varphi(q) = (p-1)(q-1)

Derivation hint: $\varphi$ is multiplicative for coprime arguments; for prime $p$ , exactly $p-1$ residues are coprime to $p$ . The key arithmetic fact is Euler's theorem: for $\gcd(a,n)=1$ ,

2

\quad a^{\varphi(n)} \equiv 1 \pmod{n}

Derivation hint: the map $x \mapsto ax$ permutes $\mathbb{Z}_n^*$ ; take the product of all group elements and cancel.

DefinitionThe RSA Cryptosystem

Key generation. Choose distinct large primes $p, q$ ; set $n = pq$ . Choose $e$ with $\gcd(e, \varphi(n)) = 1$ . Compute the private exponent $d$ as the modular inverse:

3

\quad d \equiv e^{-1} \pmod{\varphi(n)} \quad\Longleftrightarrow\quad ed \equiv 1 \pmod{\varphi(n)}

Derivation hint: $d$ exists and is unique mod $\varphi(n)$ because $\gcd(e,\varphi(n))=1$ ; compute via the extended Euclidean algorithm.

Public key: $(n, e)$ . Private key: $(d)$ (and secretly $p, q, \varphi(n)$ ).
Encryption of message $m \in \mathbb{Z}_n$ : $\;c \equiv m^e \pmod n$ .
Decryption: $\;m \equiv c^d \pmod n$ .

TheoremRSA Correctness

For all $m \in \mathbb{Z}_n$ , decryption recovers the message:

4

\quad (m^e)^d \equiv m \pmod n

Derivation hint: write $ed = 1 + k\varphi(n)$ and apply Euler's theorem, handling the case $\gcd(m,n)\neq 1$ via the Chinese Remainder Theorem.

DefinitionDiffie-Hellman Key Exchange

Fix a large prime $p$ and a generator $g$ of $\mathbb{Z}_p^*$ (or of a large prime-order subgroup). Both are public.

Alice picks secret $a \in \{1,\ldots,p-2\}$ , sends $A = g^a \bmod p$ .
Bob picks secret $b$ , sends $B = g^b \bmod p$ .
Each computes the shared secret:

5

\quad K = B^a \bmod p = A^b \bmod p = g^{ab} \bmod p

Derivation hint: $(g^b)^a = g^{ba} = (g^a)^b$ by commutativity of integer exponents. The Diffie-Hellman problem (DHP) is: given $g, g^a, g^b$ , compute $g^{ab}$ . Its hardness rests on the discrete logarithm problem (DLP): given $g, g^a$ , recover $a$ .

mathematician · Whitfield Diffie & Martin Hellman | 1944– / 1945–

At Stanford in 1976, Diffie and Hellman published New Directions in Cryptography, introducing the radical idea of asymmetric keys and the first practical key-exchange protocol. They overturned millennia of assuming both parties must share a secret in advance. Their 2015 Turing Award citation credited them with "inventing public-key cryptography." Unknown to them, GCHQ cryptographers Ellis, Cocks, and Williamson had discovered similar ideas in secret in the early 1970s — declassified only in 1997.

🧠 Intuition

Think of Diffie-Hellman as mixing paint. Public base $g$ is a common yellow. Alice secretly adds her color $a$ ; Bob secretly adds his $b$ . They swap mixtures publicly. Each then adds their own private color to the other's mixture, arriving at the same final shade $g^{ab}$ . An eavesdropper has both intermediate mixtures but cannot "un-mix" to extract the private colors — separating mixed paint is the analog of the discrete log being hard. For RSA, picture a padlock. Anyone can snap a public padlock shut (encrypt with $e$ ), but only the holder of the unique key (private $d$ ) can open it. Crucially, knowing the padlock's design ( $n, e$ ) doesn't reveal how to pick it, because picking requires factoring $n$ .

Figure

Diffie-Hellman key exchange over a public channel

```svg

```

ExampleToy RSA Encryption/Decryption

Given: primes $p = 61$ , $q = 53$ , message $m = 65$ .

Step 1. $n = pq = 61 \times 53 = 3233$ .

Step 2. $\varphi(n) = (p-1)(q-1) = 60 \times 52 = 3120$ .

Step 3. Choose $e = 17$ (check $\gcd(17, 3120) = 1$ ✓).

Step 4. Find $d \equiv 17^{-1} \pmod{3120}$ . Extended Euclid gives $d = 2753$ (since $17 \times 2753 = 46801 = 15 \times 3120 + 1$ ).

Step 5. Encrypt: $c = 65^{17} \bmod 3233 = 2790$ .

Step 6. Decrypt: $m = 2790^{2753} \bmod 3233$ .

\boxed{c = 2790,\qquad \text{decryption} = 65 = m \;\checkmark}

ExampleToy Diffie-Hellman

Given: prime $p = 23$ , generator $g = 5$ . Alice's secret $a = 6$ , Bob's secret $b = 15$ .

Step 1. Alice: $A = 5^6 \bmod 23 = 15625 \bmod 23 = 8$ .

Step 2. Bob: $B = 5^{15} \bmod 23 = 19$ .

Step 3. Alice computes $K = B^a \bmod 23 = 19^6 \bmod 23 = 2$ .

Step 4. Bob computes $K = A^b \bmod 23 = 8^{15} \bmod 23 = 2$ .

\boxed{K = g^{ab} \bmod 23 = 5^{90}\bmod 23 = 2}

Both arrive at the same shared secret $K = 2$ without ever transmitting $a$ or $b$ .

⚠️ Common mistake

"Textbook RSA is secure as-is." Raw deterministic RSA ( $c = m^e \bmod n$ ) is not semantically secure: identical messages produce identical ciphertexts, and it is malleable (multiply two ciphertexts to multiply plaintexts). Real systems use randomized padding — OAEP for encryption, PSS for signatures. Never deploy raw RSA.

"Diffie-Hellman alone gives authenticated security." Unauthenticated DH is vulnerable to a man-in-the-middle attack: an adversary intercepts and runs separate exchanges with each party. DH must be combined with authentication (signatures or certificates), as in TLS.

Counterexample

Small exponents leak data. With $e = 3$ and a short message $m$ where $m^3 < n$ , the modular reduction never occurs, so $c = m^3$ over the integers — and an attacker simply takes the integer cube root to recover $m$ , with no factoring needed. This breaks "textbook" RSA entirely for small plaintexts and motivates mandatory padding. Similarly, if the same message is sent to three recipients with $e=3$ and coprime moduli, the Chinese Remainder Theorem (Håstad's attack) recovers $m$ from the three ciphertexts.

connection

RSA and Diffie-Hellman are the canonical applications of Number Theory in practice. Both rely on Modular Arithmetic and the Chinese Remainder Theorem (the latter also speeds RSA decryption by a factor of ~4). The security of DH transfers directly to Elliptic Curve Cryptography (ECDH), where the multiplicative group $\mathbb{Z}_p^*$ is replaced by a group of points on an elliptic curve, yielding equivalent security with much smaller keys. The Discrete Logarithm Problem and the Integer Factorization Problem are the two hardness assumptions; both fall to a sufficiently large quantum computer via Shor's Algorithm, driving research in Post-Quantum Cryptography.

🔬 Where this appears

⏳ History

- 1973–74 (classified): James Ellis, Clifford Cocks, and Malcolm Williamson at GCHQ secretly invent "non-secret encryption" — essentially RSA and DH — kept classified until 1997.

- 1976: Diffie & Hellman publish New Directions in Cryptography, introducing public-key cryptography and the DH key exchange.

- 1977: Rivest, Shamir, and Adleman invent RSA at MIT; described in Martin Gardner's Scientific American column with the "RSA-129" challenge.

- 1978: The RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystems appears in Communications of the ACM.

- 1984: ElGamal publishes an encryption and signature scheme based directly on the discrete log / Diffie-Hellman problem.

- 1985: Koblitz and Miller independently propose Elliptic Curve Cryptography.

- 1994: Peter Shor publishes a quantum algorithm that factors integers and computes discrete logs in polynomial time.

- 1994: RSA-129 (426-bit) is factored by a distributed effort, revealing Gardner's plaintext "THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE."

- 2015: Diffie and Hellman receive the ACM Turing Award.

open-problem

The security of RSA and DH rests on unproven assumptions. It is not known that factoring requires superpolynomial time — a fast classical factoring algorithm would silently break RSA. Subtler open questions remain: it is unproven that breaking RSA is as hard as factoring (the RSA problem could conceivably be easier). Likewise, the Computational Diffie-Hellman assumption may be strictly weaker than the Discrete Log assumption. The most concrete threat is Shor's algorithm: a large fault-tolerant quantum computer would break both schemes, which is why NIST has standardized post-quantum alternatives (ML-KEM, ML-DSA). The exact crossover date for "store-now-decrypt-later" risk is itself an open practical question.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also