From: M.Gream@uts.EDU.AU (Matthew Gream)
Date: Mon, 5 Sep 94 15:50:41 PDT
To: ghio@chaos.bsu.edu (Matthew Ghio)
Subject: Re: How do I choose constants suitable for Diffe-Hellman?
In-Reply-To: <199409051528.KAA07031@chaos.bsu.edu>
Message-ID: <9409052253.AA19774@acacia.itd.uts.EDU.AU>
MIME-Version: 1.0
Content-Type: text/plain


"Matthew Ghio" wrote:

> Yes, Phil Karn posted a list of such numbers to the list last May, and
> the program used to generate them.  Since some people have expressed
> their distaste for large files re-posted/forwarded to the list, I won't
> send it, but you can get it from ftp cs.cmu.edu:
> /afs/andrew.cmu.edu/usr12/mg5n/public/Karn.DH.generator

I needed a few of these primes a while ago, so I took a few minutes and
hacked Phil's code to operate distributed (ie. a central machine
carried out the sieving and handed off candidates to a set of other
machines to do the Rabin-Miller). With one Sun Sparc 690MP and approx
40 Sun Sparc LX's, it was getting results like:

acacia: 7:21pm  up  2:05,  20 users,  load average: 0.95, 0.98, 0.77
mg.{~/static/d/dist} date;./go;date
Sun Jul 24 19:21:57 EST 1994
[..]
  server calls:   7235
found modulus p = 
72a925f760b2f954ed287f1b0953f3e6aef92e456172f9fe86fdd8822241b9c9788fbc289982743efbcd2ccf062b242d7a567ba8bbb40d79bca7b8e0b6c05f835a5b938d985816bc648985adcff5402aa76756b36c845a840a1d059ce02707e19cf47af0b5a882f32315c19d1b86a56c5389c5e9bee16b65fde7b1a8d74a7675de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f23d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef356a05180c3bec7ddd5ef6fe76bfd8717
finding generator
trying 2 3 5
generator g = 5
Sun Jul 24 21:10:18 EST 1994

That's 2 hours for a 2048 prime P where (P - 1)/2 is also prime, and they
also satisfied the constraint that P = 3(mod 4).

The software maintains a TCP connection to each "Rabin-Miller server"
and can dynamically deal with the loss of machines, but in it's
simplicity doesn't do reconnects.  If anyone who operates an FTP
archive wants to reply to me, I'll tar it up (in it's current "it works
for me, but no guarantees" state).

Speaking of primes with constraints, I got my hands on Harn's recent
paper on a PKCS based on both factoring and discrete logs. He wants his
modulus to be a prime P = 2p x q + 1, where p = 2r + 1, q = 2s + 1. All
P, q, q, r, s must be prime -- good luck in finding such primes by
probablistic methods !

Matthew.

mg.{~/src/rr} ls -l
total 26
-rw-------  1 mgream       8339 Jul 24 14:17 client.c
-rw-------  1 mgream       2196 Jul 24 15:00 common.h
-rw-------  1 mgream       6028 Jul 29 13:35 dhgen.c
-rwx------  1 mgream        270 Jul 24 14:58 go
-rw-------  1 mgream        527 Jul 24 14:58 makefile
-rw-------  1 mgream       3041 Jul 29 14:50 server.c
-rw-------  1 mgream        367 Jul 24 14:26 servers.src

-- 
Matthew Gream <M.Gream@uts.edu.au> -- Consent Technologies, (02) 821-2043
Disclaimer: From? \notin speaking_for(Organization?)            [cfqx103]