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