git.distorted.org.uk Git - u/mdw/catacomb/blob - bbs-jump.c

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