X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/pub/bbs-rand.c diff --git a/pub/bbs-rand.c b/pub/bbs-rand.c new file mode 100644 index 0000000..58b62b1 --- /dev/null +++ b/pub/bbs-rand.c @@ -0,0 +1,421 @@ +/* -*-c-*- + * + * Blum-Blum-Shub secure random number 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. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include +#include + +#include "arena.h" +#include "bbs.h" +#include "grand.h" +#include "mp.h" +#include "mpbarrett.h" +#include "mpint.h" +#include "mprand.h" +#include "paranoia.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @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@. + */ + +void bbs_create(bbs *b, mp *m, mp *x) +{ + mpw kw; + mp k; + + mpbarrett_create(&b->mb, m); + kw = mp_bits(m) - 1; + mp_build(&k, &kw, &kw + 1); + b->k = mp_bits(&k) - 1; + b->x = 0; + bbs_seed(b, x); +} + +/* --- @bbs_destroy@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * + * Returns: --- + * + * Use: Destroys a generator state when it's no longer wanted. + */ + +void bbs_destroy(bbs *b) +{ + mp_drop(b->x); + mpbarrett_destroy(&b->mb); +} + +/* --- @bbs_step@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator state + * + * Returns: --- + * + * Use: Steps the generator once. This isn't too useful in client + * code. + */ + +void bbs_step(bbs *b) +{ + mp *x = b->x; + x = mp_sqr(x, x); + x = mpbarrett_reduce(&b->mb, x, x); + b->x = x; + b->b = b->k; + b->r = b->x->v[0]; +} + +/* --- @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. + */ + +void bbs_set(bbs *b, mp *x) +{ + mp_drop(b->x); + b->x = MP_COPY(x); + bbs_step(b); +} + +/* --- @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. + */ + +void bbs_seed(bbs *b, mp *x) +{ + mp *y; + x = MP_COPY(x); + for (;;) { + y = mp_sqr(MP_NEW, x); + y = mpbarrett_reduce(&b->mb, y, y); + if (MP_CMP(y, <, x)) + break; + mp_drop(x); + x = y; + } + mp_drop(x); + bbs_set(b, y); + mp_drop(y); +} + +/* --- @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. + */ + +uint32 bbs_bits(bbs *b, unsigned bits) +{ + uint32 x = 0; + mpw m; + + /* --- Keep turning the handle until there's enough in the reservoir --- */ + + while (bits >= b->b) { + bits -= b->b; + m = (1 << b->b) - 1; + x |= (b->r & m) << bits; + bbs_step(b); + } + + /* --- Extract the last few bits needed --- */ + + if (bits) { + m = (1 << bits) - 1; + b->b -= bits; + x |= (b->r >> b->b) & m; + } + + /* --- Done --- */ + + return (x); +} + +/* --- @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. + */ + +void bbs_wrap(bbs *b) +{ + if (b->b < b->k) + bbs_step(b); +} + +/*----- Generic random number generator interface -------------------------*/ + +typedef struct gctx { + grand r; + bbs b; +} gctx; + +static void gdestroy(grand *r) +{ + gctx *g = (gctx *)r; + bbs_destroy(&g->b); + BURN(*g); + S_DESTROY(g); +} + +static int gmisc(grand *r, unsigned op, ...) +{ + gctx *g = (gctx *)r; + va_list ap; + int rc = 0; + va_start(ap, op); + + switch (op) { + case GRAND_CHECK: + switch (va_arg(ap, unsigned)) { + case GRAND_CHECK: + case GRAND_SEEDINT: + case GRAND_SEEDUINT32: + case GRAND_SEEDMP: + case GRAND_SEEDRAND: + case BBS_SET: + case BBS_STEP: + case BBS_STEPSZ: + case BBS_BITS: + case BBS_WRAP: + case BBS_FF: + case BBS_FFN: + case BBS_REW: + case BBS_REWN: + case BBS_MOD: + case BBS_STATE: + rc = 1; + break; + default: + rc = 0; + break; + } + break; + case GRAND_SEEDINT: { + mp *x = mp_fromuint(MP_NEW, va_arg(ap, unsigned)); + bbs_seed(&g->b, x); + mp_drop(x); + } break; + case GRAND_SEEDUINT32: { + mp *x = mp_fromuint32(MP_NEW, va_arg(ap, uint32)); + bbs_seed(&g->b, x); + mp_drop(x); + } break; + case GRAND_SEEDMP: + bbs_seed(&g->b, va_arg(ap, mp *)); + break; + case GRAND_SEEDRAND: { + grand *rr = va_arg(ap, grand *); + mp *m = mprand(MP_NEW, mp_bits(g->b.mb.m) - 1, rr, 0); + bbs_seed(&g->b, m); + mp_drop(m); + } break; + case BBS_SET: + bbs_set(&g->b, va_arg(ap, mp *)); + break; + case BBS_STEP: + bbs_step(&g->b); + break; + case BBS_STEPSZ: + rc = g->b.k; + break; + case BBS_BITS: { + unsigned nb = va_arg(ap, unsigned); + uint32 *w = va_arg(ap, uint32 *); + *w = bbs_bits(&g->b, nb); + } break; + case BBS_WRAP: + bbs_wrap(&g->b); + break; + case BBS_FF: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + mp *n = va_arg(ap, mp *); + bbs_ff(&g->b, bp, n); + } break; + case BBS_FFN: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + unsigned long n = va_arg(ap, unsigned long); + bbs_ffn(&g->b, bp, n); + } break; + case BBS_REW: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + mp *n = va_arg(ap, mp *); + bbs_rew(&g->b, bp, n); + } break; + case BBS_REWN: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + unsigned long n = va_arg(ap, unsigned long); + bbs_rewn(&g->b, bp, n); + } break; + case BBS_MOD: { + mp **n = va_arg(ap, mp **); + if (*n) MP_DROP(*n); + *n = MP_COPY(g->b.mb.m); + } break; + case BBS_STATE: { + mp **n = va_arg(ap, mp **); + if (*n) MP_DROP(*n); + *n = MP_COPY(g->b.x); + } break; + default: + GRAND_BADOP; + break; + } + + va_end(ap); + return (rc); +} + +static octet gbyte(grand *r) +{ + gctx *g = (gctx *)r; + return (bbs_bits(&g->b, 8)); +} + +static uint32 gword(grand *r) +{ + gctx *g = (gctx *)r; + return (bbs_bits(&g->b, 32)); +} + +static const grand_ops gops = { + "bbs", + GRAND_CRYPTO, 0, + gmisc, gdestroy, + gword, gbyte, gword, grand_range, grand_fill +}; + +/* --- @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. + */ + +grand *bbs_rand(mp *m, mp *x) +{ + gctx *g = S_CREATE(gctx); + g->r.ops = &gops; + bbs_create(&g->b, m, x); + return (&g->r); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +static int verify(dstr *v) +{ + mp *n = *(mp **)v[0].buf; + mp *x = *(mp **)v[1].buf; + grand *b = bbs_rand(n, x); + dstr d = DSTR_INIT; + int ok = 1; + + dstr_ensure(&d, v[2].len); + b->ops->fill(b, d.buf, v[2].len); + d.len = v[2].len; + if (memcmp(d.buf, v[2].buf, v[2].len) != 0) { + fputs("\n*** bbs failure\n", stderr); + fputs("n = ", stderr); mp_writefile(n, stderr, 10); fputc('\n', stderr); + fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr); + fputs("expected = ", stderr); type_hex.dump(&v[2], stderr); + fputc('\n', stderr); + fputs(" found = ", stderr); type_hex.dump(&d, stderr); + fputc('\n', stderr); + fprintf(stderr, "k = %u\n", ((gctx *)b)->b.k); + ok = 0; + } + b->ops->destroy(b); + mp_drop(x); + mp_drop(n); + dstr_destroy(&d); + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + +static test_chunk tests[] = { + { "bbs", verify, { &type_mp, &type_mp, &type_hex, 0 } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + sub_init(); + test_run(argc, argv, tests, SRCDIR "/t/bbs"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/