X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/bbs.h?ds=sidebyside diff --git a/bbs.h b/bbs.h deleted file mode 100644 index 30fb474..0000000 --- a/bbs.h +++ /dev/null @@ -1,296 +0,0 @@ -/* -*-c-*- - * - * $Id$ - * - * 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