Transcript Diffie-Hellman - SNS Courseware

Diffie-Hellman Key
Exchange
Whittfield Diffie and Martin Hellman are called
the inventors of Public Key Cryptography.
Diffie-Hellman Key Exchange is the first Public
Key Algorithm published in 1976.
1
What is Diffie-Hellman?

A Public Key Algorithm
 Only for Key Exchange
 Does NOT Encrypt or Decrypt
 Based on Discrete Logarithms
 Widely used in Security Protocols and
Commercial Products
 Williamson of Britain’s CESG claims to have
discovered it several years prior to 1976
2
Discrete Logarithms

What is a logarithm?
 log10100 = 2 because 102 = 100
 In general if logmb = a then ma = b
 Where m is called the base of the logarithm
 A discrete logarithm can be defined for
integers only
 In fact we can define discrete logarithms mod
p also where p is any prime number
3
Discrete Logarithms

For any integer b and a primitive root a of
prime number p, we can find a unique exponent
i such that

b ≡ ai mod p where 0≤i≤p-1

This exponent i is referred to as the discrete
logarithm of the number b for the base a (mod
p).
 And the problem of finding exponent i is
referred to as discrete logarithm problem.
4
Discrete Logarithm Problem

The security of the Diffie-Hellman algorithm
depends on the difficulty of solving the discrete
logarithm problem (DLP) in the multiplicative
group of a finite field
5
Primitive Roots






For any prime number p, if we have a number a such that powers of
a mod p generate all the numbers between 1 to p-1 then a is called a
Primitive Root of p.
That is, if a is a primitive root of the prime number p, then the
numbers
a mod p, a2 mod p,..., ap-1mod p
are distinct and consist of the integers from 1 through p-1 in some
permutation.
Then for any integer b and a primitive root a of prime number p we
can find a unique exponent i such that
b = ai mod p
The exponent i is referred to as the discrete logarithm or index, of
b for the base a.
6
Computing Primitive Root

Let’s 19 be a prime number p and its primitive
root integer say, a is 2 then

21 mod 19=2, 22 mod 19=4, 23 mod 19=8, 24 mod 19=16
25 mod 19=13, 26 mod 19=7, 27 mod 19=14...218mod19=1
The above sequence generates modulus


2n
1 2 3
values 2 4 8
4
5
6
16 13 7
7
8
14 9
9
10 11 12 13 14 15 16 17 18
18 17 15 11 3
6
12 5
10 1
It has all integers till p-1, ie called as primitive root.
Primitive roots of 19 are 2,3,10,13,14,15
7
8
9
Diffie-Hellman Algorithm

Five Parts
1.
2.
3.
4.
5.
Global Public Elements
User A Key Generation
User B Key Generation
Generation of Secret Key by User A
Generation of Secret Key by User B
10
Global Public Elements

q

Prime number
 < q and  is a primitive root
of q
 The global public elements are also sometimes
called the domain parameters
11
User A Key Generation

Select private XA
 Calculate public YA
XA < q
YA =  XA mod q
12
User B Key Generation

Select private XB
 Calculate public YB
XB < q
YB =  XB mod q
13
Generation of Secret Key by
User A

K = (YB)XA mod q
14
Generation of Secret Key by
User B

K = (YA)XB mod q
15
Diffie-Hellman Key
Exchange
16
Diffie-Hellman Example

q = 97

=5

XA = 36

XB = 58

YA = 536 = 50 mod 97

YB = 558 = 44 mod 97

K = (YB)XA mod q = 4436 mod 97 = 75 mod 97

K = (YA)XB mod q = 5058 mod 97 = 75 mod 97
17
Why Diffie-Hellman is
Secure?

Opponent has q, , YA and YB

To get XA or XB the opponent is forced to take
a discrete logarithm

The security of the Diffie-Hellman Key
Exchange lies in the fact that, while it is
relatively easy to calculate exponentials modulo
a prime, it is very difficult to calculate discrete
logarithms. For large primes, the latter task is
considered infeasible.
18