<<

. 8
( 36 .)



>>

We can see that the time of exponentiation grows linearly as the length
of numbers ( n ) increases but the time of solving the inverse problem grows
exponentially or (for the index calculus algorithm) subexponentially. The
issue of the existence of faster algorithms for computing discrete logarithms,
as well as for solving other inverse problems in cryptography, remains an
open question.
Solving Discrete Logarithm Problem 35


The Baby-step Giant-step Algorithm
3.2

In the unclassified literature this method was first described by Daniel
Shanks (see [Knuth (1973)l); references thereto have been known since 1973.
It was one of the first methods to show that the discrete logarithm problem
can be solved much faster than by the exhaustive search. The algorithm is
as follows.

Step 1 Take two integers m and k such that

mk>p. (3.3)
Step 2 Compute two number series

ay, a2Yl urn-ly (mod p ) ;
Y, (3.4)
'*el




a2m, . . . , ukm (mod p )
aml (3.5)
(all computations are carried out modulo p ) .
Step 3 Find such i and j that
-a3y.
aim '




A number
Proposition 3.1

x =i - j (3.7)
m
is the solution of Eq. (3,l). Besides, the integers a, j satisfying (3.6) exist.
Proof. The correctness of (3.7) follows from the chain of equalities below,
where all computations are modulo p and division corresponds to multipli-
cation by an inverse number:




(here the next to last equality follows from (3.6)). Next, show that the
numbers i and j satisfying (3.6) exist. For that purpose place all numbers
of the form (3.7) into the table (Table 3.1).
We can see that all numbers from 1 to k m are contained in the table.
It means by (3.3) that the table contains all numbers from 1 to p . So any
exponent z < p is present in the table, i.e. the number z satisfying (3.1)
can be represented in the form (3.7), and (3.6) always has a solution. 0
Basics of Contemporary Cryptography for IT Practitioners
36


Table 3.1 Numbers of the form im - j .

...
1 2 m-1
0
j-+
iJ.

... 1
1 m- 2
m- l
m
...
2 2m 2m- 1 2m- 2 m+l
...
... ... ...
... ...
+1
k m - 1 k m - 2 ... ( k - l)m
k km



Example 3.1 Find the solution of the equation 2” mod 23 = 9 with the
aid of baby-step giant-step algorithm.
Choose m and k. Let m = 6, k = 4. We can see that (3.3) is fulfilled.
Compute the series (3.4), (3.5):

(3.4) : 9,18,13,3,6,12 ;
(3.5) : 18.

Here we stop computations since there are equal numbers in (3.4) and (3.5)
under i = 1, j = 1. By (3.7) we obtain

1.6-1 =5.
IC=


Check it: 25 mod 23 = 9. Indeed, z = 5 is the solution.
Let us explain the name of the algorithm considered. We know that in
cryptography, p is a large number, hence m and k are also large. In the
series (3.4), the exponent is increased by 1 (baby step), and in the series
(3.5), the exponent is increased by m (giant step).
Let™s now estimate the complexity of the method.
Proposition 3.2 With the given method and f o r large p , computation
time satisfies the inequality



(Here we speak of the total time rather than of the number of multiplica-
tions.)
Proof. We can take

k=m=LfiJ+1 (3.9)
which, obviously, satisfies (3.3). Then no more than 2J?r multiplications
are required for computation of (3.4) and (3.5). We know that for “usual”
( (˜secondary school”) methods of multiplication and division, the time of
Solving Discrete Logarithm Problem 37


computation with r-digit operands is proportional to r 2 . We have all the
numbers taken from the set { I , . . . , p } , so T 5 logp and computation time
is proportional to log2p. Hence we immediately obtain the time needed
for computation of the series (3.4) and (3.5). However we have not consid-
ered all stages of the algorithm. Namely, we have not considered the time
required for the search of equal numbers between the two series. Under
large k and m this is far from being simple. The problem can be solved
in the following way: first ascribe to each number in a series the corre-
sponding value of i or j and one extra bit indicating the series (3.4) or
(3.5). Then join both series in one and sort with respect to the values of
numbers. The length of the joint series is k 3- m M 2 f i . For the best
sorting methods, Slog S comparisons are required, where S is the number
of elements to sort (see e.g. [Aho et al. (1976)l). In our case S = 2 f i and
consequently 2filog (2fi) M .\/iJlogp comparisons with words of length
logp bits are required, which totals to about Jijlog2p bit operations. After
having sorted the joint series we look it through and find two equal numbers
from different initial series (using the bit flag). Finally, summing up the
0
times on all stages of the algorithm we obtain the estimate (3.8).


Index Calculus Algorithm
3.3

The main ideas behind the index calculus algorithm had been known in
number theory since 1920s. But only in 1979 Adleman, one of the inventors
of RSA, pointed out this algorithm as a means for solving Eq. (3.1) and
investigated its complexity [Adleman (1979)l. At present time, the index
calculus algorithm and its enhanced variants offer the fastest methods for
computation of discrete logarithms in equations like (3.1).
Before describing the algorithm we introduce the following notion.
Definition 3.1 A number n is said to be p-smooth if all its prime factors
are less than or equal to p .
Example 3.2 The numbers 15, 36, 45, 270, 2025 are 5-smooth (their
factorisation includes only the prime factors 2, 3, and 5).
Proceed to the description of the algorithm.

Step 1 Select a factor base
Basics of Contemporary Cryptography for IT Practitioners
38


which consists of the first t primes (2, 3, 5, . . . , a remark concerning
the choice o f t will be given below).
Step 2 By randomly selecting k find t + c ( E is a small integer, see below) pt-
smooth numbers of the form ak mod p. That is, for each k, we compute
the number ak m o d p and check its smoothness by trial division over
the elements of S. If the number is pt-smooth then we pick it for further
use, else discard it and proceed with the next k. Write each pt-smooth
number found as a product of elements in S:
t
ci 2 0
ak m o d p = n p : i , (3.10)
i= 1
(for each value of k we obtain the corresponding set of numbers ci).
Step 3 Take logarithms on both sides of (3.10):
t
IC ci log, pi (3.11)
=
i=l
for each pt-smooth number found at Step 2. We obtain a system of
+
t E linear equations of the form (3.11) with t unknowns (log, pi). We
know that, in principle, t equations are enough for finding t unknowns.
However, it may happen that some of the equations will be linearly
dependent. That is why the number of equations is greater by E than
the number of unknowns. This increases the probability of obtaining
a unique solution should some relations be linearly dependent. Now
we solve the system using linear algebra methods with all calculations
carried out modulo p-1 (recall that exponents and hence logarithms are
reduced modulo p - 1). As a result, we obtain the values of logarithms
of elements from S: log,pl, log,p2, . . . , logapt.
Step 4 By randomly selecting T find pt-smooth number of the form y .
ar mod p:
t
(3.12)
y.armodp=npii, ei20.
i=l
That is, similar to Step 2, compute the number y . ar mod p and check
whether it is pt-smooth. If not, try the next T .
Step 5 Taking logarithms on both sides of (3.12) obtain the final result

mod(p-1). (3.13)
-T)
i=l
Solving Discrete Logarithm Problem 39


The correctness of the described algorithm is quite obvious and its effec-
tiveness is connected with the following observation. If we select randomly
a number from the infinite set of integers then with probability 1/2 it is
divisible by 2, with probability 1/3 divisible by 3, with probability 1/5 di-
visible by 5 , and so on. So we may expect that in the interval from 1 to
p - 1 there are sufficiently many numbers whose prime factors are only the
elements of our factor base S. Exactly such numbers are being sought at
steps 2 and 4 of the algorithm.
As we have mentioned above, the parameter E must ensure a unique
solution at Step 3. It is believed that given a large p the value of E about 10
guarantees the uniqueness of solution with high probability (see [Menezes
e t al. (1996)l). If it is not the case then it is necessary to revert to Step 2
and use other values of k.
Now let's discuss the complexity issues. The running time of the algo-
rithm depends on the choice of t. The more is t , i.e. the number of prime
factors in S , the less fails we meet when searching smooth numbers at steps
+
2 and 4 (it is easy to see that complexity of Step 2 is t E times greater
than that of Step 4). But with large t the complexity of Step 3 drastically
+
increases since we have to solve the system with t E equations. Find-
ing an optimum t which minimises the overall time may usually be done
by numerical methods. Adleman [Adleman (1979)l showed that under an
optimal choice of t the complexity of the algorithm is estimated as




where c1, c2 are some positive constants.


Example 3.3 Apply the index calculus algorithm to solve the equation


(3.14)
37 = 10" mod 47.


We have y = 37, a = 10, p = 47. Take as a factor base S = (2,3,5},
t = 3, and assume E = 1, i.e. we shall construct a system of 4 equations.
We completed the first step of the algorithm and proceed to the second.
Basics of Contemporary Cryptography for IT Practitioners
40


Let's find four 5-smooth numbers (taking k = 1 , 2 , 3 , .. . ):

J
10, mod 47 = 10 = 2 . 5
J
lo2 mod 47 = 6 = 2 . 3
lo3 mod 47 = 13 = 13
lo4 mod 47 = 36 = 2 . 2 . 3 . 3 J
lo5 mod 47 = 31 = 31
lo6 mod 47 = 28 = 2 . 2 . 7
lo' mod 47 = 45 = 3 . 3 . 5 J

We have found four 5-smooth numbers (marked with a J ) corresponding

<<

. 8
( 36 .)



>>