[u/mdw/catacomb] / mpmont-mexp.c

/* -*-c-*-
 *
 * $Id: mpmont-mexp.c,v 1.7 2002/01/13 13:49:14 mdw Exp $
 *
 * Multiple simultaneous exponentiations
 *
 * (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: mpmont-mexp.c,v $
 * Revision 1.7  2002/01/13 13:49:14  mdw
 * Make @const@-correct.
 *
 * Revision 1.6  2001/06/16 13:00:20  mdw
 * Use the generic exponentiation functions.
 *
 * Revision 1.5  2000/10/08 12:11:22  mdw
 * Use @MP_EQ@ instead of @MP_CMP@.
 *
 * Revision 1.4  2000/06/17 11:45:09  mdw
 * Major memory management overhaul.  Added arena support.  Use the secure
 * arena for secret integers.  Replace and improve the MP management macros
 * (e.g., replace MP_MODIFY by MP_DEST).
 *
 * Revision 1.3  1999/12/10 23:18:39  mdw
 * Change interface for suggested destinations.
 *
 * Revision 1.2  1999/11/21 11:35:10  mdw
 * Performance improvement: use @mp_sqr@ and @mpmont_reduce@ instead of
 * @mpmont_mul@ for squaring in exponentiation.
 *
 * Revision 1.1  1999/11/19 13:19:29  mdw
 * Simultaneous exponentiation support.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include "mp.h"
#include "mpmont.h"

#define EXP_WINSZ 3
#include "mpmont-exp.h"

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

/* --- @mpmont_mexpr@ --- *
 *
 * Arguments:	@mpmont *mm@ = pointer to Montgomery reduction context
 *		@mp *d@ = fake destination
 *		@mp_expfactor *f@ = pointer to array of factors
 *		@size_t n@ = number of factors supplied
 *
 * Returns:	If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
 *		exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
 *		is:
 *
 *		%$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
 *
 *		except that the %$g_i$% and result are in Montgomery form.
 */

mp *mpmont_mexpr(mpmont *mm, mp *d, mp_expfactor *f, size_t n)
{
  mp *a = mp_copy(mm->r);
  mp *spare;
  size_t i;

  spare = MP_NEW;
  for (i = 0; i < n; i++) {
    if (f[i].exp->f & MP_BURN) {
      spare = MP_NEWSEC;
      break;
    }
  }

  EXP_SIMUL(a, f, n);
  mp_drop(d);
  mp_drop(spare);
  return (a);
}

/* --- @mpmont_mexp@ --- *
 *
 * Arguments:	@mpmont *mm@ = pointer to Montgomery reduction context
 *		@mp *d@ = fake destination
 *		@const mp_expfactor *f@ = pointer to array of factors
 *		@size_t n@ = number of factors supplied
 *
 * Returns:	Product of bases raised to exponents, all mod @m@.
 *
 * Use:		Convenient interface over @mpmont_mexpr@.
 */

