chiark - git - mdw - catacomb/blob - bbs-rand.c

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