chiark - git - mdw - catacomb/blob - bbs.h

   1 /* -*-c-*-
   2  *
   3  * $Id: bbs.h,v 1.3 2000/02/12 18:21:02 mdw Exp $
   4  *
   5  * The Blum-Blum-Shub random bit 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.h,v $
  33  * Revision 1.3  2000/02/12 18:21:02  mdw
  34  * Overhaul of key management (again).
  35  *
  36  * Revision 1.2  1999/12/22 15:52:08  mdw
  37  * Rename `bbs_params' to `bbs_param' for consistency.
  38  *
  39  * Revision 1.1  1999/12/10 23:14:59  mdw
  40  * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
  41  *
  42  */
  43
  44 /*----- Notes on the BBS generator ----------------------------------------*
  45  *
  46  * The Blum-Blum-Shub generator takes the least significant bits from the
  47  * sequence %$x_i = x_{i - 1}^2 \bmod n$%, where %$n = pq$% is the product of
  48  * two primes %$p$% and %$q$%, each of which are congruent to %$3 \bmod 4$%.
  49  * For maximum period of the generator, %$(p - 1)/2$% and %$(q - 1)/1$%
  50  * should be coprime.  It is safe to use the least significant %$\log \log
  51  * n$% bits of each step in the sequence -- an adversary must factor the
  52  * modulus before being able to work forwards or backwards.  The output of
  53  * the generator cannot be distinguished from a (uniform, independent) random
  54  * sequence of bits using any polynomial-time test.  This is by far the
  55  * strongest pseudorandom number generator provided in Catacomb, and by far
  56  * the slowest too.  For normal use, the standard Catacomb @rand@ generator
  57  * should be more than adequate.
  58  */
  59
  60 #ifndef CATACOMB_BBS_H
  61 #define CATACOMB_BBS_H
  62
  63 #ifdef __cplusplus
  64   extern "C" {
  65 #endif
  66
  67 /*----- Header files ------------------------------------------------------*/
  68
  69 #include <mLib/bits.h>
  70
  71 #ifndef CATACOMB_GRAND_H
  72 #  include "grand.h"
  73 #endif
  74
  75 #ifndef CATACOMB_MP_H
  76 #  include "mp.h"
  77 #endif
  78
  79 #ifndef CATACOMB_MPBARRETT_H
  80 #  include "mpbarrett.h"
  81 #endif
  82
  83 #ifndef CATACOMB_PGEN_H
  84 #  include "pgen.h"
  85 #endif
  86
  87 /*----- Data structures ---------------------------------------------------*/
  88
  89 /* --- Basic generator state --- */
  90
  91 typedef struct bbs {
  92   mpbarrett mb;                         /* Barrett reduction context */
  93   mp *x;                                /* Current quadratic residue */
  94   unsigned k;                           /* Number of bits from each step */
  95   unsigned b;                           /* Number of bits in reservoir */
  96   mpw r;                                /* Reservoir of output bits */
  97 } bbs;
  98
  99 /* --- Parameters --- */
 100
 101 typedef struct bbs_param {
 102   mp *p, *q;                            /* Prime factors (3 mod 4) */
 103   mp *n;                                /* Product @pq@ -- a Blum integer */
 104 } bbs_param;
 105
 106 /*----- The basic generator -----------------------------------------------*/
 107
 108 /* --- @bbs_create@ --- *
 109  *
 110  * Arguments:   @bbs *b@ = pointer to BBS generator state to initialize
 111  *              @mp *m@ = modulus (must be a Blum integer)
 112  *              @mp *x@ = initial seed for generator
 113  *
 114  * Returns:     ---
 115  *
 116  * Use:         Initializes a BBS generator.  The generator is stepped once
 117  *              after initialization, as for @bbs_seed@.
 118  */
 119
 120 extern void bbs_create(bbs */*b*/, mp */*m*/, mp */*x*/);
 121
 122 /* --- @bbs_destroy@ --- *
 123  *
 124  * Arguments:   @bbs *b@ = pointer to BBS generator state
 125  *
 126  * Returns:     ---
 127  *
 128  * Use:         Destroys a generator state when it's no longer wanted.
 129  */
 130
 131 extern void bbs_destroy(bbs */*b*/);
 132
 133 /* --- @bbs_step@ --- *
 134  *
 135  * Arguments:   @bbs *b@ = pointer to BBS generator state
 136  *
 137  * Returns:     ---
 138  *
 139  * Use:         Steps the generator once.  This isn't too useful in client
 140  *              code.
 141  */
 142
 143 extern void bbs_step(bbs */*b*/);
 144
 145 /* --- @bbs_set@ --- *
 146  *
 147  * Arguments:   @bbs *b@ = pointer to BBS generator state
 148  *              @mp *x@ = new residue to set
 149  *
 150  * Returns:     ---
 151  *
 152  * Use:         Sets a new quadratic residue.  The generator is stepped once.
 153  */
 154
 155 extern void bbs_set(bbs */*b*/, mp */*x*/);
 156
 157 /* --- @bbs_seed@ --- *
 158  *
 159  * Arguments:   @bbs *b@ = pointer to BBS generator state
 160  *              @mp *x@ = new seed to set
 161  *
 162  * Returns      ---
 163  *
 164  * Use:         Sets a new seed.  The generator is stepped until the residue
 165  *              has clearly wrapped around.
 166  */
 167
 168 extern void bbs_seed(bbs */*b*/, mp */*x*/);
 169
 170 /* --- @bbs_bits@ --- *
 171  *
 172  * Arguments:   @bbs *b@ = pointer to BBS generator state
 173  *              @unsigned bits@ = number of bits wanted
 174  *
 175  * Returns:     Bits extracted from the BBS generator.
 176  *
 177  * Use:         Extracts a requested number of bits from the BBS generator.
 178  */
 179
 180 extern uint32 bbs_bits(bbs */*b*/, unsigned /*bits*/);
 181
 182 /* --- @bbs_wrap@ --- *
 183  *
 184  * Arguments:   @bbs *b@ = pointer to BBS generator state
 185  *
 186  * Returns:     ---
 187  *
 188  * Use:         Steps the generator if any of the reservoir bits are used.
 189  *              This can be used to `wrap up' after a Blum-Goldwasser
 190  *              encryption, for example, producing the final value to be sent
 191  *              along with the ciphertext.
 192  *
 193  *              If a generator is seeded, %$b$% bits are extracted, and then
 194  *              @bbs_wrap@ is called, the generator will have been stepped
 195  *              %$\lceil b/k \rceil% times.
 196  */
 197
 198 extern void bbs_wrap(bbs */*b*/);
 199
 200 /*----- Large forwards and backwards jumps --------------------------------*/
 201
 202 /* --- @bbs_ff@ --- *
 203  *
 204  * Arguments:   @bbs *b@ = pointer to a BBS generator state
 205  *              @bbs_param *bp@ = pointer to BBS modulus factors
 206  *              @unsigned long n@ = number of steps to make
 207  *
 208  * Returns:     ---
 209  *
 210  * Use:         `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps.
 211  *              Requires the factorization of the Blum modulus to do this
 212  *              efficiently.
 213  */
 214
 215 extern void bbs_ff(bbs */*b*/, bbs_param */*bp*/, unsigned long /*n*/);
 216
 217 /* --- @bbs_rew@ --- *
 218  *
 219  * Arguments:   @bbs *b@ = pointer to a BBS generator state
 220  *              @bbs_param *bp@ = pointer to BBS modulus factors
 221  *              @unsigned long n@ = number of steps to make
 222  *
 223  * Returns:     ---
 224  *
 225  * Use:         `Rewinds' a Blum-Blum-Shub generator by @n@ steps.
 226  *              Requires the factorization of the Blum modulus to do this
 227  *              at all.
 228  */
 229
 230 extern void bbs_rew(bbs */*b*/, bbs_param */*bp*/, unsigned long /*n*/);
 231
 232 /*----- Parameter generation ----------------------------------------------*/
 233
 234 /* --- @bbs_gen@ --- *
 235  *
 236  * Arguments:   @bbs_param *bp@ = pointer to parameter block
 237  *              @unsigned nbits@ = number of bits in the modulus
 238  *              @grand *r@ = pointer to random number source
 239  *              @unsigned n@ = number of attempts to make
 240  *              @pgen_proc *event@ = event handler function
 241  *              @void *ectx@ = argument for event handler
 242  *
 243  * Returns:     If it worked OK, @PGEN_DONE@, otherwise @PGEN_ABORT@.
 244  *
 245  * Use:         Finds two prime numbers %$p'$% and %$q'$% such that both are
 246  *              congruent to %$3 \bmod 4$%, and  $(p - 1)/2$% and
 247  *              %$(q - 1)/2$% have no common factors.  The product %$n = pq$%
 248  *              is eminently suitable for use as a modulus in a Blum-Blum-
 249  *              Shub pseudorandom bit generator.
 250  */
 251
 252 extern int bbs_gen(bbs_param */*bp*/, unsigned /*nbits*/, grand */*r*/,
 253                    unsigned /*n*/, pgen_proc */*event*/, void */*ectx*/);
 254
 255 /*----- Generic random number generator interface -------------------------*/
 256
 257 /* --- @bbs_rand@ --- *
 258  *
 259  * Arguments:   @mp *m@ = modulus
 260  *              @mp *x@ = initial seed
 261  *
 262  * Returns:     Pointer to a generic generator.
 263  *
 264  * Use:         Constructs a generic generator interface over a
 265  *              Blum-Blum-Shub generator.
 266  */
 267
 268 extern grand *bbs_rand(mp */*m*/, mp */*x*/);
 269
 270 /* --- Blum-Blum-Shub-specific misc op codes --- */
 271
 272 enum {
 273   BBS_SET = GRAND_SPECIFIC              /* @mp *x@ */
 274 };
 275
 276 /*----- That's all, folks -------------------------------------------------*/
 277
 278 #ifdef __cplusplus
 279   }
 280 #endif
 281
 282 #endif