44c240ee |
1 | /* -*-c-*- |
2 | * |
3 | * $Id: dh-prime.c,v 1.1 1999/11/20 22:24:44 mdw Exp $ |
4 | * |
5 | * Generate (safe) Diffie-Hellman primes |
6 | * |
7 | * (c) 1999 Straylight/Edgeware |
8 | */ |
9 | |
10 | /*----- Licensing notice --------------------------------------------------* |
11 | * |
12 | * This file is part of Catacomb. |
13 | * |
14 | * Catacomb is free software; you can redistribute it and/or modify |
15 | * it under the terms of the GNU Library General Public License as |
16 | * published by the Free Software Foundation; either version 2 of the |
17 | * License, or (at your option) any later version. |
18 | * |
19 | * Catacomb is distributed in the hope that it will be useful, |
20 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
21 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
22 | * GNU Library General Public License for more details. |
23 | * |
24 | * You should have received a copy of the GNU Library General Public |
25 | * License along with Catacomb; if not, write to the Free |
26 | * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, |
27 | * MA 02111-1307, USA. |
28 | */ |
29 | |
30 | /*----- Revision history --------------------------------------------------* |
31 | * |
32 | * $Log: dh-prime.c,v $ |
33 | * Revision 1.1 1999/11/20 22:24:44 mdw |
34 | * Add Diffie-Hellman support. |
35 | * |
36 | */ |
37 | |
38 | /*----- Header files ------------------------------------------------------*/ |
39 | |
40 | #include <stdio.h> |
41 | #include <stdlib.h> |
42 | #include <string.h> |
43 | |
44 | #include "dh.h" |
45 | #include "mp.h" |
46 | #include "pgen.h" |
47 | #include "rabin.h" |
48 | |
49 | /*----- Main code ---------------------------------------------------------*/ |
50 | |
51 | /* --- @dh_prime@ --- * |
52 | * |
53 | * Arguments: @mp *s@ = start point for search (must be odd) |
54 | * @size_t n@ = number of concerted attempts to make, or zero |
55 | * @void (*proc)(int ev, void *p)@ = event handler |
56 | * @void *p@ = argument for event handler |
57 | * |
58 | * Returns: A prime number %$p$% where %$p = 2q + 1$% for prime %$q$%. |
59 | * |
60 | * Use: Finds a safe prime by sequential search from a given starting |
61 | * point. If it fails, a null pointer is returned. |
62 | * |
63 | * The event handler is informed of the progress of the search. |
64 | * It may abort the search at any time by returning a nonzero |
65 | * value. |
66 | */ |
67 | |
68 | mp *dh_prime(mp *s, size_t n, |
69 | int (*proc)(int /*ev*/, void */*p*/), void *arg) |
70 | { |
71 | pgen pq, pp; |
72 | int rc_q, rc_p; |
73 | mpw bw; |
74 | mp b; |
75 | |
76 | /* --- Initialize prime generators --- */ |
77 | |
78 | rc_q = pgen_create(&pq, s); |
79 | rc_p = pgen_muladd(&pp, &pq, 2, 1); |
80 | mp_build(&b, &bw, &bw + 1); |
81 | |
82 | /* --- Now step along until something crops up --- */ |
83 | |
84 | for (;;) { |
85 | rabin rq, rp; |
86 | int i; |
87 | |
88 | /* --- Don't do expensive testing unless necessary --- */ |
89 | |
90 | if (rc_q == PGEN_PRIME && rc_p == PGEN_PRIME) |
91 | break; |
92 | if (rc_q == PGEN_COMPOSITE || rc_p == PGEN_COMPOSITE) |
93 | goto next; |
94 | |
95 | /* --- Initialize Rabin-Miller contexts --- */ |
96 | |
97 | if (rc_q == PGEN_MAYBE) |
98 | rabin_create(&rq, pq.m); |
99 | if (rc_p == PGEN_MAYBE) |
100 | rabin_create(&rp, pp.m); |
101 | |
102 | /* --- Now run tests on each in turn --- * |
103 | * |
104 | * On the sorts of modulus sizes which work well in discrete log |
105 | * problems, five tests should be sufficient. |
106 | */ |
107 | |
108 | for (i = 0; i < 5; i++) { |
109 | bw = ptab[i]; |
110 | if (rc_q == PGEN_MAYBE && |
111 | (rc_q = rabin_test(&rq, &b)) == PGEN_COMPOSITE) |
112 | break; |
113 | if (rc_p == PGEN_MAYBE && |
114 | (rc_p = rabin_test(&rp, &b)) == PGEN_COMPOSITE) |
115 | break; |
116 | if (proc && proc(DHEV_PASS, arg)) |
117 | break; |
118 | } |
119 | if (rc_q != PGEN_PRIME) |
120 | rabin_destroy(&rq); |
121 | if (rc_p != PGEN_PRIME) |
122 | rabin_destroy(&rp); |
123 | |
124 | /* --- If the tests passed, accept the numbers --- */ |
125 | |
126 | if (i >= 5) |
127 | break; |
128 | if (proc && proc(DHEV_FAIL, arg)) |
129 | goto fail; |
130 | if (n) { |
131 | n--; |
132 | if (!n) |
133 | goto fail; |
134 | } |
135 | |
136 | /* --- Step the contexts on --- */ |
137 | |
138 | next: |
139 | rc_q = pgen_step(&pq, 2); |
140 | rc_p = pgen_step(&pp, 4); |
141 | } |
142 | |
143 | /* --- Return a result --- */ |
144 | |
145 | { |
146 | mp *p = MP_COPY(pp.m); |
147 | pgen_destroy(&pq); |
148 | pgen_destroy(&pp); |
149 | return (p); |
150 | } |
151 | |
152 | /* --- Failure --- */ |
153 | |
154 | fail: |
155 | pgen_destroy(&pq); |
156 | pgen_destroy(&pp); |
157 | return (0); |
158 | } |
159 | |
160 | /*----- That's all, folks -------------------------------------------------*/ |