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
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
The index calculus method
Can not be used in all groups
We will only consider discrete logarithms in Z!p for
p prime with ! a primitive element modulo p
Faster than the previous algorithms
Resembles a factoring algorithm such as Dixon’s
random squares
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 index calculus method
Can not be used in all groups
We will only consider discrete logarithms in Z!p for
p prime with ! a primitive element modulo p
Faster than the previous algorithms
Resembles a factoring algorithm such as Dixon’s
random squares
Under various “reasonable” assumptions the
pre-computation phase has asymptotic running
time
O
!
e(1+o(1))
”
ln p ln ln p
”
and then to find a particular discrete logarithm:
O
!
e(1/2+o(1))
”
ln p ln ln 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
Basic idea
Pre-computation:
Find a factor base of small primes:
B = {p1, p2, . . . , pB}
Compute the discrete logarithms of the B primes in
the factor base
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
Basic idea
Pre-computation:
Find a factor base of small primes:
B = {p1, p2, . . . , pB}
Compute the discrete logarithms of the B primes in
the factor base
Then we use the knowledge of the discrete logarithms of
the primes in the factor base to compute the discrete
logarithm of the ” = !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
Pre-computation
1 Select the factor base of primes
B = {p1, p2, . . . , pB}
2 Collect congruences modulo p of the form
!xj ! pa1j1 p
a2j
2 · · · p
aBj
B (mod p)
for 1 ” j ” C. These can be written as relations
among discrete logarithms of the factor base
elements:
xj ! a1j log! p1 + . . . + aBj log! pB (mod p # 1).
Given C relations in B unknown logarithms we
hope to find a unique solution modulo p# 1 and so
we compute the discrete logarithms of the factor
base.
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
Pre-computation
1 Select the factor base of primes
B = {p1, p2, . . . , pB}
2 Collect congruences modulo p of the form
!xj ! pa1j1 p
a2j
2 · · · p
aBj
B (mod p)
for 1 ” j ” C. These can be written as relations
among discrete logarithms of the factor base
elements:
xj ! a1j log! p1 + . . . + aBj log! pB (mod p # 1).
Given C relations in B unknown logarithms we
hope to find a unique solution modulo p# 1 and so
we compute the discrete logarithms of the factor
base.
How do we find the congruences?
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
Computing a discrete logarithm
We wish to compute a = log! “.
1 Choose a random s, 1 ” s ” p # 2 and compute
# = “!s (mod p)
2 Try to factor # over B and hence find a
congruence:
“!s ! pc11 p
c2
2 · · ·p
cB
B (mod p)
which we can write as
log! “+s ! c1 log! p1+. . .+cB log! pB (mod p#1)
3 Solve for log! ”
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
Example
Let p = 223, ! = 3. We wish to calculate a = log! 19
(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
Example
Let p = 223, ! = 3. We wish to calculate a = log! 19
(mod p)
Select factor base: B = {2, 3, 5, 7}
Collect relations: Some random numbers lead us
to:
390 (mod 223) = 15 = 3 $ 5
3170 (mod 223) = 126 = 2 $ 32 $ 7
3212 (mod 223) = 63 = 32 $ 7
which become
90 ! log3 3 + log3 5 (mod 222)
170 ! log3 2 + 2 log3 3 + log3 7 (mod 222)
212 ! 2 log3 3 + log3 7 (mod 222)
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
Example
So we have the discrete logarithms of the factor base:
log3 2 = 180, log3 3 = 1
log3 5 = 89, log3 7 = 210
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
Example
We want to find the discrete logarithm of 19. Pick a
random number s and compute
# = 19 $ !s (mod 223)
Try s = 14:
# = 19 $ 314 ! 120 (mod 223)
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
Example
We want to find the discrete logarithm of 19. Pick a
random number s and compute
# = 19 $ !s (mod 223)
Try s = 14:
# = 19 $ 314 ! 120 (mod 223)
Since 120 = 23 $ 3 $ 5 we have
log3 19 + 14 ! 3 log3 2 + log3 3 + log3 5 (mod 222)
! 3 $ 180 + 1 + 89 ! 186 (mod 222)
hence log3 19 = 172.
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
A lower bound on complexity?
There exist groups where the discrete logarithm
problem can be e!ciently solved
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
A lower bound on complexity?
There exist groups where the discrete logarithm
problem can be e!ciently solved
Such algorithms work for specific groups, not in
general
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
A lower bound on complexity?
There exist groups where the discrete logarithm
problem can be e!ciently solved
Such algorithms work for specific groups, not in
general
There is a lower bound on the complexity of
generic algorithms given by Shoup
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
A lower bound on complexity?
There exist groups where the discrete logarithm
problem can be e!ciently solved
Such algorithms work for specific groups, not in
general
There is a lower bound on the complexity of
generic algorithms given by Shoup
Shoup proved that Shanks’ algorithm and Pollard’s
rho method are essentially optimal within the class
of generic algorithms
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
In practice
From Stinson:
1 G = (Z!p, ·), p prime, ! a primitive element modulo
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
In practice
From Stinson:
1 G = (Z!p, ·), p prime, ! a primitive element modulo
p
2 G = (Z!p, ·), p, q prime, p ! 1 (mod q), ! % Zp
with order q
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
In practice
From Stinson:
1 G = (Z!p, ·), p prime, ! a primitive element modulo
p
2 G = (Z!p, ·), p, q prime, p ! 1 (mod q), ! % Zp
with order q
3 G = (F2n, ·), ! a primitive element in F!2n
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
In practice
From Stinson:
1 G = (Z!p, ·), p prime, ! a primitive element modulo
p
2 G = (Z!p, ·), p, q prime, p ! 1 (mod q), ! % Zp
with order q
3 G = (F2n, ·), ! a primitive element in F!2n
4 G = (E, +), where E is an elliptic curve modulo a
prime p, ! % E is a point having prime order
q = #E/h, where (typically) h = 1, 2 or 4
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
In practice
From Stinson:
1 G = (Z!p, ·), p prime, ! a primitive element modulo
p
2 G = (Z!p, ·), p, q prime, p ! 1 (mod q), ! % Zp
with order q
3 G = (F2n, ·), ! a primitive element in F!2n
4 G = (E, +), where E is an elliptic curve modulo a
prime p, ! % E is a point having prime order
q = #E/h, where (typically) h = 1, 2 or 4
5 G = (E, +), where E is an elliptic curve over a
finite field F2n, ! % E is a point having prime order
q = #E/h, where (typically) h = 2 or 4
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