[u/mdw/catacomb] / bbs-jump.c

/* -*-c-*-
 *
 * $Id: bbs-jump.c,v 1.4 2000/07/01 11:20:36 mdw Exp $
 *
 * Jumping around a BBS sequence
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * 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.4  2000/07/01 11:20:36  mdw
 * Remove bad type name `bbs_param'.
 *
 * Revision 1.3  2000/06/17 10:44:17  mdw
 * Typesetting fix.
 *
 * 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"
#include "mp.h"
#include "mpbarrett.h"
#include "mpcrt.h"
#include "mpint.h"

/*----- Main code ---------------------------------------------------------*/

/* --- @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
 *		@mp *px@ = exponent mod @p@ for a one-step jump
 *		@mp *qx@ = exponent mod @q@ for a one-step jump
 *
 * Returns:	---
 *
 * Use:		Jumps a BBS context a certain number of places (assuming the
 *		arguments are right).
 *
 *		Let the BBS modulus be %$n = pq$% and the current residue be
 *		%$x$%.  Then the computations performed are:
 *
 *		  * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%.
 *
 *		  * Determine %$e_p = px^n \bmod (p - 1)$% and similarly
 *		    %$e_q = qx^n \bmod (p - 1)$%.
 *
 *		  * Calculate %$x_p' = x_p^{e_p} \bmod p$% and
 *		    %$x_q' = x_q^{e_q} \bmod q$%.
 *
 *		  * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder
 *		    Theorem.
 *
 *		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
 *		%$x$% is a quadratic residue mod $%p$%, then
 *
 *		%$(x^2) ^ {(p + 1)/4}$%
 *		  %${} = x^{(p + 1)/2}$%
 *		  %${} = x \cdot x^{(p - 1)/2}$%
 *		  %${} = x$%
 *
 *		Simple, no?  (Note that the division works because
 *		%$p \equiv 3 \pmod 4$%.)
 */

static void jump(bbs *b, bbs_priv *bp, unsigned long n,
		 mp *px, mp *qx)
{
  mp *ep, *eq;
  mp *v[2] = { MP_NEW, MP_NEW };

  /* --- First work out the exponents --- */

  {
    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);
    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);
      mpbarrett_destroy(&mb);
    }

    mp_drop(m);
    mp_drop(e);
  }

  /* --- Now calculate the residues of @x@ --- */

  mp_div(0, &v[0], b->x, bp->p);
  mp_div(0, &v[1], b->x, bp->q);

  /* --- Exponentiate --- */

  {
    mpbarrett mb;

    mpbarrett_create(&mb, bp->p);
    v[0] = mpbarrett_exp(&mb, v[0], v[0], ep);
    mpbarrett_destroy(&mb);

    mpbarrett_create(&mb, bp->q);
    v[1] = mpbarrett_exp(&mb, v[1], v[1], eq);
    mpbarrett_destroy(&mb);

    mp_drop(ep);
    mp_drop(eq);
  }

  /* --- Sort out the result using the Chinese Remainder Theorem --- */

  {
    mpcrt_mod mv[2];
    mpcrt c;
    int i;

    mv[0].m = MP_COPY(bp->p);
    mv[1].m = MP_COPY(bp->q);
    for (i = 0; i < 2; i++)
      mv[i].n = mv[i].ni = mv[i].nni = MP_NEW;
    mpcrt_create(&c, mv, 2, b->mb.m);
    b->x = mpcrt_solve(&c, b->x, v);
    mpcrt_destroy(&c);
  }

  /* --- Tidy away --- */

  mp_drop(v[0]);
  mp_drop(v[1]);
  b->r = b->x->v[0];
  b->b = b->k;
}

/* --- @bbs_ff@ --- *
 *
 * 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:		`Fast-forwards' a Blum-Blum-Shub generator by @n@ steps.
 *		Requires the factorization of the Blum modulus to do this
 *		efficiently.
 */

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.
 */

void bbs_rew(bbs *b, bbs_priv *bp, unsigned long n)
{
  mp *px = mp_lsr(MP_NEW, bp->p, 2);
  mp *qx = mp_lsr(MP_NEW, bp->q, 2);
  px = mp_add(px, px, MP_ONE);
  qx = mp_add(qx, qx, MP_ONE);
  jump(b, bp, n, px, qx);
  mp_drop(px);
  mp_drop(qx);
}

/*----- Test rig ----------------------------------------------------------*/

