3 * Blum-Blum-Shub secure random number generator
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
34 #include <mLib/bits.h>
41 #include "mpbarrett.h"
46 /*----- Main code ---------------------------------------------------------*/
48 /* --- @bbs_create@ --- *
50 * Arguments: @bbs *b@ = pointer to BBS generator state to initialize
51 * @mp *m@ = modulus (must be a Blum integer)
52 * @mp *x@ = initial seed for generator
56 * Use: Initializes a BBS generator. The generator is stepped once
57 * after initialization, as for @bbs_seed@.
60 void bbs_create(bbs *b, mp *m, mp *x)
65 mpbarrett_create(&b->mb, m);
67 mp_build(&k, &kw, &kw + 1);
68 b->k = mp_bits(&k) - 1;
73 /* --- @bbs_destroy@ --- *
75 * Arguments: @bbs *b@ = pointer to BBS generator state
79 * Use: Destroys a generator state when it's no longer wanted.
82 void bbs_destroy(bbs *b)
85 mpbarrett_destroy(&b->mb);
88 /* --- @bbs_step@ --- *
90 * Arguments: @bbs *b@ = pointer to BBS generator state
94 * Use: Steps the generator once. This isn't too useful in client
102 x = mpbarrett_reduce(&b->mb, x, x);
108 /* --- @bbs_set@ --- *
110 * Arguments: @bbs *b@ = pointer to BBS generator state
111 * @mp *x@ = new residue to set
115 * Use: Sets a new quadratic residue. The generator is stepped once.
118 void bbs_set(bbs *b, mp *x)
125 /* --- @bbs_seed@ --- *
127 * Arguments: @bbs *b@ = pointer to BBS generator state
128 * @mp *x@ = new seed to set
132 * Use: Sets a new seed. The generator is stepped until the residue
133 * has clearly wrapped around.
136 void bbs_seed(bbs *b, mp *x)
141 y = mp_sqr(MP_NEW, x);
142 y = mpbarrett_reduce(&b->mb, y, y);
153 /* --- @bbs_bits@ --- *
155 * Arguments: @bbs *b@ = pointer to BBS generator state
156 * @unsigned bits@ = number of bits wanted
158 * Returns: Bits extracted from the BBS generator.
160 * Use: Extracts a requested number of bits from the BBS generator.
163 uint32 bbs_bits(bbs *b, unsigned bits)
168 /* --- Keep turning the handle until there's enough in the reservoir --- */
170 while (bits >= b->b) {
173 x |= (b->r & m) << bits;
177 /* --- Extract the last few bits needed --- */
182 x |= (b->r >> b->b) & m;
190 /* --- @bbs_wrap@ --- *
192 * Arguments: @bbs *b@ = pointer to BBS generator state
196 * Use: Steps the generator if any of the reservoir bits are used.
197 * This can be used to `wrap up' after a Blum-Goldwasser
198 * encryption, for example, producing the final value to be sent
199 * along with the ciphertext.
201 * If a generator is seeded, %$b$% bits are extracted, and then
202 * @bbs_wrap@ is called, the generator will have been stepped
203 * %$\lceil b/k \rceil$% times.
206 void bbs_wrap(bbs *b)
212 /*----- Generic random number generator interface -------------------------*/
214 typedef struct gctx {
219 static void gdestroy(grand *r)
227 static int gmisc(grand *r, unsigned op, ...)
236 switch (va_arg(ap, unsigned)) {
239 case GRAND_SEEDUINT32:
260 case GRAND_SEEDINT: {
261 mp *x = mp_fromuint(MP_NEW, va_arg(ap, unsigned));
265 case GRAND_SEEDUINT32: {
266 mp *x = mp_fromuint32(MP_NEW, va_arg(ap, uint32));
271 bbs_seed(&g->b, va_arg(ap, mp *));
273 case GRAND_SEEDRAND: {
274 grand *rr = va_arg(ap, grand *);
275 mp *m = mprand(MP_NEW, mp_bits(g->b.mb.m) - 1, rr, 0);
280 bbs_set(&g->b, va_arg(ap, mp *));
289 unsigned nb = va_arg(ap, unsigned);
290 uint32 *w = va_arg(ap, uint32 *);
291 *w = bbs_bits(&g->b, nb);
297 const bbs_priv *bp = va_arg(ap, const bbs_priv *);
298 mp *n = va_arg(ap, mp *);
299 bbs_ff(&g->b, bp, n);
302 const bbs_priv *bp = va_arg(ap, const bbs_priv *);
303 unsigned long n = va_arg(ap, unsigned long);
304 bbs_ffn(&g->b, bp, n);
307 const bbs_priv *bp = va_arg(ap, const bbs_priv *);
308 mp *n = va_arg(ap, mp *);
309 bbs_rew(&g->b, bp, n);
312 const bbs_priv *bp = va_arg(ap, const bbs_priv *);
313 unsigned long n = va_arg(ap, unsigned long);
314 bbs_rewn(&g->b, bp, n);
317 mp **n = va_arg(ap, mp **);
319 *n = MP_COPY(g->b.mb.m);
322 mp **n = va_arg(ap, mp **);
324 *n = MP_COPY(g->b.x);
335 static octet gbyte(grand *r)
338 return (bbs_bits(&g->b, 8));
341 static uint32 gword(grand *r)
344 return (bbs_bits(&g->b, 32));
347 static const grand_ops gops = {
351 gword, gbyte, gword, grand_defaultrange, grand_defaultfill
354 /* --- @bbs_rand@ --- *
356 * Arguments: @mp *m@ = modulus
357 * @mp *x@ = initial seed
359 * Returns: Pointer to a generic generator.
361 * Use: Constructs a generic generator interface over a
362 * Blum-Blum-Shub generator.
365 grand *bbs_rand(mp *m, mp *x)
367 gctx *g = S_CREATE(gctx);
369 bbs_create(&g->b, m, x);
373 /*----- Test rig ----------------------------------------------------------*/
377 static int verify(dstr *v)
379 mp *n = *(mp **)v[0].buf;
380 mp *x = *(mp **)v[1].buf;
381 grand *b = bbs_rand(n, x);
385 dstr_ensure(&d, v[2].len);
386 b->ops->fill(b, d.buf, v[2].len);
388 if (memcmp(d.buf, v[2].buf, v[2].len) != 0) {
389 fputs("\n*** bbs failure\n", stderr);
390 fputs("n = ", stderr); mp_writefile(n, stderr, 10); fputc('\n', stderr);
391 fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
392 fputs("expected = ", stderr); type_hex.dump(&v[2], stderr);
394 fputs(" found = ", stderr); type_hex.dump(&d, stderr);
396 fprintf(stderr, "k = %u\n", ((gctx *)b)->b.k);
403 assert(mparena_count(MPARENA_GLOBAL) == 0);
407 static test_chunk tests[] = {
408 { "bbs", verify, { &type_mp, &type_mp, &type_hex, 0 } },
412 int main(int argc, char *argv[])
415 test_run(argc, argv, tests, SRCDIR "/t/bbs");
421 /*----- That's all, folks -------------------------------------------------*/