--- /dev/null
+/* -*-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 <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <mLib/bits.h>
+#include <mLib/sub.h>
+
+#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 -------------------------------------------------*/
--- /dev/null
+/* -*-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 <mLib/bits.h>
+
+#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
--- /dev/null
+# 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
projects / u / mdw / catacomb / commitdiff