1From: stewarts@ix.netcom.com (Bill Stewart)
2Newsgroups: sci.crypt
3Subject: Re: Diffie-Hellman key exchange
4Date: Wed, 11 Oct 1995 23:08:28 GMT
5Organization: Freelance Information Architect
6Lines: 32
7Message-ID: <45hir2$7l8@ixnews7.ix.netcom.com>
8References: <458rhn$76m$1@mhadf.production.compuserve.com>
9NNTP-Posting-Host: ix-pl4-16.ix.netcom.com
10X-NETCOM-Date: Wed Oct 11  4:09:22 PM PDT 1995
11X-Newsreader: Forte Free Agent 1.0.82
12
13Kent Briggs <72124.3234@CompuServe.COM> wrote:
14
15>I have a copy of the 1976 IEEE article describing the
16>Diffie-Hellman public key exchange algorithm: y=a^x mod q.  I'm
17>looking for sources that give examples of secure a,q pairs and
18>possible some source code that I could examine.
19
20q should be prime, and ideally should be a "strong prime",
21which means it's of the form 2n+1 where n is also prime.
22q also needs to be long enough to prevent the attacks LaMacchia and
23Odlyzko described (some variant on a factoring attack which generates
24a large pile of simultaneous equations and then solves them);
25long enough is about the same size as factoring, so 512 bits may not
26be secure enough for most applications.  (The 192 bits used by
27"secure NFS" was certainly not long enough.)
28
29a should be a generator for q, which means it needs to be
30relatively prime to q-1.   Usually a small prime like 2, 3 or 5 will
31work.
32
33....
34
35Date: Tue, 26 Sep 1995 13:52:36 MST
36From: "Richard Schroeppel" <rcs@cs.arizona.edu>
37To: karn
38Cc: ho@cs.arizona.edu
39Subject: random large primes
40
41Since your prime is really random, proving it is hard.
42My personal limit on rigorously proved primes is ~350 digits.
43If you really want a proof, we should talk to Francois Morain,
44or the Australian group.
45
46If you want 2 to be a generator (mod P), then you need it
47to be a non-square.  If (P-1)/2 is also prime, then
48non-square == primitive-root for bases << P.
49
50In the case at hand, this means 2 is a generator iff P = 11 (mod 24).
51If you want this, you should restrict your sieve accordingly.
52
533 is a generator iff P = 5 (mod 12).
54
555 is a generator iff P = 3 or 7 (mod 10).
56
572 is perfectly usable as a base even if it's a non-generator, since
58it still covers half the space of possible residues.  And an
59eavesdropper can always determine the low-bit of your exponent for
60a generator anyway.
61
62Rich  rcs@cs.arizona.edu
63
64
65
66