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

   1 /* -*-c-*-
   2  *
   3  * $Id: bbs-jump.c,v 1.3 2000/06/17 10:44:17 mdw Exp $
   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 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: bbs-jump.c,v $
  33  * Revision 1.3  2000/06/17 10:44:17  mdw
  34  * Typesetting fix.
  35  *
  36  * Revision 1.2  1999/12/22 15:52:08  mdw
  37  * Rename `bbs_params' to `bbs_param' for consistency.
  38  *
  39  * Revision 1.1  1999/12/10 23:14:59  mdw
  40  * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
  41  *
  42  */
  43
  44 /*----- Header files ------------------------------------------------------*/
  45
  46 #include "bbs.h"
  47 #include "mp.h"
  48 #include "mpbarrett.h"
  49 #include "mpcrt.h"
  50 #include "mpint.h"
  51
  52 /*----- Main code ---------------------------------------------------------*/
  53
  54 /* --- @jump@ --- *
  55  *
  56  * Arguments:   @bbs *b@ = pointer to BBS generator context
  57  *              @bbs_param *bp@ = pointer to BBS modulus factors
  58  *              @unsigned long n@ = number of steps to move
  59  *              @mp *px@ = exponent mod @p@ for a one-step jump
  60  *              @mp *qx@ = exponent mod @q@ for a one-step jump
  61  *
  62  * Returns:     ---
  63  *
  64  * Use:         Jumps a BBS context a certain number of places (assuming the
  65  *              arguments are right).
  66  *
  67  *              Let the BBS modulus be %$n = pq$% and the current residue be
  68  *              %$x$%.  Then the computations performed are:
  69  *
  70  *                * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%.
  71  *
  72  *                * Determine %$e_p = px^n \bmod (p - 1)$% and similarly
  73  *                  %$e_q = qx^n \bmod (p - 1)$%.
  74  *
  75  *                * Calculate %$x_p' = x_p^{e_p} \bmod p$% and
  76  *                  %$x_q' = x_q^{e_q} \bmod q$%.
  77  *
  78  *                * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder
  79  *                  Theorem.
  80  *
  81  *              If you want to step the generator forwards, simply set
  82  *              %$px = qx = 2$%.  If you want to step backwards, make
  83  *              %$px = (p + 1)/4$% and %$qx = (q + 1)/4$%.  Note that, if
  84  *              %$x$% is a quadratic residue mod $%p$%, then
  85  *
  86  *              %$(x^2) ^ {(p + 1)/4}$%
  87  *                %${} = x^{(p + 1)/2}$%
  88  *                %${} = x \cdot x^{(p - 1)/2}$%
  89  *                %${} = x$%
  90  *
  91  *              Simple, no?  (Note that the division works because
  92  *              %$p \equiv 3 \pmod 4$%.)
  93  */
  94
  95 static void jump(bbs *b, bbs_param *bp, unsigned long n,
  96                  mp *px, mp *qx)
  97 {
  98   mp *ep, *eq;
  99   mp *v[2] = { MP_NEW, MP_NEW };
 100
 101   /* --- First work out the exponents --- */
 102
 103   {
 104     mpbarrett mb;
 105     mp *m;
 106     mp *e;
 107
 108     e = mp_fromulong(MP_NEW, n);
 109     m = mp_sub(MP_NEW, bp->p, MP_ONE);
 110     mpbarrett_create(&mb, m);
 111     ep = mpbarrett_exp(&mb, MP_NEW, px, e);
 112     mpbarrett_destroy(&mb);
 113     if (qx == px)
 114       eq = MP_COPY(ep);
 115     else {
 116       m = mp_sub(m, bp->q, MP_ONE);
 117       mpbarrett_create(&mb, m);
 118       eq = mpbarrett_exp(&mb, MP_NEW, qx, e);
 119       mpbarrett_destroy(&mb);
 120     }
 121
 122     mp_drop(m);
 123     mp_drop(e);
 124   }
 125
 126   /* --- Now calculate the residues of @x@ --- */
 127
 128   mp_div(0, &v[0], b->x, bp->p);
 129   mp_div(0, &v[1], b->x, bp->q);
 130
 131   /* --- Exponentiate --- */
 132
 133   {
 134     mpbarrett mb;
 135
 136     mpbarrett_create(&mb, bp->p);
 137     v[0] = mpbarrett_exp(&mb, v[0], v[0], ep);
 138     mpbarrett_destroy(&mb);
 139
 140     mpbarrett_create(&mb, bp->q);
 141     v[1] = mpbarrett_exp(&mb, v[1], v[1], eq);
 142     mpbarrett_destroy(&mb);
 143
 144     mp_drop(ep);
 145     mp_drop(eq);
 146   }
 147
 148   /* --- Sort out the result using the Chinese Remainder Theorem --- */
 149
 150   {
 151     mpcrt_mod mv[2];
 152     mpcrt c;
 153     int i;
 154
 155     mv[0].m = MP_COPY(bp->p);
 156     mv[1].m = MP_COPY(bp->q);
 157     for (i = 0; i < 2; i++)
 158       mv[i].n = mv[i].ni = mv[i].nni = MP_NEW;
 159     mpcrt_create(&c, mv, 2, b->mb.m);
 160     b->x = mpcrt_solve(&c, b->x, v);
 161     mpcrt_destroy(&c);
 162   }
 163
 164   /* --- Tidy away --- */
 165
 166   mp_drop(v[0]);
 167   mp_drop(v[1]);
 168   b->r = b->x->v[0];
 169   b->b = b->k;
 170 }
 171
 172 /* --- @bbs_ff@ --- *
 173  *
 174  * Arguments:   @bbs *b@ = pointer to a BBS generator state
 175  *              @bbs_param *bp@ = pointer to BBS modulus factors
 176  *              @unsigned long n@ = number of steps to make
 177  *
 178  * Returns:     ---
 179  *
 180  * Use:         `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps.
 181  *              Requires the factorization of the Blum modulus to do this
 182  *              efficiently.
 183  */
 184
 185 void bbs_ff(bbs *b, bbs_param *bp, unsigned long n)
 186 {
 187   jump(b, bp, n, MP_TWO, MP_TWO);
 188 }
 189
 190 /* --- @bbs_rew@ --- *
 191  *
 192  * Arguments:   @bbs *b@ = pointer to a BBS generator state
 193  *              @bbs_param *bp@ = pointer to BBS modulus factors
 194  *              @unsigned long n@ = number of steps to make
 195  *
 196  * Returns:     ---
 197  *
 198  * Use:         `Rewinds' a Blum-Blum-Shub generator by @n@ steps.
 199  *              Requires the factorization of the Blum modulus to do this
 200  *              at all.
 201  */
 202
 203 void bbs_rew(bbs *b, bbs_param *bp, unsigned long n)
 204 {
 205   mp *px = mp_lsr(MP_NEW, bp->p, 2);
 206   mp *qx = mp_lsr(MP_NEW, bp->q, 2);
 207   px = mp_add(px, px, MP_ONE);
 208   qx = mp_add(qx, qx, MP_ONE);
 209   jump(b, bp, n, px, qx);
 210   mp_drop(px);
 211   mp_drop(qx);
 212 }
 213
 214 /*----- Test rig ----------------------------------------------------------*/
 215
 216 #ifdef TEST_RIG
 217
 218 static int verify(dstr *v)
 219 {
 220   bbs_param bp;
 221   bbs b;
 222   mp *x;
 223   unsigned long n;
 224   int ok = 1;
 225   uint32 p, q, r;
 226   int i;
 227
 228   bp.p = *(mp **)v[0].buf;
 229   bp.q = *(mp **)v[1].buf;
 230   bp.n = mp_mul(MP_NEW, bp.p, bp.q);
 231   x = *(mp **)v[2].buf;
 232   n = *(unsigned long *)v[3].buf;
 233
 234   bbs_create(&b, bp.n, x);
 235   p = bbs_bits(&b, 32);
 236
 237   bbs_seed(&b, x);
 238   for (i = 0; i < n; i++)
 239     bbs_step(&b);
 240   q = bbs_bits(&b, 32);
 241   bbs_wrap(&b);
 242
 243   bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k);
 244   r = bbs_bits(&b, 32);
 245
 246   if (r != p) {
 247     fputs("\n*** bbs rewind failure\n", stderr);
 248     fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
 249     fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
 250     fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
 251     fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
 252     fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
 253     fprintf(stderr, "expected output = %08lx, found %08lx\n",
 254             (unsigned long)p, (unsigned long)r);
 255     ok = 0;
 256   }
 257
 258   bbs_seed(&b, x);
 259   bbs_ff(&b, &bp, n);
 260   r = bbs_bits(&b, 32);
 261
 262   if (q != r) {
 263     fputs("\n*** bbs fastforward failure\n", stderr);
 264     fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
 265     fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
 266     fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
 267     fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
 268     fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
 269     fprintf(stderr, "expected output = %08lx, found %08lx\n",
 270             (unsigned long)q, (unsigned long)r);
 271     ok = 0;
 272   }
 273
 274   bbs_destroy(&b);
 275   mp_drop(bp.p);
 276   mp_drop(bp.q);
 277   mp_drop(bp.n);
 278   mp_drop(x);
 279
 280   assert(mparena_count(MPARENA_GLOBAL) == 0);
 281   return (ok);
 282 }
 283
 284 static test_chunk tests[] = {
 285   { "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } },
 286   { 0, 0, { 0 } }
 287 };
 288
 289 int main(int argc, char *argv[])
 290 {
 291   sub_init();
 292   test_run(argc, argv, tests, SRCDIR "/tests/bbs");
 293   return (0);
 294 }
 295
 296 #endif
 297
 298 /*----- That's all, folks -------------------------------------------------*/