On Thu, 7 Sep 2000, Asymmetric wrote:
Now, my main question about D/H is quite simple.. what is considered a "good" size for the prime and primitive used, in bits? Obviously something somewhat large, but how large is large enough? 64bits? Less or more? I can't find much information on this anywhere, and my copy of Applied Cryptography (2nd ed.) while covering D/H in detail, doesn't even mention this.
The modulus should be rather large -- something like 512 or 1024 bits. With 64 bits, someone can use Pollard's method to find discrete logs in roughly 2^32 trials, which is Bad. Taking discrete logs for larger primes requires a variant of the number field sieve; the largest announced modulus for which I'm aware of this being done is 300-400 bits, but it hasn't received as much attention as factoring. I think www.cryptosavvy.com has some key length recommendations. You might also check the April RSA Data Security Bulletin for Bob Silverman's dispute of their model. The storage problem he mentions is actually worse for discrete logs; while the vectors involved in the final step of factoring are 0-1, the vectors in the final stage of discrete log finding have full-size group elements and are therefore harder to store and manipulate. The size of the generator is a different issue. I don't see any reason why a small size generator would hurt...but I haven't thought about it very much. Note that you need the factors of p-1 in order to test if something's a generator, which means you may want to look into Maurer or Mihailescu's methods for prime generation. (Mihailescu has a paper on the subject aimed at implementors at http://www.inf.ethz.ch/~mihailes/papers/primgen.ps )
Delphi and has any libraries like this already, I'd much appreciate hearing about them.. or even some a web resource or paper Real Book (tm) resource that explains in abstract terms how to go about something like this would be appreciated.
It was after my time, but the AP Computer Science curriculum now has a BigInteger library as its "case study." :-) A web search turned up http://www.efg2.com/lab/library/Delphi/MathFunctions/Cryptography.htm which has, among other things, a Pascal header for the Gnu MP library. -David