crypto/dh/generate

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