Output armor works, RSA keygen works.

4 files changed, 144 insertions, 83 deletions

diff --git a/mpi/mpi-add.c b/mpi/mpi-add.c
index 047a2fa35..2c1aa6c61 100644
--- a/mpi/mpi-add.c
+++ b/mpi/mpi-add.c
@@ -68,7 +68,7 @@ mpi_add_ui(MPI w, MPI u, unsigned long v )
 	else {
 	    mpihelp_sub_1(wp, up, usize, v);
 	    /* Size can decrease with at most one limb. */
-	    wsize = (usize - (wp[usize-1]? 0:1));
+	    wsize = usize - (wp[usize-1]==0);
 	    wsign = 1;
 	}
     }
@@ -85,27 +85,30 @@ mpi_add(MPI w, MPI u, MPI v)
     mpi_size_t usize, vsize, wsize;
     int usign, vsign, wsign;
 
-    usize = u->nlimbs;
-    vsize = v->nlimbs;
-    usign = u->sign;
-    vsign = v->sign;
-
-    if( usize < vsize ) { /* Swap U and V. */
-	{ MPI t; t = u; u = v; v = t; }
-	{ mpi_size_t t = usize; usize = vsize; vsize = t; }
-	{ int t = usign; usign = vsign; vsign = t; }
+    if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
+	usize = v->nlimbs;
+	usign = v->sign;
+	vsize = u->nlimbs;
+	vsign = u->sign;
+	wsize = usize + 1;
+	RESIZE_IF_NEEDED(w, wsize);
+	/* These must be after realloc (u or v may be the same as w).  */
+	up    = v->d;
+	vp    = u->d;
+    }
+    else {
+	usize = u->nlimbs;
+	usign = u->sign;
+	vsize = v->nlimbs;
+	vsign = v->sign;
+	wsize = usize + 1;
+	RESIZE_IF_NEEDED(w, wsize);
+	/* These must be after realloc (u or v may be the same as w).  */
+	up    = u->d;
+	vp    = v->d;
     }
-
-    /* If not space for w (and possible carry), increase space.  */
-    wsize = usize + 1;
-    if( w->alloced < wsize )
-	mpi_resize(w, wsize);
-    wsign = 0;
-
-    /* These must be after realloc (u or v may be the same as w).  */
-    up = u->d;
-    vp = v->d;
     wp = w->d;
+    wsign = 0;
 
     if( !vsize ) {  /* simple */
 	MPN_COPY(wp, up, usize );
@@ -140,7 +143,7 @@ mpi_add(MPI w, MPI u, MPI v)
 	wp[usize] = cy;
 	wsize = usize + cy;
 	if( usign )
-	    wsize = 1;
+	    wsign = 1;
     }
 
     w->nlimbs = wsize;
@@ -193,7 +196,7 @@ mpi_sub_ui(MPI w, MPI u, unsigned long v )
 	else {
 	    mpihelp_sub_1(wp, up, usize, v);
 	    /* Size can decrease with at most one limb. */
-	    wsize = (usize - (wp[usize-1]? 1:0));
+	    wsize = usize - (wp[usize-1]==0);
 	}
     }
 
@@ -204,7 +207,7 @@ mpi_sub_ui(MPI w, MPI u, unsigned long v )
 void
 mpi_sub(MPI w, MPI u, MPI v)
 {
-    if( w == v ) {
+    if( 1 || w == v ) {
 	MPI vv = mpi_copy(v);
 	vv->sign = !vv->sign;
 	mpi_add( w, u, vv );
diff --git a/mpi/mpi-bit.c b/mpi/mpi-bit.c
index 9cb346aa4..9bde9f0fb 100644
--- a/mpi/mpi-bit.c
+++ b/mpi/mpi-bit.c
@@ -130,4 +130,25 @@ mpi_set_bytes( MPI a, unsigned nbits, byte (*fnc)(int), int opaque )
     assert(!xbits);
 }
 
+/****************
+ * Shift A by N bits to the right
+ * FIXME: should use alloc_limb if X and A are same.
+ */
+void
+mpi_rshift( MPI x, MPI a, unsigned n )
+{
+    mpi_ptr_t xp;
+    mpi_size_t xsize;
+
+    xsize = a->nlimbs;
+    x->sign = a->sign;
+    RESIZE_IF_NEEDED(x, xsize);
+    xp = x->d;
+
+    if( xsize ) {
+	mpihelp_rshift( xp, a->d, xsize, n);
+	MPN_NORMALIZE( xp, xsize);
+    }
+    x->nlimbs = xsize;
+}
 
diff --git a/mpi/mpi-inv.c b/mpi/mpi-inv.c
index acde6055a..f37f4e511 100644
--- a/mpi/mpi-inv.c
+++ b/mpi/mpi-inv.c
@@ -23,20 +23,21 @@
 #include <stdlib.h>
 #include "mpi-internal.h"
 
+
 /****************
- * Calculate the multiplicative inverse X of U mod V
- * That is: Find the solution for
- *		1 = (u*x) mod v
- * This has only a unique solution if U and V are relatively prime.
- * Returns 0 if a solution was found.
+ * Calculate the multiplicative inverse X of A mod N
+ * That is: Find the solution x for
+ *		1 = (a*x) mod n
  */
-int
-mpi_inv_mod( MPI x, MPI u, MPI v )
+void
+mpi_inv_mod( MPI x, MPI a, MPI n )
 {
   #if 0
-    /* Extended Euclid's algorithm (See TAOPC Vol II, 4.52. Alg X) */
-    MPI u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
+    MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
+    MPI ta, tb, tc;
 
+    u = mpi_copy(a);
+    v = mpi_copy(n);
     u1 = mpi_alloc_set_ui(1);
     u2 = mpi_alloc_set_ui(0);
     u3 = mpi_copy(u);
@@ -48,22 +49,20 @@ mpi_inv_mod( MPI x, MPI u, MPI v )
     t2 = mpi_alloc( mpi_get_nlimbs(u) );
     t3 = mpi_alloc( mpi_get_nlimbs(u) );
     while( mpi_cmp_ui( v3, 0 ) ) {
-      /*log_debug("----------------------\n");
-	log_mpidump("q =", u1);
-	log_mpidump("u1=", u1);
-	log_mpidump("u2=", u2);
-	log_mpidump("u3=", u3);
-	log_mpidump("v1=", v1);
-	log_mpidump("v2=", v2);
-	log_mpidump("v3=", v3); */
 	mpi_fdiv_q( q, u3, v3 );
 	mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
 	mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
-
 	mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
 	mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
     }
-    mpi_set(x, u3);
+    /*	log_debug("result:\n");
+	log_mpidump("q =", q );
+	log_mpidump("u1=", u1);
+	log_mpidump("u2=", u2);
+	log_mpidump("u3=", u3);
+	log_mpidump("v1=", v1);
+	log_mpidump("v2=", v2); */
+    mpi_set(x, u1);
 
     mpi_free(u1);
     mpi_free(u2);
@@ -75,52 +74,89 @@ mpi_inv_mod( MPI x, MPI u, MPI v )
     mpi_free(t1);
     mpi_free(t2);
     mpi_free(t3);
-  #endif
+    mpi_free(u);
+    mpi_free(v);
+  #else
+    /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
+     * modified according to Michael Penk's solution for Exercice 35 */
 
-    /*****************************
-     *	1. Init:   g0 = u  g1 = v  v0  = 0   v1 = 1
-     *	2. Test:   if g1 is 0 terminate. Result = v0 < 0: v0 + n
-     *						    else: v0
-     *	3. Divide: div,rem = g0 / g1
-     *		   t1 = v0 - div * v1
-     *		   v0 = v1
-     *		   v1 = t1
-     *		   g0 = g1
-     *		   g1 = rem
-     *	   continue with step 2.
-     */
-    MPI g0, g1, v0, v1, div, rem, t1;
+    /* FIXME: we can simplify this in most cases (see Knuth) */
+    MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
+    unsigned k;
+    int sign;
+
+    u = mpi_copy(a);
+    v = mpi_copy(n);
+    for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
+	mpi_rshift(u, u, 1);
+	mpi_rshift(v, v, 1);
+    }
 
-    g0 = mpi_copy(v);
-    g1 = mpi_copy(u);
-    v0 = mpi_alloc_set_ui( 0 );
-    v1 = mpi_alloc_set_ui( 1 );
-    div = mpi_alloc(mpi_get_nlimbs(v));
-    rem = mpi_alloc(mpi_get_nlimbs(v));
-    t1	= mpi_alloc(mpi_get_nlimbs(v));
-    while( mpi_cmp_ui( g1, 0) ) {
-	mpi_fdiv_qr(div, rem, g0, g1);
-	mpi_mul(t1, div, v1);
-	mpi_sub(t1, v0, t1);
-	mpi_set(v0, v1);
-	mpi_set(v1, t1);
-	mpi_set(g0, g1);
-	mpi_set(g1, rem);
 
+    u1 = mpi_alloc_set_ui(1);
+    u2 = mpi_alloc_set_ui(0);
+    u3 = mpi_copy(u);
+    v1 = mpi_copy(v);				   /* !-- used as const 1 */
+    v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
+    v3 = mpi_copy(v);
+    if( mpi_test_bit(u, 0) ) { /* u is odd */
+	t1 = mpi_alloc_set_ui(0);
+	t2 = mpi_alloc_set_ui(1); t2->sign = 1;
+	t3 = mpi_copy(v); t3->sign = !t3->sign;
+	goto Y4;
+    }
+    else {
+	t1 = mpi_alloc_set_ui(1);
+	t2 = mpi_alloc_set_ui(0);
+	t3 = mpi_copy(u);
     }
-    if( mpi_cmp_ui( v0, 0) < 0 )
-	mpi_add( x, v0, v);
-    else
-	mpi_set( x, v0);
+    do {
+	do {
+	    if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
+		mpi_add(t1, t1, v);
+		mpi_sub(t2, t2, u);
+	    }
+	    mpi_rshift(t1, t1, 1);
+	    mpi_rshift(t2, t2, 1);
+	    mpi_rshift(t3, t3, 1);
+	  Y4:
+	} while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
 
-    mpi_free(g0);
-    mpi_free(g1);
-    mpi_free(v0);
+	if( !t3->sign ) {
+	    mpi_set(u1, t1);
+	    mpi_set(u2, t2);
+	    mpi_set(u3, t3);
+	}
+	else {
+	    mpi_sub(v1, v, t1);
+	    sign = u->sign; u->sign = !u->sign;
+	    mpi_sub(v2, u, t2);
+	    u->sign = sign;
+	    sign = t3->sign; t3->sign = !t3->sign;
+	    mpi_set(v3, t3);
+	    t3->sign = sign;
+	}
+	mpi_sub(t1, u1, v1);
+	mpi_sub(t2, u2, v2);
+	mpi_sub(t3, u3, v3);
+	if( t1->sign ) {
+	    mpi_add(t1, t1, v);
+	    mpi_sub(t2, t2, u);
+	}
+    } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
+    /* mpi_lshift( u3, k ); */
+    mpi_set(x, u1);
+
+    mpi_free(u1);
+    mpi_free(u2);
+    mpi_free(u3);
     mpi_free(v1);
-    mpi_free(div);
-    mpi_free(rem);
+    mpi_free(v2);
+    mpi_free(v3);
     mpi_free(t1);
-    return 0;
+    mpi_free(t2);
+    mpi_free(t3);
+  #endif
 }
 
 
diff --git a/mpi/mpiutil.c b/mpi/mpiutil.c
index 752ce7f84..4e2a09056 100644
--- a/mpi/mpiutil.c
+++ b/mpi/mpiutil.c
@@ -265,6 +265,7 @@ mpi_copy( MPI a )
 	b = mpi_alloc( a->nlimbs );
       #endif
 	b->nlimbs = a->nlimbs;
+	b->sign = a->sign;
 	for(i=0; i < b->nlimbs; i++ )
 	    b->d[i] = a->d[i];
     }
@@ -318,9 +319,9 @@ mpi_alloc_set_ui( unsigned long u)
 void
 mpi_swap( MPI a, MPI b)
 {
-    MPI x;
+    struct mpi_struct tmp;
 
-    x = a; a = b; b = x;
+    tmp = *a; *a = *b; *b = tmp;
 }