-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 At 01:21 09/07/2000 -0400, dmolnar wrote:
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 figured it would be something of that nature.. hence the math library I was working on.. :)
I think www.cryptosavvy.com has some key length recommendations. You might
Thanks for the link...
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 )
Ah.. I have implemented a sieve of eros..whatever his name is.. ;) for finding smaller primes.. it runs very fast, the old rules don't apply so much anymore, memory footprint being more a concern then speed I've noticed so far.. moving the found primes into a sparse array as you find them and then reusing the memory is one way around that.. even my quickly written implementation takes negligible time to find all the primes within 16 bits.. but I've been looking at rabin-miller and some other methods as well. I'll take a look at that link, thanks.. reason again for the math library.. my stuff (obviously) falls apart > 32bits since my library for handling larger numbers is unfinished.
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.
Ah cool.. I've heard very good things about GMP and had been thinking about ways to implement it.. could solve all my problems in one fell swoop. :) I (for reasons that should be obvious) felt that writing the routines myself (with extensive testing) would be preferable, so I could avoid licensing issues as well as bugs/backdoors, but I'll look into this.. Thanks for the quick response.. the application will of course be available to anyone who wants it once finished.. and once Borland finishes Kylix, should compile nicely on the various x86 *nixes out there.. - -------signature file------- "'There comes a time when the operation of the machine becomes so odious, makes you so sick at heart, that you can't take part; you can't even passively take part, and you've got to put your bodies upon the gears and upon the wheels, upon the levers, upon all the apparatus, and you've got to make it stop. And you've got to indicate to the people who run it, to the people who own it, that unless you're free, the machine will be prevented from working at all!" - -Mario Savio- Founder of the Free Speech Movement. -----BEGIN PGP SIGNATURE----- Version: PGPfreeware 6.5.8 for non-commercial use <http://www.pgp.com> iQA/AwUBObcqEGvp1znMxX/XEQLaYQCgxBxiiYTY2OHcVgso4Iaqy7PYucAAniM9 YL2M9tDag44LaILC6mChDmyf =TL/e -----END PGP SIGNATURE-----