From 2cc3d1d0b0b535b9ef9ba206fabdf606820f9007 Mon Sep 17 00:00:00 2001 From: mdw Date: Sat, 5 Mar 2005 16:40:13 +0000 Subject: [PATCH] BBS overhaul (incompatible). Jumping is now by bignum quantities, and negative jumps are allowed. All the various cool things are supported via the miscop interface. --- bbs-jump.c | 82 +++++++++++++++++++++++++++++++++++--------------------------- bbs-rand.c | 56 +++++++++++++++++++++++++++++++++++++++++- bbs.h | 48 ++++++++++++++++++------------------ 3 files changed, 126 insertions(+), 60 deletions(-) diff --git a/bbs-jump.c b/bbs-jump.c index 135d048..250c9e2 100644 --- a/bbs-jump.c +++ b/bbs-jump.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: bbs-jump.c,v 1.5 2004/04/08 01:36:15 mdw Exp $ + * $Id$ * * Jumping around a BBS sequence * @@ -40,8 +40,8 @@ /* --- @jump@ --- * * * Arguments: @bbs *b@ = pointer to BBS generator context - * @bbs_priv *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 * @@ -78,7 +78,7 @@ * %$p \equiv 3 \pmod 4$%.) */ -static void jump(bbs *b, bbs_priv *bp, unsigned long n, +static void jump(bbs *b, const bbs_priv *bp, mp *n, mp *px, mp *qx) { mp *ep, *eq; @@ -89,24 +89,21 @@ static void jump(bbs *b, bbs_priv *bp, unsigned long n, { 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@ --- */ @@ -155,38 +152,25 @@ static void jump(bbs *b, bbs_priv *bp, unsigned long n, b->b = b->k; } -/* --- @bbs_ff@ --- * +/* --- @bbs_{ff,rew}{,n}@ --- * * * Arguments: @bbs *b@ = pointer to a BBS generator state - * @bbs_priv *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_priv *bp, unsigned long n) -{ - jump(b, bp, n, MP_TWO, MP_TWO); -} - -/* --- @bbs_rew@ --- * - * - * Arguments: @bbs *b@ = pointer to a BBS generator state - * @bbs_priv *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_priv *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); @@ -197,6 +181,34 @@ void bbs_rew(bbs *b, bbs_priv *bp, unsigned long n) 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 @@ -226,7 +238,7 @@ static int verify(dstr *v) 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) { @@ -242,7 +254,7 @@ static int verify(dstr *v) } bbs_seed(&b, x); - bbs_ff(&b, &bp, n); + bbs_ffn(&b, &bp, n); r = bbs_bits(&b, 32); if (q != r) { diff --git a/bbs-rand.c b/bbs-rand.c index 3d2563a..90669a7 100644 --- a/bbs-rand.c +++ b/bbs-rand.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: bbs-rand.c,v 1.5 2004/04/08 01:36:15 mdw Exp $ + * $Id$ * * Blum-Blum-Shub secure random number generator * @@ -242,6 +242,16 @@ static int gmisc(grand *r, unsigned op, ...) case GRAND_SEEDMP: case GRAND_SEEDRAND: case BBS_SET: + case BBS_STEP: + case BBS_STEPSZ: + case BBS_BITS: + case BBS_WRAP: + case BBS_FF: + case BBS_FFN: + case BBS_REW: + case BBS_REWN: + case BBS_MOD: + case BBS_STATE: rc = 1; break; default: @@ -271,6 +281,50 @@ static int gmisc(grand *r, unsigned op, ...) case BBS_SET: bbs_set(&g->b, va_arg(ap, mp *)); break; + case BBS_STEP: + bbs_step(&g->b); + break; + case BBS_STEPSZ: + rc = g->b.k; + break; + case BBS_BITS: { + unsigned nb = va_arg(ap, unsigned); + uint32 *w = va_arg(ap, uint32 *); + *w = bbs_bits(&g->b, nb); + } break; + case BBS_WRAP: + bbs_wrap(&g->b); + break; + case BBS_FF: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + mp *n = va_arg(ap, mp *); + bbs_ff(&g->b, bp, n); + } break; + case BBS_FFN: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + unsigned long n = va_arg(ap, unsigned long); + bbs_ffn(&g->b, bp, n); + } break; + case BBS_REW: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + mp *n = va_arg(ap, mp *); + bbs_rew(&g->b, bp, n); + } break; + case BBS_REWN: { + const bbs_priv *bp = va_arg(ap, const bbs_priv *); + unsigned long n = va_arg(ap, unsigned long); + bbs_rewn(&g->b, bp, n); + } break; + case BBS_MOD: { + mp **n = va_arg(ap, mp **); + if (*n) MP_DROP(*n); + *n = MP_COPY(g->b.mb.m); + } break; + case BBS_STATE: { + mp **n = va_arg(ap, mp **); + if (*n) MP_DROP(*n); + *n = MP_COPY(g->b.x); + } break; default: GRAND_BADOP; break; diff --git a/bbs.h b/bbs.h index 7c9cbda..96e3e84 100644 --- a/bbs.h +++ b/bbs.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: bbs.h,v 1.7 2004/04/08 01:36:15 mdw Exp $ + * $Id$ * * The Blum-Blum-Shub random bit generator * @@ -213,35 +213,25 @@ extern void bbs_wrap(bbs */*b*/); /*----- Large forwards and backwards jumps --------------------------------*/ -/* --- @bbs_ff@ --- * +/* --- @bbs_{ff,rew}{,n}@ --- * * * Arguments: @bbs *b@ = pointer to a BBS generator state - * @bbs_priv *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. */ -extern void bbs_ff(bbs */*b*/, bbs_priv */*bp*/, unsigned long /*n*/); - -/* --- @bbs_rew@ --- * - * - * Arguments: @bbs *b@ = pointer to a BBS generator state - * @bbs_priv *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. - */ - -extern void bbs_rew(bbs */*b*/, bbs_priv */*bp*/, unsigned long /*n*/); +extern void bbs_ff(bbs */*b*/, const bbs_priv */*bp*/, mp */*n*/); +extern void bbs_ffn(bbs */*b*/, const bbs_priv */*bp*/, unsigned long /*n*/); +extern void bbs_rew(bbs */*b*/, const bbs_priv */*bp*/, mp */*n*/); +extern void bbs_rewn(bbs */*b*/, const bbs_priv */*bp*/, unsigned long /*n*/); /*----- Parameter generation ----------------------------------------------*/ @@ -284,7 +274,17 @@ extern grand *bbs_rand(mp */*m*/, mp */*x*/); /* --- Blum-Blum-Shub-specific misc op codes --- */ enum { - BBS_SET = GRAND_SPECIFIC('B') /* @mp *x@ */ + BBS_SET = GRAND_SPECIFIC('B'), /* @mp *x@ */ + BBS_STEP, /* @void@ */ + BBS_STEPSZ, /* @void@ */ + BBS_BITS, /* @unsigned bits, uint32 *w@ */ + BBS_WRAP, /* @void@ */ + BBS_FF, /* @bbs_priv *p, mp *n@ */ + BBS_FFN, /* @bbs_priv *p, unsigned long n@ */ + BBS_REW, /* @bbs_priv *p, mp *n@ */ + BBS_REWN, /* @bbs_priv *p, unsigned long n@ */ + BBS_MOD, /* @mp **n@ */ + BBS_STATE /* @mp **x@ */ }; /*----- That's all, folks -------------------------------------------------*/ -- 2.11.0