| 1 | /* -*-c-*- |
| 2 | * |
| 3 | * $Id: bbs-jump.c,v 1.5 2004/04/08 01:36:15 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 | /*----- 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 | * @bbs_priv *bp@ = pointer to BBS modulus factors |
| 44 | * @unsigned long 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, bbs_priv *bp, unsigned long 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 | mp *e; |
| 93 | |
| 94 | e = mp_fromulong(MP_NEW, n); |
| 95 | m = mp_sub(MP_NEW, bp->p, MP_ONE); |
| 96 | mpbarrett_create(&mb, m); |
| 97 | ep = mpbarrett_exp(&mb, MP_NEW, px, e); |
| 98 | mpbarrett_destroy(&mb); |
| 99 | if (qx == px) |
| 100 | eq = MP_COPY(ep); |
| 101 | else { |
| 102 | m = mp_sub(m, bp->q, MP_ONE); |
| 103 | mpbarrett_create(&mb, m); |
| 104 | eq = mpbarrett_exp(&mb, MP_NEW, qx, e); |
| 105 | mpbarrett_destroy(&mb); |
| 106 | } |
| 107 | |
| 108 | mp_drop(m); |
| 109 | mp_drop(e); |
| 110 | } |
| 111 | |
| 112 | /* --- Now calculate the residues of @x@ --- */ |
| 113 | |
| 114 | mp_div(0, &v[0], b->x, bp->p); |
| 115 | mp_div(0, &v[1], b->x, bp->q); |
| 116 | |
| 117 | /* --- Exponentiate --- */ |
| 118 | |
| 119 | { |
| 120 | mpbarrett mb; |
| 121 | |
| 122 | mpbarrett_create(&mb, bp->p); |
| 123 | v[0] = mpbarrett_exp(&mb, v[0], v[0], ep); |
| 124 | mpbarrett_destroy(&mb); |
| 125 | |
| 126 | mpbarrett_create(&mb, bp->q); |
| 127 | v[1] = mpbarrett_exp(&mb, v[1], v[1], eq); |
| 128 | mpbarrett_destroy(&mb); |
| 129 | |
| 130 | mp_drop(ep); |
| 131 | mp_drop(eq); |
| 132 | } |
| 133 | |
| 134 | /* --- Sort out the result using the Chinese Remainder Theorem --- */ |
| 135 | |
| 136 | { |
| 137 | mpcrt_mod mv[2]; |
| 138 | mpcrt c; |
| 139 | int i; |
| 140 | |
| 141 | mv[0].m = MP_COPY(bp->p); |
| 142 | mv[1].m = MP_COPY(bp->q); |
| 143 | for (i = 0; i < 2; i++) |
| 144 | mv[i].n = mv[i].ni = mv[i].nni = MP_NEW; |
| 145 | mpcrt_create(&c, mv, 2, b->mb.m); |
| 146 | b->x = mpcrt_solve(&c, b->x, v); |
| 147 | mpcrt_destroy(&c); |
| 148 | } |
| 149 | |
| 150 | /* --- Tidy away --- */ |
| 151 | |
| 152 | mp_drop(v[0]); |
| 153 | mp_drop(v[1]); |
| 154 | b->r = b->x->v[0]; |
| 155 | b->b = b->k; |
| 156 | } |
| 157 | |
| 158 | /* --- @bbs_ff@ --- * |
| 159 | * |
| 160 | * Arguments: @bbs *b@ = pointer to a BBS generator state |
| 161 | * @bbs_priv *bp@ = pointer to BBS modulus factors |
| 162 | * @unsigned long n@ = number of steps to make |
| 163 | * |
| 164 | * Returns: --- |
| 165 | * |
| 166 | * Use: `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps. |
| 167 | * Requires the factorization of the Blum modulus to do this |
| 168 | * efficiently. |
| 169 | */ |
| 170 | |
| 171 | void bbs_ff(bbs *b, bbs_priv *bp, unsigned long n) |
| 172 | { |
| 173 | jump(b, bp, n, MP_TWO, MP_TWO); |
| 174 | } |
| 175 | |
| 176 | /* --- @bbs_rew@ --- * |
| 177 | * |
| 178 | * Arguments: @bbs *b@ = pointer to a BBS generator state |
| 179 | * @bbs_priv *bp@ = pointer to BBS modulus factors |
| 180 | * @unsigned long n@ = number of steps to make |
| 181 | * |
| 182 | * Returns: --- |
| 183 | * |
| 184 | * Use: `Rewinds' a Blum-Blum-Shub generator by @n@ steps. |
| 185 | * Requires the factorization of the Blum modulus to do this |
| 186 | * at all. |
| 187 | */ |
| 188 | |
| 189 | void bbs_rew(bbs *b, bbs_priv *bp, unsigned long n) |
| 190 | { |
| 191 | mp *px = mp_lsr(MP_NEW, bp->p, 2); |
| 192 | mp *qx = mp_lsr(MP_NEW, bp->q, 2); |
| 193 | px = mp_add(px, px, MP_ONE); |
| 194 | qx = mp_add(qx, qx, MP_ONE); |
| 195 | jump(b, bp, n, px, qx); |
| 196 | mp_drop(px); |
| 197 | mp_drop(qx); |
| 198 | } |
| 199 | |
| 200 | /*----- Test rig ----------------------------------------------------------*/ |
| 201 | |
| 202 | #ifdef TEST_RIG |
| 203 | |
| 204 | static int verify(dstr *v) |
| 205 | { |
| 206 | bbs_priv bp; |
| 207 | bbs b; |
| 208 | mp *x; |
| 209 | unsigned long n; |
| 210 | int ok = 1; |
| 211 | uint32 p, q, r; |
| 212 | int i; |
| 213 | |
| 214 | bp.p = *(mp **)v[0].buf; |
| 215 | bp.q = *(mp **)v[1].buf; |
| 216 | bp.n = mp_mul(MP_NEW, bp.p, bp.q); |
| 217 | x = *(mp **)v[2].buf; |
| 218 | n = *(unsigned long *)v[3].buf; |
| 219 | |
| 220 | bbs_create(&b, bp.n, x); |
| 221 | p = bbs_bits(&b, 32); |
| 222 | |
| 223 | bbs_seed(&b, x); |
| 224 | for (i = 0; i < n; i++) |
| 225 | bbs_step(&b); |
| 226 | q = bbs_bits(&b, 32); |
| 227 | bbs_wrap(&b); |
| 228 | |
| 229 | bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k); |
| 230 | r = bbs_bits(&b, 32); |
| 231 | |
| 232 | if (r != p) { |
| 233 | fputs("\n*** bbs rewind failure\n", stderr); |
| 234 | fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr); |
| 235 | fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr); |
| 236 | fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr); |
| 237 | fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr); |
| 238 | fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k); |
| 239 | fprintf(stderr, "expected output = %08lx, found %08lx\n", |
| 240 | (unsigned long)p, (unsigned long)r); |
| 241 | ok = 0; |
| 242 | } |
| 243 | |
| 244 | bbs_seed(&b, x); |
| 245 | bbs_ff(&b, &bp, n); |
| 246 | r = bbs_bits(&b, 32); |
| 247 | |
| 248 | if (q != r) { |
| 249 | fputs("\n*** bbs fastforward failure\n", stderr); |
| 250 | fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr); |
| 251 | fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr); |
| 252 | fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr); |
| 253 | fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr); |
| 254 | fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k); |
| 255 | fprintf(stderr, "expected output = %08lx, found %08lx\n", |
| 256 | (unsigned long)q, (unsigned long)r); |
| 257 | ok = 0; |
| 258 | } |
| 259 | |
| 260 | bbs_destroy(&b); |
| 261 | mp_drop(bp.p); |
| 262 | mp_drop(bp.q); |
| 263 | mp_drop(bp.n); |
| 264 | mp_drop(x); |
| 265 | |
| 266 | assert(mparena_count(MPARENA_GLOBAL) == 0); |
| 267 | return (ok); |
| 268 | } |
| 269 | |
| 270 | static test_chunk tests[] = { |
| 271 | { "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } }, |
| 272 | { 0, 0, { 0 } } |
| 273 | }; |
| 274 | |
| 275 | int main(int argc, char *argv[]) |
| 276 | { |
| 277 | sub_init(); |
| 278 | test_run(argc, argv, tests, SRCDIR "/tests/bbs"); |
| 279 | return (0); |
| 280 | } |
| 281 | |
| 282 | #endif |
| 283 | |
| 284 | /*----- That's all, folks -------------------------------------------------*/ |