Alexandre Savard | 1b09e31 | 2012-08-07 20:33:29 -0400 | [diff] [blame] | 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 | |