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