RSA Cryptography and Diffie-Hellman

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.

Public-key cryptography solves the key-distribution problem: how can two parties communicate securely without first sharing a secret? Diffie-Hellman key exchange lets Alice and Bob compute a common secret by each raising a public base to their private exponent modulo a large prime — an eavesdropper sees the bases and results but cannot feasibly recover the secret. RSA uses a public modulus $n = pq$ (product of two secret primes) together with an encryption exponent $e$ ; only the holder of the private exponent $d$ can invert the operation. The surprising fact is that security rests not on proven impossibility but on conjectured computational hardness — no one has proven factoring is hard, yet billions of transactions trust that it is.

The Core Insight

A one-way function is easy to compute but hard to invert. Modular exponentiation $x \mapsto g^{x} mod 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.

Formal Statement

Modular Arithmetic Foundations

Work in the ring $Z_{n} = {0, 1, \dots, n - 1}$ with addition and multiplication modulo $n$ . The multiplicative group $Z_{n}^{*} = {a : g cd (a, n) = 1}$ has order $φ (n)$ , where $φ$ is Euler's totient function. For $n = pq$ with distinct primes:

φ (n) = φ (p) φ (q) = (p - 1) (q - 1)

⟳

φ

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 $g cd (a, n) = 1$ ,

a^{φ (n)} \equiv 1 (mod n)

⟳the map

x \mapsto a x

permutes

Z_{n}^{*}

; take the product of all group elements and cancel.

The RSA Cryptosystem

Key generation. Choose distinct large primes

p, q

; set

n = pq

. Choose

e

with

g cd (e, φ (n)) = 1

. Compute the private exponent

d

as the modular inverse:

d \equiv e^{- 1} (mod φ (n)) ⟺ e d \equiv 1 (mod φ (n))

⟳

d

exists and is unique mod

φ (n)

because

g cd (e, φ (n)) = 1

; compute via the extended Euclidean algorithm.

Public key: $(n, e)$ . Private key: $(d)$ (and secretly $p, q, φ (n)$ ).
Encryption of message $m \in Z_{n}$ : $c \equiv m^{e} (mod n)$ .
Decryption: $m \equiv c^{d} (mod n)$ .

RSA Correctness

For all $m \in Z_{n}$ , decryption recovers the message:

(m^{e})^{d} \equiv m (mod n)

⟳write

e d = 1 + k φ (n)

and apply Euler's theorem, handling the case

g cd (m, n) \neq = 1

via the Chinese Remainder Theorem.

Diffie-Hellman Key Exchange

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

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

K = B^{a} mod p = A^{b} mod p = g^{ab} mod p

⟳

