summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authormiod <>2015-02-09 04:12:34 +0000
committermiod <>2015-02-09 04:12:34 +0000
commitfa8c678d25f7746616d3af7f521b37f8f8e24e0c (patch)
tree2fb51f202142be748eb57d5c3f49818c6aa4a360
parentbe7ab46f12a353205bcecf10b2bfc6e303253ef2 (diff)
downloadopenbsd-fa8c678d25f7746616d3af7f521b37f8f8e24e0c.tar.gz
openbsd-fa8c678d25f7746616d3af7f521b37f8f8e24e0c.tar.bz2
openbsd-fa8c678d25f7746616d3af7f521b37f8f8e24e0c.zip
This is neither code not proper documentation.
-rw-r--r--src/lib/libcrypto/dh/dh1024.pem5
-rw-r--r--src/lib/libcrypto/dh/dh192.pem3
-rw-r--r--src/lib/libcrypto/dh/dh2048.pem16
-rw-r--r--src/lib/libcrypto/dh/dh4096.pem14
-rw-r--r--src/lib/libcrypto/dh/dh512.pem4
-rw-r--r--src/lib/libcrypto/dh/example50
-rw-r--r--src/lib/libcrypto/dh/generate65
-rw-r--r--src/lib/libssl/src/crypto/dh/dh1024.pem5
-rw-r--r--src/lib/libssl/src/crypto/dh/dh192.pem3
-rw-r--r--src/lib/libssl/src/crypto/dh/dh2048.pem16
-rw-r--r--src/lib/libssl/src/crypto/dh/dh4096.pem14
-rw-r--r--src/lib/libssl/src/crypto/dh/dh512.pem4
-rw-r--r--src/lib/libssl/src/crypto/dh/example50
-rw-r--r--src/lib/libssl/src/crypto/dh/generate65
14 files changed, 0 insertions, 314 deletions
diff --git a/src/lib/libcrypto/dh/dh1024.pem b/src/lib/libcrypto/dh/dh1024.pem
deleted file mode 100644
index 81d43f6a3e..0000000000
--- a/src/lib/libcrypto/dh/dh1024.pem
+++ /dev/null
@@ -1,5 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MIGHAoGBAJf2QmHKtQXdKCjhPx1ottPb0PMTBH9A6FbaWMsTuKG/K3g6TG1Z1fkq
3/Gz/PWk/eLI9TzFgqVAuPvr3q14a1aZeVUMTgo2oO5/y2UHe6VaJ+trqCTat3xlx
4/mNbIK9HA2RgPC3gWfVLZQrY+gz3ASHHR5nXWHEyvpuZm7m3h+irAgEC
5-----END DH PARAMETERS-----
diff --git a/src/lib/libcrypto/dh/dh192.pem b/src/lib/libcrypto/dh/dh192.pem
deleted file mode 100644
index 521c07271d..0000000000
--- a/src/lib/libcrypto/dh/dh192.pem
+++ /dev/null
@@ -1,3 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MB4CGQDUoLoCULb9LsYm5+/WN992xxbiLQlEuIsCAQM=
3-----END DH PARAMETERS-----
diff --git a/src/lib/libcrypto/dh/dh2048.pem b/src/lib/libcrypto/dh/dh2048.pem
deleted file mode 100644
index 295460f508..0000000000
--- a/src/lib/libcrypto/dh/dh2048.pem
+++ /dev/null
@@ -1,16 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MIIBCAKCAQEA7ZKJNYJFVcs7+6J2WmkEYb8h86tT0s0h2v94GRFS8Q7B4lW9aG9o
3AFO5Imov5Jo0H2XMWTKKvbHbSe3fpxJmw/0hBHAY8H/W91hRGXKCeyKpNBgdL8sh
4z22SrkO2qCnHJ6PLAMXy5fsKpFmFor2tRfCzrfnggTXu2YOzzK7q62bmqVdmufEo
5pT8igNcLpvZxk5uBDvhakObMym9mX3rAEBoe8PwttggMYiiw7NuJKO4MqD1llGkW
6aVM8U2ATsCun1IKHrRxynkE1/MJ86VHeYYX8GZt2YA8z+GuzylIOKcMH6JAWzMwA
7Gbatw6QwizOhr9iMjZ0B26TE3X8LvW84wwIBAg==
8-----END DH PARAMETERS-----
9-----BEGIN DH PARAMETERS-----
10MIIBCAKCAQEArtA3w73zP6Lu3EOQtwogiXt3AXXpuS6yD4BhzNS1pZFyPHk0/an5
118ydEkPhQZHKDW+BZJxxPLANaTudWo2YT8TgtvUdN6KSgMiEi6McwqDw+SADuvW+F
12SKUYFxG6VFIxyEP6xBdf+vhJxEDbRG2EYsHDRRtJ76gp9cSKTHusf2R+4AAVGqnt
13gRAbNqtcOar/7FSj+Pl8G3v0Bty0LcCSpbqgYlnv6z+rErQmmC6PPvSz97TDMCok
14yKpCE9hFA1zkqK3TH4FmFvGeIaXJUIBZf4mArWuBTjWFW3nmhESRUn1VK3K3x42N
15a5k6c2+EhrMFiLjxuH6JZoqL0/E93FF9SwIBAg==
16-----END DH PARAMETERS-----
diff --git a/src/lib/libcrypto/dh/dh4096.pem b/src/lib/libcrypto/dh/dh4096.pem
deleted file mode 100644
index 390943a21d..0000000000
--- a/src/lib/libcrypto/dh/dh4096.pem
+++ /dev/null
@@ -1,14 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MIICCAKCAgEA/urRnb6vkPYc/KEGXWnbCIOaKitq7ySIq9dTH7s+Ri59zs77zty7
3vfVlSe6VFTBWgYjD2XKUFmtqq6CqXMhVX5ElUDoYDpAyTH85xqNFLzFC7nKrff/H
4TFKNttp22cZE9V0IPpzedPfnQkE7aUdmF9JnDyv21Z/818O93u1B4r0szdnmEvEF
5bKuIxEHX+bp0ZR7RqE1AeifXGJX3d6tsd2PMAObxwwsv55RGkn50vHO4QxtTARr1
6rRUV5j3B3oPMgC7Offxx+98Xn45B1/G0Prp11anDsR1PGwtaCYipqsvMwQUSJtyE
7EOQWk+yFkeMe4vWv367eEi0Sd/wnC+TSXBE3pYvpYerJ8n1MceI5GQTdarJ77OW9
8bGTHmxRsLSCM1jpLdPja5jjb4siAa6EHc4qN9c/iFKS3PQPJEnX7pXKBRs5f7AF3
9W3RIGt+G9IVNZfXaS7Z/iCpgzgvKCs0VeqN38QsJGtC1aIkwOeyjPNy2G6jJ4yqH
10ovXYt/0mc00vCWeSNS1wren0pR2EiLxX0ypjjgsU1mk/Z3b/+zVf7fZSIB+nDLjb
11NPtUlJCVGnAeBK1J1nG3TQicqowOXoM6ISkdaXj5GPJdXHab2+S7cqhKGv5qC7rR
12jT6sx7RUr0CNTxzLI7muV2/a4tGmj0PSdXQdsZ7tw7gbXlaWT1+MM2MCAQI=
13-----END DH PARAMETERS-----
14
diff --git a/src/lib/libcrypto/dh/dh512.pem b/src/lib/libcrypto/dh/dh512.pem
deleted file mode 100644
index 0a4d863ebe..0000000000
--- a/src/lib/libcrypto/dh/dh512.pem
+++ /dev/null
@@ -1,4 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MEYCQQDaWDwW2YUiidDkr3VvTMqS3UvlM7gE+w/tlO+cikQD7VdGUNNpmdsp13Yn
3a6LT1BLiGPTdHghM9tgAPnxHdOgzAgEC
4-----END DH PARAMETERS-----
diff --git a/src/lib/libcrypto/dh/example b/src/lib/libcrypto/dh/example
deleted file mode 100644
index 16a33d2910..0000000000
--- a/src/lib/libcrypto/dh/example
+++ /dev/null
@@ -1,50 +0,0 @@
1From owner-cypherpunks@toad.com Mon Sep 25 10:50:51 1995
2Received: from minbne.mincom.oz.au by orb.mincom.oz.au with SMTP id AA10562
3 (5.65c/IDA-1.4.4 for eay); Wed, 27 Sep 1995 19:41:55 +1000
4Received: by minbne.mincom.oz.au id AA19958
5 (5.65c/IDA-1.4.4 for eay@orb.mincom.oz.au); Wed, 27 Sep 1995 19:34:59 +1000
6Received: from relay3.UU.NET by bunyip.cc.uq.oz.au with SMTP (PP);
7 Wed, 27 Sep 1995 19:13:05 +1000
8Received: from toad.com by relay3.UU.NET with SMTP id QQzizb16156;
9 Wed, 27 Sep 1995 04:48:46 -0400
10Received: by toad.com id AA07905; Tue, 26 Sep 95 06:31:45 PDT
11Received: from by toad.com id AB07851; Tue, 26 Sep 95 06:31:40 PDT
12Received: from servo.qualcomm.com (servo.qualcomm.com [129.46.128.14])
13 by cygnus.com (8.6.12/8.6.9) with ESMTP id RAA18442
14 for <cypherpunks@toad.com>; Mon, 25 Sep 1995 17:52:47 -0700
15Received: (karn@localhost) by servo.qualcomm.com (8.6.12/QC-BSD-2.5.1)
16 id RAA14732; Mon, 25 Sep 1995 17:50:51 -0700
17Date: Mon, 25 Sep 1995 17:50:51 -0700
18From: Phil Karn <karn@qualcomm.com>
19Message-Id: <199509260050.RAA14732@servo.qualcomm.com>
20To: cypherpunks@toad.com, ipsec-dev@eit.com
21Subject: Primality verification needed
22Sender: owner-cypherpunks@toad.com
23Precedence: bulk
24Status: RO
25X-Status:
26
27Hi. I've generated a 2047-bit "strong" prime number that I would like to
28use with Diffie-Hellman key exchange. I assert that not only is this number
29'p' prime, but so is (p-1)/2.
30
31I've used the mpz_probab_prime() function in the Gnu Math Package (GMP) version
321.3.2 to test this number. This function uses the Miller-Rabin primality test.
33However, to increase my confidence that this number really is a strong prime,
34I'd like to ask others to confirm it with other tests. Here's the number in hex:
35
3672a925f760b2f954ed287f1b0953f3e6aef92e456172f9fe86fdd8822241b9c9788fbc289982743e
37fbcd2ccf062b242d7a567ba8bbb40d79bca7b8e0b6c05f835a5b938d985816bc648985adcff5402a
38a76756b36c845a840a1d059ce02707e19cf47af0b5a882f32315c19d1b86a56c5389c5e9bee16b65
39fde7b1a8d74a7675de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f2
403d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0
41ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef3
4256a05180c3bec7ddd5ef6fe76b1f717b
43
44The generator, g, for this prime is 2.
45
46Thanks!
47
48Phil Karn
49
50
diff --git a/src/lib/libcrypto/dh/generate b/src/lib/libcrypto/dh/generate
deleted file mode 100644
index 5d407231df..0000000000
--- a/src/lib/libcrypto/dh/generate
+++ /dev/null
@@ -1,65 +0,0 @@
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
diff --git a/src/lib/libssl/src/crypto/dh/dh1024.pem b/src/lib/libssl/src/crypto/dh/dh1024.pem
deleted file mode 100644
index 81d43f6a3e..0000000000
--- a/src/lib/libssl/src/crypto/dh/dh1024.pem
+++ /dev/null
@@ -1,5 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MIGHAoGBAJf2QmHKtQXdKCjhPx1ottPb0PMTBH9A6FbaWMsTuKG/K3g6TG1Z1fkq
3/Gz/PWk/eLI9TzFgqVAuPvr3q14a1aZeVUMTgo2oO5/y2UHe6VaJ+trqCTat3xlx
4/mNbIK9HA2RgPC3gWfVLZQrY+gz3ASHHR5nXWHEyvpuZm7m3h+irAgEC
5-----END DH PARAMETERS-----
diff --git a/src/lib/libssl/src/crypto/dh/dh192.pem b/src/lib/libssl/src/crypto/dh/dh192.pem
deleted file mode 100644
index 521c07271d..0000000000
--- a/src/lib/libssl/src/crypto/dh/dh192.pem
+++ /dev/null
@@ -1,3 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MB4CGQDUoLoCULb9LsYm5+/WN992xxbiLQlEuIsCAQM=
3-----END DH PARAMETERS-----
diff --git a/src/lib/libssl/src/crypto/dh/dh2048.pem b/src/lib/libssl/src/crypto/dh/dh2048.pem
deleted file mode 100644
index 295460f508..0000000000
--- a/src/lib/libssl/src/crypto/dh/dh2048.pem
+++ /dev/null
@@ -1,16 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MIIBCAKCAQEA7ZKJNYJFVcs7+6J2WmkEYb8h86tT0s0h2v94GRFS8Q7B4lW9aG9o
3AFO5Imov5Jo0H2XMWTKKvbHbSe3fpxJmw/0hBHAY8H/W91hRGXKCeyKpNBgdL8sh
4z22SrkO2qCnHJ6PLAMXy5fsKpFmFor2tRfCzrfnggTXu2YOzzK7q62bmqVdmufEo
5pT8igNcLpvZxk5uBDvhakObMym9mX3rAEBoe8PwttggMYiiw7NuJKO4MqD1llGkW
6aVM8U2ATsCun1IKHrRxynkE1/MJ86VHeYYX8GZt2YA8z+GuzylIOKcMH6JAWzMwA
7Gbatw6QwizOhr9iMjZ0B26TE3X8LvW84wwIBAg==
8-----END DH PARAMETERS-----
9-----BEGIN DH PARAMETERS-----
10MIIBCAKCAQEArtA3w73zP6Lu3EOQtwogiXt3AXXpuS6yD4BhzNS1pZFyPHk0/an5
118ydEkPhQZHKDW+BZJxxPLANaTudWo2YT8TgtvUdN6KSgMiEi6McwqDw+SADuvW+F
12SKUYFxG6VFIxyEP6xBdf+vhJxEDbRG2EYsHDRRtJ76gp9cSKTHusf2R+4AAVGqnt
13gRAbNqtcOar/7FSj+Pl8G3v0Bty0LcCSpbqgYlnv6z+rErQmmC6PPvSz97TDMCok
14yKpCE9hFA1zkqK3TH4FmFvGeIaXJUIBZf4mArWuBTjWFW3nmhESRUn1VK3K3x42N
15a5k6c2+EhrMFiLjxuH6JZoqL0/E93FF9SwIBAg==
16-----END DH PARAMETERS-----
diff --git a/src/lib/libssl/src/crypto/dh/dh4096.pem b/src/lib/libssl/src/crypto/dh/dh4096.pem
deleted file mode 100644
index 390943a21d..0000000000
--- a/src/lib/libssl/src/crypto/dh/dh4096.pem
+++ /dev/null
@@ -1,14 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MIICCAKCAgEA/urRnb6vkPYc/KEGXWnbCIOaKitq7ySIq9dTH7s+Ri59zs77zty7
3vfVlSe6VFTBWgYjD2XKUFmtqq6CqXMhVX5ElUDoYDpAyTH85xqNFLzFC7nKrff/H
4TFKNttp22cZE9V0IPpzedPfnQkE7aUdmF9JnDyv21Z/818O93u1B4r0szdnmEvEF
5bKuIxEHX+bp0ZR7RqE1AeifXGJX3d6tsd2PMAObxwwsv55RGkn50vHO4QxtTARr1
6rRUV5j3B3oPMgC7Offxx+98Xn45B1/G0Prp11anDsR1PGwtaCYipqsvMwQUSJtyE
7EOQWk+yFkeMe4vWv367eEi0Sd/wnC+TSXBE3pYvpYerJ8n1MceI5GQTdarJ77OW9
8bGTHmxRsLSCM1jpLdPja5jjb4siAa6EHc4qN9c/iFKS3PQPJEnX7pXKBRs5f7AF3
9W3RIGt+G9IVNZfXaS7Z/iCpgzgvKCs0VeqN38QsJGtC1aIkwOeyjPNy2G6jJ4yqH
10ovXYt/0mc00vCWeSNS1wren0pR2EiLxX0ypjjgsU1mk/Z3b/+zVf7fZSIB+nDLjb
11NPtUlJCVGnAeBK1J1nG3TQicqowOXoM6ISkdaXj5GPJdXHab2+S7cqhKGv5qC7rR
12jT6sx7RUr0CNTxzLI7muV2/a4tGmj0PSdXQdsZ7tw7gbXlaWT1+MM2MCAQI=
13-----END DH PARAMETERS-----
14
diff --git a/src/lib/libssl/src/crypto/dh/dh512.pem b/src/lib/libssl/src/crypto/dh/dh512.pem
deleted file mode 100644
index 0a4d863ebe..0000000000
--- a/src/lib/libssl/src/crypto/dh/dh512.pem
+++ /dev/null
@@ -1,4 +0,0 @@
1-----BEGIN DH PARAMETERS-----
2MEYCQQDaWDwW2YUiidDkr3VvTMqS3UvlM7gE+w/tlO+cikQD7VdGUNNpmdsp13Yn
3a6LT1BLiGPTdHghM9tgAPnxHdOgzAgEC
4-----END DH PARAMETERS-----
diff --git a/src/lib/libssl/src/crypto/dh/example b/src/lib/libssl/src/crypto/dh/example
deleted file mode 100644
index 16a33d2910..0000000000
--- a/src/lib/libssl/src/crypto/dh/example
+++ /dev/null
@@ -1,50 +0,0 @@
1From owner-cypherpunks@toad.com Mon Sep 25 10:50:51 1995
2Received: from minbne.mincom.oz.au by orb.mincom.oz.au with SMTP id AA10562
3 (5.65c/IDA-1.4.4 for eay); Wed, 27 Sep 1995 19:41:55 +1000
4Received: by minbne.mincom.oz.au id AA19958
5 (5.65c/IDA-1.4.4 for eay@orb.mincom.oz.au); Wed, 27 Sep 1995 19:34:59 +1000
6Received: from relay3.UU.NET by bunyip.cc.uq.oz.au with SMTP (PP);
7 Wed, 27 Sep 1995 19:13:05 +1000
8Received: from toad.com by relay3.UU.NET with SMTP id QQzizb16156;
9 Wed, 27 Sep 1995 04:48:46 -0400
10Received: by toad.com id AA07905; Tue, 26 Sep 95 06:31:45 PDT
11Received: from by toad.com id AB07851; Tue, 26 Sep 95 06:31:40 PDT
12Received: from servo.qualcomm.com (servo.qualcomm.com [129.46.128.14])
13 by cygnus.com (8.6.12/8.6.9) with ESMTP id RAA18442
14 for <cypherpunks@toad.com>; Mon, 25 Sep 1995 17:52:47 -0700
15Received: (karn@localhost) by servo.qualcomm.com (8.6.12/QC-BSD-2.5.1)
16 id RAA14732; Mon, 25 Sep 1995 17:50:51 -0700
17Date: Mon, 25 Sep 1995 17:50:51 -0700
18From: Phil Karn <karn@qualcomm.com>
19Message-Id: <199509260050.RAA14732@servo.qualcomm.com>
20To: cypherpunks@toad.com, ipsec-dev@eit.com
21Subject: Primality verification needed
22Sender: owner-cypherpunks@toad.com
23Precedence: bulk
24Status: RO
25X-Status:
26
27Hi. I've generated a 2047-bit "strong" prime number that I would like to
28use with Diffie-Hellman key exchange. I assert that not only is this number
29'p' prime, but so is (p-1)/2.
30
31I've used the mpz_probab_prime() function in the Gnu Math Package (GMP) version
321.3.2 to test this number. This function uses the Miller-Rabin primality test.
33However, to increase my confidence that this number really is a strong prime,
34I'd like to ask others to confirm it with other tests. Here's the number in hex:
35
3672a925f760b2f954ed287f1b0953f3e6aef92e456172f9fe86fdd8822241b9c9788fbc289982743e
37fbcd2ccf062b242d7a567ba8bbb40d79bca7b8e0b6c05f835a5b938d985816bc648985adcff5402a
38a76756b36c845a840a1d059ce02707e19cf47af0b5a882f32315c19d1b86a56c5389c5e9bee16b65
39fde7b1a8d74a7675de9b707d4c5a4633c0290c95ff30a605aeb7ae864ff48370f13cf01d49adb9f2
403d19a439f753ee7703cf342d87f431105c843c78ca4df639931f3458fae8a94d1687e99a76ed99d0
41ba87189f42fd31ad8262c54a8cf5914ae6c28c540d714a5f6087a171fb74f4814c6f968d72386ef3
4256a05180c3bec7ddd5ef6fe76b1f717b
43
44The generator, g, for this prime is 2.
45
46Thanks!
47
48Phil Karn
49
50
diff --git a/src/lib/libssl/src/crypto/dh/generate b/src/lib/libssl/src/crypto/dh/generate
deleted file mode 100644
index 5d407231df..0000000000
--- a/src/lib/libssl/src/crypto/dh/generate
+++ /dev/null
@@ -1,65 +0,0 @@
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