Public Key cryptography 曹天杰 Tianjie Cao ticao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou China 中国矿业大学计算机科学与技术学院 2003.6,2
1 曹天杰 Tianjie Cao tjcao@cumt.edu.cn College of Computer Science and Technology, China University of Mining and Technology, Xuzhou, China 中国矿业大学计算机科学与技术学院 2003.6.2 Public Key Cryptography
Diffie-Hellman Diffie-Hellman is a public key distribution scheme First public-key type scheme, proposed in 1976 WDiffie me hellman "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976
2 Diffie-Hellman • Diffie-Hellman is a public key distribution scheme • First public-key type scheme, proposed in 1976. – W Diffie, M E Hellman, "New directions in Cryptography", IEEE Trans. Information Theory, IT-22, pp644-654, Nov 1976
whitfield Diffie Martin Hellman
3
Diffie-Hellman Public-key distribution scheme Cannot be used to exchange an arbitrary message Exchange only a key, whose value depends on the participants(and their private and public key information) The algorithm is based on exponentiation in a finite(Galois)field, either over integers modulo a prime, or a polynomial field
4 Diffie-Hellman • Public-key distribution scheme • Cannot be used to exchange an arbitrary message • Exchange only a key, whose value depends on the participants (and their private and public key information) • The algorithm is based on exponentiation in a finite (Galois) field, either over integers modulo a prime, or a polynomial field
Diffie-Hellman Security relies on the difficulty of computing logarithms in these fields discrete logarithms takes O(e log n loglog n)operations The algorithm two people alice and Bob who wish to exchange some key over an insecure communications channel They select a large prime p( 200 digit), such as(p 1)/2 should also be prime They also select g, a primitive root mod p g is a primitive if for each n from 0 to p-1, there exists some a where ga=n mod p
5 Diffie-Hellman • Security relies on the difficulty of computing logarithms in these fields – discrete logarithms takes O(e log n log log n) operations • The algorithm: – two people Alice and Bob who wish to exchange some key over an insecure communications channel. – They select a large prime p (~200 digit), such as (p- 1)/2 should also be prime – They also select g, a primitive root mod p • g is a primitive if for each n from 0 to p-1, there exists some a where ga = n mod p
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