#ifdef TEST_RIG

static int verify(dstr *v)
{
  bbs_priv bp;
  bbs b;
  mp *x;
  unsigned long n;
  int ok = 1;
  uint32 p, q, r;
  int i;

  bp.p = *(mp **)v[0].buf;
  bp.q = *(mp **)v[1].buf;
  bp.n = mp_mul(MP_NEW, bp.p, bp.q);
  x = *(mp **)v[2].buf;
  n = *(unsigned long *)v[3].buf;

  bbs_create(&b, bp.n, x);
  p = bbs_bits(&b, 32);

  bbs_seed(&b, x);
  for (i = 0; i < n; i++)
    bbs_step(&b);
  q = bbs_bits(&b, 32);
  bbs_wrap(&b);

  bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k);
  r = bbs_bits(&b, 32);

  if (r != p) {
    fputs("\n*** bbs rewind failure\n", stderr);
    fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
    fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
    fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
    fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
    fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
    fprintf(stderr, "expected output = %08lx, found %08lx\n",
	    (unsigned long)p, (unsigned long)r);
    ok = 0;
  }

  bbs_seed(&b, x);
  bbs_ff(&b, &bp, n);
  r = bbs_bits(&b, 32);

  if (q != r) {
    fputs("\n*** bbs fastforward failure\n", stderr);
    fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
    fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
    fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
    fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
    fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
    fprintf(stderr, "expected output = %08lx, found %08lx\n",
	    (unsigned long)q, (unsigned long)r);
    ok = 0;
  }

  bbs_destroy(&b);
  mp_drop(bp.p);
  mp_drop(bp.q);
  mp_drop(bp.n);
  mp_drop(x);

  assert(mparena_count(MPARENA_GLOBAL) == 0);
  return (ok);
}

