From: "Brian A. LaMacchia" <bal@martigny.ai.mit.edu>
Recently, someone asked for a smaller prime of only 512-bits for speed. This is more than enough for the strength of keys needed for DES, 3DES, MD5 and SHA. Perhaps this would be easier to have more complete and robust verification as well.
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.]
Thanks. I have added the [from Schneier] estimate e ** ((ln p)**1/2 * (ln (ln p))**1/2) and number field sieve estimate e ** ((ln p)**1/3 * (ln (ln p))**2/3) to the Photuris draft, with a small amount of explanation. Hilarie Orman posted that 512-bits only gives an order of 56-bits strength, 1024-bits yeilds 80-bits strength, and 2048 yields 112-bits strength. I do not have the facilities to verify her numbers. As most of us agree that 56-bits is not enough (DES), the 512-bit prime seems a waste of time and a tempting target. I'd like to drop it, but Phil is inclined to keep it with a disclaimer. Bill.Simpson@um.cc.umich.edu Key fingerprint = 2E 07 23 03 C5 62 70 D3 59 B1 4F 5E 1D C2 C1 A2