5 * Jumping around a BBS sequence
7 * (c) 1999 Straylight/Edgeware
10 /*----- Licensing notice --------------------------------------------------*
12 * This file is part of Catacomb.
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.
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.
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,
30 /*----- Header files ------------------------------------------------------*/
34 #include "mpbarrett.h"
38 /*----- Main code ---------------------------------------------------------*/
42 * Arguments: @bbs *b@ = pointer to BBS generator context
43 * @const bbs_priv *bp@ = pointer to BBS modulus factors
44 * @mp *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
50 * Use: Jumps a BBS context a certain number of places (assuming the
51 * arguments are right).
53 * Let the BBS modulus be %$n = pq$% and the current residue be
54 * %$x$%. Then the computations performed are:
56 * * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%.
58 * * Determine %$e_p = px^n \bmod (p - 1)$% and similarly
59 * %$e_q = qx^n \bmod (p - 1)$%.
61 * * Calculate %$x_p' = x_p^{e_p} \bmod p$% and
62 * %$x_q' = x_q^{e_q} \bmod q$%.
64 * * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder
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
72 * %$(x^2) ^ {(p + 1)/4}$%
73 * %${} = x^{(p + 1)/2}$%
74 * %${} = x \cdot x^{(p - 1)/2}$%
77 * Simple, no? (Note that the division works because
78 * %$p \equiv 3 \pmod 4$%.)
81 static void jump(bbs
*b
, const bbs_priv
*bp
, mp
*n
,
85 mp
*v
[2] = { MP_NEW
, MP_NEW
};
87 /* --- First work out the exponents --- */
93 m
= mp_sub(MP_NEW
, bp
->p
, MP_ONE
);
94 mpbarrett_create(&mb
, m
);
95 ep
= mpbarrett_exp(&mb
, MP_NEW
, px
, n
);
96 mpbarrett_destroy(&mb
);
100 m
= mp_sub(m
, bp
->q
, MP_ONE
);
101 mpbarrett_create(&mb
, m
);
102 eq
= mpbarrett_exp(&mb
, MP_NEW
, qx
, n
);
103 mpbarrett_destroy(&mb
);
109 /* --- Now calculate the residues of @x@ --- */
111 mp_div(0, &v
[0], b
->x
, bp
->p
);
112 mp_div(0, &v
[1], b
->x
, bp
->q
);
114 /* --- Exponentiate --- */
119 mpbarrett_create(&mb
, bp
->p
);
120 v
[0] = mpbarrett_exp(&mb
, v
[0], v
[0], ep
);
121 mpbarrett_destroy(&mb
);
123 mpbarrett_create(&mb
, bp
->q
);
124 v
[1] = mpbarrett_exp(&mb
, v
[1], v
[1], eq
);
125 mpbarrett_destroy(&mb
);
131 /* --- Sort out the result using the Chinese Remainder Theorem --- */
138 mv
[0].m
= MP_COPY(bp
->p
);
139 mv
[1].m
= MP_COPY(bp
->q
);
140 for (i
= 0; i
< 2; i
++)
141 mv
[i
].n
= mv
[i
].ni
= mv
[i
].nni
= MP_NEW
;
142 mpcrt_create(&c
, mv
, 2, b
->mb
.m
);
143 b
->x
= mpcrt_solve(&c
, b
->x
, v
);
147 /* --- Tidy away --- */
155 /* --- @bbs_{ff,rew}{,n}@ --- *
157 * Arguments: @bbs *b@ = pointer to a BBS generator state
158 * @const bbs_priv *bp@ = pointer to BBS modulus factors
159 * @mp *n@, @unsigned long n@ = number of steps to make
163 * Use: `Fast-forwards' or rewinds a Blum-Blum-Shub generator by @n@
164 * steps. The @...n@ versions take an @unsigned long@ argument;
165 * the non-@...n@ versions a multiprecision integer. If @n@ is
166 * negative then the generator is stepped in the reverse
170 static void ff(bbs
*b
, const bbs_priv
*bp
, mp
*n
)
171 { jump(b
, bp
, n
, MP_TWO
, MP_TWO
); }
173 static void rew(bbs
*b
, const bbs_priv
*bp
, mp
*n
)
175 mp
*px
= mp_lsr(MP_NEW
, bp
->p
, 2);
176 mp
*qx
= mp_lsr(MP_NEW
, bp
->q
, 2);
177 px
= mp_add(px
, px
, MP_ONE
);
178 qx
= mp_add(qx
, qx
, MP_ONE
);
179 jump(b
, bp
, n
, px
, qx
);
184 void bbs_ff(bbs
*b
, const bbs_priv
*bp
, mp
*n
)
189 n
= mp_neg(MP_NEW
, n
);
195 void bbs_ffn(bbs
*b
, const bbs_priv
*bp
, unsigned long n
)
196 { mp
*nn
= mp_fromulong(MP_NEW
, n
); ff(b
, bp
, nn
); mp_drop(nn
); }
198 void bbs_rew(bbs
*b
, const bbs_priv
*bp
, mp
*n
)
203 n
= mp_neg(MP_NEW
, n
);
209 void bbs_rewn(bbs
*b
, const bbs_priv
*bp
, unsigned long n
)
210 { mp
*nn
= mp_fromulong(MP_NEW
, n
); bbs_rew(b
, bp
, nn
); mp_drop(nn
); }
212 /*----- Test rig ----------------------------------------------------------*/
216 static int verify(dstr
*v
)
226 bp
.p
= *(mp
**)v
[0].buf
;
227 bp
.q
= *(mp
**)v
[1].buf
;
228 bp
.n
= mp_mul(MP_NEW
, bp
.p
, bp
.q
);
229 x
= *(mp
**)v
[2].buf
;
230 n
= *(unsigned long *)v
[3].buf
;
232 bbs_create(&b
, bp
.n
, x
);
233 p
= bbs_bits(&b
, 32);
236 for (i
= 0; i
< n
; i
++)
238 q
= bbs_bits(&b
, 32);
241 bbs_rewn(&b
, &bp
, n
+ (32 + b
.k
- 1) / b
.k
);
242 r
= bbs_bits(&b
, 32);
245 fputs("\n*** bbs rewind failure\n", stderr
);
246 fputs("p = ", stderr
); mp_writefile(bp
.p
, stderr
, 10); fputc('\n', stderr
);
247 fputs("q = ", stderr
); mp_writefile(bp
.q
, stderr
, 10); fputc('\n', stderr
);
248 fputs("n = ", stderr
); mp_writefile(bp
.n
, stderr
, 10); fputc('\n', stderr
);
249 fputs("x = ", stderr
); mp_writefile(x
, stderr
, 10); fputc('\n', stderr
);
250 fprintf(stderr
, "stepped %lu back\n", n
+ (32 + b
.k
- 1) / b
.k
);
251 fprintf(stderr
, "expected output = %08lx, found %08lx\n",
252 (unsigned long)p
, (unsigned long)r
);
258 r
= bbs_bits(&b
, 32);
261 fputs("\n*** bbs fastforward failure\n", stderr
);
262 fputs("p = ", stderr
); mp_writefile(bp
.p
, stderr
, 10); fputc('\n', stderr
);
263 fputs("q = ", stderr
); mp_writefile(bp
.q
, stderr
, 10); fputc('\n', stderr
);
264 fputs("n = ", stderr
); mp_writefile(bp
.n
, stderr
, 10); fputc('\n', stderr
);
265 fputs("x = ", stderr
); mp_writefile(x
, stderr
, 10); fputc('\n', stderr
);
266 fprintf(stderr
, "stepped %lu back\n", n
+ (32 + b
.k
- 1) / b
.k
);
267 fprintf(stderr
, "expected output = %08lx, found %08lx\n",
268 (unsigned long)q
, (unsigned long)r
);
278 assert(mparena_count(MPARENA_GLOBAL
) == 0);
282 static test_chunk tests
[] = {
283 { "bbs-jump", verify
, { &type_mp
, &type_mp
, &type_mp
, &type_ulong
, 0 } },
287 int main(int argc
, char *argv
[])
290 test_run(argc
, argv
, tests
, SRCDIR
"/tests/bbs");
296 /*----- That's all, folks -------------------------------------------------*/