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

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