From 2c52abe67dada5660d30624417ebbd37210922da Mon Sep 17 00:00:00 2001 From: mdw Date: Fri, 10 Dec 1999 23:15:00 +0000 Subject: [PATCH] Blum-Blum-Shub generator, and Blum-Goldwasser encryption. --- bbs-gen.c | 248 +++++++++++++++++++++++++++++++++++++++++ bbs-jump.c | 292 ++++++++++++++++++++++++++++++++++++++++++++++++ bbs-rand.c | 367 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bbs.h | 291 ++++++++++++++++++++++++++++++++++++++++++++++++ tests/bbs | 16 +++ 5 files changed, 1214 insertions(+) create mode 100644 bbs-gen.c create mode 100644 bbs-jump.c create mode 100644 bbs-rand.c create mode 100644 bbs.h create mode 100644 tests/bbs diff --git a/bbs-gen.c b/bbs-gen.c new file mode 100644 index 0000000..1855219 --- /dev/null +++ b/bbs-gen.c @@ -0,0 +1,248 @@ +/* -*-c-*- + * + * $Id: bbs-gen.c,v 1.1 1999/12/10 23:14:59 mdw Exp $ + * + * Generate Blum integers + * + * (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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: bbs-gen.c,v $ + * Revision 1.1 1999/12/10 23:14:59 mdw + * Blum-Blum-Shub generator, and Blum-Goldwasser encryption. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include "bbs.h" +#include "fibrand.h" +#include "mp.h" +#include "mprand.h" +#include "pgen.h" +#include "rabin.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @bbs_gen@ --- * + * + * Arguments: @bbs_params *bp@ = pointer to parameter block + * @mp *p, *q@ = initial numbers to search from + * @size_t n@ = number of attempts to make + * @void (*proc)(int ev, mp *m, void *p)@ = event handler + * @void *arg@ = argument for event handler + * + * Returns: Zero if all went well, otherwise an event code which explains + * the problem. + * + * 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. + */ + +int bbs_gen(bbs_params *bp, mp *p, mp *q, size_t n, + int (*proc)(int /*ev*/, mp */*m*/, void */*p*/), void *arg) +{ + pgen px, py; + mp *pp; + mp *g = MP_NEW; + grand *gr = fibrand_create(0); + int rcx, rcy; + int fail = BBSEV_OK; + size_t sz; + + /* --- Initialize @p@ and @q@ --- * + * + * Divide both by two, and make the results odd. + */ + + p = mp_lsr(MP_NEW, p, 1); p->v[0] |= 1; + q = mp_lsr(MP_NEW, q, 1); q->v[0] |= 1; + + /* --- Set up the search for @p@ --- * + * + * I want a prime %$p$% such that %$(p - 1)/2$% has no small factors. + */ + + rcx = pgen_create(&px, p); mp_drop(p); + rcy = pgen_muladd(&py, &px, 2, 1); + + if (proc && (fail = proc(BBSEV_FINDP, 0, arg)) != 0) + goto fail_0; + + sz = mp_bits(py.m); + for (;;) { + if (rcx != PGEN_COMPOSITE && rcy != PGEN_COMPOSITE) { + if (rcy != PGEN_PRIME) { + rabin r; + int i; + + if (proc && (fail = proc(BBSEV_TRYP, py.m, arg)) != 0) + break; + rabin_create(&r, py.m); + for (i = 0; i < 5; i++) { + g = mprand(g, sz, gr, 1); + if ((rcy = rabin_test(&r, g)) == PGEN_COMPOSITE) + break; + if (proc && (fail = proc(BBSEV_PASSP, py.m, arg)) != 0) + break; + } + rabin_destroy(&r); + if (fail) + goto fail_0; + if (i < 5) { + if (proc && (fail = proc(BBSEV_FAILP, py.m, arg)) != 0) + goto fail_0; + if (n) { + n--; + if (!n) { + fail = BBSEV_FAILP; + goto fail_0; + } + } + } + } + + if (rcy != PGEN_COMPOSITE) + break; + } + rcx = pgen_step(&px, 2); + rcy = pgen_step(&py, 4); + } + + if (proc && (fail = proc(BBSEV_GOODP, py.m, arg)) != 0) + goto fail_0; + + /* --- I now have a @p@ (and a %$(p - 1)/2$%) --- */ + + pp = MP_COPY(px.m); pgen_destroy(&px); + p = MP_COPY(py.m); pgen_destroy(&py); + + /* --- Next trick is to generate @q@ --- * + * + * I don't care about small factors of %$(q - 1)/2$%, just that it's + * relatively prime to %$(p - 1)/2$%. + */ + + { + mp *m = mp_lsl(MP_NEW, q, 1); + m->v[0] |= 1; + rcx = pgen_create(&px, m); + mp_drop(m); + } + + if (proc && (fail = proc(BBSEV_FINDQ, 0, arg)) != 0) + goto fail_1; + + for (;;) { + if (rcx != PGEN_COMPOSITE) { + int ok; + + /* --- Ensure that %$(p - 1)/2$% and %$(q - 1)/2$% are coprime --- */ + + mp_gcd(&g, 0, 0, pp, q); + ok = MP_CMP(g, ==, MP_ONE); + + if (ok && rcx != PGEN_PRIME) { + rabin r; + int i; + + if (proc && (fail = proc(BBSEV_TRYQ, px.m, arg)) != 0) + break; + rabin_create(&r, px.m); + for (i = 0; i < 5; i++) { + g = mprand(g, sz, gr, 1); + if ((rcx = rabin_test(&r, g)) == PGEN_COMPOSITE) + break; + if (proc && (fail = proc(BBSEV_PASSQ, px.m, arg)) != 0) + break; + } + rabin_destroy(&r); + if (fail) + goto fail_1; + if (i < 5) { + if (proc && (fail = proc(BBSEV_FAILQ, px.m, arg)) != 0) + goto fail_1; + if (n) { + n--; + if (!n) { + fail = BBSEV_FAILQ; + goto fail_1; + } + } + } + } + + if (ok && rcx != PGEN_COMPOSITE) + break; + } + + q = mp_add(q, q, MP_TWO); + rcx = pgen_step(&px, 4); + } + + if (proc && (fail = proc(BBSEV_GOODQ, px.m, arg)) != 0) + goto fail_1; + + /* --- Done --- */ + + mp_drop(g); + mp_drop(q); + mp_drop(pp); + q = MP_COPY(px.m); + bp->p = p; + bp->q = q; + pgen_destroy(&px); + bp->n = mp_mul(MP_NEW, p, q); + gr->ops->destroy(gr); + return (0); + + /* --- Failed --- */ + +fail_1: + pgen_destroy(&px); + mp_drop(p); + mp_drop(pp); + mp_drop(g); + gr->ops->destroy(gr); + return (fail); + +fail_0: + if (g) + mp_drop(g); + pgen_destroy(&px); + pgen_destroy(&py); + mp_drop(q); + gr->ops->destroy(gr); + return (fail); +} + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/bbs-jump.c b/bbs-jump.c new file mode 100644 index 0000000..629871d --- /dev/null +++ b/bbs-jump.c @@ -0,0 +1,292 @@ +/* -*-c-*- + * + * $Id: bbs-jump.c,v 1.1 1999/12/10 23:14:59 mdw Exp $ + * + * Jumping around a BBS sequence + * + * (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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: bbs-jump.c,v $ + * Revision 1.1 1999/12/10 23:14:59 mdw + * Blum-Blum-Shub generator, and Blum-Goldwasser encryption. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include "bbs.h" +#include "mp.h" +#include "mpbarrett.h" +#include "mpcrt.h" +#include "mpint.h" + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @jump@ --- * + * + * Arguments: @bbs *b@ = pointer to BBS generator context + * @bbs_params *bp@ = pointer to BBS modulus factors + * @unsigned long n@ = number of steps to move + * @mp *px@ = exponent mod @p@ for a one-step jump + * @mp *qx@ = exponent mod @q@ for a one-step jump + * + * Returns: --- + * + * Use: Jumps a BBS context a certain number of places (assuming the + * arguments are right). + * + * Let the BBS modulus be %$n = pq$% and the current residue be + * %$x$%. Then the computations performed are: + * + * * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%. + * + * * Determine %$e_p = px^n \bmod (p - 1)$% and similarly + * %$e_q = qx^n \bmod (p - 1)$%. + * + * * Calculate %$x_p' = x_p^{e_p} \bmod p$% and + * %$x_q' = x_q^{e_q} \bmod q$%. + * + * * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder + * Theorem. + * + * If you want to step the generator forwards, simply set + * %$px = qx = 2$%. If you want to step backwards, make + * %$px = (p + 1)/4$% and %$qx = (q + 1)/4%$. Note that, if + * %$x$% is a quadratic residue mod $%p$%, then + * + * %$(x^2) ^ {(p + 1)/4}$% + * %${} = x^{(p + 1)/2}$% + * %${} = x \cdot x^{(p - 1)/2}$% + * %${} = x$% + * + * Simple, no? (Note that the division works because + * %$p \equiv 3 \pmod 4$%.) + */ + +static void jump(bbs *b, bbs_params *bp, unsigned long n, + mp *px, mp *qx) +{ + mp *ep, *eq; + mp *v[2] = { MP_NEW, MP_NEW }; + + /* --- First work out the exponents --- */ + + { + mpbarrett mb; + mp *m; + mp *e; + + e = mp_fromulong(MP_NEW, n); + m = mp_sub(MP_NEW, bp->p, MP_ONE); + mpbarrett_create(&mb, m); + ep = mpbarrett_exp(&mb, MP_NEW, px, e); + mpbarrett_destroy(&mb); + if (qx == px) + eq = MP_COPY(ep); + else { + m = mp_sub(m, bp->q, MP_ONE); + mpbarrett_create(&mb, m); + eq = mpbarrett_exp(&mb, MP_NEW, qx, e); + mpbarrett_destroy(&mb); + } + + mp_drop(m); + mp_drop(e); + } + + /* --- Now calculate the residues of @x@ --- */ + + mp_div(0, &v[0], b->x, bp->p); + mp_div(0, &v[1], b->x, bp->q); + + /* --- Exponentiate --- */ + + { + mpbarrett mb; + + mpbarrett_create(&mb, bp->p); + v[0] = mpbarrett_exp(&mb, v[0], v[0], ep); + mpbarrett_destroy(&mb); + + mpbarrett_create(&mb, bp->q); + v[1] = mpbarrett_exp(&mb, v[1], v[1], eq); + mpbarrett_destroy(&mb); + + mp_drop(ep); + mp_drop(eq); + } + + /* --- Sort out the result using the Chinese Remainder Theorem --- */ + + { + mpcrt_mod mv[2]; + mpcrt c; + int i; + + mv[0].m = MP_COPY(bp->p); + mv[1].m = MP_COPY(bp->q); + for (i = 0; i < 2; i++) + mv[i].n = mv[i].ni = mv[i].nni = MP_NEW; + mpcrt_create(&c, mv, 2, b->mb.m); + b->x = mpcrt_solve(&c, b->x, v); + mpcrt_destroy(&c); + } + + /* --- Tidy away --- */ + + mp_drop(v[0]); + mp_drop(v[1]); + b->r = b->x->v[0]; + b->b = b->k; +} + +/* --- @bbs_ff@ --- * + * + * Arguments: @bbs *b@ = pointer to a BBS generator state + * @bbs_params *bp@ = pointer to BBS modulus factors + * @unsigned long n@ = number of steps to make + * + * Returns: --- + * + * Use: `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps. + * Requires the factorization of the Blum modulus to do this + * efficiently. + */ + +void bbs_ff(bbs *b, bbs_params *bp, unsigned long n) +{ + jump(b, bp, n, MP_TWO, MP_TWO); +} + +/* --- @bbs_rew@ --- * + * + * Arguments: @bbs *b@ = pointer to a BBS generator state + * @bbs_params *bp@ = pointer to BBS modulus factors + * @unsigned long n@ = number of steps to make + * + * Returns: --- + * + * Use: `Rewinds' a Blum-Blum-Shub generator by @n@ steps. + * Requires the factorization of the Blum modulus to do this + * at all. + */ + +void bbs_rew(bbs *b, bbs_params *bp, unsigned long n) +{ + mp *px = mp_lsr(MP_NEW, bp->p, 2); + mp *qx = mp_lsr(MP_NEW, bp->q, 2); + px = mp_add(px, px, MP_ONE); + qx = mp_add(qx, qx, MP_ONE); + jump(b, bp, n, px, qx); + mp_drop(px); + mp_drop(qx); +} + +/*----- Test rig ----------------------------------------------------------*/ + +#ifdef TEST_RIG + +static int verify(dstr *v) +{ + bbs_params bp; + bbs b; + mp *x; + unsigned long n; + int ok = 1; + uint32 p, q, r; + int i; + + bp.p = *(mp **)v[0].buf; + bp.q = *(mp **)v[1].buf; + bp.n = mp_mul(MP_NEW, bp.p, bp.q); + x = *(mp **)v[2].buf; + n = *(unsigned long *)v[3].buf; + + bbs_create(&b, bp.n, x); + p = bbs_bits(&b, 32); + + bbs_seed(&b, x); + for (i = 0; i < n; i++) + bbs_step(&b); + q = bbs_bits(&b, 32); + bbs_wrap(&b); + + bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k); + r = bbs_bits(&b, 32); + + if (r != p) { + fputs("\n*** bbs rewind failure\n", stderr); + fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr); + fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr); + fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr); + fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr); + fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k); + fprintf(stderr, "expected output = %08lx, found %08lx\n", + (unsigned long)p, (unsigned long)r); + ok = 0; + } + + bbs_seed(&b, x); + bbs_ff(&b, &bp, n); + r = bbs_bits(&b, 32); + + if (q != r) { + fputs("\n*** bbs fastforward failure\n", stderr); + fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr); + fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr); + fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr); + fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr); + fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k); + fprintf(stderr, "expected output = %08lx, found %08lx\n", + (unsigned long)q, (unsigned long)r); + ok = 0; + } + + bbs_destroy(&b); + mp_drop(bp.p); + mp_drop(bp.q); + mp_drop(bp.n); + mp_drop(x); + + assert(mparena_count(MPARENA_GLOBAL) == 0); + return (ok); +} + +static test_chunk tests[] = { + { "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } }, + { 0, 0, { 0 } } +}; + +int main(int argc, char *argv[]) +{ + sub_init(); + test_run(argc, argv, tests, SRCDIR "/tests/bbs"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/bbs-rand.c b/bbs-rand.c new file mode 100644 index 0000000..054a158 --- /dev/null +++ b/bbs-rand.c @@ -0,0 +1,367 @@ +/* -*-c-*- + * + * $Id: bbs-rand.c,v 1.1 1999/12/10 23:14:59 mdw Exp $ + * + * 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: bbs-rand.c,v $ + * Revision 1.1 1999/12/10 23:14:59 mdw + * Blum-Blum-Shub generator, and Blum-Goldwasser encryption. + * + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include +#include + +#include "bbs.h" +#include "grand.h" +#include "mp.h" +#include "mpbarrett.h" +#include "mpint.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) +{ + if (b->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); + 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 BBS_SET: + 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 BBS_SET: + bbs_set(&g->b, va_arg(ap, mp *)); + 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", + 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 = 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 "/tests/bbs"); + return (0); +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/ diff --git a/bbs.h b/bbs.h new file mode 100644 index 0000000..851dcb8 --- /dev/null +++ b/bbs.h @@ -0,0 +1,291 @@ +/* -*-c-*- + * + * $Id: bbs.h,v 1.1 1999/12/10 23:14:59 mdw Exp $ + * + * 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. + */ + +/*----- Revision history --------------------------------------------------* + * + * $Log: bbs.h,v $ + * Revision 1.1 1999/12/10 23:14:59 mdw + * Blum-Blum-Shub generator, and Blum-Goldwasser encryption. + * + */ + +/*----- 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_MP_H +# include "mp.h" +#endif + +#ifndef CATACOMB_MPBARRETT_H +# include "mpbarrett.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_params { + mp *p, *q; /* Prime factors (3 mod 4) */ + mp *n; /* Product @pq@ -- a Blum integer */ +} bbs_params; + +/*----- Event codes from @bbs_gen@ ----------------------------------------*/ + +enum { + BBSEV_OK, + + BBSEV_FINDP, + BBSEV_TRYP, + BBSEV_PASSP, + BBSEV_FAILP, + BBSEV_GOODP, + + BBSEV_FINDQ, + BBSEV_TRYQ, + BBSEV_PASSQ, + BBSEV_FAILQ, + BBSEV_GOODQ +}; + +/*----- 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@ --- * + * + * Arguments: @bbs *b@ = pointer to a BBS generator state + * @bbs_params *bp@ = pointer to BBS modulus factors + * @unsigned long n@ = number of steps to make + * + * Returns: --- + * + * Use: `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps. + * Requires the factorization of the Blum modulus to do this + * efficiently. + */ + +extern void bbs_ff(bbs */*b*/, bbs_params */*bp*/, unsigned long /*n*/); + +/* --- @bbs_rew@ --- * + * + * Arguments: @bbs *b@ = pointer to a BBS generator state + * @bbs_params *bp@ = pointer to BBS modulus factors + * @unsigned long n@ = number of steps to make + * + * Returns: --- + * + * Use: `Rewinds' a Blum-Blum-Shub generator by @n@ steps. + * Requires the factorization of the Blum modulus to do this + * at all. + */ + +extern void bbs_rew(bbs */*b*/, bbs_params */*bp*/, unsigned long /*n*/); + +/*----- Parameter generation ----------------------------------------------*/ + +/* --- @bbs_gen@ --- * + * + * Arguments: @bbs_params *bp@ = pointer to parameter block + * @mp *p, *q@ = initial numbers to search from + * @size_t n@ = number of attempts to make + * @void (*proc)(int ev, mp *m, void *p)@ = event handler + * @void *arg@ = argument for event handler + * + * Returns: Zero if all went well, otherwise an event code which explains + * the problem. + * + * 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_params */*bp*/, mp */*p*/, mp */*q*/, size_t /*n*/, + int (*/*proc*/)(int /*ev*/, mp */*m*/, void */*p*/), + void */*arg*/); + +/*----- 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 /* @mp *x@ */ +}; + +/*----- That's all, folks -------------------------------------------------*/ + +#ifdef __cplusplus + } +#endif + +#endif diff --git a/tests/bbs b/tests/bbs new file mode 100644 index 0000000..2a753cc --- /dev/null +++ b/tests/bbs @@ -0,0 +1,16 @@ +# Test vectors for Blum-Blum-Shub generator +# +# $Id: bbs,v 1.1 1999/12/10 23:15:00 mdw Exp $ + +bbs { + 58618255351802153154518076227263324405595169368832105733339611861073310668957206153928098662820028322143309562326246028101842658621324089654810023510552099428926874474919949521150122806716423750640359105584279946965449493907636556236204117444242840921432253645386399913807490661488722966090824347967771475377 + 2 + 4a488784b0b74c53fe820e3416f67fb7f238898f711a8b5d3f3ea70b0ec264120b7bfaef30f841a979cb76ca9e9c6b01415e7618b5d6c4cc30db539852ca86d23b3527d566a76910d43ed9ba2b83596f3411354ae37c53cf0c2eab7e7e13ac7c58de83cbfd8b0a6b7cdcb7bcef92bf96a48e18124c2c21e7964a9b701b5ea4ab; +} + +bbs-jump { + 10300002644323831640029548502577413794096963710947992849414516873746495715149677373680896096678934650462228369293905743592335562158905193518665447759028003 + 8901308291494485065585437130459769427950766447948540080704500059827922533698081294071192603392538957644021072601596274962775430269633339980725226130767879 + 15 + 250; +} \ No newline at end of file -- 2.11.0