git.distorted.org.uk Git - u/mdw/catacomb/blob - bbs-rand.c

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