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

/* -*-c-*-
 *
 * $Id: bbs-jump.c,v 1.3 2000/06/17 10:44:17 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.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_param *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_param *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_param *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_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.
 */

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