Diffie-Hellman ° The algorithm The values of g and p dont need to be secret Alice then chooses a secret number a Bob also chooses a secret number b Alice and Bob compute ya and yB respectively, which are then exchanged °yA= ga mod p y= gb mod p Both alice and bob can calculate the key as AB moa p ya mod p (which B can compute) yB mod p(which a can compute The key may then be used in a private-key cipher to secure communications between a and b
6 Diffie-Hellman • The algorithm – The values of g and p don’t need to be secret – Alice then chooses a secret number a – Bob also chooses a secret number b – Alice and Bob compute yA and yB respectively, which are then exchanged • yA = ga mod p yB = gb mod p – Both Alice and Bob can calculate the key as • KAB = gab mod p = yA b mod p (which B can compute) = yB a mod p (which A can compute) – The key may then be used in a private-key cipher to secure communications between A and B
Diffie-Hellman alice a mod 506 g mod p The private key is: gab mod p where p is a prime and g is a generator of Z
7 Alice g a mod p Bob g b mod p The private key is: g ab mod p where p is a prime and g is a generator of Zp Diffie-Hellman
Diffie-Hellman ° Knows ga,gb,g,andp So we want to find the key k This is believed to be hard If one knows how to compute discrete logs efficiently, then one can break this scheme (and other schemes based on public key cryptography)
8 • Knows g a , gb , g, and p • So we want to find the key, k – k = gab – This is believed to be hard. • If one knows how to compute discrete logs efficiently, then one can break this scheme (and other schemes based on public key cryptography) Diffie-Hellman
Diffie-Hellman Can be expanded to be used with many parties · Can be extended to: Finite fields gfp Elliptic curves Galois field GF Computing discrete logarithms is closely related to factoring. If you can solve the discrete logarithm oblem, then you can factor. (The converse has proble never been proven to be true
9 Diffie-Hellman • Can be expanded to be used with many parties • Can be extended to: – Finite fields GFp – Elliptic curves – Galois field • Computing discrete logarithms is closely related to factoring. If you can solve the discrete logarithm problem, then you can factor. (The converse has never been proven to be true.) GF k 2
El gamal a variant of the diffie-Hellman key distribution scheme, allowing secure exchange of messages Published in 1985 by elgamal in T. ElGamal, a Public Key cryptosystem and a Signature Scheme Based on Discrete Logarithms IEEE Trans. Information Theory, vol IT-31(4), pp469- 472,July1985. Like Diffie-Hellman its security depends on the difficulty of factoring logarithms
10 El Gamal • A variant of the Diffie-Hellman key distribution scheme, allowing secure exchange of messages • Published in 1985 by ElGamal in – T. ElGamal, "A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Trans. Information Theory, vol IT-31(4), pp469- 472, July 1985. • Like Diffie-Hellman its security depends on the difficulty of factoring logarithms