chiark - git - mdw - catacomb/blob - bbs-jump.c

   1 /* -*-c-*-
   2  *
   3  * $Id$
   4  *
   5  * Jumping around a BBS sequence
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include "bbs.h"
  33 #include "mp.h"
  34 #include "mpbarrett.h"
  35 #include "mpcrt.h"
  36 #include "mpint.h"
  37
  38 /*----- Main code ---------------------------------------------------------*/
  39
  40 /* --- @jump@ --- *
  41  *
  42  * Arguments:   @bbs *b@ = pointer to BBS generator context
  43  *              @const bbs_priv *bp@ = pointer to BBS modulus factors
  44  *              @mp *n@ = number of steps to move
  45  *              @mp *px@ = exponent mod @p@ for a one-step jump
  46  *              @mp *qx@ = exponent mod @q@ for a one-step jump
  47  *
  48  * Returns:     ---
  49  *
  50  * Use:         Jumps a BBS context a certain number of places (assuming the
  51  *              arguments are right).
  52  *
  53  *              Let the BBS modulus be %$n = pq$% and the current residue be
  54  *              %$x$%.  Then the computations performed are:
  55  *
  56  *                * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%.
  57  *
  58  *                * Determine %$e_p = px^n \bmod (p - 1)$% and similarly
  59  *                  %$e_q = qx^n \bmod (p - 1)$%.
  60  *
  61  *                * Calculate %$x_p' = x_p^{e_p} \bmod p$% and
  62  *                  %$x_q' = x_q^{e_q} \bmod q$%.
  63  *
  64  *                * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder
  65  *                  Theorem.
  66  *
  67  *              If you want to step the generator forwards, simply set
  68  *              %$px = qx = 2$%.  If you want to step backwards, make
  69  *              %$px = (p + 1)/4$% and %$qx = (q + 1)/4$%.  Note that, if
  70  *              %$x$% is a quadratic residue mod $%p$%, then
  71  *
  72  *              %$(x^2) ^ {(p + 1)/4}$%
  73  *                %${} = x^{(p + 1)/2}$%
  74  *                %${} = x \cdot x^{(p - 1)/2}$%
  75  *                %${} = x$%
  76  *
  77  *              Simple, no?  (Note that the division works because
  78  *              %$p \equiv 3 \pmod 4$%.)
  79  */
  80
  81 static void jump(bbs *b, const bbs_priv *bp, mp *n,
  82                  mp *px, mp *qx)
  83 {
  84   mp *ep, *eq;
  85   mp *v[2] = { MP_NEW, MP_NEW };
  86
  87   /* --- First work out the exponents --- */
  88
  89   {
  90     mpbarrett mb;
  91     mp *m;
  92
  93     m = mp_sub(MP_NEW, bp->p, MP_ONE);
  94     mpbarrett_create(&mb, m);
  95     ep = mpbarrett_exp(&mb, MP_NEW, px, n);
  96     mpbarrett_destroy(&mb);
  97     if (qx == px)
  98       eq = MP_COPY(ep);
  99     else {
 100       m = mp_sub(m, bp->q, MP_ONE);
 101       mpbarrett_create(&mb, m);
 102       eq = mpbarrett_exp(&mb, MP_NEW, qx, n);
 103       mpbarrett_destroy(&mb);
 104     }
 105
 106     mp_drop(m);
 107   }
 108
 109   /* --- Now calculate the residues of @x@ --- */
 110
 111   mp_div(0, &v[0], b->x, bp->p);
 112   mp_div(0, &v[1], b->x, bp->q);
 113
 114   /* --- Exponentiate --- */
 115
 116   {
 117     mpbarrett mb;
 118
 119     mpbarrett_create(&mb, bp->p);
 120     v[0] = mpbarrett_exp(&mb, v[0], v[0], ep);
 121     mpbarrett_destroy(&mb);
 122
 123     mpbarrett_create(&mb, bp->q);
 124     v[1] = mpbarrett_exp(&mb, v[1], v[1], eq);
 125     mpbarrett_destroy(&mb);
 126
 127     mp_drop(ep);
 128     mp_drop(eq);
 129   }
 130
 131   /* --- Sort out the result using the Chinese Remainder Theorem --- */
 132
 133   {
 134     mpcrt_mod mv[2];
 135     mpcrt c;
 136     int i;
 137
 138     mv[0].m = MP_COPY(bp->p);
 139     mv[1].m = MP_COPY(bp->q);
 140     for (i = 0; i < 2; i++)
 141       mv[i].n = mv[i].ni = mv[i].nni = MP_NEW;
 142     mpcrt_create(&c, mv, 2, b->mb.m);
 143     b->x = mpcrt_solve(&c, b->x, v);
 144     mpcrt_destroy(&c);
 145   }
 146
 147   /* --- Tidy away --- */
 148
 149   mp_drop(v[0]);
 150   mp_drop(v[1]);
 151   b->r = b->x->v[0];
 152   b->b = b->k;
 153 }
 154
 155 /* --- @bbs_{ff,rew}{,n}@ --- *
 156  *
 157  * Arguments:   @bbs *b@ = pointer to a BBS generator state
 158  *              @const bbs_priv *bp@ = pointer to BBS modulus factors
 159  *              @mp *n@, @unsigned long n@ = number of steps to make
 160  *
 161  * Returns:     ---
 162  *
 163  * Use:         `Fast-forwards' or rewinds a Blum-Blum-Shub generator by @n@
 164  *              steps.  The @...n@ versions take an @unsigned long@ argument;
 165  *              the non-@...n@ versions a multiprecision integer.  If @n@ is
 166  *              negative then the generator is stepped in the reverse
 167  *              direction.
 168  */
 169
 170 static void ff(bbs *b, const bbs_priv *bp, mp *n)
 171   { jump(b, bp, n, MP_TWO, MP_TWO); }
 172
 173 static void rew(bbs *b, const bbs_priv *bp, mp *n)
 174 {
 175   mp *px = mp_lsr(MP_NEW, bp->p, 2);
 176   mp *qx = mp_lsr(MP_NEW, bp->q, 2);
 177   px = mp_add(px, px, MP_ONE);
 178   qx = mp_add(qx, qx, MP_ONE);
 179   jump(b, bp, n, px, qx);
 180   mp_drop(px);
 181   mp_drop(qx);
 182 }
 183
 184 void bbs_ff(bbs *b, const bbs_priv *bp, mp *n)
 185 {
 186   if (!MP_NEGP(n))
 187     ff(b, bp, n);
 188   else {
 189     n = mp_neg(MP_NEW, n);
 190     rew(b, bp, n);
 191     mp_drop(n);
 192   }
 193 }
 194
 195 void bbs_ffn(bbs *b, const bbs_priv *bp, unsigned long n)
 196   { mp *nn = mp_fromulong(MP_NEW, n); ff(b, bp, nn); mp_drop(nn); }
 197
 198 void bbs_rew(bbs *b, const bbs_priv *bp, mp *n)
 199 {
 200   if (!MP_NEGP(n))
 201     rew(b, bp, n);
 202   else {
 203     n = mp_neg(MP_NEW, n);
 204     ff(b, bp, n);
 205     mp_drop(n);
 206   }
 207 }
 208
 209 void bbs_rewn(bbs *b, const bbs_priv *bp, unsigned long n)
 210   { mp *nn = mp_fromulong(MP_NEW, n); bbs_rew(b, bp, nn); mp_drop(nn); }
 211
 212 /*----- Test rig ----------------------------------------------------------*/
 213
 214 #ifdef TEST_RIG
 215
 216 static int verify(dstr *v)
 217 {
 218   bbs_priv bp;
 219   bbs b;
 220   mp *x;
 221   unsigned long n;
 222   int ok = 1;
 223   uint32 p, q, r;
 224   int i;
 225
 226   bp.p = *(mp **)v[0].buf;
 227   bp.q = *(mp **)v[1].buf;
 228   bp.n = mp_mul(MP_NEW, bp.p, bp.q);
 229   x = *(mp **)v[2].buf;
 230   n = *(unsigned long *)v[3].buf;
 231
 232   bbs_create(&b, bp.n, x);
 233   p = bbs_bits(&b, 32);
 234
 235   bbs_seed(&b, x);
 236   for (i = 0; i < n; i++)
 237     bbs_step(&b);
 238   q = bbs_bits(&b, 32);
 239   bbs_wrap(&b);
 240
 241   bbs_rewn(&b, &bp, n + (32 + b.k - 1) / b.k);
 242   r = bbs_bits(&b, 32);
 243
 244   if (r != p) {
 245     fputs("\n*** bbs rewind failure\n", stderr);
 246     fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
 247     fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
 248     fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
 249     fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
 250     fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
 251     fprintf(stderr, "expected output = %08lx, found %08lx\n",
 252             (unsigned long)p, (unsigned long)r);
 253     ok = 0;
 254   }
 255
 256   bbs_seed(&b, x);
 257   bbs_ffn(&b, &bp, n);
 258   r = bbs_bits(&b, 32);
 259
 260   if (q != r) {
 261     fputs("\n*** bbs fastforward failure\n", stderr);
 262     fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
 263     fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
 264     fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
 265     fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
 266     fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
 267     fprintf(stderr, "expected output = %08lx, found %08lx\n",
 268             (unsigned long)q, (unsigned long)r);
 269     ok = 0;
 270   }
 271
 272   bbs_destroy(&b);
 273   mp_drop(bp.p);
 274   mp_drop(bp.q);
 275   mp_drop(bp.n);
 276   mp_drop(x);
 277
 278   assert(mparena_count(MPARENA_GLOBAL) == 0);
 279   return (ok);
 280 }
 281
 282 static test_chunk tests[] = {
 283   { "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } },
 284   { 0, 0, { 0 } }
 285 };
 286
 287 int main(int argc, char *argv[])
 288 {
 289   sub_init();
 290   test_run(argc, argv, tests, SRCDIR "/tests/bbs");
 291   return (0);
 292 }
 293
 294 #endif
 295
 296 /*----- That's all, folks -------------------------------------------------*/