--- /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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff