A history of public key cryptography

Merkle puzzles

• Secure communications over insecure channels
• Drafted in 1974, submitted in 1975, rejected several times, finally published in ACM in 1978
• Contained first asymmetric cryptosystem, based on symmetric crypto 'puzzles'

Merkle puzzles - an example

• Suppose Alice and Bob secretly want to establish a secret key over a public channel
• Alice generates \(m\) puzzles \(c_i\) by setting \[ c_i = E_{k_i}( r_i || s_i || 0_{2n})\] with \(E\) a strong symmetric encryption algorithm, \(k_i\) a random \(n\)-bit key, \(r_i\) a 128-bit identifier and \(s_i\) a 128-bit secret and \(0_{2n}\) are 2n zero bits, and sends them to Bob
• Alice keeps the pairs \(\{r_i,s_i\}\) stored
• Bob selects a random puzzle \(c_i\), tries all possible values for \(k_i\) until a plaintext is found with \(2n\) trailing zero bits
• Bob sends the recoverd identifier \(r_i\) to Alice, who looks up the corresponding value of \(s_i\), which is a secret they both know now
• On average, it will take Bob \(2^{n-1}\) trial decryption
• An eavesdropper doesn't know which puzzle Bob selected, so will have to try random puzzles
• This will take an eavesdropper on average roughly \(m/2 \cdot 2^{n}\) decryptions
• For example, when \(m \approx 2^n\), that is the square of the amount of work Bob had to do

New directions (1976)

Diffie-Hellman(-Merkle) key exchange

• Suppose Alice wants to agree on a shared secret over a public channel
• First Alice and Bob agree publicly on a group \(G\) and a generator \(g\)
• Alice generates a random number \(r_A\) and sends Bob \[ R_A = g^{r_A} \]
• Similarly, Bob generates a random number \(r_B\) and sends Alice \[ R_B = g^{r_B} \]
• Now, Alice and Bob can both compute \[s = g^{r_Ar_B} = R_A^{r_B} = R_B^{r_A}\]
• An eavesdropper sees only \(g_{r_A}\) and \(g_{r_B}\), best known method for an eavesdropper to construct \(s\) is to solve the discrete logarithm: recovering \(x\) from \(g^x\)
• In the original paper \(G = \mathbb{F}_p^*\) for a prime \(p\)

RSA (1977)

Vanilla RSA explained

• Suppose Alice wants to send a message \(m\) only Bob can read
• First Bob will generate two large primes \(p,q\) and computes the product \(N = pq\)
• Bob also generates a number \(e\) that has no divisors in common with both \(p-1\) and \(q-1\)
• Finally, Bob computes (via Chinese remainder theorem) \(d\) such that \[ ed = 1 \ ( \text{mod} \ (p-1)(q-1))\]
• Bob sends the pair \((N,e)\) to Alice and keeps \(d\) secret
• Alice sends Bob the ciphertext \(c\) with \[ c = m^e \ (\text{mod} \ N)\]
• Bob can recover \(m\) from \(c\) since basic number theory gives \[c^d = m^{ed} = m \ ( \text{mod} \ N)\]
• Best known method to recover \(m\) from just \(c\) is to first recover \(d \ \) by factoring \(N\).

RSA signatures

• Suppose Bob wants to sign a message \(m\) with his secret key \(d\) corresponding with his public key \((N,e)\)
• With a cryptographic hash function \(H\)), the message \(m\) is digested to \(h = H(m)\)
• Bob computes the signature \(s\) over \(m\) as \[ s = h^d \ (\text{mod} \ N)\]
• To verify the signature, anyone can recover \(h\) from \(s\) since \[s^e = h^{ed} = h \ ( \text{mod} \ N)\] and verify \(H(m) = h\)
• If the hash verifies, \(s\) can only have been constructed by Bob, since he is the only one knowing \(d\)

Taher Elgamal

• Student at Stanford of Martin Hellman in early 80s
• Basically made DH protocol non-interactive (1985)
• Elgamal encryption and digital signature scheme
• Digital signature scheme basis for (EC)DSA
• In the 90s, Elgamal (then at Netscape) was one of the drivers behind development of SSL

Elgamal hybrid encryption scheme

• Suppose Alice wants to send a message \(m\) only Bob can read
• First Alice and Bob will agree on group \(G\) with generator \(g\)
• Bob generates a secret key \(s_B\) and publishes the public key \(p_B = g^{s_B}\)
• Alice generates a random ephemeral key \(r_A\) and computes the message key \[k = p_B^{r_A} = g^{s_Br_A}\]
• Finally, Alice sends Bob the pair \((g^{r_A}, E_k(m))\) with \(E\) a symmetric encryption algorithm
• Bob can recompute \(k\) as \[ (g_{r_A})^{s_B} = g^{r_As_B} = k\] and decrypt \(E_k(m)\) to recover \(m\)
• In the original paper \(G = \mathbb{F}_p^*\) for a prime \(p\) and \(E: (k,m) \to k \cdot m \in G\)

Elgamal signature scheme

• Let \(H\) be a cryptographic hash function, \(p\) a large prime and a \(g\) generator of \(\mathbb{F}_p^*\)
• Suppose Bob wants to sign a message \(m\) with his secret key \(s_B\), with \(p_B = g^{s_B}\) his public key
• First, the message \(m\) is digested to \(h = H(m)\)
• Bob generates a random number \(k\) and computes \(r = g^k\)
• The signature then consists of the pair \((r,s)\) with \[s = \frac{h - r \cdot s_B}{k} \ \ \text{mod} \ (p-1)\]
• To verify the signature \((r,s)\) on \(m\) one computes \(h = H(m)\) and verfies that \[ g^h = p_B^r \cdot r^s \]
• This works since \[ p_B^r \cdot r^s = g^{rs_B} \cdot g^{ks} = g^{rs_B} \cdot g^{h - r \cdot s_B} = g^h \]