Cryptography: Theory and Practice:Other Public-key Cryptosystems

cryptography: theory and practice Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210   Pub Date: 03/17/95
  

Previous Table of Contents Next


Now, given that we have already successfully carried out the precomputation step, we compute a desired logarithm logα β by means of a Las Vegas type probabilistic algorithm. Choose a random integer s (1 ≤ sp - 2) and compute

Now attempt to factor γ over the factor base . If this can be done, then we obtain a congruence of the form

This can be written equivalently as

Since everything is now known except logαβ, we can easily solve for logαβ.

Here is a small, very artificial, example to illustrate the two steps in the algorithm.

Example 5.4

Suppose p = 10007 and α = 5 is the primitive element used as the base of logarithms modulo p. Suppose we take as the factor base. Of course log5 5 = 1, so there are three logs of factor base elements to be determined.

Some examples of “lucky” exponents that might be chosen are 4063, 5136 and 9865.

With x = 4063, we compute

This yields the congruence

Similarly, since

and

we obtain two more congruences:

and

We now have three congruences in three unknowns, and there happens to be a unique solution modulo 10006, namely log5 2 = 6578, log5 3 = 6190 and log5 7 = 1301.

Now, let’s suppose that we wish to find log5 9451. Suppose we choose the “random” exponent s = 7736, and compute

Since 8400 = 24315271 factors over , we obtain

To verify, we can check that 56087 = 9451 (mod 10007).

Heuristic analyses of various versions of the algorithm have been done. Under reasonable assumptions, the asymptotic running time of the precomputation is , and the time to find an individual discrete phase log is .

5.1.2 Bit Security of Discrete Logs

We now look at the question of partial information about discrete logs. In particular, we consider whether individual bits of a discrete logarithm are easy or hard to compute. To be precise, consider the problem presented in Figure 5.5, which we call the ith Bit problem.


Figure 5.5  ith bit of discrete logarithm

We will first show that computing the least significant bit of a discrete logarithm is easy. In other words, if i = 1, the ith Bit problem can be solved efficiently. This follows from Euler’s criterion concerning quadratic residues modulo p, where p is prime.

Consider the mapping defined by

Denote by QR(p) the set of quadratic residues modulo p; then

First, observe that f(x) = f(p - x). Next note that

if and only if

which happens if and only if

It follows that

for every y ∈ QR(p), and hence

That is, exactly half the residues in are quadratic residues and half are not.

Now, suppose a is a primitive element of . Then αa ∈ QR(p) if a is even. Since the (p - 1)/2 elements α0 mod p, α2 mod p,..., αp-3 mod p are all distinct, it follows that

Hence, β is a quadratic residue if and only if logα β is even, that is, if and only it L1(β) = 0. But we already know, by Euler’s criterion, that β is a quadratic residue if and only if

So we have the following efficient formula to calculate L1 (β):

Let’s now consider the computation of Li(β) for values of i exceeding 1. Suppose

where t is odd. Then it can be shown that it is easy to compute Li(β) if is. On the other hand, computing Ls+1 (β) is (probably) difficult, in the sense that any hypothetical algorithm (or oracle) to compute Ls+1 (β) could be used to find discrete logarithms in .

We shall prove this result in the case s = 1. More precisely, if p ≡ 3 (mod 4) is prime, then we show how any oracle for computing L2(β) can be used to solve the Discrete Log problem in .

Recall that, if β is a quadratic residue in and p ≡ 3 (mod 4), then the two square roots of β modulo p are ± β(p+1)/4 mod p. It is also important that, for any β ≠ 0,

if p ≡ 3 (mod 4). We see this as follows. Suppose

then

Since p ≡ 3 (mod 4), the integer (p - 1)/2 is odd, and the result follows.

Now, suppose that β = αa for some (unknown) even exponent a. Then either

or

We can determine which of these two possibilities is correct if we know the value L2 (β), since

This fact is exploited in our algorithm, which we present in Figure 5.6.

At the end of the algorithm, the xi’s comprise the bits in the binary representation of logα β; that is,

We will work out a small example to illustrate the algorithm.


Figure 5.6  Computing discrete logs in for p ≡ 3 (mod 4), given an oracle for L2(β)


Previous Table of Contents Next

Copyright © CRC Press LLC



Cryptography. Theory and Practice
Modern Cryptography: Theory and Practice
ISBN: 0130669431
EAN: 2147483647
Year: 1995
Pages: 133
Authors: Wenbo Mao

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net