X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/pub/bbs.h diff --git a/pub/bbs.h b/pub/bbs.h new file mode 100644 index 0000000..4eb48d7 --- /dev/null +++ b/pub/bbs.h @@ -0,0 +1,294 @@ +/* -*-c-*- + * + * The Blum-Blum-Shub random bit generator + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Notes on the BBS generator ----------------------------------------* + * + * The Blum-Blum-Shub generator takes the least significant bits from the + * sequence %$x_i = x_{i - 1}^2 \bmod n$%, where %$n = pq$% is the product of + * two primes %$p$% and %$q$%, each of which are congruent to %$3 \bmod 4$%. + * For maximum period of the generator, %$(p - 1)/2$% and %$(q - 1)/1$% + * should be coprime. It is safe to use the least significant + * %$\log \log n$% bits of each step in the sequence -- an adversary must + * factor the modulus before being able to work forwards or backwards. The + * output of the generator cannot be distinguished from a (uniform, + * independent) random sequence of bits using any polynomial-time test. This + * is by far the strongest pseudorandom number generator provided in + * Catacomb, and by far the slowest too. For normal use, the standard + * Catacomb @rand@ generator should be more than adequate. + */ + +#ifndef CATACOMB_BBS_H +#define CATACOMB_BBS_H + +#ifdef __cplusplus + extern "C" { +#endif + +/*----- Header files ------------------------------------------------------*/ + +#include + +#ifndef CATACOMB_GRAND_H +# include "grand.h" +#endif + +#ifndef CATACOMB_KEY_H +# include "key.h" +#endif + +#ifndef CATACOMB_MP_H +# include "mp.h" +#endif + +#ifndef CATACOMB_MPBARRETT_H +# include "mpbarrett.h" +#endif + +#ifndef CATACOMB_PGEN_H +# include "pgen.h" +#endif + +/*----- Data structures ---------------------------------------------------*/ + +/* --- Basic generator state --- */ + +typedef struct bbs { + mpbarrett mb; /* Barrett reduction context */ + mp *x; /* Current quadratic residue */ + unsigned k; /* Number of bits from each step */ + unsigned b; /* Number of bits in reservoir */ + mpw r; /* Reservoir of output bits */ +} bbs; + +/* --- Parameters --- */ + +typedef struct bbs_pub { + mp *n; +} bbs_pub; + +typedef struct bbs_priv { + mp *p, *q; /* Prime factors (3 mod 4) */ + mp *n; /* Product @pq@ -- a Blum integer */ +} bbs_priv; + +/*----- Key fetching ------------------------------------------------------*/ + +extern const key_fetchdef bbs_pubfetch[]; +#define BBS_PUBFETCHSZ 3 + +extern const key_fetchdef bbs_privfetch[]; +#define BBS_PRIVFETCHSZ 7 + +/* --- @bbs_pubfree@, @bbs_privfree@ --- * + * + * Arguments: @bbs_pub *bp@, @bbs_priv *bp@ = pointer to key block + * + * Returns: --- + * + * Use: Frees a BBS key block. + */ + +extern void bbs_pubfree(bbs_pub */*bp*/); +extern void bbs_privfree(bbs_priv */*bp*/); + +/*----- The basic generator -----------------------------------------------*/ + +/* --- @bbs_create@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state to initialize + * @mp *m@ = modulus (must be a Blum integer) + * @mp *x@ = initial seed for generator + * + * Returns: --- + * + * Use: Initializes a BBS generator. The generator is stepped once + * after initialization, as for @bbs_seed@. + */ + +extern void bbs_create(bbs */*b*/, mp */*m*/, mp */*x*/); + +/* --- @bbs_destroy@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * + * Returns: --- + * + * Use: Destroys a generator state when it's no longer wanted. + */ + +extern void bbs_destroy(bbs */*b*/); + +/* --- @bbs_step@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * + * Returns: --- + * + * Use: Steps the generator once. This isn't too useful in client + * code. + */ + +extern void bbs_step(bbs */*b*/); + +/* --- @bbs_set@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * @mp *x@ = new residue to set + * + * Returns: --- + * + * Use: Sets a new quadratic residue. The generator is stepped once. + */ + +extern void bbs_set(bbs */*b*/, mp */*x*/); + +/* --- @bbs_seed@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * @mp *x@ = new seed to set + * + * Returns --- + * + * Use: Sets a new seed. The generator is stepped until the residue + * has clearly wrapped around. + */ + +extern void bbs_seed(bbs */*b*/, mp */*x*/); + +/* --- @bbs_bits@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * @unsigned bits@ = number of bits wanted + * + * Returns: Bits extracted from the BBS generator. + * + * Use: Extracts a requested number of bits from the BBS generator. + */ + +extern uint32 bbs_bits(bbs */*b*/, unsigned /*bits*/); + +/* --- @bbs_wrap@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * + * Returns: --- + * + * Use: Steps the generator if any of the reservoir bits are used. + * This can be used to `wrap up' after a Blum-Goldwasser + * encryption, for example, producing the final value to be sent + * along with the ciphertext. + * + * If a generator is seeded, %$b$% bits are extracted, and then + * @bbs_wrap@ is called, the generator will have been stepped + * %$\lceil b/k \rceil$% times. + */ + +extern void bbs_wrap(bbs */*b*/); + +/*----- Large forwards and backwards jumps --------------------------------*/ + +/* --- @bbs_{ff,rew}{,n}@ --- * + * + * Arguments: @bbs *b@ = pointer to a BBS generator state + * @const bbs_priv *bp@ = pointer to BBS modulus factors + * @mp *n@, @unsigned long n@ = number of steps to make + * + * Returns: --- + * + * Use: `Fast-forwards' or rewinds a Blum-Blum-Shub generator by @n@ + * steps. The @...n@ versions take an @unsigned long@ argument; + * the non-@...n@ versions a multiprecision integer. If @n@ is + * negative then the generator is stepped in the reverse + * direction. + */ + +extern void bbs_ff(bbs */*b*/, const bbs_priv */*bp*/, mp */*n*/); +extern void bbs_ffn(bbs */*b*/, const bbs_priv */*bp*/, unsigned long /*n*/); +extern void bbs_rew(bbs */*b*/, const bbs_priv */*bp*/, mp */*n*/); +extern void bbs_rewn(bbs */*b*/, const bbs_priv */*bp*/, unsigned long /*n*/); + +/*----- Parameter generation ----------------------------------------------*/ + +/* --- @bbs_gen@ --- * + * + * Arguments: @bbs_priv *bp@ = pointer to parameter block + * @unsigned nbits@ = number of bits in the modulus + * @grand *r@ = pointer to random number source + * @unsigned n@ = number of attempts to make + * @pgen_proc *event@ = event handler function + * @void *ectx@ = argument for event handler + * + * Returns: If it worked OK, @PGEN_DONE@, otherwise @PGEN_ABORT@. + * + * Use: Finds two prime numbers %$p'$% and %$q'$% such that both are + * congruent to %$3 \bmod 4$%, and $(p - 1)/2$% and + * %$(q - 1)/2$% have no common factors. The product %$n = pq$% + * is eminently suitable for use as a modulus in a Blum-Blum- + * Shub pseudorandom bit generator. + */ + +extern int bbs_gen(bbs_priv */*bp*/, unsigned /*nbits*/, grand */*r*/, + unsigned /*n*/, pgen_proc */*event*/, void */*ectx*/); + +/*----- Generic random number generator interface -------------------------*/ + +/* --- @bbs_rand@ --- * + * + * Arguments: @mp *m@ = modulus + * @mp *x@ = initial seed + * + * Returns: Pointer to a generic generator. + * + * Use: Constructs a generic generator interface over a + * Blum-Blum-Shub generator. + */ + +extern grand *bbs_rand(mp */*m*/, mp */*x*/); + +/* --- Blum-Blum-Shub-specific misc op codes --- */ + +enum { + BBS_SET = GRAND_SPECIFIC('B'), /* @mp *x@ */ + BBS_STEP, /* @void@ */ + BBS_STEPSZ, /* @void@ */ + BBS_BITS, /* @unsigned bits, uint32 *w@ */ + BBS_WRAP, /* @void@ */ + BBS_FF, /* @bbs_priv *p, mp *n@ */ + BBS_FFN, /* @bbs_priv *p, unsigned long n@ */ + BBS_REW, /* @bbs_priv *p, mp *n@ */ + BBS_REWN, /* @bbs_priv *p, unsigned long n@ */ + BBS_MOD, /* @mp **n@ */ + BBS_STATE /* @mp **x@ */ +}; + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif