X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/4640a0dd947f422cfda780c62da342792af27b7b..20fa0f6976d598481208c0583d72b2ccef637be9:/mpmont.c diff --git a/mpmont.c b/mpmont.c index 2371de8..65b3fcc 100644 --- a/mpmont.c +++ b/mpmont.c @@ -1,13 +1,13 @@ /* -*-c-*- * - * $Id: mpmont.c,v 1.15 2001/06/16 13:00:20 mdw Exp $ + * $Id$ * * Montgomery reduction * * (c) 1999 Straylight/Edgeware */ -/*----- Licensing notice --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of Catacomb. * @@ -15,83 +15,22 @@ * 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.c,v $ - * 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. - * - * Revision 1.7 1999/12/11 01:51:14 mdw - * Use a Karatsuba-based reduction for large moduli. - * - * Revision 1.6 1999/12/10 23:18:39 mdw - * Change interface for suggested destinations. - * - * Revision 1.5 1999/11/22 13:58:40 mdw - * Add an option to disable Montgomery reduction, so that performance - * comparisons can be done. - * - * Revision 1.4 1999/11/21 12:27:06 mdw - * Remove a division from the Montgomery setup by calculating - * %$R^2 \bmod m$% first and then %$R \bmod m$% by Montgomery reduction of - * %$R^2$%. - * - * Revision 1.3 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.2 1999/11/19 13:17:26 mdw - * Add extra interface to exponentiation which returns a Montgomerized - * result. - * - * Revision 1.1 1999/11/17 18:02:16 mdw - * New multiprecision integer arithmetic suite. - * - */ - /*----- Header files ------------------------------------------------------*/ #include "mp.h" #include "mpmont.h" -#include "mpmont-exp.h" /*----- Tweakables --------------------------------------------------------*/ @@ -110,7 +49,7 @@ * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context * @mp *m@ = modulus to use * - * Returns: --- + * Returns: Zero on success, nonzero on error. * * Use: Initializes a Montgomery reduction context ready for use. * The argument @m@ must be a positive odd integer. @@ -118,32 +57,28 @@ #ifdef MPMONT_DISABLE -void mpmont_create(mpmont *mm, mp *m) +int mpmont_create(mpmont *mm, mp *m) { mp_shrink(m); mm->m = MP_COPY(m); mm->r = MP_ONE; mm->r2 = MP_ONE; mm->mi = MP_ONE; + return (0); } #else -void mpmont_create(mpmont *mm, mp *m) +int mpmont_create(mpmont *mm, mp *m) { size_t n = MP_LEN(m); 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); + if (!MP_POSP(m) || !MP_ODDP(m)) + return (-1); mm->m = MP_COPY(m); /* --- Determine %$R^2$% --- */ @@ -155,8 +90,7 @@ void mpmont_create(mpmont *mm, mp *m) /* --- Find the magic value @mi@ --- */ mp_build(&r, r2->v + n, r2->vl); - mm->mi = MP_NEW; - mp_gcd(0, 0, &mm->mi, &r, m); + mm->mi = mp_modinv(MP_NEW, m, &r); mm->mi = mp_sub(mm->mi, &r, mm->mi); /* --- Discover the values %$R \bmod m$% and %$R^2 \bmod m$% --- */ @@ -165,6 +99,7 @@ void mpmont_create(mpmont *mm, mp *m) mp_div(0, &mm->r2, r2, m); mm->r = mpmont_reduce(mm, MP_NEW, mm->r2); MP_DROP(r2); + return (0); } #endif @@ -367,53 +302,6 @@ mp *mpmont_mul(mpmont *mm, mp *d, mp *a, mp *b) #endif -/*----- Exponentiation ----------------------------------------------------*/ - -/* --- @mpmont_expr@ --- * - * - * Arguments: @mpmont *mm@ = pointer to Montgomery reduction context - * @mp *d@ = fake destination - * @mp *a@ = base - * @mp *e@ = exponent - * - * Returns: Result, %$(a R^{-1})^e R \bmod m$%. - */ - -mp *mpmont_expr(mpmont *mm, mp *d, mp *a, mp *e) -{ - mp *x = MP_COPY(mm->r); - mp *spare = (e->f & MP_BURN) ? MP_NEWSEC : MP_NEW; - - MP_SHRINK(e); - if (MP_LEN(e) == 0) - ; - else if (MP_LEN(e) < EXP_THRESH) - EXP_SIMPLE(x, a, e); - else - EXP_WINDOW(x, a, e); - mp_drop(d); - mp_drop(spare); - 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_mul(mm, d, a, mm->r2); - d = mpmont_expr(mm, d, d, e); - d = mpmont_reduce(mm, d, d); - return (d); -} - /*----- Test rig ----------------------------------------------------------*/ #ifdef TEST_RIG @@ -442,7 +330,7 @@ static int tcreate(dstr *v) fputs("\n*** bad r", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); fputs("\nexpected ", stderr); mp_writefile(r, stderr, 10); - fputs("\n found ", stderr); mp_writefile(mm.r, stderr, 10); + fputs("\n found ", stderr); mp_writefile(mm.r, stderr, 10); fputc('\n', stderr); ok = 0; } @@ -451,7 +339,7 @@ static int tcreate(dstr *v) fputs("\n*** bad r2", stderr); fputs("\nm = ", stderr); mp_writefile(m, stderr, 10); fputs("\nexpected ", stderr); mp_writefile(r2, stderr, 10); - fputs("\n found ", stderr); mp_writefile(mm.r2, stderr, 10); + fputs("\n found ", stderr); mp_writefile(mm.r2, stderr, 10); fputc('\n', stderr); ok = 0; } @@ -523,46 +411,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_EQ(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 } }, };