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

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