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

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