Cryptography (Classic & Modern) Chapter 4-2 PDF

Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) Dr. Ahmed AlMokhtar Ben Hmida...

Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Course Cryptography (Classic & Modern) Dr. Ahmed AlMokhtar Ben Hmida College of Computer Science, King Khaled University 'KKU', KSA Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 4-2 : Asymmetric Cryptography, Diffie-HellMan… ❑Asymmetric Cryptography: issues, ❑ DH Algorithm (Formalism) ❑ DH Algorithm Development, Examples… Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA RSA issues ◼ Algorithmic complexity of the method: ◼ search for large prime numbers, and choice of very long keys ◼ Performing operations modulo n. ◼ Implementation problem on equipment with low computing power (eg bank cards, mobile stations, etc.) ◼ The method is officially secure if key length and usage constraints are respected. ◼ ➔ Solution: Use of RSA for the exchange of secret session keys of a symmetric algorithm with private keys. Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Encryption Weaknesses ◼ Efficiency is lower than Symmetric Algorithms ◼ A 1024-bit asymmetric key is equivalent to 128-bit Why symmetric key ◼ Potential for man-in-the middle attack https://blog.cloudflare.com/why-are-some-keys-small/ Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Encryption Man-in-the-middle Attack ◼ Hacker could generate a key pair, give the public key away and tell everybody, that it belongs to somebody else. Now, everyone believing it will use this key for encryption, resulting in the hacker being able to read the messages. If he encrypts the messages again with the public key of the real recipient, he will not be recognized easily. Bob Trudeau’s Trudeau’s Message Encrypted + public key Cipher Message David’s Public Key David’s Public Key Bob’s Bob’s Trudeau Message Encrypted Cipher (Middle-man) David + Public key Message Bob’s Public Key Attacker Trudeau’s Public Key Trudeau’s David’s Trudeau’s New Message Trudeau’s Message Encrypted + public key Encrypted + public key Cipher Cipher Message Message Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Encryption Session-Key Encryption ◼ Used to improve efficiency ◼ Symmetric key is used for encrypting data ◼ Asymmetric key is used for encrypting the symmetric key Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA ◼ Pretty Good Privacy (PGP) ◼ Used to encrypt e-mail using session key encryption ◼ Combines RSA, TripleDES, and other algorithms ◼ Secure/Multipurpose Internet Mail Asymmetric Encryption Extension (S/MIME) Encryption Protocols ◼ Newer algorithm for securing e-mail ◼ Backed by Microsoft, RSA, AOL ◼ Secure Socket Layer(SSL) and Transport Layer Socket(TLS) ◼ Used for securing TCP/IP Traffic ◼ Mainly designed for web use ◼ Can be used for any kind of internet traffic ◼ Used by GMAIL Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA ◼ Key agreement is a method to create secret key by exchanging only public keys. Example ◼ Bob sends Alice his public key ◼ Alice sends Bob her public key Asymmetric ◼ Bob uses Alice’s public key and his private key to generate a session key ◼ Alice uses Bob’s public key and her private key to generate a session key Encryption ◼ Using a key agreement algorithm both will generate same key Key Agreement ◼ Bob and Alice do not need to transfer any key Alice’s Private Key Bob’s Cipher Public Key (DES) Alice and Bob Bob’s Session Key Generate Same Private Key Session Key! Alice’s Cipher Public Key (DES) Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 4-2 : Asymmetric Cryptography, Diffie-HellMan… ❑Asymmetric Cryptography: issues, ❑ DH Algorithm (Formalism; Key Exchange…) ❑ DH Algorithm Development, Examples… Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Diffie-Hellman algorithm ◼ The Diffie-Hellman algorithm is one of the most used algorithms for the first step: key exchange. ◼ The objective of Diffie-Hellman is to allow the establishment of a private key between two parties, via the exchange of messages over an insecure channel. ◼ When establishing a key with Diffie-Hellman, the messages are indeed sent in the clear over the network, and anyone who intercepts the transmitted messages should not be able to deduce the generated key. Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Encryption Key Diffie-Hellman Mathematical Analysis Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Asymmetric Encryption Key Agreement cont. ◼ Diffie-Hellman is the first key agreement algorithm ◼ Invented by Whitfield Diffie & Martin Hellman ◼ Provided ability for messages to be exchanged securely without having to have shared some secret information previously ◼ Inception of public key cryptography which allowed keys to be exchanged in the open ◼ No exchange of secret keys ◼ Man-in-the middle attack avoided Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Diffie-Hellman Key Exchange Consider the following problem: Two people (or computers) need to communicate securely. They have access to a symmetric cypher (the same key is used for encryption and decryption). They have not yet agreed on a key (they may not have ever met or communicated before). The challenge here is “how can these two people decide on a key to use without anyone being able to capture it?” The first effective public key exchange method is known as Diffie-Hellman Key Exchange after the researchers that discovered it. Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Diffie–Hellman key exchange establishes a shared secret between two parties that can be used for Eve secret communication for exchanging data over a public network. starting color The process begins by having the two parties, Alice and Bob, publicly agree on an arbitrary starting color that does not need to be kept secret. In this example, the color is yellow. secret color Each person also selects a secret color that they keep to themselves – in this case, red and cyan. The crucial part of the process is that Alice and Bob each mix their own secret color together with their mutually shared color, resulting in orange-tan and light-blue mixtures Public transport respectively, and then publicly exchange the two mixed colors. Finally, each of them mixes the color they received from the partner with their own private Public color. The result is a final color mixture (yellow-brown in this case) that is identical to their transport partner's final color mixture. If a third party listened to the exchange, they would only know the common color (yellow) and the first mixed colors (orange-tan and light-blue), but it would be very hard for them to secret color find out the final secret color (yellow-brown). Bringing the analogy back to a real-life exchange using large numbers rather than colors, secret shared this determination is computationally expensive. It is impossible to compute in a practical amount of time even for modern supercomputers. Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Diffie-Hellman Key Exchange Because they were used in the original description of the algorithm, Diffie-Hellman key exchange is usually described assuming that Alice and Bob want to use a symmetric cipher and so need to exchange a private key. Alice and Bob agree on two numbers g and p with 0 < g < p. These numbers are not private and can be known by anyone. Alice picks a private number 0 < a and computes α = g a mod p. Alice sends α to Bob. Meanwhile, Bob picks a private number 0 < b and computes β = g b mod p. He then sends β to Alice. Alice computes k = βa mod p and Bob computes k = αb mod p. Both of them obtain the same number k which can then be used as the secret key. Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA Diffie-Hellman Key Exchange ◼ DH allows Alice and Bob to agree on a key over an insecure channel. ◼ Let p be a large prime number (2K-4K bits) ◼ Let g be a generator of Zp* ◼ g is a generator if for all 0 < x ≠ y < p, gx ≠ gy (mod p). ◼ Alice chooses random x, 1 < x < p-1, and sends gx (mod p) to Bob. ◼ Bob chooses random y, 1 < y < p-1, and sends gy (mod p) to Alice. ◼ Alice and Bob use K = (gx)y = (gy)x = gxy ◼ Eve cannot compute gxy from p, g, gx and gy. ◼ Computing x from gx (mod p) (discrete logarithm problem) is believed (but not proven) to be hard. Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Cryptography (Classic & Modern) College of Computer Science ; King Khalid University ; KKU - KSA CHAPTER 4-2 : Asymmetric Cryptography, Diffie-HellMan… ❑Asymmetric Cryptography: issues, ❑ DH Algorithm (Formalism; Key Exchange…) ❑ DH Algorithm Development, Examples… Ahmed AlMokhtar BEN HMIDA, Dr. & Full Professor, Head of ATMS Lab, Expert in Signal Processing , CS College at King Khalid University Asymmetric Encryption Key Diffie-Hellman Mathematical Analysis Bob & Alice Bob agree on non-secret Alice prime p and value a Generate Secret Generate Secret Random Number x Random Number y Bob & Alice Compute Public Key exchange Compute Public Key ax mod p public keys ay mod p Compute Session Key Compute Session Key (ay)x mod p (ax)y mod p Identical Secret Key  Diffie-Hellman Key Exchange Example: Alice and Bob agree on g = 327 and p = 919. Alice chooses a = 400; this is her private key. She then computes α = 327400 mod 919 = 231. This is Alice’s public key and can be known by anyone. She can send this number to Bob in cleartext. Bob chooses b = 729 for his private key and computes β = 327729 mod 919 = 162 and sends this number (his public key) to Alice. Alice computes k = 162400 mod 919 = 206. Bob computes k = 231729 mod 919 = 206. k = 206 is the secret key that both Alice and Bob will use to encrypt their messages to each other. ) Diffie-Hellman algorithm Suppose Alice and Bob want to agree on a private key. The Diffie-Hellman algorithm allows the establishment of this private key, via the following steps: Alice and Bob agree on 2 numbers: p (a very large prime number), and g (another very large number, called a generator). p and g are transmitted in the clear over the network. Alice and Bob each choose a very large random number, which they keep secret. Let x be the number chosen by Alice, and y the number chosen by Bob. Alice calculates P1 = g^x mod p, and sends the result to Bob Bob calculates P2 = g^y mod p, and sends the result to Alice Alice calculates K1 = P2^x mod p, and Bob calculates K2 = P1^y mod p At this stage, the value K1 calculated by Alice is therefore equal to (g^y mod p)^x mod p. The value K2 calculated by Bob is equal to (g^x mod p)^y mod p.. The laws of arithmetic prove that the two values K1 and K2 are equal. Alice and Bob have therefore managed to agree on a common private key. Sample Diffie-Helman How it works ? The purpose of the Diffie-Hellman algorithm is to create a common secret for people who want to communicate and to use this secret to encrypt the data exchanged. Let's imagine that Alice and Bob want to communicate. Everything in green is public (broadcast on the internet). Anything in red is private. arbitrary prime number random number less than p random number (private) random number (private) exchange of encrypted data with s s is Alice and Bob's common secret. A spy will be unable to calculate s from p and g, because he knows neither the random number Ax chosen by Alice, nor the random number Bx chosen by Bob. Ay and By exchanged between Alice and Bob will also not help her to calculate s. Sample Diffie-Helman arbitrary prime number = 419 random number less than p = 7 Alice chooses a random Bob chooses a random number (private) = 178 number (private) = 344 exchange of encrypted data with s Alice and Bob calculated the same common secret: 107. We use 107 to encrypt the data exchanged Sample 1 The chart below depicts who knows what, again with non-secret values in blue, and secret values in red. Here Eve is an eavesdropper – she watches what is sent between Alice and Bob, but she does not alter the contents of their communications. g, public (primitive root) base, known to Alice, Bob, and Eve. g = 5 p, public (prime) modulus, known to Alice, Bob, and Eve. p = 23 a, Alice's private key, known only to Alice. a = 6 b, Bob's private key known only to Bob. b = 15 A, Alice's public key, known to Alice, Bob, and Eve. A = g a mod p = 8 B, Bob's public key, known to Alice, Bob, and Eve. B = g b mod p = 19 Alice Bob Eve Known Unknown Known Unknown Known Unknown p = 23 p = 23 p = 23 g =5 g =5 g =5 a =6 b b = 15 a a, b A = 5 a mod 23 B = 5 b mod 23 B = 5 15 mod 23 = 1 A = 5 6 mod 23 = 8 9 B = 19 A =8 A = 8, B = 19 a b s = B mod 23 s = A mod 23 6 s = 19 mod 23 = s = 8 15 mod 23 = 2 s 2 Now s is the shared secret key and it is known to both Alice and Bob, but not to Eve. Sample 2 These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1. Here is an example of the protocol, with non-secret values in blue, and secret values in red. 1.Alice and Bob publicly agree to use a modulus p = 23 and base g = 5 (which is a primitive root modulo 23). 2.Alice chooses a secret integer a = 4, then sends Bob A = ga mod p A = 54 mod 23 = 4 (in this example both A and a have the same value 4, but this is usually not the case) 3.Bob chooses a secret integer b = 3, then sends Alice B = gb mod p B = 53 mod 23 = 10 4.Alice computes s = Ba mod p s = 104 mod 23 = 18 5.Bob computes s = Ab mod p s = 43 mod 23 = 18 6.Alice and Bob now share a secret (the number 18). Both Alice and Bob have arrived at the same values because under mod p,