Gather up another utility.

[u/mdw/catacomb] / bbs-jump.c

/* -*-c-*-
 *
 * $Id: bbs-jump.c,v 1.5 2004/04/08 01:36:15 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.
 */

/*----- 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_priv *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_priv *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_priv *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_priv *bp, unsigned long n)
{
  jump(b, bp, n, MP_TWO, MP_TWO);
}

/* --- @bbs_rew@ --- *
 *
 * Arguments:   @bbs *b@ = pointer to a BBS generator state
 *              @bbs_priv *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_priv *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_priv 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 -------------------------------------------------*/