projects / u / mdw / catacomb / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Add an internal-representation no-op function.
[u/mdw/catacomb] / bbs-rand.c
CommitLineData
2c52abe6 1/* -*-c-*-
2 *
f1140c41 3 * $Id: bbs-rand.c,v 1.4 2001/02/03 12:00:29 mdw Exp $
2c52abe6 4 *
5 * Blum-Blum-Shub secure random number generator
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-rand.c,v $
f1140c41 33 * Revision 1.4 2001/02/03 12:00:29 mdw
34 * Now @mp_drop@ checks its argument is non-NULL before attempting to free
35 * it. Note that the macro version @MP_DROP@ doesn't do this.
36 *
fbdfd34e 37 * Revision 1.3 2000/06/17 10:45:21 mdw
38 * Typesetting fixes. Advertise random number generator strength. Use
39 * secure arena for memory allocation.
40 *
4ab1268f 41 * Revision 1.2 1999/12/13 15:34:01 mdw
42 * Add support for seeding from a generic pseudorandom source.
43 *
2c52abe6 44 * Revision 1.1 1999/12/10 23:14:59 mdw
45 * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
46 *
47 */
48
49/*----- Header files ------------------------------------------------------*/
50
51#include <stdarg.h>
52#include <stdlib.h>
53#include <string.h>
54
55#include <mLib/bits.h>
56#include <mLib/sub.h>
57
fbdfd34e 58#include "arena.h"
2c52abe6 59#include "bbs.h"
60#include "grand.h"
61#include "mp.h"
62#include "mpbarrett.h"
63#include "mpint.h"
4ab1268f 64#include "mprand.h"
fbdfd34e 65#include "paranoia.h"
2c52abe6 66
67/*----- Main code ---------------------------------------------------------*/
68
69/* --- @bbs_create@ --- *
70 *
71 * Arguments: @bbs *b@ = pointer to BBS generator state to initialize
72 * @mp *m@ = modulus (must be a Blum integer)
73 * @mp *x@ = initial seed for generator
74 *
75 * Returns: ---
76 *
77 * Use: Initializes a BBS generator. The generator is stepped once
78 * after initialization, as for @bbs_seed@.
79 */
80
81void bbs_create(bbs *b, mp *m, mp *x)
82{
83 mpw kw;
84 mp k;
85
86 mpbarrett_create(&b->mb, m);
87 kw = mp_bits(m) - 1;
88 mp_build(&k, &kw, &kw + 1);
89 b->k = mp_bits(&k) - 1;
90 b->x = 0;
91 bbs_seed(b, x);
92}
93
94/* --- @bbs_destroy@ --- *
95 *
96 * Arguments: @bbs *b@ = pointer to BBS generator state
97 *
98 * Returns: ---
99 *
100 * Use: Destroys a generator state when it's no longer wanted.
101 */
102
103void bbs_destroy(bbs *b)
104{
105 mp_drop(b->x);
106 mpbarrett_destroy(&b->mb);
107}
108
109/* --- @bbs_step@ --- *
110 *
111 * Arguments: @bbs *b@ = pointer to BBS generator state
112 *
113 * Returns: ---
114 *
115 * Use: Steps the generator once. This isn't too useful in client
116 * code.
117 */
118
119void bbs_step(bbs *b)
120{
121 mp *x = b->x;
122 x = mp_sqr(x, x);
123 x = mpbarrett_reduce(&b->mb, x, x);
124 b->x = x;
125 b->b = b->k;
126 b->r = b->x->v[0];
127}
128
129/* --- @bbs_set@ --- *
130 *
131 * Arguments: @bbs *b@ = pointer to BBS generator state
132 * @mp *x@ = new residue to set
133 *
134 * Returns: ---
135 *
136 * Use: Sets a new quadratic residue. The generator is stepped once.
137 */
138
139void bbs_set(bbs *b, mp *x)
140{
f1140c41 141 mp_drop(b->x);
2c52abe6 142 b->x = MP_COPY(x);
143 bbs_step(b);
144}
145
146/* --- @bbs_seed@ --- *
147 *
148 * Arguments: @bbs *b@ = pointer to BBS generator state
149 * @mp *x@ = new seed to set
150 *
151 * Returns ---
152 *
153 * Use: Sets a new seed. The generator is stepped until the residue
154 * has clearly wrapped around.
155 */
156
157void bbs_seed(bbs *b, mp *x)
158{
159 mp *y;
160 x = MP_COPY(x);
161 for (;;) {
162 y = mp_sqr(MP_NEW, x);
163 y = mpbarrett_reduce(&b->mb, y, y);
164 if (MP_CMP(y, <, x))
165 break;
166 mp_drop(x);
167 x = y;
168 }
169 mp_drop(x);
170 bbs_set(b, y);
171 mp_drop(y);
172}
173
174/* --- @bbs_bits@ --- *
175 *
176 * Arguments: @bbs *b@ = pointer to BBS generator state
177 * @unsigned bits@ = number of bits wanted
178 *
179 * Returns: Bits extracted from the BBS generator.
180 *
181 * Use: Extracts a requested number of bits from the BBS generator.
182 */
183
184uint32 bbs_bits(bbs *b, unsigned bits)
185{
186 uint32 x = 0;
187 mpw m;
188
189 /* --- Keep turning the handle until there's enough in the reservoir --- */
190
191 while (bits >= b->b) {
192 bits -= b->b;
193 m = (1 << b->b) - 1;
194 x |= (b->r & m) << bits;
195 bbs_step(b);
196 }
197
198 /* --- Extract the last few bits needed --- */
199
200 if (bits) {
201 m = (1 << bits) - 1;
202 b->b -= bits;
203 x |= (b->r >> b->b) & m;
204 }
205
206 /* --- Done --- */
207
208 return (x);
209}
210
211/* --- @bbs_wrap@ --- *
212 *
213 * Arguments: @bbs *b@ = pointer to BBS generator state
214 *
215 * Returns: ---
216 *
217 * Use: Steps the generator if any of the reservoir bits are used.
218 * This can be used to `wrap up' after a Blum-Goldwasser
219 * encryption, for example, producing the final value to be sent
220 * along with the ciphertext.
221 *
222 * If a generator is seeded, %$b$% bits are extracted, and then
223 * @bbs_wrap@ is called, the generator will have been stepped
fbdfd34e 224 * %$\lceil b/k \rceil$% times.
2c52abe6 225 */
226
227void bbs_wrap(bbs *b)
228{
229 if (b->b < b->k)
230 bbs_step(b);
231}
232
233/*----- Generic random number generator interface -------------------------*/
234
235typedef struct gctx {
236 grand r;
237 bbs b;
238} gctx;
239
240static void gdestroy(grand *r)
241{
242 gctx *g = (gctx *)r;
243 bbs_destroy(&g->b);
fbdfd34e 244 BURN(*g);
245 S_DESTROY(g);
2c52abe6 246}
247
248static int gmisc(grand *r, unsigned op, ...)
249{
250 gctx *g = (gctx *)r;
251 va_list ap;
252 int rc = 0;
253 va_start(ap, op);
254
255 switch (op) {
256 case GRAND_CHECK:
257 switch (va_arg(ap, unsigned)) {
258 case GRAND_CHECK:
259 case GRAND_SEEDINT:
260 case GRAND_SEEDUINT32:
261 case GRAND_SEEDMP:
4ab1268f 262 case GRAND_SEEDRAND:
2c52abe6 263 case BBS_SET:
264 rc = 1;
265 break;
266 default:
267 rc = 0;
268 break;
269 }
270 break;
271 case GRAND_SEEDINT: {
272 mp *x = mp_fromuint(MP_NEW, va_arg(ap, unsigned));
273 bbs_seed(&g->b, x);
274 mp_drop(x);
275 } break;
276 case GRAND_SEEDUINT32: {
277 mp *x = mp_fromuint32(MP_NEW, va_arg(ap, uint32));
278 bbs_seed(&g->b, x);
279 mp_drop(x);
280 } break;
281 case GRAND_SEEDMP:
282 bbs_seed(&g->b, va_arg(ap, mp *));
283 break;
4ab1268f 284 case GRAND_SEEDRAND: {
285 grand *rr = va_arg(ap, grand *);
286 mp *m = mprand(MP_NEW, mp_bits(g->b.mb.m) - 1, rr, 0);
287 bbs_seed(&g->b, m);
288 mp_drop(m);
289 } break;
2c52abe6 290 case BBS_SET:
291 bbs_set(&g->b, va_arg(ap, mp *));
292 break;
293 default:
294 GRAND_BADOP;
295 break;
296 }
297
298 va_end(ap);
299 return (rc);
300}
301
302static octet gbyte(grand *r)
303{
304 gctx *g = (gctx *)r;
305 return (bbs_bits(&g->b, 8));
306}
307
308static uint32 gword(grand *r)
309{
310 gctx *g = (gctx *)r;
311 return (bbs_bits(&g->b, 32));
312}
313
314static const grand_ops gops = {
315 "bbs",
fbdfd34e 316 GRAND_CRYPTO, 0,
2c52abe6 317 gmisc, gdestroy,
318 gword, gbyte, gword, grand_range, grand_fill
319};
320
321/* --- @bbs_rand@ --- *
322 *
323 * Arguments: @mp *m@ = modulus
324 * @mp *x@ = initial seed
325 *
326 * Returns: Pointer to a generic generator.
327 *
328 * Use: Constructs a generic generator interface over a
329 * Blum-Blum-Shub generator.
330 */
331
332grand *bbs_rand(mp *m, mp *x)
333{
fbdfd34e 334 gctx *g = S_CREATE(gctx);
2c52abe6 335 g->r.ops = &gops;
336 bbs_create(&g->b, m, x);
337 return (&g->r);
338}
339
340/*----- Test rig ----------------------------------------------------------*/
341
342#ifdef TEST_RIG
343
344static int verify(dstr *v)
345{
346 mp *n = *(mp **)v[0].buf;
347 mp *x = *(mp **)v[1].buf;
348 grand *b = bbs_rand(n, x);
349 dstr d = DSTR_INIT;
350 int ok = 1;
351
352 dstr_ensure(&d, v[2].len);
353 b->ops->fill(b, d.buf, v[2].len);
354 d.len = v[2].len;
355 if (memcmp(d.buf, v[2].buf, v[2].len) != 0) {
356 fputs("\n*** bbs failure\n", stderr);
357 fputs("n = ", stderr); mp_writefile(n, stderr, 10); fputc('\n', stderr);
358 fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
359 fputs("expected = ", stderr); type_hex.dump(&v[2], stderr);
360 fputc('\n', stderr);
361 fputs(" found = ", stderr); type_hex.dump(&d, stderr);
362 fputc('\n', stderr);
363 fprintf(stderr, "k = %u\n", ((gctx *)b)->b.k);
364 ok = 0;
365 }
366 b->ops->destroy(b);
367 mp_drop(x);
368 mp_drop(n);
369 dstr_destroy(&d);
370 assert(mparena_count(MPARENA_GLOBAL) == 0);
371 return (ok);
372}
373
374static test_chunk tests[] = {
375 { "bbs", verify, { &type_mp, &type_mp, &type_hex, 0 } },
376 { 0, 0, { 0 } }
377};
378
379int main(int argc, char *argv[])
380{
381 sub_init();
382 test_run(argc, argv, tests, SRCDIR "/tests/bbs");
383 return (0);
384}
385
386#endif
387
388/*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library (downstream of http://git.distorted.org.uk/~mdw/catacomb/)