2c52abe6 |
1 | /* -*-c-*- |
2 | * |
3 | * $Id: bbs-gen.c,v 1.1 1999/12/10 23:14:59 mdw Exp $ |
4 | * |
5 | * Generate Blum integers |
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: bbs-gen.c,v $ |
33 | * Revision 1.1 1999/12/10 23:14:59 mdw |
34 | * Blum-Blum-Shub generator, and Blum-Goldwasser encryption. |
35 | * |
36 | */ |
37 | |
38 | /*----- Header files ------------------------------------------------------*/ |
39 | |
40 | #include <stdio.h> |
41 | #include <stdlib.h> |
42 | #include <string.h> |
43 | |
44 | #include "bbs.h" |
45 | #include "fibrand.h" |
46 | #include "mp.h" |
47 | #include "mprand.h" |
48 | #include "pgen.h" |
49 | #include "rabin.h" |
50 | |
51 | /*----- Main code ---------------------------------------------------------*/ |
52 | |
53 | /* --- @bbs_gen@ --- * |
54 | * |
55 | * Arguments: @bbs_params *bp@ = pointer to parameter block |
56 | * @mp *p, *q@ = initial numbers to search from |
57 | * @size_t n@ = number of attempts to make |
58 | * @void (*proc)(int ev, mp *m, void *p)@ = event handler |
59 | * @void *arg@ = argument for event handler |
60 | * |
61 | * Returns: Zero if all went well, otherwise an event code which explains |
62 | * the problem. |
63 | * |
64 | * Use: Finds two prime numbers %$p'$% and %$q'$% such that both are |
65 | * congruent to %$3 \bmod 4$%, and $(p - 1)/2$% and |
66 | * %$(q - 1)/2$% have no common factors. The product %$n = pq$% |
67 | * is eminently suitable for use as a modulus in a Blum-Blum- |
68 | * Shub pseudorandom bit generator. |
69 | */ |
70 | |
71 | int bbs_gen(bbs_params *bp, mp *p, mp *q, size_t n, |
72 | int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg) |
73 | { |
74 | pgen px, py; |
75 | mp *pp; |
76 | mp *g = MP_NEW; |
77 | grand *gr = fibrand_create(0); |
78 | int rcx, rcy; |
79 | int fail = BBSEV_OK; |
80 | size_t sz; |
81 | |
82 | /* --- Initialize @p@ and @q@ --- * |
83 | * |
84 | * Divide both by two, and make the results odd. |
85 | */ |
86 | |
87 | p = mp_lsr(MP_NEW, p, 1); p->v[0] |= 1; |
88 | q = mp_lsr(MP_NEW, q, 1); q->v[0] |= 1; |
89 | |
90 | /* --- Set up the search for @p@ --- * |
91 | * |
92 | * I want a prime %$p$% such that %$(p - 1)/2$% has no small factors. |
93 | */ |
94 | |
95 | rcx = pgen_create(&px, p); mp_drop(p); |
96 | rcy = pgen_muladd(&py, &px, 2, 1); |
97 | |
98 | if (proc && (fail = proc(BBSEV_FINDP, 0, arg)) != 0) |
99 | goto fail_0; |
100 | |
101 | sz = mp_bits(py.m); |
102 | for (;;) { |
103 | if (rcx != PGEN_COMPOSITE && rcy != PGEN_COMPOSITE) { |
104 | if (rcy != PGEN_PRIME) { |
105 | rabin r; |
106 | int i; |
107 | |
108 | if (proc && (fail = proc(BBSEV_TRYP, py.m, arg)) != 0) |
109 | break; |
110 | rabin_create(&r, py.m); |
111 | for (i = 0; i < 5; i++) { |
112 | g = mprand(g, sz, gr, 1); |
113 | if ((rcy = rabin_test(&r, g)) == PGEN_COMPOSITE) |
114 | break; |
115 | if (proc && (fail = proc(BBSEV_PASSP, py.m, arg)) != 0) |
116 | break; |
117 | } |
118 | rabin_destroy(&r); |
119 | if (fail) |
120 | goto fail_0; |
121 | if (i < 5) { |
122 | if (proc && (fail = proc(BBSEV_FAILP, py.m, arg)) != 0) |
123 | goto fail_0; |
124 | if (n) { |
125 | n--; |
126 | if (!n) { |
127 | fail = BBSEV_FAILP; |
128 | goto fail_0; |
129 | } |
130 | } |
131 | } |
132 | } |
133 | |
134 | if (rcy != PGEN_COMPOSITE) |
135 | break; |
136 | } |
137 | rcx = pgen_step(&px, 2); |
138 | rcy = pgen_step(&py, 4); |
139 | } |
140 | |
141 | if (proc && (fail = proc(BBSEV_GOODP, py.m, arg)) != 0) |
142 | goto fail_0; |
143 | |
144 | /* --- I now have a @p@ (and a %$(p - 1)/2$%) --- */ |
145 | |
146 | pp = MP_COPY(px.m); pgen_destroy(&px); |
147 | p = MP_COPY(py.m); pgen_destroy(&py); |
148 | |
149 | /* --- Next trick is to generate @q@ --- * |
150 | * |
151 | * I don't care about small factors of %$(q - 1)/2$%, just that it's |
152 | * relatively prime to %$(p - 1)/2$%. |
153 | */ |
154 | |
155 | { |
156 | mp *m = mp_lsl(MP_NEW, q, 1); |
157 | m->v[0] |= 1; |
158 | rcx = pgen_create(&px, m); |
159 | mp_drop(m); |
160 | } |
161 | |
162 | if (proc && (fail = proc(BBSEV_FINDQ, 0, arg)) != 0) |
163 | goto fail_1; |
164 | |
165 | for (;;) { |
166 | if (rcx != PGEN_COMPOSITE) { |
167 | int ok; |
168 | |
169 | /* --- Ensure that %$(p - 1)/2$% and %$(q - 1)/2$% are coprime --- */ |
170 | |
171 | mp_gcd(&g, 0, 0, pp, q); |
172 | ok = MP_CMP(g, ==, MP_ONE); |
173 | |
174 | if (ok && rcx != PGEN_PRIME) { |
175 | rabin r; |
176 | int i; |
177 | |
178 | if (proc && (fail = proc(BBSEV_TRYQ, px.m, arg)) != 0) |
179 | break; |
180 | rabin_create(&r, px.m); |
181 | for (i = 0; i < 5; i++) { |
182 | g = mprand(g, sz, gr, 1); |
183 | if ((rcx = rabin_test(&r, g)) == PGEN_COMPOSITE) |
184 | break; |
185 | if (proc && (fail = proc(BBSEV_PASSQ, px.m, arg)) != 0) |
186 | break; |
187 | } |
188 | rabin_destroy(&r); |
189 | if (fail) |
190 | goto fail_1; |
191 | if (i < 5) { |
192 | if (proc && (fail = proc(BBSEV_FAILQ, px.m, arg)) != 0) |
193 | goto fail_1; |
194 | if (n) { |
195 | n--; |
196 | if (!n) { |
197 | fail = BBSEV_FAILQ; |
198 | goto fail_1; |
199 | } |
200 | } |
201 | } |
202 | } |
203 | |
204 | if (ok && rcx != PGEN_COMPOSITE) |
205 | break; |
206 | } |
207 | |
208 | q = mp_add(q, q, MP_TWO); |
209 | rcx = pgen_step(&px, 4); |
210 | } |
211 | |
212 | if (proc && (fail = proc(BBSEV_GOODQ, px.m, arg)) != 0) |
213 | goto fail_1; |
214 | |
215 | /* --- Done --- */ |
216 | |
217 | mp_drop(g); |
218 | mp_drop(q); |
219 | mp_drop(pp); |
220 | q = MP_COPY(px.m); |
221 | bp->p = p; |
222 | bp->q = q; |
223 | pgen_destroy(&px); |
224 | bp->n = mp_mul(MP_NEW, p, q); |
225 | gr->ops->destroy(gr); |
226 | return (0); |
227 | |
228 | /* --- Failed --- */ |
229 | |
230 | fail_1: |
231 | pgen_destroy(&px); |
232 | mp_drop(p); |
233 | mp_drop(pp); |
234 | mp_drop(g); |
235 | gr->ops->destroy(gr); |
236 | return (fail); |
237 | |
238 | fail_0: |
239 | if (g) |
240 | mp_drop(g); |
241 | pgen_destroy(&px); |
242 | pgen_destroy(&py); |
243 | mp_drop(q); |
244 | gr->ops->destroy(gr); |
245 | return (fail); |
246 | } |
247 | |
248 | /*----- That's all, folks -------------------------------------------------*/ |