X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/01f6ed1aafd567672bfb07d98c3bfa2ec19f8b3e..02d7884df1f33c9c7dc3a14c4b1a5f520ebe090a:/mpmont.c diff --git a/mpmont.c b/mpmont.c index cabb2cb..bfede63 100644 --- a/mpmont.c +++ b/mpmont.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: mpmont.c,v 1.8 1999/12/22 15:55:00 mdw Exp $ + * $Id: mpmont.c,v 1.18 2004/04/03 03:32:05 mdw Exp $ * * Montgomery reduction * @@ -30,6 +30,45 @@ /*----- Revision history --------------------------------------------------* * * $Log: mpmont.c,v $ + * Revision 1.18 2004/04/03 03:32:05 mdw + * General robustification. + * + * Revision 1.17 2004/04/01 12:50:09 mdw + * Add cyclic group abstraction, with test code. Separate off exponentation + * functions for better static linking. Fix a buttload of bugs on the way. + * Generally ensure that negative exponents do inversion correctly. Add + * table of standard prime-field subgroups. (Binary field subgroups are + * currently unimplemented but easy to add if anyone ever finds a good one.) + * + * Revision 1.16 2002/01/13 13:40:31 mdw + * Avoid trashing arguments before we've used them. + * + * Revision 1.15 2001/06/16 13:00:20 mdw + * Use the generic exponentiation functions. + * + * Revision 1.14 2001/02/22 09:04:26 mdw + * Cosmetic fix. + * + * Revision 1.13 2001/02/03 12:00:29 mdw + * Now @mp_drop@ checks its argument is non-NULL before attempting to free + * it. Note that the macro version @MP_DROP@ doesn't do this. + * + * Revision 1.12 2000/10/08 15:48:35 mdw + * Rename Karatsuba constants now that we have @gfx_kmul@ too. + * + * Revision 1.11 2000/10/08 12:04:27 mdw + * (mpmont_reduce, mpmont_mul): Cope with negative numbers. + * + * Revision 1.10 2000/07/29 17:05:43 mdw + * (mpmont_expr): Use sliding window exponentiation, with a drop-through + * for small exponents to use a simple left-to-right bitwise routine. This + * can reduce modexp times by up to a quarter. + * + * Revision 1.9 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.8 1999/12/22 15:55:00 mdw * Adjust Karatsuba parameters. * @@ -76,7 +115,7 @@ /* #define MPMONT_DISABLE */ -/*----- Main code ---------------------------------------------------------*/ +/*----- Reduction and multiplication --------------------------------------*/ /* --- @mpmont_create@ --- * * @@ -105,18 +144,12 @@ void mpmont_create(mpmont *mm, mp *m) void mpmont_create(mpmont *mm, mp *m) { size_t n = MP_LEN(m); - mp *r2 = mp_create(2 * n + 1); + mp *r2 = mp_new(2 * n + 1, 0); mp r; - /* --- Validate the arguments --- */ - - assert(((void)"Montgomery modulus must be positive", - (m->f & MP_NEG) == 0)); - assert(((void)"Montgomery modulus must be odd", m->v[0] & 1)); - /* --- Take a copy of the modulus --- */ - mp_shrink(m); + assert(MP_ISPOS(m) && MP_ISODD(m)); mm->m = MP_COPY(m); /* --- Determine %$R^2$% --- */ @@ -185,7 +218,7 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Check for serious Karatsuba reduction --- */ - if (n > KARATSUBA_CUTOFF * 3) { + if (n > MPK_THRESH * 3) { mp al; mpw *vl; mp *u; @@ -213,13 +246,12 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Initial conditioning of the arguments --- */ - if (d == a) - MP_MODIFY(d, 2 * n + 1); - else { - MP_MODIFY(d, 2 * n + 1); - MPX_COPY(d->v, d->vl, a->v, a->vl); - } - + a = MP_COPY(a); + if (d) + MP_DROP(d); + d = a; + MP_DEST(d, 2 * n + 1, a->f); + dv = d->v; dvl = d->vl; mv = mm->m->v; mvl = mm->m->vl; @@ -235,11 +267,14 @@ mp *mpmont_reduce(mpmont *mm, mp *d, mp *a) /* --- Wrap everything up --- */ - d->f = a->f & MP_BURN; memmove(d->v, d->v + n, MPWS(MP_LEN(d) - n)); d->vl -= n; - if (MP_CMP(d, >=, mm->m)) - d = mp_sub(d, d, mm->m); + if (MPX_UCMP(d->v, d->vl, >=, mm->m->v, mm->m->vl)) + mpx_usub(d->v, d->vl, d->v, d->vl, mm->m->v, mm->m->vl); + if (d->f & MP_NEG) { + mpx_usub(d->v, d->vl, mm->m->v, mm->m->vl, d->v, d->vl); + d->f &= ~MP_NEG; + } MP_SHRINK(d); return (d); } @@ -268,7 +303,7 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) { - if (mm->n > KARATSUBA_CUTOFF * 3) { + if (mm->n > MPK_THRESH * 3) { d = mp_mul(d, a, b); d = mpmont_reduce(mm, d, d); } else { @@ -289,7 +324,7 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) a = MP_COPY(a); b = MP_COPY(b); - MP_MODIFY(d, 2 * n + 1); + MP_DEST(d, 2 * n + 1, a->f | b->f | MP_UNDEF); dv = d->v; dvl = d->vl; MPX_ZERO(dv, dvl); av = a->v; avl = a->vl; @@ -323,10 +358,12 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) memmove(d->v, dv, MPWS(dvl - dv)); d->vl -= dv - d->v; + if (MPX_UCMP(d->v, d->vl, >=, mm->m->v, mm->m->vl)) + mpx_usub(d->v, d->vl, d->v, d->vl, mm->m->v, mm->m->vl); + if ((a->f ^ b->f) & MP_NEG) + mpx_usub(d->v, d->vl, mm->m->v, mm->m->vl, d->v, d->vl); MP_SHRINK(d); d->f = (a->f | b->f) & MP_BURN; - if (MP_CMP(d, >=, mm->m)) - d = mp_sub(d, d, mm->m); MP_DROP(a); MP_DROP(b); } @@ -336,69 +373,6 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) #endif -/* --- @mpmont_expr@ --- * - * - * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context - * @mp *d@ = fake destination - * @mp *a@ = base - * @mp *e@ = exponent - * - * Returns: Result, %$a^e R \bmod m$%. - */ - -mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e) -{ - mpscan sc; - mp *ar = mpmont_mul(mm, MP_NEW, a, mm->r2); - mp *x = MP_COPY(mm->r); - mp *spare = MP_NEW; - - mp_scan(&sc, e); - - if (MP_STEP(&sc)) { - size_t sq = 0; - for (;;) { - mp *dd; - if (MP_BIT(&sc)) { - while (sq) { - dd = mp_sqr(spare, ar); - dd = mpmont_reduce(mm, dd, dd); - spare = ar; ar = dd; - sq--; - } - dd = mpmont_mul(mm, spare, x, ar); - spare = x; x = dd; - } - sq++; - if (!MP_STEP(&sc)) - break; - } - } - MP_DROP(ar); - if (spare != MP_NEW) - MP_DROP(spare); - if (d != MP_NEW) - MP_DROP(d); - return (x); -} - -/* --- @mpmont_exp@ --- * - * - * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context - * @mp *d@ = fake destination - * @mp *a@ = base - * @mp *e@ = exponent - * - * Returns: Result, %$a^e \bmod m$%. - */ - -mp *mpmont_exp(mpmont *mm, mp *d, mp *a, mp *e) -{ - d = mpmont_expr(mm, d, a, e); - d = mpmont_reduce(mm, d, d); - return (d); -} - /*----- Test rig ----------------------------------------------------------*/ #ifdef TEST_RIG @@ -423,7 +397,7 @@ static int tcreate(dstr *v) ok = 0; } - if (MP_CMP(mm.r, !=, r)) { + if (!MP_EQ(mm.r, r)) { fputs("\n*** bad r", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); fputs("\nexpected ", stderr); mp_writefile(r, stderr, 10); @@ -432,7 +406,7 @@ static int tcreate(dstr *v) ok = 0; } - if (MP_CMP(mm.r2, !=, r2)) { + if (!MP_EQ(mm.r2, r2)) { fputs("\n*** bad r2", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); fputs("\nexpected ", stderr); mp_writefile(r2, stderr, 10); @@ -465,7 +439,7 @@ static int tmul(dstr *v) mp *qr = mp_mul(MP_NEW, a, b); mp_div(0, &qr, qr, m); - if (MP_CMP(qr, !=, r)) { + if (!MP_EQ(qr, r)) { fputs("\n*** classical modmul failed", stderr); fputs("\n m = ", stderr); mp_writefile(m, stderr, 10); fputs("\n a = ", stderr); mp_writefile(a, stderr, 10); @@ -484,7 +458,7 @@ static int tmul(dstr *v) mp *br = mpmont_mul(&mm, MP_NEW, b, mm.r2); mp *mr = mpmont_mul(&mm, MP_NEW, ar, br); mr = mpmont_reduce(&mm, mr, mr); - if (MP_CMP(mr, !=, r)) { + if (!MP_EQ(mr, r)) { fputs("\n*** montgomery modmul failed", stderr); fputs("\n m = ", stderr); mp_writefile(m, stderr, 10); fputs("\n a = ", stderr); mp_writefile(a, stderr, 10); @@ -508,46 +482,9 @@ static int tmul(dstr *v) return ok; } -static int texp(dstr *v) -{ - mp *m = *(mp **)v[0].buf; - mp *a = *(mp **)v[1].buf; - mp *b = *(mp **)v[2].buf; - mp *r = *(mp **)v[3].buf; - mp *mr; - int ok = 1; - - mpmont mm; - mpmont_create(&mm, m); - - mr = mpmont_exp(&mm, MP_NEW, a, b); - - if (MP_CMP(mr, !=, r)) { - fputs("\n*** montgomery modexp failed", stderr); - fputs("\n m = ", stderr); mp_writefile(m, stderr, 10); - fputs("\n a = ", stderr); mp_writefile(a, stderr, 10); - fputs("\n e = ", stderr); mp_writefile(b, stderr, 10); - fputs("\n r = ", stderr); mp_writefile(r, stderr, 10); - fputs("\nmr = ", stderr); mp_writefile(mr, stderr, 10); - fputc('\n', stderr); - ok = 0; - } - - MP_DROP(m); - MP_DROP(a); - MP_DROP(b); - MP_DROP(r); - MP_DROP(mr); - mpmont_destroy(&mm); - assert(mparena_count(MPARENA_GLOBAL) == 0); - return ok; -} - - static test_chunk tests[] = { { "create", tcreate, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, { "mul", tmul, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, - { "exp", texp, { &type_mp, &type_mp, &type_mp, &type_mp, 0 } }, { 0, 0, { 0 } }, };