(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$ .

Why It Holds / Derivation

:::proof[RSA Correctness, Equation [4]] Step 1. By construction $e d \equiv 1 (mod φ (n))$ , so write $e d = 1 + k (p - 1) (q - 1)$ for some integer $k \geq 0$ .

Step 2 (case $g cd (m, p) = 1$ ). By Fermat's little theorem

m^{p - 1} \equiv 1 (mod p)

. Then

m^{e d} = m^{1 + k (p - 1) (q - 1)} = m \cdot (m^{p - 1})^{k (q - 1)} \equiv m \cdot 1 \equiv m (mod p) .

Step 3 (case $p ∣ m$ ). Then

m \equiv 0 (mod p)

and also

m^{e d} \equiv 0 (mod p)

, so

m^{e d} \equiv m (mod p)

holds trivially. Step 4. In both cases

m^{e d} \equiv m (mod p)

. By the identical argument,

m^{e d} \equiv m (mod q)

. Step 5. Since

p

and

q

are distinct primes, the Chinese Remainder Theorem gives that the congruences

m^{e d} \equiv m (mod p)

and

m^{e d} \equiv m (mod q)

together imply

m^{e d} \equiv m (mod pq) = (mod n)

■

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.

Building 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$ .

Diffie-Hellman key exchange over a public channel

<svg viewBox="0 0 640 360" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="360" fill="#0a0e17"/>
<text x="320" y="30" fill="#e2e8f0" font-size="16" text-anchor="middle">Diffie–Hellman Key Exchange (public p, g)</text>
<rect x="40" y="70" width="180" height="70" fill="none" stroke="#94a3b8"/>
<text x="130" y="95" fill="#e2e8f0" font-size="14" text-anchor="middle">Alice</text>
<text x="130" y="118" fill="#d4a853" font-size="13" text-anchor="middle">secret a</text>
<text x="130" y="135" fill="#e2e8f0" font-size="12" text-anchor="middle">A = g^a mod p</text>
<rect x="420" y="70" width="180" height="70" fill="none" stroke="#94a3b8"/>
<text x="510" y="95" fill="#e2e8f0" font-size="14" text-anchor="middle">Bob</text>
<text x="510" y="118" fill="#d4a853" font-size="13" text-anchor="middle">secret b</text>
<text x="510" y="135" fill="#e2e8f0" font-size="12" text-anchor="middle">B = g^b mod p</text>
<line x1="220" y1="100" x2="420" y2="100" stroke="#94a3b8" marker-end="url(#ar)"/>
<text x="320" y="92" fill="#e2e8f0" font-size="12" text-anchor="middle">send A &#8594;</text>
<line x1="420" y1="125" x2="220" y2="125" stroke="#94a3b8" marker-end="url(#ar)"/>
<text x="320" y="145" fill="#e2e8f0" font-size="12" text-anchor="middle">&#8592; send B</text>
<rect x="200" y="200" width="240" height="60" fill="none" stroke="#d4a853"/>
<text x="320" y="225" fill="#d4a853" font-size="14" text-anchor="middle">Shared secret</text>
<text x="320" y="248" fill="#e2e8f0" font-size="13" text-anchor="middle">K = B^a = A^b = g^(ab) mod p</text>
<line x1="130" y1="140" x2="290" y2="200" stroke="#94a3b8"/>
<line x1="510" y1="140" x2="350" y2="200" stroke="#94a3b8"/>
<text x="320" y="310" fill="#94a3b8" font-size="12" text-anchor="middle">Eavesdropper sees g, p, A, B — but computing g^(ab) requires the discrete log.</text>
<defs><marker id="ar" markerWidth="8" markerHeight="8" refX="7" refY="3" orient="auto"><path d="M0,0 L7,3 L0,6" fill="#94a3b8"/></marker></defs>
</svg>

Worked Examples

Toy RSA Encryption/Decryption

Given: primes

p = 61

q = 53

, message

m = 65

. Step 1.

n = pq = 61 \times 53 = 3233

. Step 2.

φ (n) = (p - 1) (q - 1) = 60 \times 52 = 3120

. Step 3. Choose

e = 17

(check

g cd (17, 3120) = 1

✓). Step 4. Find

d \equiv 1 7^{- 1} (mod 3120)

. Extended Euclid gives

d = 2753

(since

17 \times 2753 = 46801 = 15 \times 3120 + 1

). Step 5. Encrypt:

c = 6 5^{17} mod 3233 = 2790

. Step 6. Decrypt:

m = 279 0^{2753} mod 3233

c = 2790, decryption = 65 = m ✓

Toy 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} mod 23 = 15625 mod 23 = 8

. Step 2. Bob:

B = 5^{15} mod 23 = 19

. Step 3. Alice computes

K = B^{a} mod 23 = 1 9^{6} mod 23 = 2

. Step 4. Bob computes

K = A^{b} mod 23 = 8^{15} mod 23 = 2

K = g^{ab} mod 23 = 5^{90} mod 23 = 2

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

Common Misconceptions

"Textbook RSA is secure as-is." Raw deterministic RSA (

c = m^{e} mod 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. 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.

Connections

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 $Z_{p}^{*}$ is replaced by a Group Theory|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.

Real-World Applications

TLS / HTTPS — every padlock in a browser uses (Elliptic-Curve) Diffie-Hellman for key exchange and RSA or ECDSA for server authentication.
SSH — secure remote login uses DH key exchange and RSA/Ed25519 host keys.
PGP / GPG email — RSA (or ElGamal, a DH variant) encrypts and signs email and files.
Signal / WhatsApp — the Signal Protocol uses X3DH, a triple Diffie-Hellman handshake over elliptic curves, for end-to-end encryption.
Digital signatures & certificates — RSA-PSS signs X.509 certificates underpinning the entire web PKI.
Bitcoin & blockchains — use ECDSA (signature) over the secp256k1 curve, a DLP-based scheme cousin of DH.
Smart cards / EMV chips — payment cards perform RSA operations to authenticate transactions.

Historical Development

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.

Subtleties & Limits

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.