static test_chunk tests[] = {
  { "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } },
  { 0, 0, { 0 } }
};

int main(int argc, char *argv[])
{
  sub_init();
  test_run(argc, argv, tests, SRCDIR "/tests/bbs");
  return (0);
}

#endif

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
2c52abe6	1	/* --c--
2c52abe6	2	*
a22bbdf6	3	* $Id: bbs-jump.c,v 1.4 2000/07/01 11:20:36 mdw Exp $
2c52abe6	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	/----- Revision history --------------------------------------------------
	31	*
	32	* $Log: bbs-jump.c,v $
a22bbdf6	33	* Revision 1.4 2000/07/01 11:20:36 mdw
	34	* Remove bad type name `bbs_param'.
	35	*
38f31040	36	* Revision 1.3 2000/06/17 10:44:17 mdw
	37	* Typesetting fix.
	38	*
4f743df5	39	* Revision 1.2 1999/12/22 15:52:08 mdw
	40	* Rename `bbs_params' to `bbs_param' for consistency.
	41	*
2c52abe6	42	* Revision 1.1 1999/12/10 23:14:59 mdw
	43	* Blum-Blum-Shub generator, and Blum-Goldwasser encryption.
	44	*
	45	*/
	46
	47	/----- Header files ------------------------------------------------------/
	48
	49	#include "bbs.h"
	50	#include "mp.h"
	51	#include "mpbarrett.h"
	52	#include "mpcrt.h"
	53	#include "mpint.h"
	54
	55	/----- Main code ---------------------------------------------------------/
	56
	57	/* --- @jump@ --- *
	58	*
	59	* Arguments: @bbs *b@ = pointer to BBS generator context
a22bbdf6	60	* @bbs_priv *bp@ = pointer to BBS modulus factors
2c52abe6	61	* @unsigned long n@ = number of steps to move
	62	* @mp *px@ = exponent mod @p@ for a one-step jump
	63	* @mp *qx@ = exponent mod @q@ for a one-step jump
	64	*
	65	* Returns: ---
	66	*
	67	* Use: Jumps a BBS context a certain number of places (assuming the
	68	* arguments are right).
	69	*
	70	* Let the BBS modulus be %$n = pq$% and the current residue be
	71	* %$x$%. Then the computations performed are:
	72	*
	73	* * Calculate %$x_p = x \bmod p$% and %$x_q = x \bmod q$%.
	74	*
	75	* * Determine %$e_p = px^n \bmod (p - 1)$% and similarly
	76	* %$e_q = qx^n \bmod (p - 1)$%.
	77	*
	78	* * Calculate %$x_p' = x_p^{e_p} \bmod p$% and
	79	* %$x_q' = x_q^{e_q} \bmod q$%.
	80	*
	81	* * Combine %$x_p'$% and %$x_q'$% using the Chinese Remainder
	82	* Theorem.
	83	*
	84	* If you want to step the generator forwards, simply set
	85	* %$px = qx = 2$%. If you want to step backwards, make
38f31040	86	* %$px = (p + 1)/4$% and %$qx = (q + 1)/4$%. Note that, if
2c52abe6	87	* %$x$% is a quadratic residue mod $%p$%, then
	88	*
	89	* %$(x^2) ^ {(p + 1)/4}$%
	90	* %${} = x^{(p + 1)/2}$%
	91	* %${} = x \cdot x^{(p - 1)/2}$%
	92	* %${} = x$%
	93	*
	94	* Simple, no? (Note that the division works because
	95	* %$p \equiv 3 \pmod 4$%.)
	96	*/
	97
a22bbdf6	98	static void jump(bbs b, bbs_priv bp, unsigned long n,
2c52abe6	99	mp px, mp qx)
	100	{
	101	mp ep, eq;
	102	mp *v[2] = { MP_NEW, MP_NEW };
	103
	104	/* --- First work out the exponents --- */
	105
	106	{
	107	mpbarrett mb;
	108	mp *m;
	109	mp *e;
	110
	111	e = mp_fromulong(MP_NEW, n);
	112	m = mp_sub(MP_NEW, bp->p, MP_ONE);
	113	mpbarrett_create(&mb, m);
	114	ep = mpbarrett_exp(&mb, MP_NEW, px, e);
	115	mpbarrett_destroy(&mb);
	116	if (qx == px)
	117	eq = MP_COPY(ep);
	118	else {
	119	m = mp_sub(m, bp->q, MP_ONE);
	120	mpbarrett_create(&mb, m);
	121	eq = mpbarrett_exp(&mb, MP_NEW, qx, e);
	122	mpbarrett_destroy(&mb);
	123	}
	124
	125	mp_drop(m);
	126	mp_drop(e);
	127	}
	128
	129	/* --- Now calculate the residues of @x@ --- */
	130
	131	mp_div(0, &v[0], b->x, bp->p);
	132	mp_div(0, &v[1], b->x, bp->q);
	133
	134	/* --- Exponentiate --- */
	135
	136	{
	137	mpbarrett mb;
	138
	139	mpbarrett_create(&mb, bp->p);
	140	v[0] = mpbarrett_exp(&mb, v[0], v[0], ep);
	141	mpbarrett_destroy(&mb);
	142
	143	mpbarrett_create(&mb, bp->q);
	144	v[1] = mpbarrett_exp(&mb, v[1], v[1], eq);
	145	mpbarrett_destroy(&mb);
	146
	147	mp_drop(ep);
	148	mp_drop(eq);
	149	}
	150
	151	/* --- Sort out the result using the Chinese Remainder Theorem --- */
	152
	153	{
	154	mpcrt_mod mv[2];
	155	mpcrt c;
	156	int i;
	157
	158	mv[0].m = MP_COPY(bp->p);
	159	mv[1].m = MP_COPY(bp->q);
	160	for (i = 0; i < 2; i++)
	161	mv[i].n = mv[i].ni = mv[i].nni = MP_NEW;
	162	mpcrt_create(&c, mv, 2, b->mb.m);
163	b->x = mpcrt_solve(&c, b->x, v);
164	mpcrt_destroy(&c);
165	}
166
167	/* --- Tidy away --- */
168
169	mp_drop(v[0]);
170	mp_drop(v[1]);
171	b->r = b->x->v[0];
172	b->b = b->k;
173	}
174
175	/* --- @bbs_ff@ --- *
176	*
177	* Arguments: @bbs *b@ = pointer to a BBS generator state
a22bbdf6	178	* @bbs_priv *bp@ = pointer to BBS modulus factors
2c52abe6	179	* @unsigned long n@ = number of steps to make
	180	*
	181	* Returns: ---
	182	*
	183	* Use: `Fast-forwards' a Blum-Blum-Shub generator by @n@ steps.
	184	* Requires the factorization of the Blum modulus to do this
	185	* efficiently.
	186	*/
	187
a22bbdf6	188	void bbs_ff(bbs b, bbs_priv bp, unsigned long n)
2c52abe6	189	{
	190	jump(b, bp, n, MP_TWO, MP_TWO);
	191	}
	192
	193	/* --- @bbs_rew@ --- *
	194	*
	195	* Arguments: @bbs *b@ = pointer to a BBS generator state
a22bbdf6	196	* @bbs_priv *bp@ = pointer to BBS modulus factors
2c52abe6	197	* @unsigned long n@ = number of steps to make
	198	*
	199	* Returns: ---
	200	*
	201	* Use: `Rewinds' a Blum-Blum-Shub generator by @n@ steps.
	202	* Requires the factorization of the Blum modulus to do this
	203	* at all.
	204	*/
	205
a22bbdf6	206	void bbs_rew(bbs b, bbs_priv bp, unsigned long n)
2c52abe6	207	{
	208	mp *px = mp_lsr(MP_NEW, bp->p, 2);
	209	mp *qx = mp_lsr(MP_NEW, bp->q, 2);
	210	px = mp_add(px, px, MP_ONE);
	211	qx = mp_add(qx, qx, MP_ONE);
	212	jump(b, bp, n, px, qx);
	213	mp_drop(px);
	214	mp_drop(qx);
	215	}
	216
	217	/----- Test rig ----------------------------------------------------------/
	218
	219	#ifdef TEST_RIG
	220
	221	static int verify(dstr *v)
	222	{
a22bbdf6	223	bbs_priv bp;
2c52abe6	224	bbs b;
	225	mp *x;
	226	unsigned long n;
	227	int ok = 1;
	228	uint32 p, q, r;
	229	int i;
	230
	231	bp.p = (mp *)v[0].buf;
	232	bp.q = (mp *)v[1].buf;
	233	bp.n = mp_mul(MP_NEW, bp.p, bp.q);
	234	x = (mp *)v[2].buf;
	235	n = (unsigned long )v[3].buf;
	236
	237	bbs_create(&b, bp.n, x);
	238	p = bbs_bits(&b, 32);
	239
	240	bbs_seed(&b, x);
	241	for (i = 0; i < n; i++)
	242	bbs_step(&b);
	243	q = bbs_bits(&b, 32);
	244	bbs_wrap(&b);
	245
	246	bbs_rew(&b, &bp, n + (32 + b.k - 1) / b.k);
	247	r = bbs_bits(&b, 32);
	248
	249	if (r != p) {
	250	fputs("\n*** bbs rewind failure\n", stderr);
	251	fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
	252	fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
	253	fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
	254	fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
	255	fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
	256	fprintf(stderr, "expected output = %08lx, found %08lx\n",
	257	(unsigned long)p, (unsigned long)r);
	258	ok = 0;
	259	}
	260
	261	bbs_seed(&b, x);
	262	bbs_ff(&b, &bp, n);
	263	r = bbs_bits(&b, 32);
	264
	265	if (q != r) {
	266	fputs("\n*** bbs fastforward failure\n", stderr);
	267	fputs("p = ", stderr); mp_writefile(bp.p, stderr, 10); fputc('\n', stderr);
	268	fputs("q = ", stderr); mp_writefile(bp.q, stderr, 10); fputc('\n', stderr);
	269	fputs("n = ", stderr); mp_writefile(bp.n, stderr, 10); fputc('\n', stderr);
	270	fputs("x = ", stderr); mp_writefile(x, stderr, 10); fputc('\n', stderr);
	271	fprintf(stderr, "stepped %lu back\n", n + (32 + b.k - 1) / b.k);
	272	fprintf(stderr, "expected output = %08lx, found %08lx\n",
	273	(unsigned long)q, (unsigned long)r);
	274	ok = 0;
	275	}
	276
	277	bbs_destroy(&b);
	278	mp_drop(bp.p);
	279	mp_drop(bp.q);
	280	mp_drop(bp.n);
	281	mp_drop(x);
	282
	283	assert(mparena_count(MPARENA_GLOBAL) == 0);
	284	return (ok);
	285	}
	286
	287	static test_chunk tests[] = {
288	{ "bbs-jump", verify, { &type_mp, &type_mp, &type_mp, &type_ulong, 0 } },
289	{ 0, 0, { 0 } }
290	};
291
292	int main(int argc, char *argv[])
293	{
294	sub_init();
295	test_run(argc, argv, tests, SRCDIR "/tests/bbs");
296	return (0);
297	}
298
299	#endif
300
301	/----- That's all, folks -------------------------------------------------/