[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Photuris Primality verification needed
Date: Tue, 7 Nov 1995 17:43:49 -0800 (PST)
From: Phil Karn <[email protected]>
Cc: [email protected], [email protected]
> 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