Public-Key Cryptography

For much of history, cryptography was concerned with encoding/decoding systems devised in *private* with the aim of their operation remaining obscure to the public. There are plenty of fascinating stories from this classical era--cracking of the Enigma machine, for one. However, the need for establishing such systems over *public* infrastructure became increasingly apparent in the second half of the 20th century. Public-key cryptography emerged in the 1970s to address this need, with its defining feature being the key pair. Broadly speaking, a key pair consists of public data and private data which form an encoding/decoding system in tandem. This eliminates the need for prior knowledge of the system as well as providing a novel method for authentication. First theorized by Diffie and Hellman as a strategy for key exchange, actual implementations of public-key crytography (RSA, ElGamal) soon followed. Surprisingly, the security of these cryptosystems relies only on some key ideas from elementary number theory, which will form the basis of this talk. If time permits, elliptic curve DH and the "post-quantum" NTRU cryptosystem will also be discussed.