Another merge to beecrypt-3.0.0.

CVS patchset: 6872
CVS date: 2003/05/23 15:55:57

15 files changed, 226 insertions, 162 deletions

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
@@ -651,6 +651,12 @@ void mpgcd_w(size_t size, const mpw* xdata, const mpw* ydata, /*@out@*/ mpw* res
 
 /**
  */
+BEECRYPTAPI
+int mpextgcd_w(size_t size, const mpw* xdata, const mpw* ydata, /*@out@*/ mpw* result, /*@out@*/ mpw* wksp)
+	/*@modifies result, wksp @*/;
+
+/**
+ */
 /*@-exportlocal@*/
 BEECRYPTAPI
 mpw mppndiv(mpw xhi, mpw xlo, mpw y)
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 <bob.deblier@pandora.be>
+ * \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;
+}