From: Hal <hfinney@shell.portal.com>
Date: Sun, 22 May 94 11:11:08 PDT
To: cypherpunks@toad.com
Subject: Re:  Is my DH exchange secure?
Message-ID: <199405221812.LAA17924@jobe.shell.portal.com>
MIME-Version: 1.0
Content-Type: text/plain


> With a strong prime, there is no need to use generators, as Eric implied.

My wording here was a little clumsy; I was not contradicting Eric but
rather attempting to amplify his comments.  There is no need to look
for primitive roots (elements of maximal order); rather you just want to
avoid elements of low order.

I found the paper I referred to which described the tradeoffs between the
order of the group and the size of the modulus.  It is "Efficient Signature
Generation by Smart Cards", by C.P. Schnorr, in the Journal of Cryptology,
1991, v4, pp161-174.  This is the patented Schnorr signature which has been
the basis for PKP's claim that the federal Digital Signature Standard
infringes the Schnorr patent.  (Bruce Schneier recently posted on sci.crypt
that a paper presented at Eurocrypt 94 analyzed all the different discrete-
log based signature scheme, and in his opinion cast doubt on this claim of
infringement.)

Schnorr deals with a prime p, and a smaller prime q which divide p-1.
In his system, q is a lot smaller than p, just big enough to provide the
requisite security.  Small q's allow for faster calculation of g^x since
x is, say, 140 bits rather than 512 bits.  Here is what Schnorr writes on
page 163 (he uses "alpha" where we were using g, as the generator of
the group):

"The Security Complexity 2^t.  We wish to choose the parameters p, q so
that forging a signature or an authentication requires about 2^t steps by
known methods.  For this we choose q >= 2^(2t) and p such that 2^t is about
exp(sqrt(ln p ln ln p)).  The security number t may depend on the
application intended.  For signature we consider in particular t=72 rather
that [sic] t=64, since 2^64 steps may be insufficient in view of the rapid
technological progress in computing power and speed.  For p>=2^512 and
q>=2^140 the discrete logarithm problem requires at least 2^72 steps by
known algorithms.  (It may soon be necessary to increase the lower bound
p>=2^512 due to the current progress in computing discrete logarithms.)
The restriction that the order of [alpha] is a prime much smaller than p
provides no advantage in any of the known discrete logarithm algorithms
provided that q>=2^140.  The prime q is necessary to avoid an index
calculus attack and a square root attack (see Section 2)."

The attack described in section 2 is interesting.  Also known as the
baby-step-giant-step attack, it is a simple meet-in-the-middle-technique.
Suppose you wanted to solve a^x=y given a and y.  Suppose for simplicity
that x is known to be in the range of 0 to 100.  What you can do is to
calculate two lists.  The first is ( a^10, a^20, a^30, ..., a^90 ).  The
second is ( y/(a^1), y/(a^2), y/(a^3), y/(a^4), ..., y/(a^9) ).  Then
you just look for a number which is common to both lists.  If a^20 is the
same as y/(a^4) then we know that y = a^24.  So this takes square root of
q in time and space.  Schnorr says that Pollard has a trick to use less
space.  (Remember the discussion we had here some time back of the prac-
ticality of meet-in-the-middle attacks given the huge space needs for even
2^64 hashes?  I think Pollard's trick may apply to those as well.)

Hal