5 * Blum-Blum-Shub secure random number generator
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Header files ------------------------------------------------------*/
36 #include <mLib/bits.h>
43 #include "mpbarrett.h"
48 /*----- Main code ---------------------------------------------------------*/
50 /* --- @bbs_create@ --- *
52 * Arguments: @bbs *b@ = pointer to BBS generator state to initialize
53 * @mp *m@ = modulus (must be a Blum integer)
54 * @mp *x@ = initial seed for generator
58 * Use: Initializes a BBS generator. The generator is stepped once
59 * after initialization, as for @bbs_seed@.
62 void bbs_create(bbs
*b
, mp
*m
, mp
*x
)
67 mpbarrett_create(&b
->mb
, m
);
69 mp_build(&k
, &kw
, &kw
+ 1);
70 b
->k
= mp_bits(&k
) - 1;
75 /* --- @bbs_destroy@ --- *
77 * Arguments: @bbs *b@ = pointer to BBS generator state
81 * Use: Destroys a generator state when it's no longer wanted.
84 void bbs_destroy(bbs
*b
)
87 mpbarrett_destroy(&b
->mb
);
90 /* --- @bbs_step@ --- *
92 * Arguments: @bbs *b@ = pointer to BBS generator state
96 * Use: Steps the generator once. This isn't too useful in client
100 void bbs_step(bbs
*b
)
104 x
= mpbarrett_reduce(&b
->mb
, x
, x
);
110 /* --- @bbs_set@ --- *
112 * Arguments: @bbs *b@ = pointer to BBS generator state
113 * @mp *x@ = new residue to set
117 * Use: Sets a new quadratic residue. The generator is stepped once.
120 void bbs_set(bbs
*b
, mp
*x
)
127 /* --- @bbs_seed@ --- *
129 * Arguments: @bbs *b@ = pointer to BBS generator state
130 * @mp *x@ = new seed to set
134 * Use: Sets a new seed. The generator is stepped until the residue
135 * has clearly wrapped around.
138 void bbs_seed(bbs
*b
, mp
*x
)
143 y
= mp_sqr(MP_NEW
, x
);
144 y
= mpbarrett_reduce(&b
->mb
, y
, y
);
155 /* --- @bbs_bits@ --- *
157 * Arguments: @bbs *b@ = pointer to BBS generator state
158 * @unsigned bits@ = number of bits wanted
160 * Returns: Bits extracted from the BBS generator.
162 * Use: Extracts a requested number of bits from the BBS generator.
165 uint32
bbs_bits(bbs
*b
, unsigned bits
)
170 /* --- Keep turning the handle until there's enough in the reservoir --- */
172 while (bits
>= b
->b
) {
175 x
|= (b
->r
& m
) << bits
;
179 /* --- Extract the last few bits needed --- */
184 x
|= (b
->r
>> b
->b
) & m
;
192 /* --- @bbs_wrap@ --- *
194 * Arguments: @bbs *b@ = pointer to BBS generator state
198 * Use: Steps the generator if any of the reservoir bits are used.
199 * This can be used to `wrap up' after a Blum-Goldwasser
200 * encryption, for example, producing the final value to be sent
201 * along with the ciphertext.
203 * If a generator is seeded, %$b$% bits are extracted, and then
204 * @bbs_wrap@ is called, the generator will have been stepped
205 * %$\lceil b/k \rceil$% times.
208 void bbs_wrap(bbs
*b
)
214 /*----- Generic random number generator interface -------------------------*/
216 typedef struct gctx
{
221 static void gdestroy(grand
*r
)
229 static int gmisc(grand
*r
, unsigned op
, ...)
238 switch (va_arg(ap
, unsigned)) {
241 case GRAND_SEEDUINT32
:
262 case GRAND_SEEDINT
: {
263 mp
*x
= mp_fromuint(MP_NEW
, va_arg(ap
, unsigned));
267 case GRAND_SEEDUINT32
: {
268 mp
*x
= mp_fromuint32(MP_NEW
, va_arg(ap
, uint32
));
273 bbs_seed(&g
->b
, va_arg(ap
, mp
*));
275 case GRAND_SEEDRAND
: {
276 grand
*rr
= va_arg(ap
, grand
*);
277 mp
*m
= mprand(MP_NEW
, mp_bits(g
->b
.mb
.m
) - 1, rr
, 0);
282 bbs_set(&g
->b
, va_arg(ap
, mp
*));
291 unsigned nb
= va_arg(ap
, unsigned);
292 uint32
*w
= va_arg(ap
, uint32
*);
293 *w
= bbs_bits(&g
->b
, nb
);
299 const bbs_priv
*bp
= va_arg(ap
, const bbs_priv
*);
300 mp
*n
= va_arg(ap
, mp
*);
301 bbs_ff(&g
->b
, bp
, n
);
304 const bbs_priv
*bp
= va_arg(ap
, const bbs_priv
*);
305 unsigned long n
= va_arg(ap
, unsigned long);
306 bbs_ffn(&g
->b
, bp
, n
);
309 const bbs_priv
*bp
= va_arg(ap
, const bbs_priv
*);
310 mp
*n
= va_arg(ap
, mp
*);
311 bbs_rew(&g
->b
, bp
, n
);
314 const bbs_priv
*bp
= va_arg(ap
, const bbs_priv
*);
315 unsigned long n
= va_arg(ap
, unsigned long);
316 bbs_rewn(&g
->b
, bp
, n
);
319 mp
**n
= va_arg(ap
, mp
**);
321 *n
= MP_COPY(g
->b
.mb
.m
);
324 mp
**n
= va_arg(ap
, mp
**);
326 *n
= MP_COPY(g
->b
.x
);
337 static octet
gbyte(grand
*r
)
340 return (bbs_bits(&g
->b
, 8));
343 static uint32
gword(grand
*r
)
346 return (bbs_bits(&g
->b
, 32));
349 static const grand_ops gops
= {
353 gword
, gbyte
, gword
, grand_range
, grand_fill
356 /* --- @bbs_rand@ --- *
358 * Arguments: @mp *m@ = modulus
359 * @mp *x@ = initial seed
361 * Returns: Pointer to a generic generator.
363 * Use: Constructs a generic generator interface over a
364 * Blum-Blum-Shub generator.
367 grand
*bbs_rand(mp
*m
, mp
*x
)
369 gctx
*g
= S_CREATE(gctx
);
371 bbs_create(&g
->b
, m
, x
);
375 /*----- Test rig ----------------------------------------------------------*/
379 static int verify(dstr
*v
)
381 mp
*n
= *(mp
**)v
[0].buf
;
382 mp
*x
= *(mp
**)v
[1].buf
;
383 grand
*b
= bbs_rand(n
, x
);
387 dstr_ensure(&d
, v
[2].len
);
388 b
->ops
->fill(b
, d
.buf
, v
[2].len
);
390 if (memcmp(d
.buf
, v
[2].buf
, v
[2].len
) != 0) {
391 fputs("\n*** bbs failure\n", stderr
);
392 fputs("n = ", stderr
); mp_writefile(n
, stderr
, 10); fputc('\n', stderr
);
393 fputs("x = ", stderr
); mp_writefile(x
, stderr
, 10); fputc('\n', stderr
);
394 fputs("expected = ", stderr
); type_hex
.dump(&v
[2], stderr
);
396 fputs(" found = ", stderr
); type_hex
.dump(&d
, stderr
);
398 fprintf(stderr
, "k = %u\n", ((gctx
*)b
)->b
.k
);
405 assert(mparena_count(MPARENA_GLOBAL
) == 0);
409 static test_chunk tests
[] = {
410 { "bbs", verify
, { &type_mp
, &type_mp
, &type_hex
, 0 } },
414 int main(int argc
, char *argv
[])
417 test_run(argc
, argv
, tests
, SRCDIR
"/tests/bbs");
423 /*----- That's all, folks -------------------------------------------------*/