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

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