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

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