Objectives
-
Distinguish between symmetric key and public key crypto systems.
-
Apply the Diffie-Hellman key exchange to exchange secrets.
-
Apply the ElGamal crypto system to the encryption and decryption of text.
Chapter 16 Public Key Cryptography
Opinions on internet privacy
The philosopher: Two women stand talking to each other. Woman 1: "Privacy" is an impractical way to think about data in a digital world so unlike the one in which our soci- Woman 2: SO BORED.
The crypto nut: A figure stands behind another sitting at a desk, who is working a computer. Sitting figure: My data is safe behind six layers of symmetric and public-key algorithms. Standing figure: What data is it? Sitting figure: Mostly me emailing with people about cryptography.
The conspiricist: A figure stands talking to a woman. Figure: These leaks are just the tip of the iceberg. There’s a warehouse in Utah where the NSA has the *entire* iceberg. I don’t know how they got it there.
The nihilist: A woman stands, addressing the ’camera’. Woman: Joke’s on them. Gathering all this data on me as if anything I do means anything.
The exhibitionist: Two official-looking figures are looking at a console. One is sitting; another is standing behind the chair. Console screen: Mmmm, I sure hope the NSA isn’t watching me bite into these juicy strawberries!! Oops, I dropped some on my shirt! Better take it off. Google, are you there? Google, this lotion feels soooo good. Operator: Um.
The sage: Beret guy is sitting with a friend at a restaurant table. Beret guy: I don’t know or care what data *anyone* has about me. Data is imaginary. This burrito is real.
Title text: I’m the Philosopher until someone hands me a burrito.
I’m the Philosopher until someone hands me a burrito.
https://xkcd.com/1269)We bring concepts from all chapters of the course together in the presentation of public key crypto systems. These concepts are
-
Chapter 1 Integers and Algorithm:.The operation \(\fmod\text{,}\) the Euclidean algorithm, and Bézout’s identity for finding inverse in the group \((\Z_p^\otimes,\otimes)\text{.}\)
-
Chapter 2 Sets and Functions:.The encoding function \(C\) for converting text into a sequence of numbers.
-
Chapter 3 Numbers and Counting:.Prime numbers, binary numbers needed for fast exponentiation, and the representation of text by numbers.
-
Chapter 4 Groups:.The groups \((\Z_p^\otimes,\otimes)\text{,}\) (fast) exponentiation, and the discrete logarithm needed to attack the crypto systems.
In particular we present the Diffie-Hellman key exchange and the ElGamal crypto system, which are both widely used in practice. The Diffie-Hellman key exchange is used to initiate secure connections such as the secure communication between web browser and web server. ElGamal is applied in the encryption of email and other forms a secure communication.
