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

   1 /* -*-c-*-
   2  *
   3  * $Id: bbs-rand.c,v 1.5 2004/04/08 01:36:15 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 /*----- 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           rc = 1;
 246           break;
 247         default:
 248           rc = 0;
 249           break;
 250       }
 251       break;
 252     case GRAND_SEEDINT: {
 253       mp *x = mp_fromuint(MP_NEW, va_arg(ap, unsigned));
 254       bbs_seed(&g->b, x);
 255       mp_drop(x);
 256     } break;
 257     case GRAND_SEEDUINT32: {
 258       mp *x = mp_fromuint32(MP_NEW, va_arg(ap, uint32));
 259       bbs_seed(&g->b, x);
 260       mp_drop(x);
 261     } break;
 262     case GRAND_SEEDMP:
 263       bbs_seed(&g->b, va_arg(ap, mp *));
 264       break;
 265     case GRAND_SEEDRAND: {
 266       grand *rr = va_arg(ap, grand *);
 267       mp *m = mprand(MP_NEW, mp_bits(g->b.mb.m) - 1, rr, 0);
 268       bbs_seed(&g->b, m);
 269       mp_drop(m);
 270     } break;
 271     case BBS_SET:
 272       bbs_set(&g->b, va_arg(ap, mp *));
 273       break;
 274     default:
 275       GRAND_BADOP;
 276       break;
 277   }
 278
 279   va_end(ap);
 280   return (rc);
 281 }
 282
 283 static octet gbyte(grand *r)
 284 {
 285   gctx *g = (gctx *)r;
 286   return (bbs_bits(&g->b, 8));
 287 }
 288
 289 static uint32 gword(grand *r)
 290 {
 291   gctx *g = (gctx *)r;
 292   return (bbs_bits(&g->b, 32));
 293 }
 294
 295 static const grand_ops gops = {
 296   "bbs",
 297   GRAND_CRYPTO, 0,
 298   gmisc, gdestroy,
 299   gword, gbyte, gword, grand_range, grand_fill
 300 };
 301
 302 /* --- @bbs_rand@ --- *
 303  *
 304  * Arguments:   @mp *m@ = modulus
 305  *              @mp *x@ = initial seed
 306  *
 307  * Returns:     Pointer to a generic generator.
 308  *
 309  * Use:         Constructs a generic generator interface over a
 310  *              Blum-Blum-Shub generator.
 311  */
 312
 313 grand *bbs_rand(mp *m, mp *x)
 314 {
 315   gctx *g = S_CREATE(gctx);
 316   g->r.ops = &gops;
 317   bbs_create(&g->b, m, x);
 318   return (&g->r);
 319 }
 320
 321 /*----- Test rig ----------------------------------------------------------*/
 322
 323 #ifdef TEST_RIG
 324
 325 static int verify(dstr *v)
 326 {
 327   mp *n = *(mp **)v[0].buf;
 328   mp *x = *(mp **)v[1].buf;
 329   grand *b = bbs_rand(n, x);
 330   dstr d = DSTR_INIT;
 331   int ok = 1;
 332
 333   dstr_ensure(&d, v[2].len);
 334   b->ops->fill(b, d.buf, v[2].len);
 335   d.len = v[2].len;
 336   if (memcmp(d.buf, v[2].buf, v[2].len) != 0) {
 337     fputs("\n*** bbs failure\n", stderr);
 338     fputs("n = ", stderr); mp_writefile(n, stderr, 10); fputc('\n', stderr);
 339     fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
 340     fputs("expected = ", stderr); type_hex.dump(&v[2], stderr);
 341     fputc('\n', stderr);
 342     fputs("   found = ", stderr); type_hex.dump(&d, stderr);
 343     fputc('\n', stderr);
 344     fprintf(stderr, "k = %u\n", ((gctx *)b)->b.k);
 345     ok = 0;
 346   }
 347   b->ops->destroy(b);
 348   mp_drop(x);
 349   mp_drop(n);
 350   dstr_destroy(&d);
 351   assert(mparena_count(MPARENA_GLOBAL) == 0);
 352   return (ok);
 353 }
 354
 355 static test_chunk tests[] = {
 356   { "bbs", verify, { &type_mp, &type_mp, &type_hex, 0 } },
 357   { 0, 0, { 0 } }
 358 };
 359
 360 int main(int argc, char *argv[])
 361 {
 362   sub_init();
 363   test_run(argc, argv, tests, SRCDIR "/tests/bbs");
 364   return (0);
 365 }
 366
 367 #endif
 368
 369 /*----- That's all, folks -------------------------------------------------*/