/* -*-c-*-
*
- * $Id: bbs-jump.c,v 1.2 1999/12/22 15:52:08 mdw Exp $
+ * $Id$
*
* Jumping around a BBS sequence
*
* (c) 1999 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of Catacomb.
*
* it under the terms of the GNU Library General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
- *
+ *
* Catacomb is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Library General Public License for more details.
- *
+ *
* You should have received a copy of the GNU Library General Public
* License along with Catacomb; if not, write to the Free
* Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
* MA 02111-1307, USA.
*/
-/*----- Revision history --------------------------------------------------*
- *
- * $Log: bbs-jump.c,v $
- * Revision 1.2 1999/12/22 15:52:08 mdw
- * Rename `bbs_params' to `bbs_param' for consistency.
- *
- * Revision 1.1 1999/12/10 23:14:59 mdw
- * Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
- *
- */
-
/*----- Header files ------------------------------------------------------*/
#include "bbs.h"
/* --- @jump@ --- *
*
* Arguments: @bbs *b@ = pointer to BBS generator context
- * @bbs_param *bp@ = pointer to BBS modulus factors
- * @unsigned long n@ = number of steps to move
+ * @const bbs_priv *bp@ = pointer to BBS modulus factors
+ * @mp *n@ = number of steps to move
* @mp *px@ = exponent mod @p@ for a one-step jump
* @mp *qx@ = exponent mod @q@ for a one-step jump
*
*
* If you want to step the generator forwards, simply set
* %$px = qx = 2$%. If you want to step backwards, make
- * %$px = (p + 1)/4$% and %$qx = (q + 1)/4%$. Note that, if
+ * %$px = (p + 1)/4$% and %$qx = (q + 1)/4$%. Note that, if
* %$x$% is a quadratic residue mod $%p$%, then
*
* %$(x^2) ^ {(p + 1)/4}$%
* %$p \equiv 3 \pmod 4$%.)
*/
-static void jump(bbs *b, bbs_param *bp, unsigned long n,
+static void jump(bbs *b, const bbs_priv *bp, mp *n,
mp *px, mp *qx)
{
mp *ep, *eq;
{
mpbarrett mb;
mp *m;
- mp *e;
- e = mp_fromulong(MP_NEW, n);
m = mp_sub(MP_NEW, bp->p, MP_ONE);
mpbarrett_create(&mb, m);
- ep = mpbarrett_exp(&mb, MP_NEW, px, e);
+ ep = mpbarrett_exp(&mb, MP_NEW, px, n);
mpbarrett_destroy(&mb);
if (qx == px)
eq = MP_COPY(ep);
else {
m = mp_sub(m, bp->q, MP_ONE);
mpbarrett_create(&mb, m);
- eq = mpbarrett_exp(&mb, MP_NEW, qx, e);
+ eq = mpbarrett_exp(&mb, MP_NEW, qx, n);
mpbarrett_destroy(&mb);
}
mp_drop(m);
- mp_drop(e);
}
/* --- Now calculate the residues of @x@ --- */
b->b = b->k;
}
-/* --- @bbs_ff@ --- *
+/* --- @bbs_{ff,rew}{,n}@ --- *
*
* Arguments: @bbs *b@ = pointer to a BBS generator state
- * @bbs_param *bp@ = pointer to BBS modulus factors
- * @unsigned long n@ = number of steps to make
+ * @const bbs_priv *bp@ = pointer to BBS modulus factors
+ * @mp *n@, @unsigned long n@ = number of steps to make
*
* Returns: ---
*
- * Use: `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps.
- * Requires the factorization of the Blum modulus to do this
- * efficiently.
+ * Use: `Fast-forwards' or rewinds a Blum-Blum-Shub generator by @n@
+ * steps. The @...n@ versions take an @unsigned long@ argument;
+ * the non-@...n@ versions a multiprecision integer. If @n@ is
+ * negative then the generator is stepped in the reverse
+ * direction.
*/
-void bbs_ff(bbs *b, bbs_param *bp, unsigned long n)
-{
- jump(b, bp, n, MP_TWO, MP_TWO);
-}
-
-/* --- @bbs_rew@ --- *
- *
- * Arguments: @bbs *b@ = pointer to a BBS generator state
- * @bbs_param *bp@ = pointer to BBS modulus factors
- * @unsigned long n@ = number of steps to make
- *
- * Returns: ---
- *
- * Use: `Rewinds' a Blum-Blum-Shub generator by @n@ steps.
- * Requires the factorization of the Blum modulus to do this
- * at all.
- */
+static void ff(bbs *b, const bbs_priv *bp, mp *n)
+ { jump(b, bp, n, MP_TWO, MP_TWO); }
-void bbs_rew(bbs *b, bbs_param *bp, unsigned long n)
+static void rew(bbs *b, const bbs_priv *bp, mp *n)
{
mp *px = mp_lsr(MP_NEW, bp->p, 2);
mp *qx = mp_lsr(MP_NEW, bp->q, 2);
mp_drop(qx);
}
+void bbs_ff(bbs *b, const bbs_priv *bp, mp *n)
+{
+ if (!MP_NEGP(n))
+ ff(b, bp, n);
+ else {
+ n = mp_neg(MP_NEW, n);
+ rew(b, bp, n);
+ mp_drop(n);
+ }
+}
+
+void bbs_ffn(bbs *b, const bbs_priv *bp, unsigned long n)
+ { mp *nn = mp_fromulong(MP_NEW, n); ff(b, bp, nn); mp_drop(nn); }
+
+void bbs_rew(bbs *b, const bbs_priv *bp, mp *n)
+{
+ if (!MP_NEGP(n))
+ rew(b, bp, n);
+ else {
+ n = mp_neg(MP_NEW, n);
+ ff(b, bp, n);
+ mp_drop(n);
+ }
+}
+
+void bbs_rewn(bbs *b, const bbs_priv *bp, unsigned long n)
+ { mp *nn = mp_fromulong(MP_NEW, n); bbs_rew(b, bp, nn); mp_drop(nn); }
+
/*----- Test rig ----------------------------------------------------------*/
#ifdef TEST_RIG
static int verify(dstr *v)
{
- bbs_param bp;
+ bbs_priv bp;
bbs b;
mp *x;
unsigned long n;
q = bbs_bits(&b, 32);
bbs_wrap(&b);
- bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k);
+ bbs_rewn(&b, &bp, n + (32 + b.k - 1) / b.k);
r = bbs_bits(&b, 32);
if (r != p) {
}
bbs_seed(&b, x);
- bbs_ff(&b, &bp, n);
+ bbs_ffn(&b, &bp, n);
r = bbs_bits(&b, 32);
if (q != r) {
projects / u / mdw / catacomb / blobdiff