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
The discrete logarithm problem
Discrete logarithm problem (DLog problem)
Given p prime, ! a primitive element modulo p and
” ! Z!p find an element a, 0 ” a ” p # 2 such that
!a $ ” (mod p)
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Recall
Definition (One-way function)
A one-way function is a function f : X % Y such that
for all x ! X it is easy to compute f(x) but for
(almost) all y ! Y it is computationally infeasible to
find an x such that f(x) = y.
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Recall
Definition (One-way function)
A one-way function is a function f : X % Y such that
for all x ! X it is easy to compute f(x) but for
(almost) all y ! Y it is computationally infeasible to
find an x such that f(x) = y.
Definition (Trap-door one-way function)
A trap-door one-way function is a one-way function
f : X % Y such that given some additional trap-door
information it becomes feasible, for all y ! Y to find
x ! X such that y = f(x).
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
Di!e-Hellman key exchange
Public parameters: p prime, and !, a primitive element
modulo p which has order p # 1.
1 Alice chooses 1 ” a ” p # 1 at random and
computes
A = !a (mod p) and sends A to Bob.
2 Bob chooses 1 ” b ” p # 1 at random and
computes
B = !b (mod p) and sends B to Alice.
3 Alice receives B and computes
Ba = !ab (mod p)
4 Bob received A and computes
Ab = !ab (mod p)
5 k = Ab = Ba = !ab (mod p)
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
The Computational Di!e-Hellman
problem
Computational Di!e-Hellman problem (CDH)
Given p prime, ! a primitive element modulo p and two
elements “, # ! Z!p find $ ! Z
!
p such that
log! $ $ log! ” & log! # (mod p)
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
The Computational Di!e-Hellman
problem
Computational Di!e-Hellman problem (CDH)
Given p prime, ! a primitive element modulo p and two
elements “, # ! Z!p find $ ! Z
!
p such that
log! $ $ log! ” & log! # (mod p)
That is, given !a and !b, find !ab.
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
Basic idea
Unfortunately…
Oscar is an active attacker.
Oscar intercepts all messages between Alice and
Bob and substitutes his own messages in their
place.
At the end of the exchanges Alice has established a
secret key with Oscar and Bob has established a
secret key with Oscar.
Can this be avoided?
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Attempts to avoid the attack
Can Alice and Bob detect the attack?
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Attempts to avoid the attack
Can Alice and Bob detect the attack?
What if Alice and Bob prove their identities to each
other before they start?
CM30173:
Cryptography
Part IV
Discrete logarithms
More mathematics
The discrete logarithm
problem
Di!e-Hellman
Man in the middle
attack
The ElGamal
cryptosystem
Attempts to avoid the attack
Can Alice and Bob detect the attack?
What if Alice and Bob prove their identities to each
other before they start?
A more promising approach would be to design a
key agreement scheme where the participants are
authenticated at the same time as the key is
established. These are called authenticated key
agreement schemes and we won’t be studying
these.
Public-key cryptography
Discrete logarithms
More mathematics
The discrete logarithm problem
Diffie-Hellman
Man in the middle attack
The ElGamal cryptosystem