CDR: Re: StoN, Diffie-Hellman, other junk..

[dmolnar]

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