From: "Brian A. LaMacchia" <bal@martigny.ai.mit.edu>
Date: Thu, 9 Nov 1995 08:09:16 +0800
To: karn@qualcomm.com
Subject: Re: Photuris Primality verification needed
In-Reply-To: <199511080143.RAA22564@servo.qualcomm.com>
Message-ID: <9511081704.AA24263@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


   Date: Tue, 7 Nov 1995 17:43:49 -0800 (PST)
   From: Phil Karn <karn@qualcomm.com>
   Cc: cypherpunks@toad.com, ipsec-dev@eit.COM

   > 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?

Factoring has received more attention than discrete log; certainly when
it comes to net-wide computations it's all factoring.  But that's partly
due, I think, to a lack of targets to attack.  

   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?

You definitely should allow any modulus between consenting parties.  As
for what moduli the standard says "must be" (vs. "should be") supported,
I don't know.  Maybe the right thing to do is require conforming
implementations to support a large modulus but include recommended
smaller moduli.  Then Alice can always force Bob to use the large
modulus but, if both agree, they can use something smaller from the
standard or even their own home-grown modulus.

					--bal