[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Re: Photuris Primality verification needed*From*: Phil Karn <[email protected]>*Date*: Tue, 7 Nov 1995 17:43:49 -0800 (PST)*Cc*: [email protected], [email protected]*In-Reply-To*: <[email protected]>*Sender*: [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? 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

**Follow-Ups**:**Re: Photuris Primality verification needed***From:*"Brian A. LaMacchia" <[email protected]>

**References**:**Re: Photuris Primality verification needed***From:*"William Allen Simpson" <[email protected]>

- Prev by Date:
**Re: Exporting software doesn't mean exporting** - Next by Date:
**Re: Photuris Primality verification needed** - Prev by thread:
**Re: Photuris Primality verification needed** - Next by thread:
**Re: Photuris Primality verification needed** - Index(es):