The first published public-key algorithm appeared in the seminal paper by Diffie The purpose of the algorithm is to enable two users to exchange a secret key securely that then can be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of the keys.
The purpose of the algorithm is to enable two users to exchange a secret key securely that then can be used for subsequent encryption of messages. The algorithm itself is limited to the exchange of the keys. The Diffie Hellman algorithm depends for its effectiveness on the difficulty of computing discrete logarithms. Briefly, we can define the discrete logarithm in the following way. First, we define a primitive root of a prime number p as one whose powers generate all the integers from 1 to p 1.That is, if a is a primitive root of the prime number p, then the numbers a mod p, a2 mod p, . . ., ap 1 mod p are distinct and consist of the integers from 1 through p 1 in some permutation. For any integer b less than p and a primitive root a of prime number p, one can find a unique exponent i such that b ai mod p 0 … i … (p 1) The exponent i is referred to as the discrete logarithm, or index, of b for the base a, mod p.We denote this value as dloga,p(b).
- all users agree on global parameters:
- large prime integer or polynomial q
- a being a primitive root mod q
- chooses a secret key (number): xA < q
- compute their public key: yA = axA mod q
- each user makes public that key yA
- shared session key for users A & B is KAB:
- KAB = axA.xB mod q
- = yAxB mod q (which B can compute)
- = yBxA mod q (which A can compute)
- KAB is used as session key in private-key encryption scheme between Alice and Bob
- if Alice and Bob subsequently communicate, they will have the same key as before, unless they choose new public-keys
- attacker needs an x, must solve discrete log
each user (eg. A) generates their key