]>
Commit | Line | Data |
---|---|---|
d02b48c6 RE |
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 |