Public-Key Cryptography - A Classical Introduction to Cryptography: Applications for Communications Security - page 224

9
Public-Key Cryptography

Content

Diffie-Hellman: asymmetric cryptography, the DH key agreement protocol

Knapsack problems: NP-completeness, the Merkle-Hellman cryptosystem
RSA: the cryptosystem, attacks against particular implementations
ElGamal Encryption

Interestingly, cryptography was the first application of computer science: after
Alan Turing created the notion of Turing machine, the very first computer was built
in order to break real-life cryptosystems for military purposes. Similarly, the in-
vention of complexity theory—in particular the notion of intractability through NP-
completeness—has been directly applied to cryptography in order to invent asymmetric
cryptography , also called public-key cryptography .

This chapter relates to the early foundations of asymmetric cryptography, and
modern applications (and attacks).

9.1 Diffie-Hellman

Invention of public-key cryptography is often attributed to Whitfield Diffie and Martin
Hellman: in a famous paper (Ref. [59]) which was published in the IEEE Transactions
on Information Theory journal in 1976, they gave “new directions in cryptography,”
describing how we can use one-way functions , and notions of trapdoor permutations in
cryptography. A public-key cryptosystem is nothing but a kind of one-way permutation
(anybody can encrypt, but cannot decrypt) with a hidden trapdoor which enables the
decryption to the legitimate party.

Although this seminal paper played an outstanding role in the area of cryptography,
the role of Ralph Merkle in the foundations should not be neglected. Merkle submitted
his scheme in 1975 1 (discussed in p. 115) which enables the secure communication
over an insecure channel. The Merkle Signature Scheme based on hash trees was also
made in the late seventies 2 . The Lamport scheme which is given on p. 111 (published
in 1979; see Ref. [113]) also illustrates how to make an asymmetric access control
protocol from a one-way function.

1

But it was published in 1978 only! See Ref. [129].

2

But it was rejected for publication, and then published 10 years later. See Ref. [131].