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

Asymmetric all at biosys.net
Wed Sep 6 22:39:28 PDT 2000


-----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-----





More information about the cypherpunks-legacy mailing list