Cryptography 1 Week 6.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": "true"
   },
   "source": [
    "# Table of Contents\n",
    " <p><div class=\"lev1 toc-item\"><a href=\"#Summary\" data-toc-modified-id=\"Summary-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Summary</a></div><div class=\"lev1 toc-item\"><a href=\"#Public-key-encryption-scheme\" data-toc-modified-id=\"Public-key-encryption-scheme-2\"><span class=\"toc-item-num\">2&nbsp;&nbsp;</span>Public key encryption scheme</a></div><div class=\"lev2 toc-item\"><a href=\"#Applications\" data-toc-modified-id=\"Applications-21\"><span class=\"toc-item-num\">2.1&nbsp;&nbsp;</span>Applications</a></div><div class=\"lev1 toc-item\"><a href=\"#Definition-of-Public-Key-Encryption\" data-toc-modified-id=\"Definition-of-Public-Key-Encryption-3\"><span class=\"toc-item-num\">3&nbsp;&nbsp;</span>Definition of Public Key Encryption</a></div><div class=\"lev2 toc-item\"><a href=\"#Security:-Eavesdropping\" data-toc-modified-id=\"Security:-Eavesdropping-31\"><span class=\"toc-item-num\">3.1&nbsp;&nbsp;</span>Security: Eavesdropping</a></div><div class=\"lev2 toc-item\"><a href=\"#Security:-Active-Attacks\" data-toc-modified-id=\"Security:-Active-Attacks-32\"><span class=\"toc-item-num\">3.2&nbsp;&nbsp;</span>Security: Active Attacks</a></div><div class=\"lev2 toc-item\"><a href=\"#Chosen-ciphertext-security:-definition\" data-toc-modified-id=\"Chosen-ciphertext-security:-definition-33\"><span class=\"toc-item-num\">3.3&nbsp;&nbsp;</span>Chosen ciphertext security: definition</a></div><div class=\"lev1 toc-item\"><a href=\"#Public-Key-Constructions-(Public-key-Encryptions-from-trap-door-permutations)\" data-toc-modified-id=\"Public-Key-Constructions-(Public-key-Encryptions-from-trap-door-permutations)-4\"><span class=\"toc-item-num\">4&nbsp;&nbsp;</span>Public Key Constructions (Public key Encryptions from trap door permutations)</a></div><div class=\"lev3 toc-item\"><a href=\"#Goal-:-Construct-chosen-ciphertext-secure-public-key-encryption\" data-toc-modified-id=\"Goal-:-Construct-chosen-ciphertext-secure-public-key-encryption-401\"><span class=\"toc-item-num\">4.0.1&nbsp;&nbsp;</span>Goal : Construct chosen ciphertext secure public-key encryption</a></div><div class=\"lev2 toc-item\"><a href=\"#Secure-Trapdoor-Functions-(TDF)\" data-toc-modified-id=\"Secure-Trapdoor-Functions-(TDF)-41\"><span class=\"toc-item-num\">4.1&nbsp;&nbsp;</span>Secure Trapdoor Functions (TDF)</a></div><div class=\"lev2 toc-item\"><a href=\"#Public-Key-Encryption-from-Trapdoor-Functions\" data-toc-modified-id=\"Public-Key-Encryption-from-Trapdoor-Functions-42\"><span class=\"toc-item-num\">4.2&nbsp;&nbsp;</span>Public Key Encryption from Trapdoor Functions</a></div><div class=\"lev1 toc-item\"><a href=\"#Trapdoor-Functions-:-RSA\" data-toc-modified-id=\"Trapdoor-Functions-:-RSA-5\"><span class=\"toc-item-num\">5&nbsp;&nbsp;</span>Trapdoor Functions : RSA</a></div><div class=\"lev2 toc-item\"><a href=\"#Review-Trapdoor-Functions\" data-toc-modified-id=\"Review-Trapdoor-Functions-51\"><span class=\"toc-item-num\">5.1&nbsp;&nbsp;</span>Review Trapdoor Functions</a></div><div class=\"lev2 toc-item\"><a href=\"#Review-Arithmetic-mod-composites\" data-toc-modified-id=\"Review-Arithmetic-mod-composites-52\"><span class=\"toc-item-num\">5.2&nbsp;&nbsp;</span>Review Arithmetic mod composites</a></div><div class=\"lev1 toc-item\"><a href=\"#The-RSA-Trapdoor-Permutation\" data-toc-modified-id=\"The-RSA-Trapdoor-Permutation-6\"><span class=\"toc-item-num\">6&nbsp;&nbsp;</span>The RSA Trapdoor Permutation</a></div><div class=\"lev2 toc-item\"><a href=\"#RSA-Assumption\" data-toc-modified-id=\"RSA-Assumption-61\"><span class=\"toc-item-num\">6.1&nbsp;&nbsp;</span>RSA Assumption</a></div><div class=\"lev1 toc-item\"><a href=\"#Review-(ISO-Standard)\" data-toc-modified-id=\"Review-(ISO-Standard)-7\"><span class=\"toc-item-num\">7&nbsp;&nbsp;</span>Review (ISO Standard)</a></div><div class=\"lev2 toc-item\"><a href=\"#How-not-to-use-RSA-(RSA-Text-book-Encryption)\" data-toc-modified-id=\"How-not-to-use-RSA-(RSA-Text-book-Encryption)-71\"><span class=\"toc-item-num\">7.1&nbsp;&nbsp;</span>How not to use RSA (RSA Text book Encryption)</a></div><div class=\"lev2 toc-item\"><a href=\"#Real-World-Example--A-simple-attack-on-textbook-RSA\" data-toc-modified-id=\"Real-World-Example--A-simple-attack-on-textbook-RSA-72\"><span class=\"toc-item-num\">7.2&nbsp;&nbsp;</span>Real World Example  A simple attack on textbook RSA</a></div><div class=\"lev1 toc-item\"><a href=\"#PKCS-v-1.5-RSA\" data-toc-modified-id=\"PKCS-v-1.5-RSA-8\"><span class=\"toc-item-num\">8&nbsp;&nbsp;</span>PKCS v 1.5 RSA</a></div><div class=\"lev2 toc-item\"><a href=\"#PKCS1-v1.5-mode-2(encryption)\" data-toc-modified-id=\"PKCS1-v1.5-mode-2(encryption)-81\"><span class=\"toc-item-num\">8.1&nbsp;&nbsp;</span>PKCS1 v1.5 mode 2(encryption)</a></div><div class=\"lev2 toc-item\"><a href=\"#Attack-on-PKCS1-v1.5\" data-toc-modified-id=\"Attack-on-PKCS1-v1.5-82\"><span class=\"toc-item-num\">8.2&nbsp;&nbsp;</span>Attack on PKCS1 v1.5</a></div><div class=\"lev2 toc-item\"><a href=\"#PKCS1-v2.0:-OAEP\" data-toc-modified-id=\"PKCS1-v2.0:-OAEP-83\"><span class=\"toc-item-num\">8.3&nbsp;&nbsp;</span>PKCS1 v2.0: OAEP</a></div><div class=\"lev2 toc-item\"><a href=\"#RSA-in-Practice\" data-toc-modified-id=\"RSA-in-Practice-84\"><span class=\"toc-item-num\">8.4&nbsp;&nbsp;</span>RSA in Practice</a></div><div class=\"lev1 toc-item\"><a href=\"#PKCS-:-Diffie-Hellman(ElGamal)\" data-toc-modified-id=\"PKCS-:-Diffie-Hellman(ElGamal)-9\"><span class=\"toc-item-num\">9&nbsp;&nbsp;</span>PKCS : Diffie-Hellman(ElGamal)</a></div><div class=\"lev3 toc-item\"><a href=\"#Review-PKCS\" data-toc-modified-id=\"Review-PKCS-901\"><span class=\"toc-item-num\">9.0.1&nbsp;&nbsp;</span>Review PKCS</a></div><div class=\"lev2 toc-item\"><a href=\"#Review-Application\" data-toc-modified-id=\"Review-Application-91\"><span class=\"toc-item-num\">9.1&nbsp;&nbsp;</span>Review Application</a></div><div class=\"lev3 toc-item\"><a href=\"#Secure-Email\" data-toc-modified-id=\"Secure-Email-911\"><span class=\"toc-item-num\">9.1.1&nbsp;&nbsp;</span>Secure Email</a></div><div class=\"lev3 toc-item\"><a href=\"#Encrypted-File-Systems\" data-toc-modified-id=\"Encrypted-File-Systems-912\"><span class=\"toc-item-num\">9.1.2&nbsp;&nbsp;</span>Encrypted File Systems</a></div><div class=\"lev3 toc-item\"><a href=\"#Encryption\" data-toc-modified-id=\"Encryption-913\"><span class=\"toc-item-num\">9.1.3&nbsp;&nbsp;</span>Encryption</a></div><div class=\"lev3 toc-item\"><a href=\"#Key-Escrow-Service-in-Organizations\" data-toc-modified-id=\"Key-Escrow-Service-in-Organizations-914\"><span class=\"toc-item-num\">9.1.4&nbsp;&nbsp;</span>Key Escrow Service in Organizations</a></div><div class=\"lev3 toc-item\"><a href=\"#Constructions\" data-toc-modified-id=\"Constructions-915\"><span class=\"toc-item-num\">9.1.5&nbsp;&nbsp;</span>Constructions</a></div><div class=\"lev1 toc-item\"><a href=\"#Review--Diffie-Hellman-Protocol\" data-toc-modified-id=\"Review--Diffie-Hellman-Protocol-10\"><span class=\"toc-item-num\">10&nbsp;&nbsp;</span>Review  Diffie-Hellman Protocol</a></div><div class=\"lev2 toc-item\"><a href=\"#Converting-Diffie-Hellman-protocol-to-actual-Public--key-encryption\" data-toc-modified-id=\"Converting-Diffie-Hellman-protocol-to-actual-Public--key-encryption-101\"><span class=\"toc-item-num\">10.1&nbsp;&nbsp;</span>Converting Diffie-Hellman protocol to actual Public -key encryption</a></div><div class=\"lev2 toc-item\"><a href=\"#ElGamal-Performance\" data-toc-modified-id=\"ElGamal-Performance-102\"><span class=\"toc-item-num\">10.2&nbsp;&nbsp;</span>ElGamal Performance</a></div><div class=\"lev2 toc-item\"><a href=\"#ElGamal-Security\" data-toc-modified-id=\"ElGamal-Security-103\"><span class=\"toc-item-num\">10.3&nbsp;&nbsp;</span>ElGamal Security</a></div><div class=\"lev2 toc-item\"><a href=\"#ElGamal-is-semantically-secure-under-the-Hash-Diffie-Hellman\" data-toc-modified-id=\"ElGamal-is-semantically-secure-under-the-Hash-Diffie-Hellman-104\"><span class=\"toc-item-num\">10.4&nbsp;&nbsp;</span>ElGamal is semantically secure under the Hash Diffie-Hellman</a></div><div class=\"lev2 toc-item\"><a href=\"#ElGamal-Chosen-Ciphertext-Security\" data-toc-modified-id=\"ElGamal-Chosen-Ciphertext-Security-105\"><span class=\"toc-item-num\">10.5&nbsp;&nbsp;</span>ElGamal Chosen Ciphertext Security</a></div><div class=\"lev2 toc-item\"><a href=\"#ElGamal-Review\" data-toc-modified-id=\"ElGamal-Review-106\"><span class=\"toc-item-num\">10.6&nbsp;&nbsp;</span>ElGamal Review</a></div><div class=\"lev1 toc-item\"><a href=\"#A-Unifying-Theme\" data-toc-modified-id=\"A-Unifying-Theme-11\"><span class=\"toc-item-num\">11&nbsp;&nbsp;</span>A Unifying Theme</a></div><div class=\"lev2 toc-item\"><a href=\"#One-Way-Functions\" data-toc-modified-id=\"One-Way-Functions-111\"><span class=\"toc-item-num\">11.1&nbsp;&nbsp;</span>One-Way Functions</a></div><div class=\"lev2 toc-item\"><a href=\"#Example-of-One-Way-Function\" data-toc-modified-id=\"Example-of-One-Way-Function-112\"><span class=\"toc-item-num\">11.2&nbsp;&nbsp;</span>Example of One-Way Function</a></div><div class=\"lev2 toc-item\"><a href=\"#Discrete-Log-One-way-function\" data-toc-modified-id=\"Discrete-Log-One-way-function-113\"><span class=\"toc-item-num\">11.3&nbsp;&nbsp;</span>Discrete Log One way function</a></div><div class=\"lev2 toc-item\"><a href=\"#RSA-One-Way-Function\" data-toc-modified-id=\"RSA-One-Way-Function-114\"><span class=\"toc-item-num\">11.4&nbsp;&nbsp;</span>RSA One Way Function</a></div><div class=\"lev1 toc-item\"><a href=\"#Summary\" data-toc-modified-id=\"Summary-12\"><span class=\"toc-item-num\">12&nbsp;&nbsp;</span>Summary</a></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 1.16.26.png\"/>\n",
    "* This brings us to the end of the six weeks course. I had a lot of fun teaching this course and I hope you enjoyed it too. I really love this material and I always enjoy teaching it. Before we say our farewells, please do a quick review of the topics that we discussed and see what's left to cover. \n",
    "    * So here's a brief diagram of the primitive that we discussed in the class.\n",
    "    * If you remember in week one we started off by discussing pseudorandom generators and stream ciphers.\n",
    "    * In week two we talked about block ciphers and we said that the right way to think about block cipher is as pseudorandom permutations and pseudorandom functions. We said that using counter mode we can convert a block cipher into a PRG. And we said that using the GGM construction. We can construct block ciphers from pseudorandom generators. \n",
    "    * Then in week three, we talked about data integrity. In particular, we talked about MACs and we looked at various constructions of MACs from pseudorandom functions like the CMAC, the HMAC, the PMAC constructions and so on. \n",
    "        * We also discussed collision resistance and we said that collision resistance can be used for data integrity where one has access to read-only memory. \n",
    "        * Basically, you would hash the data using a collision resistance hash function; write the hash into read-only memory. And then later, when you want to verify authenticity of your data, you just compare its hash to whatever is written in read-only memory. \n",
    "    * Then in week 4 we talked about how to combine integrity and confidentiality, in particular we kinda talk about to combine encryption and MACs to build what we called Authenticated Encryption and I told you that really in practice, the only foremost Symmetric Encryption that you're allowed to use is Authenticated Encryption. \n",
    "        * Basically, encryption that's only secure against eavesdropping attacks is not generally secure, you must always also guard against tampering and as a result, you should only be using Authenticated Encryption modes to do Symmetric Encryption. So that was the end of week four. \n",
    "    * And then for weeks five and six, we switched topics and talked about key exchange and public key encryption. \n",
    "        * In particular, in week five we talked about Trapdoor Functions and the Diffie-Hellman Protocol the Mathematics that are necessary to explain how those things work. \n",
    "        * And then in week six we talked about how public key encryption can be built from trapdoor functions and, the Diffie-Hellman Protocol. I wanna emphasize that the key exchange protocols that we saw in week five are only secure against eavesdropping and should never be used in practice. \n",
    "        * In fact in week eight we're gonna see authenticated key exchange protocols and those are the ones that are actually used in the wild for example in SSL and other protocols like that. \n",
    "        * But, the ones that we saw in week five should never actually be deployed in the real world. The only reason we looked at those simple key exchange mechanisms was as motivation for trapdoor functions and Diffie-Hellman groups. \n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 1.22.47.png\"/>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Public key encryption scheme\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.15.37.png\" width=700 height=700/>\n",
    "\n",
    "* So let me remind you that in a public key encryption scheme, \n",
    "    * There is an **encryption** algorithm which is usually denoted by **E**, and there's a **decryption** algorithm which we denote by **D**.\n",
    "    * However here, the encryption algorithm takes a **public key**(pk), while the decryption algorithm takes a **secret key**(sk). This pair is called a **key pair**. \n",
    "    * And the public key is used for encrypting messages while the secret key is used for decrypting messages. So in this case a **message m** is encrypting using the public key and what comes out of that is the **ciphertext c**. \n",
    "    * And similarly the ciphertext is fed into the decryption algorithm and using the secret key, what comes out of the decryption algorithm is the original message m.\n",
    "    \n",
    "## Applications \n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.25.42.png\" width=700 height=700/>\n",
    "\n",
    "* Now public key encryption has many applications.\n",
    "* Last week we saw the classic application which is **session setup**, namely, **key exchange** and for now we're just looking at key exchange that is secure against **eavesdropping** only. \n",
    "* And if you remember the way the protocol works \n",
    "    * Basically Alice, what she would do is she would generate a **public key secret pair.**\n",
    "    * She would send the public key to Bob. \n",
    "    * Bob will **generate a random X**, which is gonna serve as their **shared secret**, and then he sends **X encrypted** to Alice, encrypted under her **public key**. Alice can decrypt, recover X and now both of them have this shared secret X which they can use to communicate securely with one another. \n",
    "    * The attacker, of course, all he gets to see is just the public key, the encryption of X under the public key, from which he should not be able to get any information about X. \n",
    "* **For example,** it's very useful in **non-interactive applications**. So think of an **email system** for example. So here, Bob wants to send mail to Alice, and as Bob sends the email, the email passes from mail relay to mail relay until finally it reaches Alice, at which point Alice should decrypt. The way the email system is set up, is designed for kind of non-interactive settings where Bob sends the email. And then Alice is supposed to receive it. And Alice should not be to communicate with Bob in order to decrypt the email. So in this case, because of the non-interactivity, there's no opportunity for setting up a shared secret between Alice and Bob. So in this case, what would happen is, Bob basically would, would send the email encrypted, using Alice's, public key. So he sends the email. Anyone in the world can send the email encrypted to Alice, encrypted using her public key. When Alice receives this email, she uses her secret key to decrypt the ciphertext and recover the plain text message. Of course the one caveat(limitations/warnings) in a system like this is that in fact Bob needs to somehow obtain Alice's public key So for now we are just going to assume Bob already has Alice's public key, but later on, actually, when we talk about digital signatures we're gonna see how, this can actually be done very efficiently using what's called public key management and as I said we'll actually get back to that at a later time. But the main thing I want you to remember, is that public key encryption is used for session setup. This is very common on the web, where public key encryption is used to set up a secure key between a web browser and, and web server. And public key encryption is also very useful for non-interactive applications, where anyone in the world, non-interactively, needs to send a message to Alice, they can encrypt the message using Alice's public key, and Alice can decrypt and recover the plain text.\n",
    "\n",
    "# Definition of Public Key Encryption\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.29.19.png\"  width=700 height=700/>\n",
    "\n",
    "\n",
    "* So let me remind you in a bit more detail what a public key encryption system is.\n",
    "    * Well, it's made up of **three algorithms G, E, and D**. **G** is called the **key generation algorithm**. \n",
    "    * Basically what it will do is it will generate this key pair, the public key and the secret key. As written here, G takes no arguments, but in real life, G actually does take an argument called the **security parameter** which specifies the size of the keys that are generated by this key generation algorithm.\n",
    "    * Then there are these E **encryption algorithms** as usual that take a public key and a message and produce a ciphertext in a D **decryption algorithm** that takes the corresponding secret key and a ciphertext and it produces a corresponding message. And as usual for consistency we say that if we encrypt a message under a given public key and then decrypt with a corresponding secret key we should get the original message back.\n",
    "\n",
    "## Security: Eavesdropping\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.37.22.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So the way to define security against eavesdropping is very similar to the symmetric case we've already this last week so we're gonna go through this quickly just as a review. \n",
    "* Basically the attack game is defined as follows. We defined these two experiments, experiment zero and experiment one. \n",
    "* At in either experiment the challenger is gonna generate a public and a secret key pair. He's gonna give the public key to the adversary. The adversary's gonna output two messages m0 and m1 of equal length and then what he gets back is either the encryption of m0 or the encryption of m1. \n",
    "* In experiment zero he gets the encryption of m0. In experiment one he gets the encryption of m1. And then the adversary is supposed to say which one did he get. Did he get the encryption of m0 or did he get the encryption of m1? So in this game, the attacker only gets one ciphertext. \n",
    "* This corresponds to an eavesdropping attack where he simply eavesdropped on that ciphertext C. And now his goal is to tell whether the ciphertext C i s the encryption of M0 or M1. No tampering on the ciphertext C is allowed just yet. And as usual we say that the public key encryption scheme is semantically secure if the attacker cannot distinguish experiment zero from experiment one. In other words he cannot tell whether he got the encryption of M0, or the encryption of M1.\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.44.35.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* If you remember, when we talked about eavesdropping security for symmetric ciphers, we distinguished between the case where the key is used once, and the case where the key is used multiple times. And, in fact we saw that, there's a clear separation. For example, the onetime pad. Is secure if the key is used to encrypt a single message, but is completely insecure if the key is used to encrypt multiple messages. And in fact we had two different definitions if you remember we had a definition for one-time security, and then we had a separate definition, which was stronger, when the key was used multiple times. The definition that I showed you on the previous slide's very similar to the definition of one time security for symmetric ciphers. And in fact, it turns out that for public key encryption, if a system is secure under a onetime key, in a sense, it's also secure for a many time key. So in other words, we don't have to explicitly give the attacker the ability to, request encryptions of messages of his choice. Because he could just create those encryptions all by himself. He is given the public key, and therefore he can by himself encrypt any message he likes. As a result any public key secret pair in some sense inherently is used to encrypt multiple messages because the attacker could have just encrypted many, many messages of his choice using the given public key that we just gave him in the first step. And so, as a result in fact, the definition of one time security is enough to imply many time security and that's why we refer to the concept as indistinguishability under a chosen plain text attach. So this is just a minor point to explain why the settings of public encryption, we don't need a more complicated definition to capture eavesdropping security. \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "## Security: Active Attacks\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.52.08.png\" width=700 height=700/>\n",
    "\n",
    "* So, in particular, let's look at the email example. So here, we have our friend Bob who wants to send mail to his friend Caroline. And Caroline happens to have, an account at Gmail. \n",
    "* And the way this works is basically, the email is sent to the Gmail server, encrypted. \n",
    "* The Gmail server decrypts the email, looks at the, intended recipients. And then, if it's, the intended recipient is Caroline, it forwards the email to Caroline. If the intended recipient is the attacker, it forwards the email to the attacker. This is similar to how Gmail actually works because the sender would send the email encrypted over SSL to the Gmail server. \n",
    "* The Gmail server would terminate the SSL and then forward the email to the appropriate recipients. **Now suppose Bob encrypts the email using a system that allows the adversary to tamper with the ciphertext without being detected.** * For example, imagine this email is encrypted using Counter Mode, or something like that. Then when the attacker intercepts this email, he can change the recipient, so that now the recipient says attacker@gmail.com, and we know that for Counter Mode, for example, this is quite easy to do. The attacker knows that the email is intended for Caroline, he is just interested in the email body. So he can easily change the email recipient to attacker@gmail.com and now when the server receives the email, he will decrypt it, see that the recipient is supposed to be attacker, and forward the body to the attacker. And now the attacker was able to read the body of the email that was intended for Caroline. So this is a classic example of an active attack, and you notice what the attacker could do here, is it could decrypt any ciphertext where the intended recipient is to: attacker. So any ciphertext where the plain text begins with the words \"to: attacker\". So our goal is to design public key systems that are secure, even if the attacker can tamper with ciphertext and possibly decrypt certain cyphertexts. And again, I want to emphasize that here the attacker's goal was to get the message body. The attacker already knew that the email is intended for Caroline\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 14.57.51.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "* So let me explain how the attack and as I said our goal is to build systems that are secure under this very, very conservative notion of encryption. \n",
    "* So we have an encryption scheme (G, E, D). And let's say that's defined over a message space and a ciphertext (M, C) and as usual we're gonna define two experiments, experiment zero, and experiment one. \n",
    "* So 'b' here says whether the challenger is implementing experiment zero or experiment one. \n",
    "    * The challenger begins by generating a public key and a secret key, and then gives the public key to the adversary. \n",
    "    * Now the adversary can say, \"Well, here are a bunch of ciphertexts, please decrypt them for me.\" So here the adversary submits ciphertext C1 and he gets the decryption of ciphertext C1, namely M1. \n",
    "    * And he gets to do this again and again, so he submits ciphertext C2, and he gets the decryption, which is M2, ciphertext C3, and he gets the decryption M3, and so on and so forth. \n",
    "    * Finally, the adversary says, \"This squaring phase is over,\" and now he submits basically two equal length messages, M0 and M1 as normal, and he receives in response the challenge ciphertext C, Which is the encryption of M zero or the encryption of M one. \n",
    "    * Depending on whether we're in experiment zero or experiment one. Now, the adversary can continue to issue these ciphertext queries. So he can continue to issue, decryption requests.\n",
    "    * So he submits a ciphertext, and he gets a decryption of that ciphertext, but of course, now, there has to be a caveat. **If the attacker could submit arbitrary ciphertext of his choice, of course, he could break the challenge.** \n",
    "    * What he would do is he would submit the challenge ciphertext C as a decryption query. And then he would be told whether in the challenge phase he was given the encryption of M0 or the encryption of M1. \n",
    "        * As a result we put this **limitation** here, that says that he can in fact submit any ciphertext of his choice except,  **For the challenge ciphertext.**\n",
    "    * So the attacker could ask for the decryption of any ciphertext of his choice other than the challenge ciphertext. And even though he was given all these decryptions, he still shouldn't be able to tell whether he was given the encryption of M0 or the encryption of M1. \n",
    "    * So you notice this is a very conservative definition. It gives the attacker more power than what we saw in the previous slide.\n",
    "\n",
    "\n",
    "\n",
    "## Chosen ciphertext security: definition\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 15.07.04.png\" width=700 height=700/>\n",
    "\n",
    "* And then his goal is to say whether the challenge ciphertext is the encryption of M0 or the encryption of M1. And as usual, if he can't do that, in other words, his behavior in experiment zero is basically the same as his behavior in experiment one, so he wasn't able to distinguish the encryption of M0 from the encryption of M1, even though he had all this power Then we say that the system is chosen ciphertext secure, CCA secure. And sometimes there is an acronym, the acronym for this is indistinguishability under a chosen ciphertext attack, but I'm just gonna say CCA secured. So let's see how this captures, the email example we saw before. So suppose the encryption system being used is such that just given the encryption of a message the attacker can change the intended recipient from to Alice say to, to Charlie. Then here's how we would win the CCA game. Well in the first step he's given the public key of course. And then what the attacker will do is he would issue two equal length messages, namely in the first message, the body is zero. In the second message the body is one. But both messages are intended for Alice. And in response, he would be given the challenge ciphertext C. Okay, so now here we have our challenge ciphertext C. Now what the attacker is gonna do is he's gonna use his, his ability here to modify the intended recipient. And he's gonna send back a ciphertext C', where C' is the encryption of the message to Charlie with body being the challenge body b. So if you remember is either zero or one. Now, because the plain text is different, we know that the ciphertext must also be different. So in particular, C prime must be different from the challenge ciphertext C, yeah? So the C prime here must be different from C. And as a result, the poor challenger now has to decrypt by definition of the CCA game. The challenger must decrypt any ciphertext that's not equal to a challenge ciphertext. So the challenger decrypts give the adversary M prime. Basically he gave the adversary B, and now the adversary can output the challenge B and he wins the game with advantage one. So he's advantage with this particular scheme is one. So, simply because the attacker was able to change the challenge ciphertext from one recipient to another that allows him to, to win the CCA game with advantage one. So as I said, chosen ciphertext security turns out actually is the correct notion of security for public key encryption systems. And it's a very, very interesting concept, right? Basically, somehow even though the attacker has this ability to decrypt anything he wants. Other than the challenge ciphertext, still he can't learn what the challenge ciphertext is. \n",
    "\n",
    "\n",
    "# Public Key Constructions (Public key Encryptions from trap door permutations)\n",
    "\n",
    "### Goal : Construct chosen ciphertext secure public-key encryption\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 16.07.31.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* And in this segment, we're gonna start by constructing public key encryptions from, a concept called a trapdoor permutation. \n",
    "* So let's start by defining a general concept called a trapdoor function. \n",
    "    * So what is a trapdoor function? Well, a trapdoor function basically is a function that goes from some set X to some set Y. \n",
    "    * And it's really defined by a **triple** of algorithms.There's a **generation algorithm**, the **function f**(f), and the **inverse of the function f**(-f). \n",
    "    * So the generation algorithm, basically what it does when you run it, it will generate a key pair, a public key and a secret key.\n",
    "        * The public key is gonna define a specific function from the set X to the set Y. \n",
    "        * And then the secret key is going to define the inverse function now from the set Y to the set X. \n",
    "        * So the idea is that you can evaluate the function at any point using a **public key PK and then you can invert that function using the secret key, SK**\n",
    "    *  So what do I mean by inversion? \n",
    "        * More precisely, if we look at any public key and secret key pair generated by the key generation algorithm G, then it so happens that if I evaluate the function at the point X, and then I evaluate the inverse at the resulting point, I should get the original point X back.\n",
    "        * So the picture you should have in your mind, is there is this big set X and this big set Y And then, this function will map any point in X to a point in Y, and this can be done using the public key. \n",
    "        * So again any point in X can be mapped, to a point in Y. And then if someone has the secret key, then basically they can go in the reverse direction by applying, this secret key sk\n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "## Secure Trapdoor Functions (TDF)\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 16.17.43.png\" width=700 height=700/>\n",
    "\n",
    "* So now that we understand what a trapdoor function is, let's define what it means for a trapdoor function to be secure.\n",
    "* And so we'll say that this triple, (G, F, F inverse), is secure if in fact this function F(PK, .) is what's called a one way function. And let me explain what a, what is a one way function. \n",
    "* The idea is that basically the function can be evaluated at any point, but inverting it is difficult without the secret key SK. So let's define that more precisely. \n",
    "* As usual we define that using a game. So here we have our game between the challenger and the adversary. And the game proceeds as follows. Basically the challenger will generate a public key and a secret key. \n",
    "* And then they will generate a random X. It will send the public key over to the adversary and then it will evaluate the function at the point X and send the resulting Y also to the adversary. \n",
    "* So all the adversary gets to see is just a public key, which defines what the function is, and then he gets to see the image of this function on a random point X and is goal is basically to invert the function at this point Y. Okay, so he outputs some X prime. \n",
    "    * And we said that the trap door function is secure if the probability that the ad, adversary inverts the given at point y is negligible. \n",
    "    * In other words, given y the probability that the adversary's able to alter the pre image of y is in fact a negligible probability and if that's true for all efficient algorithms then we say that this trapdor function is secure.\n",
    "    \n",
    "## Public Key Encryption from Trapdoor Functions\n",
    "<img  src=\"Screen Shot 2017-01-30 at 16.22.31.png\" width=700 height=700/> \n",
    "\n",
    "\n",
    "* So here we have we our trap door function, (G, F, and F inverse). The other tool that we are going to need is a symmetric encryption scheme, and I'm going to assume that this encryption scheme is actually secure against active attacks, so in particular I needed to provide authenticated encryption. \n",
    "* Notice that the symmetric encryption system takes keys in K and the trapdoor function takes inputs in X. Those are two different sets and so we're also gonna need the hash function. That goes from X to K. In other words, it maps elements in the set X into keys for the symmetric encryption systems. \n",
    "* And now once we have these three components, we can actually construct the public key encryption system as follows: * so the key generation for the public key encryption system is basically exactly the same as the key generation for the trap door function. \n",
    "    * So we run G for the trap door function, we get a public key and a secret key. And those are gonna be the public and secret keys for the public key encryption system. \n",
    "    * And how do we encrypt and decrypt? Let's start with encryption. \n",
    "        * So the encryption algorithm takes a public key and a message as input. So what it will do is it will generate a random X from the set capital X. It will then apply the trapdoor function to this random X, to obtain Y. So Y is the image of X under the trapdoor function.\n",
    "        * Then it will go ahead and generate a symmetric key by hashing X. So this is a symmetric key for the symmetric key system. And then finally it encrypts the plain text message 'm' using this key that was just generated. And then it outputs the value Y that it just computed, which is the image of X, along the encryption under the symmetric system of the message M. So that's how encryption works. And I want to emphasize again that the trapdoor function is only applied to this random value X, whereas the message itself is encrypted using a symmetric key system using a key that was derived from the value X that we chose at random. So now that we understand encryption, \n",
    "    * Let's see how to decrypt. \n",
    "        * While the decryption algorithm takes a secret key as input, and the ciphertext. The ciphertext itself contains two components, the value Y and the value C. So the first step we're gonna do, is we're gonna apply the inverse transformation, the inverse trap door function to the value Y, and that will give us back the original X that was chosen during encryption. So now let me ask you, how do we derive the symmetric decryption key K from this X that we just obtained? Well, so that's an easy question. We basically hash X again. That gives us K just as during encryption. And now that we have this symmetric encryption key we can apply the, the symmetric decryption algorithm to decrypt the ciphertext C. We get the original message M and that's what we output. \n",
    "        \n",
    "        \n",
    "    \n",
    "<img  src=\"Screen Shot 2017-01-30 at 16.34.17.png\" width=700 height=700/>    \n",
    "    \n",
    "    \n",
    "* So in pictures here, we have the message M obviously the plain text could be quite large. So, here we have the body of the deciphered text which can be quite long is actually encrypted using the symmetric system. And then again I emphasize that the key for the symmetric system is simply the hash of X. And then the header of ciphertext is simply this application of the trapdoor function to this random X that we picked. And so during decryption what happens is we first decrypt the header to get X and then we decrypt the body using the symmetric system to actually get the original plain text M. So as usual when I show you a system like this, obviously you want to verify that decryption in fact is the inverse of encryption. But more importantly you want to ask why is this system secure. And in fact there's a nice security theorem here that says. That if the trap door function that we started with is secure. In other words, that's a one way function if the adversary doesn't have a secret key. The symmetric encryption system provides authenticated encryption. And the hash function is a random oracle, which simply means that it's a random function from the set X to the set of keys K. So a random oracle is some sort of an idealization of, what a hash function is supposed to be. In practice, of course, when you come to implement a system like this, you would just use, SHA-256, or any of the other hash functions that we discussed in class.\n",
    "* So, under those three conditions in fact the system that we just described is chosen cipher text secure so it is CCA secure, the little ro here just denote the fact that security is set in whats called a random oracle model. But, that's a detail that's actually not so important for discussion here, \n",
    "    * what I want you to remember is that if the trap door function is in fact a secure trap door function. The symmetric encryption system is secure against tampering so it provides authenticated encryption. And H is in some sense a good hash function. It's a random, function, which in practice you would just use SHA-256, then in fact the system that we just showed is CCA secure, is chosen ciphertext secure. I should tell you that there's actually an ISO standard that, defines this mode of encryption, of public encryption.\n",
    "    \n",
    "    <img  src=\"Screen Shot 2017-01-30 at 16.37.26.png\" width=700 height=700/>\n",
    "    \n",
    "* To conclude this segment, I want to warn you about an incorrect way of using a trapdoor function to build a public key encryption system. And in fact this method might be the first thing that comes to mind, and yet it's completely insecure. So let me show you, how not to encrypt using a trapdoor function. Well the first thing that might come to mind is, well, let's apply the trapdoor function directly to the message M. So we encrypt simply by applying a function to the message M, and we decrypt simply by applying F inverse to the ciphertext C to recover the original message M. So functionally, this is in fact, decryption is the inverse of encryption, and yet this is completely insecure for many, many different reasons. The easiest way to see that this is insecure, is that it's simply, this is deterministic encryption. You notice there is no randomness being used here. When we encrypt a message M, and since it is deterministic, it's cannot possibly be semantically secure. But in fact, as I said, when we instantiate this trap door function with particular implementations, for example with the RSA trap door function, then there are many, many attacks that are possible on this particular construction, and so you should never, ever, ever use it, and I'm gonna repeat this throughout this module, and in fact in the next segment I'll show you a number of attacks on this particular implementation. \n",
    "* Okay so, what I would like you to remember is that you should be using an encryption system like the ISO standard, and you should never apply the trap door function directly to the message M. Although in the next segment we'll see other ways to encrypt using a trap door function that are also correct, but this particular method is clearly, clearly incorrect.\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# Trapdoor Functions : RSA \n",
    "\n",
    "\n",
    "## Review Trapdoor Functions\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.06.11.png\"width=700 height=700/>\n",
    "\n",
    "* So recall that a trapdoor function is made up of three algorithms. \n",
    "* There is a key generation algorithm, the function itself, and the inverse of the function. The key generation algorithm outputs a public key and a secret key.\n",
    "* And in this case, in this lecture the public key is going to define a function that maps the set X onto itself. \n",
    "* Which is why I call these things trapdoor permutations, as opposed to trapdoor functions, simply because the function maps X onto itself, whereas a trapdoor function might map the set X to some arbitrary set Y. \n",
    "* Now given the public key, the function, as we say, basically defines this function from the set X to the set X. \n",
    "* And then given the secret key, we can invert this function. So this function F evaluates the function in the forward direction, and this function F inverse, which means the secret key SK, computes F in the reverse direction. \n",
    "* Now we say that the trapdoor permutation is secure if the function defined by the public key is in fact a one-way function, which means that it's easy to evaluate, but without the trapdoor, the secret trapdoor, it's difficult to invert.\n",
    "\n",
    "\n",
    "## Review Arithmetic mod composites\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.03.15.png\"width=700 height=700/>\n",
    "\n",
    "\n",
    "* Before we look at our first example of a trapdoor permutation, I want to do a quick review of some necessary arithmetic facts that we're gonna need. And in particular, let's look at some arithmetic facts modulo composites. \n",
    "    * So here we have our modulus N, which happens to be a product of two primes, and you should be thinking of P and Q as roughly equal size numbers, since particular P and Q are both roughly on the size of square root of N.\n",
    "    * So both are roughly the same size. Recall that we denoted by ZN the set of integers from zero to N minus one, and we said that we can do addition and multiplication module N. \n",
    "    * We denoted by ZN star the set of invertible elements in ZN. So these are all the elements, which have a modular inverse. And we said that actually X is invertible if and only if it's relatively prime to N. \n",
    "    * Moreover, I also told you that the number of invertible elements in ZN star is denoted by this function phi(N). So phi(N) is the number of invertible elements in ZN star, And I told you that when N is a product of two distinct primes, then in fact phi(N) is equal to (P - 1) times (Q - 1) and if you extend that out, you see that this is really equal to (N - P - Q + 1). \n",
    "    * Now remember that I said that P and Q are on the order of square root of N which means that P + Q is also on the order of square root of N. Which means that really phi(N) is on the order of N minus two square root of N. \n",
    "    * So, in other words, it's very, very close to N. Basically, subtracting the square root of N from a number, this is from, N is going to be a huge number in our case, like 600 digits. \n",
    "    * And so subtracting from a 600 digit number, the square root of that 600 digit number, namely a 300 digit number, hardly affects the size of the number. Which means that phi(N) is really, really, really close to N, and I want you to remember that, because we will actually be using this now and again. \n",
    "    * And so the fact that phi(N) is really close to N, means that if we choose a random element modulo N It's very, very, very likely to be in ZN star. So it's very unlikely that by choosing a random element in ZN, we will end up choosing an element that is not invertable. \n",
    "    * Okay. So just remember that, that in fact almost all elements in ZN are actually invertible. And the last thing that we'll need is Euler's theorem, which we covered last week, which basically says that for any element X in ZN star, if I raise X to the power of phi(N), I get one, in ZN. So in other words, I get 1 modulo N. I'll say it one more time because this is gonna be critical to what's coming. Again X to the phi(N) is equal to 1 modulo N. So now that we have the necessary background we can actually describe the RSA trapdoor permutation.\n",
    "    \n",
    "    \n",
    "* This is a classic, classic, classic construction in cryptography that was first published in Scientific American back in 1977, this is a very well known article in cryptography. And ever since then, this was 35 years ago, the RSA trapdoor permutation has been used extensively in cryptographic applications.\n",
    "\n",
    "# The RSA Trapdoor Permutation\n",
    "\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.26.58.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* **The Key Generation algorithm**\n",
    "\n",
    "\n",
    "* So now we're ready to describe the RSA trapdoor permutation.\n",
    "* To do that, I have to describe the key generation algorithm, the function ƒ and the function ƒ−1.\n",
    "* So let's see. So the way the key generation algorithm works is as follows: \n",
    "    * What we do is we generate two primes, P and Q, each would be, say on the order of 1000 bits, so, you know, roughly 300 digits, \n",
    "        * The RSA modulus is simply going to be the product of those two primes.\n",
    "    * The next thing we do is we pick two exponents, e and d, such that e times d is 1 modulo phi(N). \n",
    "        * What this means is that e and d first of all are relatively prime to phi(N) and second of all they're actually modular inverses of one another, modulo phi(N). \n",
    "    * And then we output the public key as the pair N,e and the secret key is the secret key N,d. \n",
    "    * I should mention that the exponent e, that the number e is sometimes called the encryption exponent and the exponent d is sometimes called the decryption exponent.\n",
    "    \n",
    "* **The Functions of F and the Inverse of F-1**\n",
    "\n",
    "* For simplicity I'm gonna define it as the function from ZN star to ZN star. And the way the function is defined is simply given an input X, all we do is we simply take X and raise it to the power of e in ZN. So we just compute X to the e, modulo N. That's it. And then to decrypt, what we do is we simply, given an input Y, we simply raise Y to the power of d, modulo N. And that's it. So now you can see why as I refer to e and d as exponents. They're the things that X and Y are being raised to. So let's quickly verify that F inverse really does invert the function F. So let's see what happens when we compute Y to the d. So suppose Y itself happens to be the RSA function of some value X. In which case, what Y to the d is, is really RSA of X to the power of d. While X by itself is simply gonna be X to the e modulo N, And therefore, Y to the d is simply X to the e times d modulo N. Again, just using rules of exponentiation, the exponents multiply, so we get X to the e times d. But what do we know about e times d? e times d we said is one modulo phi(N). And what that means is there exists some integer such that e times d is equal to K times phi(N) plus one. This is what it means that e times d is one modulo phi(N). So, we can simply replace e times d by K times phi(N)+1. So, that's what I wrote here. So, we have X to the power of K times phi(N)+1. But now again just using rules of exponentiation, we can re-write this as X to the power of phi(N) to the power of K times X. This is really the same thing as K times phi(N)+1 as the exponent. I just kind of separated the exponent into it's different components. Now, X to the phi(N) by Euler's theorem, we know that X to the phi(N) is equal to one. So what is this whole product equal to? Well since X to the phi(N) is equal to one, one to the K is also equal to one, so this whole thing over here is simply equal to one. And what we're left with is X. So what we just proved is that if I take the output of the RSA function and raise it to the power of 'd', I get back X. Which means that raising to the power of 'd' basically inverts the RSA function, which is what we wanted to show. So that's it, that's the whole description of the function, we've described the key generation. The function itself, which is simply raising things to the power of e modulo N, and the inversion function which is simply raising things to the power of d, also modulo N.\n",
    "\n",
    "## RSA Assumption\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.29.04.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So this assumption is called the RSA assumption. It basically states that RSA is a one way permutation just given the public . And therefore, it is a trapdoor permutation because it has a trapdoor. And makes this easy to invert for anyone who knows the trap door. So now that we have a secure trap door permutation, we can simply plug that into our construction for public key encryption, and get our first real world public key encryption system. And so what we'll do is we'll simply plug the, the RSA trapdoor permutation into the iso standard construction that we saw in the previous segment\n",
    "\n",
    "# Review (ISO Standard) \n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.31.38.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So, if you recall, that construction was based on a symmetric encryption system that had to provide authenticated encryption. And it was also based on a hash function. Then mapped while transferring it into the world of RSA, it maps elements in ZN, into secret keys for the symmetric key system. And now the way the encryption scheme works is really easy to describe. Basically algorithm G just runs the RSA key generation algorithm and produces a public key and a secret key. Just as before. So you notice the public key contains the encryption exponent and the, secret key contains the decryption exponent. And the way we encrypt is as follows. Well, we're going to choose a random X in ZN. We're going to apply the RSA function to this X, we're going to deduce a symmetric key from this X by hashing it, so we compute H of X to obtain the key K, and then we output this Y along with the encryption of the message under the symmetric key K. And in practice, the hash function H would be just implemented just using SHA-256, and you would use the output of SHA-256 to generate a symmetric key that could then be used for the symmetric encryption assistant. So that's how we would encrypt and then the way we would decrypt is pretty much as we saw in the previous segment, where the first thing we would do is we would use the secret key to invert the header of the ciphertext. So we would compute RSA invert of Y, that would give us the value X. Then we would apply the hash function to X so that this would give us the key K. And then we would run the decryption algorithm for the symmetric system on the ciphertext and that would produce the original message m. And then we stated a theorem in the previous segment to say that if the RSA trapdoor permutation is secure, Es and Ds, the symmetric encryption scheme  provides authenticated encryption. And as we said, H is just random oracle. It's, you know, kind of a random function from ZN to the key space. Then, in fact, this system is chosen cipher text secure, and is a good public key system to use. So now that we have our first example of a good public key system to use, I wanna quickly warn you about how not to use RSA for encryption.\n",
    "\n",
    "## How not to use RSA (RSA Text book Encryption)\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.37.51.png\"width=700 height=700 />\n",
    "\n",
    "\n",
    "* So I'd like to call this, textbook RSA. Which basically is the first thing that comes to mind when you think about encrypting using RSA, namely, the secret key and the public key will be as before. But now instead of running through, a hash function to generate a symmetric key, what we would do is we would directly use RSA to encrypt the given message M. And then we would directly use the decryption exponent to decrypt the cipher text and obtain the plain text M. I'm going to call this textbook RSA, because there are many textbooks that describe RSA encryption in this way. And this is completely wrong. This is not how RSA encryption works. It's an insecure system. In particular, it's deterministic encryption, and so it can't possibly be semantically secure, but in fact there are many attacks exist that I'm going to show you an attack in just a minute, but the message that I want to make clear here, is that RSA, all it is, is a trap door permutation. By itself it's not an encryption system. You have to embellish it with this ISO standard for example, to make it into an encryption system. By itself, all it is, is just a function. So let's see what goes wrong if you try to use textbook RSA, In other words, if you try to encrypt a message using RSA directly. \n",
    "\n",
    "## Real World Example  A simple attack on textbook RSA\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 17.45.35.png\" width=700 height=700/>\n",
    "* I'm going to call this textbook RSA, because there are many textbooks that describe RSA encryption in this way. And this is completely wrong. This is not how RSA encryption works. It's an insecure system. In particular, it's deterministic encryption, and so it can't possibly be semantically secure, but in fact there are many attacks exist that I'm going to show you an attack in just a minute, but the message that I want to make clear here, is that RSA, all it is, is a trap door permutation. By itself it's not an encryption system. You have to embellish it with this ISO standard for example, to make it into an encryption system. By itself, all it is, is just a function. So let's see what goes wrong if you try to use textbook RSA, In other words, if you try to encrypt a message using RSA directly. And I'll give you an example attack from the world of the web. So imagine we have a web server. The web server has an RSA secret key. Here's it's denoted by N and D. And here we have a web browser who's trying to establish a secure session, a secure SSL session, with the web server. So the way SSL works is that the web browser starts off by sending this client hello message saying, hey, I want to set up a secure session with you. The web server responds with a server hello message that contains the server's public key And then the web browser will go ahead and generate a random what's called a premaster secret K, it will encrypt the premaster secret using K and send the result in ciphertext over to the web server. The web server will decrypt and then the web server will also get K, so now the two have a shared key that they can use to then secure a session between them. So I want to show you what goes wrong if we directly use the RSA function for encrypting K. In other words, if directly K is encrypted as K to the e modulo N. Just for the sake of argument let's suppose that K is a 64-bit key. We're going to treat K as an integer in the range as zero to 2 to the 64. More precisely two to the 64 minus one, and now what we're going to do is the following. First of all, suppose it so happens that K factors into a product of roughly equal sized numbers. So K we can write as K1 times K2, where K1 and K2 are integers. And both are say less than two to the 34. So, it turns out this happens with probability roughly twenty percent so one in five times K can actually be written in this way. But, now if we plug this K, K=K1 x K2 if we plug that into the equation that defines the cipher text you see that we can simply substitute K by K1 x k2 and then we can move k1 to the other side. So then we end up with this equation here, namely C over K1 to the e is equal to K2 to the e. You notice if I multiply both sides by K1 to the e, I get that C is equal to K1 times K2 to the e, which is precisely this equation here. Okay, so all I did is I just replaced K by K1 times K2 and then divided by K1 to the e. So by now this should look familiar to you. So now we have two variables in this equation, of course. C is known to the attacker, E is known to the attacker, and N is known to the attacker. The two variables in this equation are K1 and K2, and we've separated them into a different side of the equation, and as a result we can do now a meet in the middle attack on this equation. So let's do the meet in the middle attack. What we would do is we would build a table of all possible values Of the left-hand side. So all possible values of C over K1 to the E, there are 2 to the 34 of them. And then, for all possible values on the right-hand side, for all possible values of K2 to the e, we're gonna check whether this value here lives in the table that we constructed in step one. And if it is then we found a collision, and basically we have a solution to this equation. So as soon as we find an element of the form K2 to the E that lives in the table that we built in step one, we've solved this equation and we found K1 and K2. And of course once we found K1 and K2, we can easily recover K simply by multiplying them. So then we multiply K1 and K2 and we get, the secret key K. Okay? So, we've broken, basically, this, this encryption system. And how long did it take? Well, by brute force, we could have broken it in time 2 to the 64, simply by trying all possible keys. But this attack, you notice, it took 2 to the 34 time for step number one. Well, it took a little bit more than 2 to the 34, 'cause we had to do these exponentiations. It took 2 to the 34 time for step two against slightly more than two to the 34 because of the exponentiations. So let's say that the whole algorithm took time two to the 40. The point is that this is much, much less time due to the 64. So here you have an example. Where if you encrypt using RSA directly, in other words you directly compute, K to the E, mod N, instead of going through the ISO standard, for example, then you get an attack that runs much faster than exhaustive search. You get an attack that runs in time two to the 40, rather than time two to the 64. Okay, so this is a cute example of how things can break if you use the RSA trapdoor permutation directly to encrypt a message. So the message to remember here, is never, ever, ever use RSA directly to encrypt. You have to use to go through an encryption mechanism. For example, like the ISO standard. And in fact, in the next segment we are going to see other ways of using RSA to build public key encryption. \n",
    "\n",
    "# PKCS v 1.5 RSA \n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 19.24.32.png\" width=700 height=700/>\n",
    "\n",
    "* In this segment I wanna show you how RSA is used in practice and in particular, I wanna tell you about a standard called a Public Key Cryptography standard number one PKCS one.\n",
    "* So I've already told you a couple of times that you should never use what's called textbook RSA. You should never directly encrypt the message using RSA because that's insecure. \n",
    "* You always have to do something to the message before you actually apply the RSA function. \n",
    "* We saw the ISO standard in the previous segment where what we did is we generated a random x, encrypted x using RSA, and then from this x we derived a symmetric encryption key. \n",
    "* But that's actually not how RSA is used in practice. \n",
    "    * In practice things worked a little differently and typically what happens is the system generates a symmetric encryption key and then RSA is asked to encrypt the given symmetric encryption key rather than generating the symmetric key as part of . \n",
    "    * So in practice as I say, what happens the RSA system is given this input a **symmetric encryption key** to encrypt for example this could be a, such as an **AES** key that would be like **128 bits** and then the way this key is actually encrypted is first we take these 128 bits and we expand them into the full modulo size. \n",
    "    * For example, this would be 2048 bits, and then we apply the RSA function. \n",
    "    * And so the question is, how should this preprocessing be done? How should we expand the 128 bit AES key that was given to us into a 2048 bit value that can then be applied with RSA. \n",
    "    \n",
    "## PKCS1 v1.5 mode 2(encryption)\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 19.34.35.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So I wanna show you how this mechanism works and in particular, I'll show you what's called PKCS1 Mode 2.\n",
    "* Mode 2 denotes encryption, mode 1 denotes signatures so here we're gonna just focus on the encryption. \n",
    "    * So the way PKCS1 works is as follows, you take your message, this would be the **128 bit AES key for example**, and you put it as a least significant bit of the value that you're creating. \n",
    "    * The next thing you do is you append sixteen bits of one to it, you know .(FF) This is sixteen bits of one.\n",
    "    * And then the next you do is you append the random pad that actually does not contain FF anywhere inside the random pad. \n",
    "    * So this is basically something like on the order of what is it, 1900 random bits except that there are on FF's inside those random bits and finally at the very top, you put the number 02.\n",
    "    * This indicates that this plain text has been encoded using PKCS1 mode 2. And then this whole value here, this whole thing that we just created. This is just 2048 bit string is the thing that gets fed into the RSA function and is raised to the power of e modulo N. And the resulting thing is PKCS1 ciphertext.\n",
    "* Now the decrypter of course is going to invert the RSA function, He's gonna get back this block, \n",
    "    * He's gonna look at the most significant bits and he's gonna say there's a 02 in there that means that this PKCS one formatted. \n",
    "    * Since it's PKCS one formatted, it's gonna remove those 02. It's gonna remove all the random pad up until the FF.\n",
    "    * And then anything that stays beyond that is the original message which is then used you know to say decrypt the actual body of the ciphertext. And as I said, this mechanism is extremely widely deployed, For example, it's used in HTTPS.\n",
    "    \n",
    "    \n",
    "## Attack on PKCS1 v1.5\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 19.41.30.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So let's see how the attack works. So the idea is this, supposed the attacker intercepted a certain ciphertext so this is PKCS1 ciphertext so the point is it's encoded using PKCS1 and then the result is fed into the RSA function. And we call the ciphertext the output of the RSA function. The attacker wants to basically decrypt the ciphertext, So let me show you abstractly what the attacker is gonna do. We're gonna just simplify SSL and just say that the attacker can basically send the ciphertext directly to the web server. The web server is gonna try and decrypt the ciphertext using its secret key. And then what is it gonna do? Well, the first thing it does after the encryption, well, it's gonna ask: is the decryption of the ciphertext PKCS1 encoded? In other words, it's gonna look at the most significant bits and ask: is this 02 in the most significant positions? If they are, it's gonna continue properly decrypting and then continue with the protocol and if there is no 02 in those positions, it's gonna announce an error. So if the most significant bits of the plaintext are 02, it's gonna continue with the protocol as expected, if the most significant bits are not 02 is gonna send back an error message and tell the attacker, hey, you sent in invalid ciphertext. Now the amazing thing is that, this lets the attacker test whether the sixteen most significant bits of the decryption of the given ciphertext are 02 or not. In other words, the attacker can submit whatever ciphertext he wants to the web server. The web server will invert the RSA function and then tell the attacker whether the inversion started with 02 or not. So in some sense gives the attacker an oracle that lets him test whether the inversion of any ciphertext begins with 02 or not. And it turns out that's actually enough to completely decrypt any ciphertext the attacker wants, Just add little bit of information leakage just by properties of RSA lest the attacker completely decrypt a given ciphertext. Also here's what the attacker is gonna do, well, he has a ciphertext that he wants to decrypt so what he'll do is he'll take a cyphertext and of course feed that directly into the web server and ask does it begin with the 02 or not. The next thing he's gonna do is he's gonna chose a random value r and he's gonna build a new ciphertext c prime. Which is (r to the e) c modulo N. Now what does that do? If we pull the r into the RSA function, really what we just did is we multiply the RSA plaintext, you know the PKCS1 including in m, we multiply that by r and that, that whole thing gets raised to the power of e. Okay. So that's the effect of multiplying c by (r to the e). It multiplies the plaintext by r, a value that the attacker controls. And then he's gonna send c prime to the web server and the web server is gonna say yes, this starts with 02 or no, this doesn't start with 02.\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 19.47.34.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "## PKCS1 v2.0: OAEP  \n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 20.00.22.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* And that brings us to a different way of doing encryption using RSA which is called **Optimal Asymmetric Encryption Padding**, OAEP. And in fact the PKCS standard was updated and PKCS1 version 2.0 actually has support for OAEP which is a better way of doing RSA encryption. \n",
    "* So let me explain how OAEP works. So OAEP is due to the Bellare and Rogaway back in 1994. \n",
    "* And the way OAEP works is as follows. \n",
    "    * So you take your message that you wanna encrypt this for example could be the 128 bits AES key. \n",
    "    * And then the first thing you do is you append a short pad to it. So in this case, you put a 01 in the beginning and then you add a whole bunch of zeroes. How many zeroes is actually depends on the standard but you know that's supposed like they're 128 zeroes in here. \n",
    "    * And then you also choose a random value so that this whole string is as big as your RSA modulus so let's just say this is 2047 bits. \n",
    "    * Now before you apply the RSA function, you first of all take the random value that you chose and you feed it into the hash function. \n",
    "    * This hash function produces a value that's as big as the left hand side of your encoding. You XOR the outputs. You feed the result into another hash function which we call a g. \n",
    "    * You XOR that with a random value. And then finally, you get these two values that you concatenate together. \n",
    "    * Okay, So, you concatenate either left side and the right side that gives you something that says is 2047 bits long and that's the thing that you apply the RSA function to. And the result is the RSA encryption. \n",
    "    * Now there's a theory that was proved in 2001, due to Fujisaki, Okamoto, Pointcheval, and Stern, that shows that in fact if all you do is you, you assume that the RSA function is a Trapdoor permutation, a secure Trapdoor permut ation, but in fact this mode of encrypting using RSA is in fact chosen ciphertext secure but we have to assume that the functions h and g are kind of ideal hash functions as I said these are called random oracles. \n",
    "    * Basically, we assume that h and g are just random functions from their domains to their range. \n",
    "        *  In practice of course when OAEP is implemented, people just use SHA-256 say for h and g. \n",
    "        \n",
    "<img  src=\"Screen Shot 2017-01-30 at 20.03.17.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* **even though we have a reduction from taking square roots to factoring, e equals 2 cannot be used as an RSA exponent. So, really the smallest RSA exponent that is legal is in fact e equals 3. But, for e equal 3, the question of whether computing cube roots is as hard as factoring, is an open problem. It's actually a lot of fun to think about this question**\n",
    "* But as I said, as far as we know, RSA is a one way function. In fact, breaking RSA, computing e'th roots that is, actually requires factoring the modulus. We all believe that's true, and that's the state of the art. But, now there has been a lot of work on trying to improve the performance of RSA. Either, RSA encryption or improve the performance of RSA decryption.\n",
    "\n",
    "## RSA in Practice\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 20.51.59.png\" width=700 height=700/>\n",
    "\n",
    "* The last attack I want to talk about is a very recent observation that was observed by Heninger et al and Lenstra et al that shows that RSA key generation can be problematic when it's done with bad entropy. So here's how things go wrong. So the way open SSL generates RSA keys is as follows. Well, it starts by basically seeding the pseudo random number generator. And then it uses random bits from a pseudo random number generator to generate the first prime p. Then it will go ahead and seed the random number generator some more, and will generate bits from the pseudo random number generator to generate q. And finally, it will output the product of p and q. Okay so the two steps, where we see the seed the pseudo random number generator. Now suppose that this is implemented on a router or a firewall of some sort, and suppose that the key generation happens right after the firewall starts up. So the firewall boots up. At the time of the boot, there's not a lot of entropy in the pseudo random number generator, and as a result the firewall is likely to generate a prime p that comes from a very low entropy pool. Which means that this p is gonna be one of a small number of possibilities. However, after we've generated p, generating the prime actually takes a little bit of time, a few microseconds. And so, by then the firewall will have generated more entropy and so after we add more entropy to the entropy pool, the prime q say is generated from a much larger entropy pool and is therefore unique to this firewall. Now the problem is that many different firewalls if they generate an RSA key in this way many of them will actually end up using the same prime p but a different prime q. So what this says is that if we look at two RSA moduli from two different firewalls, N1 and N2. If we compute the GCD of N1 and N2, well both of them had different q's but the same p. So if we compute the GCD, actually we will end up with a factorization of N, of both N1 and N2 and then we can actually figure out the private key both for N1 and for N2. So this has actually been observed in practice. Both of these groups, what they did is they scanned the web and recovered all of the public keys out there that are used on various web servers. They then ran a massive GCD, using some arithmetic tricks they were able to compute this massive GCD of all pairs of public keys N1 and N2. And lo and behold, they actually realized that a fair number of these keys have a common factor. So they were actually able to factor these moduli. So in the experiment, they were actually able to factor about .4% of all public SSL keys. This is an amazing fact, that, in fact, so many web server public keys out there are vulnerable just because they happened to generate the RSA key using low entropy. So they have a common factor with somebody else's factor and GCDing the two together gives you the factorization. So, the lesson from all this is when you generate keys, no matter whether they are RSA keys or ElGamal keys or symmetric keys, it's crucial that the number--, that your generator is properly seeded. So don't generate keys immediately after start up. You have to kind of make sure the seeding of the generator has had enough time to actually generate enough entropy. And only then you can start generating keys. So this is a really nice example of how a, a bad random number generator can mess up your RSA public keys.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# PKCS : Diffie-Hellman(ElGamal)\n",
    "\n",
    "\n",
    "### Review PKCS\n",
    "\n",
    "* So, first recall that a public key encryption system is made up of three algorithms. There is a key generation algorithm that I will denote by Gen, that basically generates a public key and a secret key. And then there are two algorithms: E and D that encrypt and decrypt. And the point is the encryption algorithm encrypts using the public key and the decryption algorithm decrypts using the secret key. The physical world analogy for public key encryption is a locked box, where anyone can put a message inside the box and then lock the box, that corresponds to the public key and then no one can open this box, except the person who has the secret key, that has the key can put it in the lock, unlock the box and the recover the message in the box. \n",
    "\n",
    "## Review Application\n",
    "<img  src=\"Screen Shot 2017-01-30 at 23.12.53.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* Now, in the previous lecture, we looked at a number of applications for public key encryption. In particular, we looked at the key exchange application, in fact, this is how public key encryption is used in SSL, where the server sends its public key to the browser, the browser chooses a secret and then encrypts the secret using the server's public key, sends it back to the server, the server decrypts and now both the browser and the server have a common secret that they can then use to encrypt data, going back and forth, between them. \n",
    "\n",
    "### Secure Email\n",
    "\n",
    "* So, in the interactive settings, such as in a networking protocol, public key encryption would primarily be used for setting up shared symmetric key which the two parties can then use to exchange information. However, there are many settings where interaction is simply not possible and then public key encryption is directly used to encrypt messages. One example of this is secure email. The email system in some sense is designed to be non- interactive, in the sense that the sender sends an email, the email travels from relay to relay, to relay, until it finally arrives at the destination and the destination should be able to decrypt, without interacting with the sender at that point. That can be done basically, by the sender encrypting the message using the recipient's public key. The ciphertext would travel along the SMTP chain until it reaches the recipient. The recipient would use a secret key and recover the original sent message. \n",
    "\n",
    "### Encrypted File Systems\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 23.30.06.png\" width=700 height=700/>\n",
    "\n",
    "### Encryption\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 23.30.26.png\" width=700 height=700/>\n",
    "* However, there are many other cases where interaction is not possible and I want to show you two such cases. The first example is file systems. And in fact, public key encryption is a good way to manage file sharing, in an encrypted file system. So, let me show you what I mean by that. So, imagine we have our friend Bob here, who wants to store\n",
    " an encrypted file on some storage server. So, he will go ahead and write the encrypted file to the storage server. What he actually writes in the server is basically the following: he will generate a random file encryption key, we will call it 'K sub F' and then he will use the symmetric encryption system to encrypt the file using the key 'K sub F'. Then, he will encrypt the key 'K sub F', using his own public key. So public key of Bob. This will give Bob access to the file at a later time, right. Using his secret key, Bob can decrypt this header, recover 'K sub F'. Then he will decrypt the actual encrypted file and recover the plaintext file. So, decryption will work in two steps. However, Bob now wants also to give access to Alice, to this file. What he will do is, he will go ahead and in addition he will also include in the file header, an encyption of 'K sub F' under Alice's public key. OK. So, notice that there was no interaction here. All that Bob knows is Alice's public key and yet he was able to the make the file accesible to Alice at a later time. So, now Bob disappears and then Alice comes and accesses the disk at a later time. She will read the ciphertext, decrypt her part of the header, recover Kf and then she can decrypt the symmetrically encrypted file and recover the actual file contents. Ok, so you can see that without any interaction, Bob was able to write to the file system and enable Alice to access the file, as well. Again, at the time that Alice was reading the file, there is no interaction with Bob, because maybe Bob is already inaccesible and yet Alice can still read the file recovered by hersel.\n",
    " \n",
    " \n",
    "### Key Escrow Service in Organizations\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 23.34.23.png\" width=700 height=700/>\n",
    "\n",
    "* So, another example of a non-interactive application of public key encryption is what's called key escrow. Now, key escrow may actually sound like a bad thing but in fact it is a mandatory feature in corporate environments. So, the idea here is this. So imagine Bob writes data to a disk and then later Bob becomes inaccesible. Maybe Bob is fired. Maybe Bob is out sick. And somehow the company needs to have access to Bob's files. So having Bob be the only one able to decrypt these files is simply unacceptable in corporate settings. The corporation might need access to those files. So, the question is what to do. And the answer is to introduce this entity called a key escrow service. The way the system then would work is as follows: Basically, when Bob writes his file to disk, his system, as it's writing the file to this shared storage medium, what it would do of course, as before, it would encrypt the file using the file encryption key Kf. It would encrypt Kf using Bob's public key, but it would also encrypt Kf using an escrow service. So here, the escrow service is completely offline. We never talk to it unless we actually need its services. As Bob is writing the file, all he does is he simply writes the encryption of Kf under the escrow authority's public key into the file header. Now, later Bob disappears and now the company needs to recover Bob's file. What does it do? Well, at this point it would contact the escrow service. The escrow service would read this part of the header, use its secret key to decrypt the header and recover Kf and then use Kf to decrypt the actual file. Ok. So, in this way again you notice that the escrow service was completely offline. There was no interaction with the escrow service until the point at which the escrow services were actually needed. And again, you can see that this is a very clean and elegant application of public key encryption\n",
    "\n",
    "\n",
    "### Constructions\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 23.44.18.png\" width=700 height=700/>\n",
    "\n",
    "* we saw constructions for public key encryption based on trapdoor functions. In particular, we look at RSA. We looked at the generic construction we called ISO standard. We looked at constructions like OAEP+ and so on and so forth. In this lecture, we are going to look at public key constructions from the Diffie-Hellman protocol. This is another family of public key systems and I am going to show you how they work. These public key systems are generally called ElGamal public key encryption schemes. Taher ElGamal was actually Marty Hellman's student. He came up with this ElGamal encryption system as part of his PhD thesis. And, in fact, ElGamal encryption, for historical reasons, is used in an email encryption system called GPG, the GNU Privacy Guard. As usual, when we construct public key encryption systems, our goal is to build systems that have chosen ciphertext security, so that they are secure both against eavesdropping and tampering attacks. \n",
    "\n",
    "# Review  Diffie-Hellman Protocol\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-30 at 23.51.04.png\" width=700 height=700/>\n",
    "\n",
    "* So, before I show you the ElGamal system let's do a very brief review of the Diffie-Hellman protocol. So, in my description here, I am going to abstract a little bit from the version that we saw last week. In fact, I just going to use the concept of a finite cyclic group. In fact, we have an arbitrary finite cyclic group, for example, it could be the group (Zp) star, but it could also be the points of an elliptic curve. **And as I mentioned, there are some benefits to doing Diffie-Hellman over an elliptic curve.** But, for simplicity, I am just going to refer to G as an abstract finite cyclic group, but in your heads you should be thinking G is the group (Zp) and let's suppose that the group has order n for some integer n. Now, we are going to fix a generator g of this group and all this means, is basically, if you look at the successive powers of g, that basically you get all the elements in the group G. You notice, because the group has order n, we know that g to the power of n is equal to 1. And, therefore there is no reason to go beyond the n-1st power of g. g to the n is equal to 1 so that we just wrap around. Ok.\n",
    "\n",
    "*  So, we have this cyclic group G. We have this generator whose powers gave us all the elements of G, and now let me remind you how the Diffie-Hellman protocol works.\n",
    "    * Basically, what Alice does is she chooses a random a. She computes g to the a and sends it over to Bob. Bob chooses a random b.\n",
    "    * So, Bob sends over to Alice g to the b and of course I should remind you that both g to the a and g to the b are just elements in this group G. \n",
    "    * Now, they can derive the shared secret, If you remember, the shared secret is g to the ab, and these equalities here shows that both sides can actually compute the shared secret given the values at their disposal.\n",
    "    * So, Alice for example, has B and she has a, and so raising B to the power of a, gives her the shared secret. The attacker, of course, the poor attacker he gets to see A and B and his goal is now, of course, he also gets to see the generated g, and his goal now is to compute g to the ab. \n",
    "    * But, we said that this is believed to be a hard problem. Given g, g to the a, and g to the b, in a group like Zp, computing g to the ab is difficult.\n",
    "    \n",
    "## Converting Diffie-Hellman protocol to actual Public -key encryption\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-31 at 0.04.53.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So, now let's see how to convert to the Diffie-Hellman protocol into an actual public key system. As I said, this was a brilliant idea due to Taher ElGamal. \n",
    "    * So, as before, we are going to fix our cyclic group G and a generator g inside of G. \n",
    "    * Now, here I wrote the Diffie-Hellman protocol again, except now we are going to assume that these guys are separated in time. \n",
    "    * These two steps do not have to occur simultaneously; They could actually take place at quite different times.\n",
    "    * The first step of the Diffie-Hellman protocol is what we are going to view as **key generation.**\n",
    "    * That is the public key is going to be this capital A and the secret key is simply going to be the little a. \n",
    "    * So, you notice of course that extracting the secret key from the public key, namely extracting the little a from capital A is a discrete log problem. \n",
    "    * So, that recovering a secret key is actually difficult. Ok, now this gives us our public key.\n",
    "    \n",
    "* So, now at a later time Bob wants to encrypt a message to Alice, encrypted using her public key. So how does Bob encrypt? \n",
    "    * Well, what he is going to do is he's going to compute his contribution to the Diffie-Hellman protocol. Namely, he is going to send over g to the little b. Of course, he is going to choose this little b at random and now he is going to compute by himself the shared secret. \n",
    "    * So, he is going to compute by himself g to the ab. From this g to the ab he is going to derive a symmetric key for a symmetric encryption system and then he is going to encrypt the message m using this symmetric key that he just derived. And that is the pair he is going to send.\n",
    "    * So, he is going to send over his contribution to the Diffie-Hellman protocol plus the symmetric encryption of the message m that he wants to send over to Alice. \n",
    "    * Ok, so you can see basically, we are doing the exact same thing as we would do in the Diffie-Hellman protocol except now we, Bob directly immediately is using his Diffie-Hellman secret to encrypt the message that he wants to send over to Alice. \n",
    "* Now, what does Alice do to decrypt? \n",
    "    * Basically, she is going also to compute the Diffie-Hellman secret. Remember, that now she just received Bob's contribution to the Diffie-Hellman protocol and she has her secret key a. \n",
    "    * So, she can compute also the Diffie-Hellman secret, namely g to the ab, from which she is going to derive the symmetric encryption key k. \n",
    "    * And then, she is going to decrypt the message to recover the actual plaintext. Ok, so that is the intuition for how we convert the Diffie-Hellman protocol into a public key system. \n",
    "    \n",
    " \n",
    " <img  src=\"Screen Shot 2017-01-31 at 0.07.31.png\" width=700 height=700/>\n",
    " \n",
    " \n",
    "* So, I am going to refer to it as E sub s, and D sub s. These are the encryption and decryption algorithms of a symmetric encryption system that happens to provide authenticated encryption. And, the key space for this system is capital K. And, then we are also going to need a hash function that maps pairs of elements in the group, namely elements in G squared into the key space. Now, here is how the public key encryption system works. So, I have to describe three algorithms. Algorithm that generates the public key and the secret key, and then the encryption and decryption algorithms. So, the key generation algorithm works as follows: All we do is basically, build up Alice's contribution to the Diffie-Hellman protocol. What we are going to do is going to choose a random generator g in G and then we are going to choose a random exponent a. The secret key is going to be a and then the public key is going to be the generator g and Alice's contribution to the Diffie-Hellman protocol. The reason, by the way, we don't use a fix generator, is because it allows us to somewhat use a weaker assumption, improving security. And, so it is actually better to choose a random generator every time. It is easy enough to choose a random generator. All we do, is we take the generator that we started with and then we raise it to some power that is relatively prime to n. That will give us another generator. A random generator of the group capital G. Ok. So, you can see here that again the public key is simply Alice's contribution to the Diffie-Hellman protocol. And, the secret key is the random a that she chose.\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-31 at 0.12.21.png\"width=700 height=700/>\n",
    "\n",
    "\n",
    "* Now, how do we encrypt and decrypt? Well, when Bob wants to encrypt the message, he is going to use the public key. Remember, it consists of g and h. Here, he wants to encrypt a message m. So, here is what he is going to do. So, he is going to choose his contribution to the Diffie-Hellman protocol. So, this is the secret b that he would normally choose in Diffie-Hellman. And, now he is going to compute g to the b, which is actually his message, that gets send to Alice in the Diffie-Hellman protocol. He is going to compute the Diffie-Hellman secret, that's h to the b. If you remember, h was g to the a, therefore, this value here is really g to the ab. That's the Diffie-Hellman secret. That is the one thing that the attacker doesn't actually know. Next, he is going to compute a symmetric key by basically hashing this pair u comma v. So, u, of course, is something that the attacker is going to know because that is going to be sent as part of the ciphertext. But v, the attacker isn't going to know. Again, for the proof of security, actually it helps to hash both u and v. So, we hash both of them together. Although, strictly speaking we just needed to hash v, because v is the only value that the attacker doesn't know. The attacker already knows u, because that's going to be part of the data that's sent on the network. So, anyhow, so Bob derives this symmetric key k, by hashing u and v. Then, he goes ahead and encrypts the message using the symmetric key k and finally he outputs his contribution to the Diffie-Hellman protocol. The value u and then the symmetric ciphertext that directly encrypts the message m. That's it. So, the ciphertext consists of these two parts and that is the thing that gets sent over the network.\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-31 at 0.15.12.png\"width=700 height=700/>\n",
    "\n",
    "* Let's see, how does Alice decrypt now\n",
    "* So, she is going to use her secret key a to decrypt and she receives here, Bob's contribution to the Diffie-Hellman protocol plus the symmetric encryption of the message that Bob sent. What she will do is she'll compute herself the Diffie-Hellman secret. If you remember, u to the a is simply g to the b to the a. Which is g to the ab. So, here Alice computed the Diffie-Hellman secret. And, now let me ask you, how does she derive the symmetric key k given the Diffie-Hellman secret, g to the ab and the ciphertext that she was given? \n",
    "* Well, what she will do, is simply again, now she has u from the ciphertext and she has v, because she just computed it herself. So, now she can rederive the symmetric encryption key by hashing u and v together to get the symmetric encryption key and then she just decrypts the ciphertext to get the actual plaintext. OK, so that's it. That is the whole encryption and decryption algorithm. In a picture, the way the ciphertext would look, is also as kind of what we saw in the last lecture. Basically, there would be a short header that contains u. Which as you recall, is g to the b. And, then the rest of the ciphertext would be the encryption of the message that is being sent, under the symmetric key k. And, then to decrypt, Alice would use this header to derive the Diffie-Hellman secret from which she will derive k and then decrypts the body, to get the original plaintext.\n",
    "\n",
    "## ElGamal Performance\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-31 at 23.17.53.png\" width=700 height=700/>\n",
    "\n",
    "* Ok, so you would think that encryption actually is, takes twice as long as decryption, because encryption requires two exponentiations, while decryption requires only one. It turns out, that is not entirely accurate because, you notice that the exponentiation during decryption is done to a variable basis. Namely, u changes every time. Whereas during encryption, the basis is fixed: g and h are derived from the public key and are fixed forever. So, in fact, in turns out that if you want to do exponentiation to a fixed basis, you can do a lot of precomputation. In particular, you can do all the squaring steps in the repeated squaring algorithm offline. So, here what you would do, you would compute all powers of 2 of g. So, you would compute g, g squared, g to the fourth, g to the eighth, go to the sixteenth, g to the thirty two, and so on and so forth. These are all the squaring steps of the repeated squaring algorithm you would do offline. The same thing for h. And, then when it comes time to actually do the real exponentiation all you need to do is just do the multiplications, to accumulate these powers of 2 into the exponent b, that you're trying to compute. So, if you think about it, this can actually speed up exponentiation by a factor of 3. In fact, it would speed up it even more if you allow me to store even larger tables. This is called a windowed exponentiation. But, regardless, if you allow the encryptor to store large tables that are derived from the public key, then in fact encryption is not going to be slower than decryption. In fact, encryption will be faster than decryption. But, again, this requires that the encryptor to precompute these large tables and store them around. So, if all the encryptor is doing, is just constantly encrypting to a single recipient, that can be done actually fairly fast using these precomputed tables. If the encryptor, for every message is encrypting to a different recipient, for example, if every time you send an email, you send an email to a different recipient, then, in fact, the encryption will be twice as slow as decryption. So, this is a good trick to keep in mind. In fact, most cryptolibraries don't do this. So, if you see that you are always encrypting to the same public key and for some reason your encryption process takes a lot of time, it's a bottleneck for you, keep in mind that you can actually really speed things up using precomputation. Of couse, if encryption is a bottleneck for you, you might as well be using RSA, where an RSA encryption is really fast. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ElGamal Security\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-31 at 23.37.37.png\" width=700 height=700/>\n",
    "\n",
    "* So let me remind you that when we first presented the Diffie-Hellman protocol, we said that the security is based on the assumption that says that given G, G to the A, G to the B, it's difficult to compute the Diffie-Hellman secret, G to the AB. This is basically what the attacker has to do. He sees Alice's contribution. He sees Bob's contribution and then his goal is to figure out what the Diffie-Hellman secret is. And we said that this problem is difficult. The statement that the problem is difficult is what's called the computational Diffie-Hellman assumption. So, let's take this assumption more precisely. So, as usual we're going to look at a finite cyclic group of order N, so G is some group, in your head you should be thinking ZP star, but there could be other groups, for example, like an ellipctic curve group. And then we say that the computational Diffie-Hellman assumption. I've often used the shorthand CDH for Computational Diffie Hellman. We'll say this assumption holds in G if the following condition holds, namely for all efficient algorithms. If we choose a random generator, and then we choose random exponents A, B in ZN. Then when we give the algorithm G, G to the A, and G to the B, the probability that the algorithm will produce the Diffie Hellman secret is negligible. If this is true for all efficient algorithms, then we say that the CDH assumption holds for G. CDH, as I said, stands for Computational Diffie Hellman.\n",
    "\n",
    "<img  src=\"Screen Shot 2017-01-31 at 23.40.51.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* I'm gonna go ahead and make a slightly stronger assumption called a hash Diffie-Hellman assumption. Okay. So what is hash Diffie-Hellman assumption? Again, we are focusing on a particular group G and now we're also gonna introduce a hash function H that maps pairs of elements in G into the key space of some symmetric encryption system. And then we say that the hash Diffie-Hellman a ssumption, or HDH for short, holds for this pair, G comma H for the group in the hash function if the following is true. Basically, if I choose a random generator and then I choose random exponents A and B in ZN and then I also choose a random R and K, then the following distributions are computationally indistinguishable. That is, if I give you G, G to the A, G to the B, and then this hash value, this should look familiar to you. This is the hash value that's used in the ElGamal system to derive the symmetric encryption key. What we're saying is that this distribution is indistinguishable from a distribution where you're also given. G, G to the A, G to the B. But now, instead of giving the hash, you're given just really random key. So what this assumption says is that the symmetric key that was derived during encryption in the ElGamal system, essentially is indistinguishable from a truly random key that is derived independently from the rest of the parameters of the system. It's a truly independent random key, looks basically the same as the key that we used, to derive from the G to the A and the G to the B. Now I'd like to point out that the Hash Diffie-Hellman assumption is actually a stronger assumption than the Computational Diffie-Hellman assumption. The way to see that is using the contra positive, that is suppose the Computational Diffie-Hellman assumption happens to be easy in the group G. Then I claim that in fact the Hash Diffie-Hellman assumption is also easy in the group G. In fact, I'll say for G, H and this is true in fact for all hash functions where the image of the hash function. It contains at least two elements. In other words all I want to say is that the Hash Diffie-Hellman assumption and it's easy for all hash functions to go match everything to a single point. Which is true for almost all hash functions of interest to us. So actually, this is a really simple statement to prove. Basically, if the Computational Diffie-Hellman assumption is easy, what that says is that, given G to the A and G to the B, I can actually calculate G to the AB myself. Cuz I know the hash function H, I can calculate this complete value here.\n",
    "\n",
    "\n",
    "## ElGamal is semantically secure under the Hash Diffie-Hellman \n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.10.38.png\" width=700 height=700/>\n",
    "\n",
    "* So let me quickly remind you how theElGamal system works. While we're gonna choose a random generator G, we're gonna choose a random 'a' in ZN, the public key is gonna be G, and G to the A, the secret key is simply gonna be A. And now here I wrote shorthand for the ElGamal encryption. Basically, what to encrypt, what we do is we choose a random B. We hash G as being H to the B. Remember this H to the B is the value G to the AB. This is the Diffie Hellman secret. The hash function gave us a symmetric encryption key K. We encrypt the message with K, and we output G to the B and the symmetric cipher text. To decrypt we have to value U, and the Diffie Hellman secret, G to the A. To derive a symmetric key, we decrypt the cipher text. And then we output the plaintext message m.\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.14.35.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So let's see how to argue that, in fact, ElGamal is semantically secure under this Hash Diffie-Hillman assumption is fairly simple. So well we have to argue, remember we had, in semantic security, we have these two experiments. One experiment, the attacker is given the encryption of m0. In the other experiment, the attacker is given the encryption of m1. So I wrote the two experiments here. Here you notice that the attacker starts by sending off the public key to the adversary. The adversary then chooses two equal length messages m0 and m1. And then if he gets the ElGamal encryption of M0, and a kind of rough shorthand for what ElGamal ciphertext is, okay? Similarly, in encryption one, he simply gets the encryption of M1 instead of M0, and everything else is the same about these two experiments. Now, because of the Hash Diffie-Hellman assumption, we know that even though the attacker got to see G, G to the a and G to the b, we know that the output of the hash of G to the b, G to the ab is indistinguishable from random. Therefore, if we replace the actual hash function by a truly generated random key K that's independent of everything else, by the Hash Diffie-Hellman assumption, the attacker can't distinguish these two games. And again, it's a simple exercise for you to show that if he could distinguish these two games, then he would break the Hash Diffie-Hellman assumption. But then the same is true for experiment one. The attacker also could not distinguish the output of the hash function from a truly random key, that was used the generate the challenge cipher text. Okay. So now basically we look at these two experiments and we realize that, wait a minute, what's going on in these two experiments? Basically everything is the same except in one experiment, the attacker gets the encryption under a symmetric encryption system of m0. In the other one, he gets the encryption under a symmetric encryption system of m1 and the key is chosen at random independently over everything else. So by the fact that the symmetric encryption system is semantically secure, these two games are indistinguishable. If they were distinguishable, then the attacker could break the semantic security of this symmetric encryption system. So now we kinda prove this, you know, this chain of equivalences. And that proves that the original games, in fact, are indistinguishable, computationally indistinguishable. And therefore, the ElGamal system is semantically secure.\n",
    "\n",
    "## ElGamal Chosen Ciphertext Security\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.20.06.png\" width=700 height=700/>\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.21.03.png\" width=700 height=700/>\n",
    "\n",
    "## ElGamal Review\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.24.53.png\" width=700 height=700/>\n",
    "\n",
    "* So let me start by reminding you how the ElGamal encryption system works. I'm sure by now you all remember how ElGamal works, but just to be safe, let me remind you that key generation in ElGamal picks a random generator, a random exponent from ZN and then the public key is simply the generator and this element g to the a, whereas the secret key is simply the discrete log of h base g. This value A. Now the way we encrypt is we pick a random exponent B from ZN. We compute the hash of G to the B and H to the B. And I'm gonna remind you that H to the B is the Diffie Hellman secret, G to the AB. And then we actually encrypt a message using a symmetric encryption system with the key K that's derived from the hash function. And finally, the output cipher text is G to the B, and the symmetric cipher text. The way we decrypt is you know, as we've seen before basically, by hashing U and the Diffie Hellman secrets, decrypting the symmetric system, and outputting the message M.\n",
    "\n",
    " \n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.21.03.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.40.00.png\" width=700 height=700/>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A Unifying Theme\n",
    "\n",
    "\n",
    "\n",
    "* **This week, we saw two families of public encryption systems. One family was built from trapdoor functions, and particularly RSA, and the other family was built from the Diffie-Hellman protocol.**\n",
    "\n",
    "* I wanna show you that both families in fact follow from a more general principle. \n",
    "* The unifying theme is what's called a one-way function. \n",
    "\n",
    "## One-Way Functions\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.43.35.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So what is a one-way function? Well, we've already seen this concept briefly before. \n",
    "    * But basically, a function from, one set to another, say, from X to Y is said to be one way, if, in fact, there's an efficient algorithm that allows us to evaluate the function F. \n",
    "    * So anyone can evaluate the function F at any point of their choice. However, inverting the function F should be difficult. That's what makes the function one way. \n",
    "    * So what do I mean by that? Well, you can think of the function F as a function again mapping the set X to the set Y. But it so happens in many points in X could actually be mapped into a single point in Y. \n",
    "    * Now when they say that the function is difficult to invert, what I mean is that when I give you some point inside of Y and I ask you find me pre-image of this point, you won't be able to point to any of these as a pre-image. \n",
    "    * In other words, no efficient algorithm can find any point that is the inverse of the given point Y. Now the way we say that more precisely is that we say that for all efficient algorithm A, if I chose a random X in the set, capital X, and now I'm gonna give f(x) to algorithm A. And then, what I'm gonna ask algorithm A to do, is basically produce a pre-image of the point f(x). Well, what does it mean that A produced a pre-image of the point f(x)? It means that if I apply the function f to the output of A, what I should get back is, well, f(x). \n",
    "    * Let's think through this one more time. \n",
    "        * So I chose a random point x in Capital X. You know I give algorithm A f(x).\n",
    "        * So I'm gonna give algorithm A this point here. And now A is gonna produce some points. \n",
    "        * So let's pretend that A produces this point over here. And now I wanna say that if I apply the function F to this point here, that A produced, the probability that I get the same point that I started with is negligible. \n",
    "        * In other words the probability that algorithm A was able to produce one of these three points is, in fact, negligible. \n",
    "        * All he can do is produce some other point that maps into something other than f(x), okay? So, again, all this is trying to do is just capture the fact that given f(x), it's hard to find some pre-image of f(x). \n",
    "\n",
    "## Example of One-Way Function \n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 0.56.38.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So let's look at our first example of a 1-way function. Or at least a presumed 1-way function. And so we're gonna build it from a pseudo random generator.  \n",
    "* Or at least a presumed 1-way function. And so we're gonna build it from a pseudo random generator. And suppose I have a function F from x to y there is a secure pseudo random generator. So the output of f s much larger than the input. Remember, a pseudo-random generator takes a small seed and expands it into a much larger output. And for example you can, you know, the pseudo random generator maybe is built using deterministic counter mode out of AES. Well, it's fairly easy to see that if, in fact, F is a secure pseudo random generator, then F is in fact a one-way function. So our first example of a one-way function is directly built from a pseudo random generator. This is actually kind of a trivial proof, so let's prove the contra positive. So suppose I have an efficient algorithm that inverts F, okay? So I'm proving the contra positive. Suppose F is not one way. Then A is an efficient algorithm than an inverse F. And now I need to build an algorithm B that breaks the pseudorandom generator. Ok, so I'm proving again by contra-positive. Okay so how do I break the pseudo-random generator? Well, all we do is the following. So algorithm B is given some y in the set Y. And what it's gonna do is the following, it's gonna try and run algorithm a on the input y. And now, well, if y is the output of the pseudorandom generator, then algorithm A will output the seed, and namely  an element in X with, you know, non-negligible probability. So what we'll do is we'll apply the pseudorandom generator again to the output of algorithm A. As I said, if y was the output of a generator, then will have output the seed cuz it inverted the pseudorandom generator. So if we apply the pseudorandom generator again to the output of A, what we should get back is basically the y that we started with. Okay, so if this condition holds we're gonna say we're gonna output zero. And if this condition doesn't hold, we're gonna output one otherwise. That's it, that's our distinguisher against a pseudo-random generator. So if our distinguisher is given a y that is the output of the pseudo random generator, then with non-negligible probability, our distinguisher B will output zero. However, if our distinguisher B is given a truly random string. Well, a truly random string doesn't have any seed that causes the generator to output that string. And therefore our distinguishable output one with again, with also very high probability. And again I hope that's clear. Basically, if we look at the set of all possible outputs, namely the set Y, very few of those outputs happened to be the output of the pseudorandom generator. So if we are just given an output y over hearsay, that's not the output of the pseudorandom generator, then we rerun algorithm A on it. It can't possibly produce a seed that will output this point starr because there is no such seed. And as a result, since most points actually are not in the image of the pseudorandom generator, most points will not have a seed that, maps the generator to them and there's also where we were given a random point in Y, a truly uniform point in Y, our distinguishable B will output 1 with very high probability. However, if we are given a pseudo random output of a generator, then algorithm A will output the corresponding seed. When we apply the generator to that seed, we'll get the initial output y and therefore we'll output zero with non-negligible probability. Okay, so if A was able to invert F, then B is able to break the generator. And since the generator is secure, algorithm A can't invert F. And in particular, no efficient algorithm can invert F. And therefore, F is a one-way function. Excellent, so this is a long discussion of kind of a minor point. But all I wanted to show you is that in fact, a pseudo-random generator directly gives us a one-way function. Unfortunately, this one-way function has no special properties. And what that means is it's actually difficult to use it for key exchange or for public key encryption. In some sense, the best key exchange we can do with this, as far as we know, is Merkle puzzles.\n",
    "\n",
    "* **But all I wanted to show you is that in fact, a pseudo-random generator directly gives us a one-way function. Unfortunately, this one-way function has no special properties. And what that means is it's actually difficult to use it for key exchange or for public key encryption.**\n",
    "\n",
    "\n",
    "## Discrete Log One way function\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 1.03.17.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So now let's look at our second example. \n",
    "* The second example is what I'm gonna call the discrete log one way function. \n",
    "    * So let's fix a group, a cyclic group of order N the group G and let g be some generator of the group capital G so again I remind you that all that means is, if I look at all powers of g, then I basically span the entire group capital G. \n",
    "    * And now let's define the following function. The function goes from ZN to G and it's defined basically as the exponentiation to the power of X. \n",
    "    * Okay, so this maps any element between zero and n-1 to an element of the group capital G simply by raising g, little g to the appropriate power. \n",
    "    * And it's kind of obvious that if the discrete log problem in the group capital G is hard, then in fact f is one way. In fact, the one wayness of f is the discrete log assumption. So if the discrete log is hard, f is one way.\n",
    "    * Now the interesting thing about this one-way functions is it's got some interesting properties.\n",
    "    * In particular, if I give you f(x) and f(y) I claim that it's very easy to compute f(x + y). Even though we have no idea what x or y are. All we're given is just f(x) and f(y), nevertheless, we can compute f(x + y). \n",
    "    * Let me ask you, how would you do that? Well, just by rules of exponentiation, basically, f(x + y) is simply f(x) times f(y). And again, this is all done inside the group G. If you're not convinced, simply recall that f(x + y) is g to the (x + y). Which is simply g to the x times g to the y, which is exactly what we have here. \n",
    "    * **And this simple property, this simple fact that the function has this additive property, if you think about it, is exactly what enables key exchange and public key encryption. So, this additional property of the one-way function is what enabled all of public key cryptography.**\n",
    "    \n",
    "    \n",
    "## RSA One Way Function \n",
    "\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 1.08.42.png\" width=700 height=700 />\n",
    "\n",
    "\n",
    "* So let's look at our next example the RSA one way function so here we're going to choose two primes p and q we're going to set N to be p times q then were going to choose e that's relatively prime to phi(N). And then, we define the functions, and simply as a function from ZN star to ZN star, simply as f(x) equals x to the e. Okay, so raising x to the power of e. And again we say that this function is one way, simply under the RSA assumption. Again, the RSA assumption is the assumption that this function is one way. And the interesting thing about this function is that it has properties similar to the one that we saw on the previous slide, namely the given f(x) and f(y), now we can compute f(x y) as opposed to f(x + y) So we say that this function has a multiplicative property as opposed to the additive property on the previous slide. But more importantly this is kind of not the most interesting thing about this function. The really exciting thing about this function is it in fact has a trapdoor. In other words there's a secret key that all of a sudden allows us to invert this function. Even though without the secret key the function is one way. As far as we know. And this property, I'll say, the fact that it has a trap door, again, enabled all of public key cryptography. I'll say that this trap door also makes the RSA function especially well suited for digital signatures. In week seven, we're gonna see that both the RSA function and the discrete log functions let us construct digital signatures. But the RSA function, because it has a trap door, makes it very, very easy to construct digital signatures from it. And so, in fact, most digital signatures out there in the world, in fact, rely on the RSA function just because it's so simple to build digital signatures from it. So again, we see that this one-way function with the special properties. It has a multiplicative property and a trap door. Essentially again, enables all of public key crypto.\n",
    "\n",
    "# Summary\n",
    "\n",
    "\n",
    "<img  src=\"Screen Shot 2017-02-01 at 1.12.50.png\" width=700 height=700/>\n",
    "\n",
    "\n",
    "* So to summarize, the reason we are able to build public key cryptography namely, the reason we're able to do key exchange and public key encryption and so on, is because we're able to construct one-way functions that have very, very special properties.\n",
    "* In particular, they have these properties that are sometimes called homomorphic properties, namely they're given f(x) and f(y). We can construct a f(x + y) or, f(x y), and some functions, like RSA, even have trap doors, which let us build digital signatures very, very easily. But the main thing I wanted to show you is that the magic of public key crypto is basically made possible because of these one-way functions with their special properties. \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [default]",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "labels_anchors": false,
   "latex_user_defs": false,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "512px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": true,
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}