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

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