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

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