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