[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: How do I choose constants suitable for Diffe-Hellman?
"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 <[email protected]> -- Consent Technologies, (02) 821-2043
Disclaimer: From? \notin speaking_for(Organization?) [cfqx103]