CM30173: Cryptography\reserved@d =[@let@token art IV
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Part V
Public-key cryptography
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
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
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Generalised discrete logarithm problem
Generalized discrete logarithm problem
Given a finite cyclic group G of order n, ! a generator
of G and ” ! G find an element a, 0 ” a ” n # 1 such
that
!a = ”
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Algorithms for computing discrete logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus method
A lower bound on complexity?
Discrete logarithms in other groups
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Types of algorithms
Algorithms which work in arbitrary groups
Exhaustive search
Shanks’ algorithm
Pollard’s rho algorithm
Algorithms which work in arbitrary groups but
require the order of the group to have only small
prime factors
Pohlig-Hellman algorithm
Algorithms which only work in certain groups
Index-calculus method
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Algorithms for computing discrete logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus method
A lower bound on complexity?
Discrete logarithms in other groups
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Exhaustive search
Compute
!, !2, !3, . . . (1)
until ” = !a is found.
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Exhaustive search
Compute
!, !2, !3, . . . (1)
until ” = !a is found.
We compute a new term in the list by multiplying
the previous term by !
We only store the current element of the list
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Exhaustive search
Compute
!, !2, !3, . . . (1)
until ” = !a is found.
We compute a new term in the list by multiplying
the previous term by !
We only store the current element of the list
Total time: O(n)
Total space: O(1)
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Algorithms for computing discrete logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus method
A lower bound on complexity?
Discrete logarithms in other groups
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Shanks’ algorithm
It is a time-memory trade-o!
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Shanks’ algorithm
It is a time-memory trade-o!
Let m = %
&
n’
CM30173:
Cryptography
Part IV
Algorithms for
computing discrete
logarithms
Exhaustive search
Shanks’ algorithm
Pohlig-Hellman
The index calculus
method
A lower bound on
complexity?
Discrete logarithms
in other groups
Shanks’ algorithm
It is a time-memory trade-o!
Let m = %
&
n’
If !a = ” then we can write
” = !a = !mj+i
for 0 ” j, i < m CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Shanks’ algorithm It is a time-memory trade-o! Let m = % & n' If !a = " then we can write " = !a = !mj+i for 0 " j, i < m We can now write !mj+i = !mj!i and hence " = !mj!i ( "!"i = !mj CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Shanks’ algorithm Algorithm (Shanks(G, n, !, ")) 1 m = % & n' 2 Compute list L1: (0, !0), (1, !m), (2, !2m), . . . , (m # 1, !(m"1)m) 3 Sort list L1 of pairs (j, !mj) on the value of !mj 4 Compute list L2: (0, "!0), (1, "!"1), (2, "!"2), . . . , (m#1, "!"(m"1)) 5 Sort list L2 of pairs (i, "!"i) on the value of "!"i 6 Find (j, y) ! L1 and (i, y) ! L2 7 log! " = (mj + i) (mod n) CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups CM30173: Cryptography Part IV Algorithms for computing discrete logarithms Exhaustive search Shanks’ algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups Pohlig-Hellman Key point: The run time of Pohlig-Hellman depends on the size of the prime factors of the group order n The implication is that when selecting a group for cryptographic purposes we should ensure that n has at least one large prime factor Public-key cryptography Algorithms for computing discrete logarithms Exhaustive search Shanks' algorithm Pohlig-Hellman The index calculus method A lower bound on complexity? Discrete logarithms in other groups