3 * Jumping around a BBS sequence
5 * (c) 1999 Straylight/Edgeware
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Catacomb.
12 * Catacomb is free software; you can redistribute it and/or modify
13 * it under the terms of the GNU Library General Public License as
14 * published by the Free Software Foundation; either version 2 of the
15 * License, or (at your option) any later version.
17 * Catacomb is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20 * GNU Library General Public License for more details.
22 * You should have received a copy of the GNU Library General Public
23 * License along with Catacomb; if not, write to the Free
24 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
28 /*----- Header files ------------------------------------------------------*/
32 #include "mpbarrett.h"
36 /*----- Main code ---------------------------------------------------------*/
40 * Arguments: @bbs *b@ = pointer to BBS generator context
41 * @const bbs_priv *bp@ = pointer to BBS modulus factors
42 * @mp *n@ = number of steps to move
43 * @mp *px@ = exponent mod @p@ for a one-step jump
44 * @mp *qx@ = exponent mod @q@ for a one-step jump
48 * Use: Jumps a BBS context a certain number of places (assuming the
49 * arguments are right).
51 * Let the BBS modulus be %$n = pq$% and the current residue be
52 * %$x$%. Then the computations performed are:
54 * * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%.
56 * * Determine %$e_p = px^n \bmod (p - 1)$% and similarly
57 * %$e_q = qx^n \bmod (p - 1)$%.
59 * * Calculate %$x_p' = x_p^{e_p} \bmod p$% and
60 * %$x_q' = x_q^{e_q} \bmod q$%.
62 * * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder
65 * If you want to step the generator forwards, simply set
66 * %$px = qx = 2$%. If you want to step backwards, make
67 * %$px = (p + 1)/4$% and %$qx = (q + 1)/4$%. Note that, if
68 * %$x$% is a quadratic residue mod $%p$%, then
70 * %$(x^2) ^ {(p + 1)/4}$%
71 * %${} = x^{(p + 1)/2}$%
72 * %${} = x \cdot x^{(p - 1)/2}$%
75 * Simple, no? (Note that the division works because
76 * %$p \equiv 3 \pmod 4$%.)
79 static void jump(bbs *b, const bbs_priv *bp, mp *n,
83 mp *v[2] = { MP_NEW, MP_NEW };
85 /* --- First work out the exponents --- */
91 m = mp_sub(MP_NEW, bp->p, MP_ONE);
92 mpbarrett_create(&mb, m);
93 ep = mpbarrett_exp(&mb, MP_NEW, px, n);
94 mpbarrett_destroy(&mb);
98 m = mp_sub(m, bp->q, MP_ONE);
99 mpbarrett_create(&mb, m);
100 eq = mpbarrett_exp(&mb, MP_NEW, qx, n);
101 mpbarrett_destroy(&mb);
107 /* --- Now calculate the residues of @x@ --- */
109 mp_div(0, &v[0], b->x, bp->p);
110 mp_div(0, &v[1], b->x, bp->q);
112 /* --- Exponentiate --- */
117 mpbarrett_create(&mb, bp->p);
118 v[0] = mpbarrett_exp(&mb, v[0], v[0], ep);
119 mpbarrett_destroy(&mb);
121 mpbarrett_create(&mb, bp->q);
122 v[1] = mpbarrett_exp(&mb, v[1], v[1], eq);
123 mpbarrett_destroy(&mb);
129 /* --- Sort out the result using the Chinese Remainder Theorem --- */
136 mv[0].m = MP_COPY(bp->p);
137 mv[1].m = MP_COPY(bp->q);
138 for (i = 0; i < 2; i++)
139 mv[i].n = mv[i].ni = mv[i].nni = MP_NEW;
140 mpcrt_create(&c, mv, 2, b->mb.m);
141 b->x = mpcrt_solve(&c, b->x, v);
145 /* --- Tidy away --- */
153 /* --- @bbs_{ff,rew}{,n}@ --- *
155 * Arguments: @bbs *b@ = pointer to a BBS generator state
156 * @const bbs_priv *bp@ = pointer to BBS modulus factors
157 * @mp *n@, @unsigned long n@ = number of steps to make
161 * Use: `Fast-forwards' or rewinds a Blum-Blum-Shub generator by @n@
162 * steps. The @...n@ versions take an @unsigned long@ argument;
163 * the non-@...n@ versions a multiprecision integer. If @n@ is
164 * negative then the generator is stepped in the reverse
168 static void ff(bbs *b, const bbs_priv *bp, mp *n)
169 { jump(b, bp, n, MP_TWO, MP_TWO); }
171 static void rew(bbs *b, const bbs_priv *bp, mp *n)
173 mp *px = mp_lsr(MP_NEW, bp->p, 2);
174 mp *qx = mp_lsr(MP_NEW, bp->q, 2);
175 px = mp_add(px, px, MP_ONE);
176 qx = mp_add(qx, qx, MP_ONE);
177 jump(b, bp, n, px, qx);
182 void bbs_ff(bbs *b, const bbs_priv *bp, mp *n)
187 n = mp_neg(MP_NEW, n);
193 void bbs_ffn(bbs *b, const bbs_priv *bp, unsigned long n)
194 { mp *nn = mp_fromulong(MP_NEW, n); ff(b, bp, nn); mp_drop(nn); }
196 void bbs_rew(bbs *b, const bbs_priv *bp, mp *n)
201 n = mp_neg(MP_NEW, n);
207 void bbs_rewn(bbs *b, const bbs_priv *bp, unsigned long n)
208 { mp *nn = mp_fromulong(MP_NEW, n); bbs_rew(b, bp, nn); mp_drop(nn); }
210 /*----- Test rig ----------------------------------------------------------*/
214 static int verify(dstr *v)
224 bp.p = *(mp **)v[0].buf;
225 bp.q = *(mp **)v[1].buf;
226 bp.n = mp_mul(MP_NEW, bp.p, bp.q);
227 x = *(mp **)v[2].buf;
228 n = *(unsigned long *)v[3].buf;
230 bbs_create(&b, bp.n, x);
231 p = bbs_bits(&b, 32);
234 for (i = 0; i < n; i++)
236 q = bbs_bits(&b, 32);
239 bbs_rewn(&b, &bp, n + (32 + b.k - 1) / b.k);
240 r = bbs_bits(&b, 32);
243 fputs("\n*** bbs rewind failure\n", stderr);
244 fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
245 fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
246 fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
247 fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
248 fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
249 fprintf(stderr, "expected output = %08lx, found %08lx\n",
250 (unsigned long)p, (unsigned long)r);
256 r = bbs_bits(&b, 32);
259 fputs("\n*** bbs fastforward failure\n", stderr);
260 fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
261 fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
262 fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
263 fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
264 fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
265 fprintf(stderr, "expected output = %08lx, found %08lx\n",
266 (unsigned long)q, (unsigned long)r);
276 assert(mparena_count(MPARENA_GLOBAL) == 0);
280 static test_chunk tests[] = {
281 { "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } },
285 int main(int argc, char *argv[])
288 test_run(argc, argv, tests, SRCDIR "/t/bbs");
294 /*----- That's all, folks -------------------------------------------------*/