Diffie-Hellman · The algorithn 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 yg respectively, which are then exchanged ya -ga mod p yB= moc Both alice and bob can calculate the key as KaR=gab mod p yab mod p( which B can compute) b 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 p Bob g mod 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, and p So we want to find the key k b This is believed to be hard If one knows how to compute discrete logs efficient ntly 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 GF2 Computing discrete logarithms is closely related to factoring. If you can solve the discrete logarithm problem. the len you can factor. (The converse has 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