From 0baf05de865499764c4d9ff82c56679737432a0d Mon Sep 17 00:00:00 2001 From: jbj Date: Fri, 23 May 2003 15:55:57 +0000 Subject: Another merge to beecrypt-3.0.0. CVS patchset: 6872 CVS date: 2003/05/23 15:55:57 --- beecrypt/Makefile.am | 2 +- beecrypt/acinclude.m4 | 20 ++++----- beecrypt/beecrypt.api.h | 30 ------------- beecrypt/dsa.c | 4 +- beecrypt/mp.c | 97 ++++++++++++++++++++++++++++++++++++++++++ beecrypt/mp.h | 6 +++ beecrypt/mpbarrett.c | 102 +-------------------------------------------- beecrypt/mpbarrett.h | 6 --- beecrypt/mpnumber.c | 17 ++++++++ beecrypt/mpnumber.h | 6 +++ beecrypt/python/mpw-py.c | 5 +-- beecrypt/rsakp.c | 11 +++-- beecrypt/tests/Makefile.am | 6 ++- beecrypt/tests/testmp.c | 4 +- beecrypt/tests/testmpinv.c | 72 ++++++++++++++++++++++++++++++++ 15 files changed, 226 insertions(+), 162 deletions(-) create mode 100644 beecrypt/tests/testmpinv.c diff --git a/beecrypt/Makefile.am b/beecrypt/Makefile.am index 01b58ddd5..eab18845a 100644 --- a/beecrypt/Makefile.am +++ b/beecrypt/Makefile.am @@ -36,7 +36,7 @@ AUTOMAKE_OPTIONS = gnu check-news no-dependencies LINT = splint -SUBDIRS = docs gas masm python tests +SUBDIRS = . docs gas masm python tests SUFFIXES = .s diff --git a/beecrypt/acinclude.m4 b/beecrypt/acinclude.m4 index a723df683..8ec4282f1 100644 --- a/beecrypt/acinclude.m4 +++ b/beecrypt/acinclude.m4 @@ -565,17 +565,15 @@ dnl BEECRYPT_ASM_ALIGN AC_DEFUN(BEECRYPT_ASM_ALIGN,[ AC_CACHE_CHECK([how to align symbols], bc_cv_asm_align,[ - case $target_os in - linux*) - case $target_cpu in - i[[3456]]86 | athlon*) - bc_cv_asm_align=".align 4" - ;; - s390x) - bc_cv_asm_align=".align 4" - ;; - esac - ;; + case $target_cpu in + i[[3456]]86 | athlon*) + bc_cv_asm_align=".align 4" ;; + ia64) + bc_cv_asm_align=".align 16" ;; + s390x) + bc_cv_asm_align=".align 4" ;; + sparc*) + bc_cv_asm_align=".align 4" ;; esac ]) AC_SUBST(ASM_ALIGN,$bc_cv_asm_align) diff --git a/beecrypt/beecrypt.api.h b/beecrypt/beecrypt.api.h index 22ac58508..1ed54d96f 100644 --- a/beecrypt/beecrypt.api.h +++ b/beecrypt/beecrypt.api.h @@ -41,36 +41,6 @@ # define BEECRYPTAPI #endif -/* Starting from GCC 3.2, the compiler seems smart enough to figure - * out that we're trying to do a rotate without having to specify it. - */ -#if defined(__GNUC__) && (__GNUC__ < 3 || __GNUC_MINOR__ < 2) -# if defined(__i386__) -static inline uint32_t _rotl32(uint32_t x, const unsigned char n) -{ - __asm__("roll %2,%0" - : "=r" (x) - : "0" (x), "I" (n)); - - return x; -} - -#define ROTL32(x, n) _rotl32(x, n) - -static inline uint32_t _rotr32(uint32_t x, const unsigned char n) -{ - __asm__("rorl %2,%0" - : "=r" (x) - : "0" (x), "I" (n)); - - return x; -} - -#define ROTR32(x, n) _rotr32(x, n) - -# endif -#endif - #ifndef ROTL32 # define ROTL32(x, s) (((x) << (s)) | ((x) >> (32 - (s)))) #endif diff --git a/beecrypt/dsa.c b/beecrypt/dsa.c index ecea2a1b1..c8222d632 100644 --- a/beecrypt/dsa.c +++ b/beecrypt/dsa.c @@ -147,8 +147,10 @@ int dsavrfy(const mpbarrett* p, const mpbarrett* q, const mpnumber* g, const mpn pwksp = ptemp+2*psize; qwksp = qtemp+2*qsize; + mpsetx(qsize, qtemp+qsize, s->size, s->data); + /* compute w = inv(s) mod q */ - if (mpbinv_w(q, s->size, s->data, qtemp, qwksp)) + if (mpextgcd_w(qsize, qtemp+qsize, q->modl, qtemp, qwksp)) { /* compute u1 = h(m)*w mod q */ mpbmulmod_w(q, hm->size, hm->data, qsize, qtemp, qtemp+qsize, qwksp); diff --git a/beecrypt/mp.c b/beecrypt/mp.c index 158132a97..2369e63b3 100644 --- a/beecrypt/mp.c +++ b/beecrypt/mp.c @@ -1155,6 +1155,103 @@ void mpgcd_w(size_t size, const mpw* xdata, const mpw* ydata, mpw* result, mpw* } #endif +#ifndef ASM_MPEXTGCD_W +/* needs workspace of (6*size+6) words */ +/* used to compute the modular inverse */ +int mpextgcd_w(size_t size, const mpw* xdata, const mpw* ndata, mpw* result, mpw* wksp) +{ + /* + * For computing a modular inverse, pass the modulus as ndata and the number + * to be inverted as xdata. + * + * Fact: if a element of Zn, then a is invertible if and only if gcd(a,n) = 1 + * Hence: if ndata is even, then x must be odd, otherwise the gcd(x,n) >= 2 + * + * The calling routine must guarantee this condition. + */ + + register size_t sizep = size+1; + register int full; + + mpw* udata = wksp; + mpw* vdata = udata+sizep; + mpw* adata = vdata+sizep; + mpw* bdata = adata+sizep; + mpw* cdata = bdata+sizep; + mpw* ddata = cdata+sizep; + + mpsetx(sizep, udata, size, ndata); + mpsetx(sizep, vdata, size, xdata); + mpzero(sizep, bdata); + mpsetw(sizep, ddata, 1); + + if ((full = mpeven(sizep, udata))) + { + mpsetw(sizep, adata, 1); + mpzero(sizep, cdata); + } + + while (1) + { + while (mpeven(sizep, udata)) + { + mpdivtwo(sizep, udata); + + if ((full && mpodd(sizep, adata)) || mpodd(sizep, bdata)) + { + if (full) mpaddx(sizep, adata, size, xdata); + mpsubx(sizep, bdata, size, ndata); + } + + if (full) mpsdivtwo(sizep, adata); + mpsdivtwo(sizep, bdata); + } + while (mpeven(sizep, vdata)) + { + mpdivtwo(sizep, vdata); + + if ((full && mpodd(sizep, cdata)) || mpodd(sizep, ddata)) + { + if (full) mpaddx(sizep, cdata, size, xdata); + mpsubx(sizep, ddata, size, ndata); + } + + if (full) mpsdivtwo(sizep, cdata); + mpsdivtwo(sizep, ddata); + } + if (mpge(sizep, udata, vdata)) + { + mpsub(sizep, udata, vdata); + if (full) mpsub(sizep, adata, cdata); + mpsub(sizep, bdata, ddata); + } + else + { + mpsub(sizep, vdata, udata); + if (full) mpsub(sizep, cdata, adata); + mpsub(sizep, ddata, bdata); + } + if (mpz(sizep, udata)) + { + if (mpisone(sizep, vdata)) + { + if (result) + { + mpsetx(size, result, sizep, ddata); + if (*ddata & MP_MSBMASK) + { + /* keep adding the modulus until we get a carry */ + while (!mpadd(size, result, ndata)); + } + } + return 1; + } + return 0; + } + } +} +#endif + #ifndef ASM_MPPNDIV mpw mppndiv(mpw xhi, mpw xlo, mpw y) { diff --git a/beecrypt/mp.h b/beecrypt/mp.h index 2d41b3155..c1c6ed54e 100644 --- a/beecrypt/mp.h +++ b/beecrypt/mp.h @@ -649,6 +649,12 @@ BEECRYPTAPI void mpgcd_w(size_t size, const mpw* xdata, const mpw* ydata, /*@out@*/ mpw* result, /*@out@*/ mpw* wksp) /*@modifies result, wksp @*/; +/** + */ +BEECRYPTAPI +int mpextgcd_w(size_t size, const mpw* xdata, const mpw* ydata, /*@out@*/ mpw* result, /*@out@*/ mpw* wksp) + /*@modifies result, wksp @*/; + /** */ /*@-exportlocal@*/ diff --git a/beecrypt/mpbarrett.c b/beecrypt/mpbarrett.c index bdc127afd..3c18c0595 100644 --- a/beecrypt/mpbarrett.c +++ b/beecrypt/mpbarrett.c @@ -30,6 +30,7 @@ #include "system.h" #include "mp.h" #include "mpprime.h" +#include "mpnumber.h" #include "mpbarrett.h" #include "debug.h" @@ -283,7 +284,7 @@ void mpbrndinv_w(const mpbarrett* b, randomGeneratorContext* rc, mpw* result, mp else mpbrnd_w(b, rc, result, wksp); - } while (mpbinv_w(b, size, result, inverse, wksp) == 0); + } while (mpextgcd_w(size, result, b->modl, inverse, wksp) == 0); } /** @@ -706,105 +707,6 @@ void mpbtwopowmod_w(const mpbarrett* b, size_t psize, const mpw* pdata, mpw* res } #ifdef DYING -/** - * Computes the inverse (modulo b) of x, and returns 1 if x was invertible. - * needs workspace of (6*size+6) words - * @note xdata and result cannot point to the same area - */ -int mpbinv_w(const mpbarrett* b, size_t xsize, const mpw* xdata, mpw* result, mpw* wksp) -{ - /* - * Fact: if a element of Zn, then a is invertible if and only if gcd(a,n) = 1 - * Hence: if b->modl is even, then x must be odd, otherwise the gcd(x,n) >= 2 - * - * The calling routine must guarantee this condition. - */ - - register size_t size = b->size; - register int full; - - mpw* udata = wksp; - mpw* vdata = udata+size+1; - mpw* adata = vdata+size+1; - mpw* bdata = adata+size+1; - mpw* cdata = bdata+size+1; - mpw* ddata = cdata+size+1; - - mpsetx(size+1, udata, size, b->modl); - mpsetx(size+1, vdata, xsize, xdata); - mpzero(size+1, bdata); - mpsetw(size+1, ddata, 1); - - if ((full = mpeven(b->size, b->modl))) - { - mpsetw(size+1, adata, 1); - mpzero(size+1, cdata); - } - - while (1) - { - while (mpeven(size+1, udata)) - { - mpdivtwo(size+1, udata); - - if ((full && mpodd(size+1, adata)) || mpodd(size+1, bdata)) - { - if (full) (void) mpaddx(size+1, adata, xsize, xdata); - (void) mpsubx(size+1, bdata, size, b->modl); - } - - if (full) mpsdivtwo(size+1, adata); - mpsdivtwo(size+1, bdata); - } - while (mpeven(size+1, vdata)) - { - mpdivtwo(size+1, vdata); - - if ((full && mpodd(size+1, cdata)) || mpodd(size+1, ddata)) - { - if (full) (void) mpaddx(size+1, cdata, xsize, xdata); - (void) mpsubx(size+1, ddata, size, b->modl); - } - - if (full) mpsdivtwo(size+1, cdata); - mpsdivtwo(size+1, ddata); - } - if (mpge(size+1, udata, vdata)) - { - (void) mpsub(size+1, udata, vdata); - if (full) (void) mpsub(size+1, adata, cdata); - (void) mpsub(size+1, bdata, ddata); - } - else - { - (void) mpsub(size+1, vdata, udata); - if (full) (void) mpsub(size+1, cdata, adata); - (void) mpsub(size+1, ddata, bdata); - } - - if (mpz(size+1, udata)) - { - if (mpisone(size+1, vdata)) - { - if (result) - { - mpsetx(size, result, size+1, ddata); - /*@-usedef@*/ - if (*ddata & MP_MSBMASK) - { - /* keep adding the modulus until we get a carry */ - while (!mpadd(size, result, b->modl)); - } - /*@=usedef@*/ - } - return 1; - } - return 0; - } - } -} -#else - /*@unchecked@*/ static int _debug = 0; diff --git a/beecrypt/mpbarrett.h b/beecrypt/mpbarrett.h index ada85aa71..6bfcf6008 100644 --- a/beecrypt/mpbarrett.h +++ b/beecrypt/mpbarrett.h @@ -169,12 +169,6 @@ BEECRYPTAPI void mpbtwopowmod_w(const mpbarrett* b, size_t psize, const mpw* pdata, /*@out@*/ mpw* result, /*@out@*/ mpw* wksp) /*@modifies result, wksp @*/; -/** - */ -BEECRYPTAPI -int mpbinv_w(const mpbarrett* b, size_t xsize, const mpw* xdata, /*@out@*/ mpw* result, /*@out@*/ mpw* wksp) - /*@modifies result, wksp @*/; - #ifdef NOTYET /** * @todo Simultaneous multiple exponentiation, for use in dsa and elgamal diff --git a/beecrypt/mpnumber.c b/beecrypt/mpnumber.c index a8fcc02c3..463247048 100644 --- a/beecrypt/mpnumber.c +++ b/beecrypt/mpnumber.c @@ -181,3 +181,20 @@ void mpnsethex(mpnumber* n, const char* hex) } } /*@=usedef @*/ + +int mpninv(mpnumber* inv, const mpnumber* k, const mpnumber* mod) +{ + int rc = 0; + size_t size = mod->size; + mpw* wksp = (mpw*) malloc((7*size+6) * sizeof(mpw)); + + if (wksp) + { + mpnsize(inv, size); + mpsetx(size, wksp, k->size, k->data); + rc = mpextgcd_w(size, wksp, mod->data, inv->data, wksp+size); + free(wksp); + } + + return rc; +} diff --git a/beecrypt/mpnumber.h b/beecrypt/mpnumber.h index 9fe41dd9d..66b6b06dd 100644 --- a/beecrypt/mpnumber.h +++ b/beecrypt/mpnumber.h @@ -95,6 +95,12 @@ BEECRYPTAPI /*@unused@*/ void mpnsethex(/*@out@*/ mpnumber* n, const char* hex) /*@modifies n->size, n->data @*/; +/** + */ +BEECRYPTAPI /*@unused@*/ +int mpninv(/*@out@*/ mpnumber* inv, const mpnumber* k, const mpnumber* mod) + /*@modifies inv->size, inv->data @*/; + #ifdef __cplusplus } #endif diff --git a/beecrypt/python/mpw-py.c b/beecrypt/python/mpw-py.c index b2b51e103..bd910bffb 100644 --- a/beecrypt/python/mpw-py.c +++ b/beecrypt/python/mpw-py.c @@ -1567,10 +1567,9 @@ fprintf(stderr, "sub ++: borrow\n"); mpgcd_w(xsize, xdata, mdata, MPW_DATA(z), wksp); break; case 'I': - wksp = alloca(6*(msize+1)*sizeof(*wksp)); - mpbset(&b, msize, mdata); + wksp = alloca((7*msize+6)*sizeof(*wksp)); z = mpw_New(msize); - mpbinv_w(&b, xsize, xdata, MPW_DATA(z), wksp); + (void) mpextgcd_w(msize, wksp, mdata, MPW_DATA(z), wksp+msize); break; #ifdef DYING case 'R': diff --git a/beecrypt/rsakp.c b/beecrypt/rsakp.c index b47db79ba..89ac25165 100644 --- a/beecrypt/rsakp.c +++ b/beecrypt/rsakp.c @@ -45,7 +45,8 @@ int rsakpMake(rsakp* kp, randomGeneratorContext* rgc, size_t nsize) if (temp) { - mpbarrett r, psubone, qsubone, phi; + mpbarrett r, psubone, qsubone; + mpnumber phi; nsize = pqsize << 1; @@ -67,7 +68,7 @@ int rsakpMake(rsakp* kp, randomGeneratorContext* rgc, size_t nsize) mpbzero(&r); mpbzero(&psubone); mpbzero(&qsubone); - mpbzero(&phi); + mpnzero(&phi); while (1) { @@ -120,8 +121,7 @@ int rsakpMake(rsakp* kp, randomGeneratorContext* rgc, size_t nsize) mpbset(&phi, nsize, temp); /* compute d = inv(e) mod phi */ - mpnsize(&kp->d, nsize); - (void) mpbinv_w(&phi, kp->e.size, kp->e.data, kp->d.data, temp); + (void) mpninv(&kp->d, &kp->e, &phi); /* compute d1 = d mod (p-1) */ mpnsize(&kp->d1, pqsize); @@ -132,8 +132,7 @@ int rsakpMake(rsakp* kp, randomGeneratorContext* rgc, size_t nsize) mpbmod_w(&qsubone, kp->d.data, kp->d2.data, temp); /* compute c = inv(q) mod p */ - mpnsize(&kp->c, pqsize); - (void) mpbinv_w(&kp->p, pqsize, kp->q.modl, kp->c.data, temp); + (void) mpninv(&kp->c, (const mpnumber*) &kp->q, (const mpnumber*) &kp->p); free(temp); /*@=usedef@*/ diff --git a/beecrypt/tests/Makefile.am b/beecrypt/tests/Makefile.am index dbc1c5f78..b069ea009 100644 --- a/beecrypt/tests/Makefile.am +++ b/beecrypt/tests/Makefile.am @@ -25,9 +25,9 @@ AUTOMAKE_OPTIONS = gnu no-dependencies INCLUDES = -I$(top_srcdir) LDADD = $(top_builddir)/libbeecrypt.la -TESTS = testmd5 testsha1 testsha256 testhmacmd5 testhmacsha1 testmp testrsa testdldp +TESTS = testmd5 testsha1 testsha256 testhmacmd5 testhmacsha1 testmp testmpinv testrsa testdldp -check_PROGRAMS = testmd5 testsha1 testsha256 testhmacmd5 testhmacsha1 testmp testrsa testdldp +check_PROGRAMS = testmd5 testsha1 testsha256 testhmacmd5 testhmacsha1 testmp testmpinv testrsa testdldp testmd5_SOURCES = testmd5.c @@ -41,6 +41,8 @@ testhmacsha1_SOURCES = testhmacsha1.c testmp_SOURCES = testmp.c +testmpinv_SOURCES = testmpinv.c + testrsa_SOURCES = testrsa.c testdldp_SOURCES = testdldp.c diff --git a/beecrypt/tests/testmp.c b/beecrypt/tests/testmp.c index 04e533af5..9b9d2672c 100644 --- a/beecrypt/tests/testmp.c +++ b/beecrypt/tests/testmp.c @@ -6,8 +6,8 @@ #define INIT 0xdeadbeefU; static const mpw Z[4] = { 0U, 0U, 0U, 0U }; -static const mpw F[4] = { ~((mpw) 0U), ~((mpw) 0U), ~((mpw) 0U), ~((mpw) 0U)}; -static const mpw P[8] = { ~((mpw) 0U), ~((mpw) 0U), ~((mpw) 0U), ~((mpw) 0U) - 1U, 0U, 0U, 0U, 1U }; +static const mpw F[4] = { MP_ALLMASK, MP_ALLMASK, MP_ALLMASK, MP_ALLMASK}; +static const mpw P[8] = { MP_ALLMASK, MP_ALLMASK, MP_ALLMASK, MP_ALLMASK-1U, 0U, 0U, 0U, 1U }; int main() { diff --git a/beecrypt/tests/testmpinv.c b/beecrypt/tests/testmpinv.c new file mode 100644 index 000000000..129718929 --- /dev/null +++ b/beecrypt/tests/testmpinv.c @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2003 Bob Deblier + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library 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 + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ + +/*!\file testmpinv.c + * \brief Unit test program for the multi-precision modular inverse. + * \author Bob Deblier + * \ingroup UNIT_m + */ + +#include "system.h" + +#include "beecrypt.h" +#include "mpbarrett.h" + +#include "debug.h" + +static const char* dsa_q = "c773218c737ec8ee993b4f2ded30f48edace915f"; +static const char* dsa_k = "358dad571462710f50e254cf1a376b2bdeaadfbf"; +static const char* dsa_inv_k = "0d5167298202e49b4116ac104fc3f415ae52f917"; + +int main() +{ + int failures = 0; + + mpnumber q; + mpnumber k; + mpnumber inv_k; + mpnumber inv; + + mpnzero(&q); + mpnzero(&k); + mpnzero(&inv_k); + mpnzero(&inv); + + mpnsethex(&q, dsa_q); + mpnsethex(&k, dsa_k); + mpnsethex(&inv_k, dsa_inv_k); + + if (mpninv(&inv, &k, &q)) + { + if (mpnex(inv.size, inv.data, inv_k.size, inv_k.data)) + { + printf("mpninv return unexpected result\n"); + mpprintln(inv_k.size, inv_k.data); + mpprintln(inv.size, inv.data); + failures++; + } + } + else + { + printf("mpninv failed\n"); + failures++; + } + + return failures; +} -- cgit v1.2.3