From: Phil Karn <karn@qualcomm.com>
Date: Wed, 8 Nov 1995 10:07:19 +0800
To: bal@martigny.ai.mit.edu
Subject: Re: Photuris Primality verification needed
In-Reply-To: <1999.bsimpson@morningstar.com>
Message-ID: <199511080143.RAA22564@servo.qualcomm.com>
MIME-Version: 1.0
Content-Type: text/plain


> Our practical experiences with discrete logs suggests that the effort
> required to perform the discrete log precomputations in (a) is slightly
> more difficult than factoring a composite of the same size in bits.  In
> 1990-91 we estimated that performing (a) for a k-bit prime modulus was
> about as hard as factoring a k+32-bit composite.  [Recent factoring work
> has probably changed this a bit, but it's still a good estimate.]

This is also my understanding, which I got from you in the first
place.  I take it there have been no dramatic breakthroughs in the
last few years in the discrete log problem? How heavily has it been
studied in comparison with factoring?

Yes, in theory once an attacker spends enough time precomputing a
table for a particular modulus he can then attack individual DH key
exchanges with ease. This seems entirely analogous to attacking
RSA. If you spend the time up front to factor my public RSA key, then
you can also easily attack individual messages to me.

So if I am willing to rely on a PGP key of, say, 1024 bits then I
should be equally willing to rely on a 1024-bit DH modulus.

Now there is admittedly a practical difference here -- people *can*
change their PGP RSA keys occasionally, though this is hard to do when
you have a lot of signatures.  And each user has his/her own PGP RSA
key, and cracking that gives you only the traffic to that user.  A
public DH modulus will be shared by many more people -- making it a
much more tempting target.

Still, requiring support of a fixed modulus for shared public use is
important to promote a basic level of interoperability. This has its
risks, but it should be okay *provided* it's a strong prime of
sufficient strength to preclude the precomputation of the discrete log
tables by even a highly motivated and resourceful attacker. And as a
backup the protocol should provide for the optional use of private
moduli between consenting parties. Sound reasonable?

Phil