TABLE OF CONTENTS 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 invention 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).
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...