mp *mpmont_mexp(mpmont *mm, mp *d, const mp_expfactor *f, size_t n)
{
  mp_expfactor *v = xmalloc(sizeof(*v) * n);
  size_t i;

  for (i = 0; i < n; i++) {
    v[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
    v[i].exp = f[i].exp;
  }
  d = mpmont_mexpr(mm, d, v, n);
  for (i = 0; i < n; i++)
    MP_DROP(v[i].base);
  xfree(v);
  d = mpmont_reduce(mm, d, d);
  return (d);
}

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

#ifdef TEST_RIG

#include <mLib/testrig.h>

static int verify(size_t n, dstr *v)
{
  mp *m = *(mp **)v[0].buf;
  mp_expfactor *f = xmalloc(n * sizeof(*f));
  mp *r, *rr;
  size_t i, j;
  mpmont mm;
  int ok = 1;

  j = 1;
  for (i = 0; i < n; i++) {
    f[i].base = *(mp **)v[j++].buf;
    f[i].exp = *(mp **)v[j++].buf;
  }

  rr = *(mp **)v[j].buf;
  mpmont_create(&mm, m);
  r = mpmont_mexp(&mm, MP_NEW, f, n);
  if (!MP_EQ(r, rr)) {
    fputs("\n*** mexp failed\n", stderr);
    fputs("m = ", stderr); mp_writefile(m, stderr, 10);
    for (i = 0; i < n; i++) {
      fprintf(stderr, "\ng_%u = ", i);
      mp_writefile(f[i].base, stderr, 10);
      fprintf(stderr, "\ne_%u = ", i);
      mp_writefile(f[i].exp, stderr, 10);
    }
    fputs("\nr = ", stderr); mp_writefile(r, stderr, 10);
    fputs("\nR = ", stderr); mp_writefile(rr, stderr, 10);
    fputc('\n', stderr);
    ok = 0;
  }

  for (i = 0; i < n; i++) {
    MP_DROP(f[i].base);
    MP_DROP(f[i].exp);
  }
  MP_DROP(m);
  MP_DROP(r);
  MP_DROP(rr);
  mpmont_destroy(&mm);
  assert(mparena_count(MPARENA_GLOBAL) == 0);
  return (ok);
}

static int t1(dstr *v) { return verify(1, v); }
static int t2(dstr *v) { return verify(2, v); }
static int t3(dstr *v) { return verify(3, v); }
static int t4(dstr *v) { return verify(4, v); }
static int t5(dstr *v) { return verify(5, v); }

static test_chunk tests[] = {
  { "mexp-1", t1, { &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, 0 } },
  { "mexp-2", t2, { &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, 0 } },
  { "mexp-3", t3, { &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, 0 } },
  { "mexp-4", t4, { &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, 0 } },
  { "mexp-5", t5, { &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, &type_mp,
		    &type_mp, 0 } },
  { 0, 0, { 0 } }
};

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

#endif

/*----- That's all, folks -------------------------------------------------*/
Commit	Line	Data
4cc02d06	1	/* --c--
4cc02d06	2	*
3beded37	3	* $Id: mpmont-mexp.c,v 1.7 2002/01/13 13:49:14 mdw Exp $
4cc02d06	4	*
d34decd2	5	* Multiple simultaneous exponentiations
4cc02d06	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: mpmont-mexp.c,v $
3beded37	33	* Revision 1.7 2002/01/13 13:49:14 mdw
	34	* Make @const@-correct.
	35	*
4640a0dd	36	* Revision 1.6 2001/06/16 13:00:20 mdw
	37	* Use the generic exponentiation functions.
	38	*
22bab86c	39	* Revision 1.5 2000/10/08 12:11:22 mdw
	40	* Use @MP_EQ@ instead of @MP_CMP@.
	41	*
d34decd2	42	* Revision 1.4 2000/06/17 11:45:09 mdw
	43	* Major memory management overhaul. Added arena support. Use the secure
	44	* arena for secret integers. Replace and improve the MP management macros
	45	* (e.g., replace MP_MODIFY by MP_DEST).
	46	*
ef5f4810	47	* Revision 1.3 1999/12/10 23:18:39 mdw
	48	* Change interface for suggested destinations.
	49	*
79a34029	50	* Revision 1.2 1999/11/21 11:35:10 mdw
	51	* Performance improvement: use @mp_sqr@ and @mpmont_reduce@ instead of
	52	* @mpmont_mul@ for squaring in exponentiation.
	53	*
4cc02d06	54	* Revision 1.1 1999/11/19 13:19:29 mdw
	55	* Simultaneous exponentiation support.
	56	*
	57	*/
	58
	59	/----- Header files ------------------------------------------------------/
	60
	61	#include "mp.h"
	62	#include "mpmont.h"
	63
4640a0dd	64	#define EXP_WINSZ 3
	65	#include "mpmont-exp.h"
	66
4cc02d06	67	/----- Main code ---------------------------------------------------------/
	68
	69	/* --- @mpmont_mexpr@ --- *
	70	*
	71	* Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
ef5f4810	72	* @mp *d@ = fake destination
4640a0dd	73	* @mp_expfactor *f@ = pointer to array of factors
4cc02d06	74	* @size_t n@ = number of factors supplied
	75	*
	76	* Returns: If the bases are %$g_0, g_1, \ldots, g_{n-1}$% and the
	77	* exponents are %$e_0, e_1, \ldots, e_{n-1}$% then the result
	78	* is:
	79	*
4640a0dd	80	* %$g_0^{e_0} g_1^{e_1} \ldots g_{n-1}^{e_{n-1}} \bmod m$%
	81	*
	82	* except that the %$g_i$% and result are in Montgomery form.
4cc02d06	83	*/
4cc02d06	84
4640a0dd	85	mp mpmont_mexpr(mpmont mm, mp d, mp_expfactor f, size_t n)
4cc02d06	86	{
4640a0dd	87	mp *a = mp_copy(mm->r);
	88	mp *spare;
	89	size_t i;
	90
	91	spare = MP_NEW;
	92	for (i = 0; i < n; i++) {
	93	if (f[i].exp->f & MP_BURN) {
	94	spare = MP_NEWSEC;
	95	break;
4cc02d06	96	}
	97	}
	98
4640a0dd	99	EXP_SIMUL(a, f, n);
	100	mp_drop(d);
	101	mp_drop(spare);
4cc02d06	102	return (a);
	103	}
	104
	105	/* --- @mpmont_mexp@ --- *
	106	*
	107	* Arguments: @mpmont *mm@ = pointer to Montgomery reduction context
ef5f4810	108	* @mp *d@ = fake destination
3beded37	109	* @const mp_expfactor *f@ = pointer to array of factors
4cc02d06	110	* @size_t n@ = number of factors supplied
	111	*
	112	* Returns: Product of bases raised to exponents, all mod @m@.
	113	*
	114	* Use: Convenient interface over @mpmont_mexpr@.
	115	*/
	116
3beded37	117	mp mpmont_mexp(mpmont mm, mp d, const mp_expfactor f, size_t n)
4cc02d06	118	{
4640a0dd	119	mp_expfactor v = xmalloc(sizeof(v) * n);
	120	size_t i;
	121
	122	for (i = 0; i < n; i++) {
	123	v[i].base = mpmont_mul(mm, MP_NEW, f[i].base, mm->r2);
	124	v[i].exp = f[i].exp;
	125	}
	126	d = mpmont_mexpr(mm, d, v, n);
	127	for (i = 0; i < n; i++)
	128	MP_DROP(v[i].base);
	129	xfree(v);
4cc02d06	130	d = mpmont_reduce(mm, d, d);
	131	return (d);
	132	}
	133
	134	/----- Test rig ----------------------------------------------------------/
	135
	136	#ifdef TEST_RIG
	137
	138	#include <mLib/testrig.h>
	139
	140	static int verify(size_t n, dstr *v)
	141	{
	142	mp m = (mp **)v[0].buf;
4640a0dd	143	mp_expfactor f = xmalloc(n sizeof(*f));
4cc02d06	144	mp r, rr;
	145	size_t i, j;
	146	mpmont mm;
	147	int ok = 1;
	148
	149	j = 1;
	150	for (i = 0; i < n; i++) {
	151	f[i].base = (mp *)v[j++].buf;
	152	f[i].exp = (mp *)v[j++].buf;
	153	}
	154
	155	rr = (mp *)v[j].buf;
	156	mpmont_create(&mm, m);
ef5f4810	157	r = mpmont_mexp(&mm, MP_NEW, f, n);
22bab86c	158	if (!MP_EQ(r, rr)) {
4cc02d06	159	fputs("\n*** mexp failed\n", stderr);
	160	fputs("m = ", stderr); mp_writefile(m, stderr, 10);
	161	for (i = 0; i < n; i++) {
	162	fprintf(stderr, "\ng_%u = ", i);
	163	mp_writefile(f[i].base, stderr, 10);
	164	fprintf(stderr, "\ne_%u = ", i);
	165	mp_writefile(f[i].exp, stderr, 10);
	166	}
	167	fputs("\nr = ", stderr); mp_writefile(r, stderr, 10);
	168	fputs("\nR = ", stderr); mp_writefile(rr, stderr, 10);
	169	fputc('\n', stderr);
	170	ok = 0;
	171	}
	172
	173	for (i = 0; i < n; i++) {
	174	MP_DROP(f[i].base);
	175	MP_DROP(f[i].exp);
	176	}
	177	MP_DROP(m);
	178	MP_DROP(r);
	179	MP_DROP(rr);
	180	mpmont_destroy(&mm);
ef5f4810	181	assert(mparena_count(MPARENA_GLOBAL) == 0);
4cc02d06	182	return (ok);
	183	}
	184
	185	static int t1(dstr *v) { return verify(1, v); }
	186	static int t2(dstr *v) { return verify(2, v); }
	187	static int t3(dstr *v) { return verify(3, v); }
	188	static int t4(dstr *v) { return verify(4, v); }
	189	static int t5(dstr *v) { return verify(5, v); }
	190
	191	static test_chunk tests[] = {
	192	{ "mexp-1", t1, { &type_mp,
	193	&type_mp, &type_mp,
	194	&type_mp, 0 } },
	195	{ "mexp-2", t2, { &type_mp,
	196	&type_mp, &type_mp,
	197	&type_mp, &type_mp,
	198	&type_mp, 0 } },
	199	{ "mexp-3", t3, { &type_mp,
	200	&type_mp, &type_mp,
	201	&type_mp, &type_mp,
	202	&type_mp, &type_mp,
	203	&type_mp, 0 } },
	204	{ "mexp-4", t4, { &type_mp,
	205	&type_mp, &type_mp,
	206	&type_mp, &type_mp,
	207	&type_mp, &type_mp,
	208	&type_mp, &type_mp,
	209	&type_mp, 0 } },
	210	{ "mexp-5", t5, { &type_mp,
	211	&type_mp, &type_mp,
	212	&type_mp, &type_mp,
	213	&type_mp, &type_mp,
	214	&type_mp, &type_mp,
	215	&type_mp, &type_mp,
	216	&type_mp, 0 } },
	217	{ 0, 0, { 0 } }
	218	};
	219
	220	int main(int argc, char *argv[])
	221	{
	222	sub_init();
	223	test_run(argc, argv, tests, SRCDIR "/tests/mpmont");
	224	return (0);
	225	}
	226
	227	#endif
	228
	229	/----- That's all, folks -------------------------------------------------/