CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Discrete logarithms
More mathematics
The discrete logarithm problem
Di!e-Hellman
Man in the middle attack
The ElGamal cryptosystem
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Recall Z!p
The set of residues modulo p is denoted Zp
We also call this the integers modulo p
If p is prime then Zp is a field
Z
!
p = Zp \ {0} is an Abelian multiplicative group
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Order
Definition (Order of a group)
The order of a group is the number of elements in the
group.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Order
Definition (Order of a group)
The order of a group is the number of elements in the
group.
If the order of a group is finite it is called a finite
group.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Order
Definition (Order of a group)
The order of a group is the number of elements in the
group.
If the order of a group is finite it is called a finite
group.
Definition (Order of an element)
Let G be a finite group. The order of an element
g ” G is the smallest positive integer m such that
gm = 1.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Cyclic group
Definition (Cyclic group)
Let G be a finite group of order m. G is said to be a
cyclic group if there exists an element ! ” G having
order equal to m. ! is called a generator of G.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Cyclic group
Definition (Cyclic group)
Let G be a finite group of order m. G is said to be a
cyclic group if there exists an element ! ” G having
order equal to m. ! is called a generator of G.
Fact
Z
!
p is a cyclic group.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Primitive element modulo p
Definition (Primitive element modulo p)
An element ! ” Z!p with order p # 1 modulo p is called
a primitive element modulo p.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Primitive element modulo p
Definition (Primitive element modulo p)
An element ! ” Z!p with order p # 1 modulo p is called
a primitive element modulo p.
It immediately follows that ! is a primitive element
modulo p if and only if
{!i | 0 $ i $ p # 2} = Z!p
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
Let p = 7.
We have “(6) = “(2 % 3) = “(2) % “(3) = 2
primitive elements modulo 7.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
Let p = 7.
We have “(6) = “(2 % 3) = “(2) % “(3) = 2
primitive elements modulo 7.
How can we find these? How can we check an
element is primitive modulo p?
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
Let p = 7.
We have “(6) = “(2 % 3) = “(2) % “(3) = 2
primitive elements modulo 7.
How can we find these? How can we check an
element is primitive modulo p?
Lets see if 2 is a primitive element modulo 7:
20 (mod 7) = 1
21 (mod 7) = 2
22 (mod 7) = 4
23 (mod 7) = 1
2 has order 3.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
32 (mod 7) = 2
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
32 (mod 7) = 2 33 (mod 7) = 6
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
32 (mod 7) = 2 33 (mod 7) = 6
34 (mod 7) = 4
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
32 (mod 7) = 2 33 (mod 7) = 6
34 (mod 7) = 4 35 (mod 7) = 5
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
32 (mod 7) = 2 33 (mod 7) = 6
34 (mod 7) = 4 35 (mod 7) = 5
And just to check:
36 (mod 7) = 1
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
What about 3:
30 (mod 7) = 1 31 (mod 7) = 3
32 (mod 7) = 2 33 (mod 7) = 6
34 (mod 7) = 4 35 (mod 7) = 5
And just to check:
36 (mod 7) = 1
Since 3 is primitive we know that 3i is primitive if
and only if gcd(i, 6) = 1
Hence the primitive elements are 3 and
35 (mod 7) = 5
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Finding primitive elements
Theorem (Stinson p172)
Suppose that p > 2 is prime and ! ” Z!p. Then ! is a
primitive element modulo p if and only if
!
p!1
q &’ 1 (mod p)
for all primes q|(p # 1).
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Definition of discrete logarithm
Definition (Discrete logarithm in Z!
p
)
Let p be prime and let ! ” Z!p be a primitive element
modulo p. If # ” Z!p such that
!a ‘ # (mod p)
then a is called the discrete logarithm of # and is
denoted log! #.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
Let p = 7, ! = 3
Given # = 6 we know from previous slides that
33 ‘ 6 (mod 7)
and hence that in Z!
7
log
3
6 = 3
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Example
Let p = 7, ! = 3
Given # = 6 we know from previous slides that
33 ‘ 6 (mod 7)
and hence that in Z!
7
log
3
6 = 3
How would we calculate discrete logarithms in Z!p in
general?
Public-key cryptography
Discrete logarithms
More mathematics
The discrete logarithm problem
Diffie-Hellman
Man in the middle attack
The ElGamal cryptosystem