Output armor works, RSA keygen works.
authorWerner Koch <wk@gnupg.org>
Wed, 19 Nov 1997 13:12:23 +0000 (13:12 +0000)
committerWerner Koch <wk@gnupg.org>
Wed, 19 Nov 1997 13:12:23 +0000 (13:12 +0000)
21 files changed:
acconfig.h
cipher/rsa.c
config.h.in
configure.in
g10/Makefile.am
g10/Makefile.in
g10/build-packet.c
g10/encode.c
g10/g10.c
g10/keygen.c
include/cipher.h
include/iobuf.h
include/mpi.h
mpi/mpi-add.c
mpi/mpi-bit.c
mpi/mpi-inv.c
mpi/mpiutil.c
tools/Makefile.am
tools/Makefile.in
tools/mpicalc.c
util/iobuf.c

index 01aab2a..fa6f986 100644 (file)
 
 
 @@TOP@@
-
 #undef M_DEBUG
 #undef VERSION
 #undef PACKAGE
+/* RSA is only compiled in if you have these files. You can use
+ * RSA with out any restrictions, if your not in the U.S. or
+ * wait until sep 20, 2000
+ */
+#undef HAVE_RSA_CIPHER
 
 @@BOTTOM@@
 
index ec761a9..b2694ed 100644 (file)
@@ -91,50 +91,57 @@ rsa_generate( RSA_public_key *pk, RSA_secret_key *sk, unsigned nbits )
     MPI n;    /* the public key */
     MPI e;    /* the exponent */
     MPI phi;  /* helper: (p-a)(q-1) */
+    MPI g;
+    MPI f;
 
     /* select two (very secret) primes */
     p = generate_random_prime( nbits / 2 );
     q = generate_random_prime( nbits / 2 );
-    if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q */
+    if( mpi_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
        mpi_swap(p,q);
-    /* calculate phi = (p-1)(q-1) */
+    /* calculate Euler totient: phi = (p-1)(q-1) */
     t1 = mpi_alloc_secure( mpi_get_nlimbs(p) );
     t2 = mpi_alloc_secure( mpi_get_nlimbs(p) );
     phi = mpi_alloc_secure( nbits / BITS_PER_MPI_LIMB  );
+    g  = mpi_alloc_secure( nbits / BITS_PER_MPI_LIMB  );
+    f  = mpi_alloc_secure( nbits / BITS_PER_MPI_LIMB  );
     mpi_sub_ui( t1, p, 1 );
     mpi_sub_ui( t2, q, 1 );
     mpi_mul( phi, t1, t2 );
+    mpi_gcd(g, t1, t2);
+    mpi_fdiv_q(f, phi, g);
     /* multiply them to make the private key */
     n = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
     mpi_mul( n, p, q );
     /* find a public exponent  */
     e = mpi_alloc(1);
     mpi_set_ui( e, 17); /* start with 17 */
-    while( !mpi_gcd(t1, e, phi) ) { /* (while gcd is not 1) */
-       if( DBG_CIPHER )
-           log_mpidump("trying e=", e);
+    while( !mpi_gcd(t1, e, phi) ) /* (while gcd is not 1) */
        mpi_add_ui( e, e, 2);
-    }
     /* calculate the secret key d = e^1 mod phi */
     d = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
-    mpi_inv_mod(d, e, phi );
+    mpi_inv_mod(d, e, f );
     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
     u = mpi_alloc( nbits / BITS_PER_MPI_LIMB );
     mpi_inv_mod(u, p, q );
 
     if( DBG_CIPHER ) {
-       log_mpidump("p=", p );
-       log_mpidump("q=", q );
-       log_mpidump("phi=", phi );
-       log_mpidump("n=", n );
-       log_mpidump("e=", e );
-       log_mpidump("d=", d );
-       log_mpidump("u=", u );
+       log_mpidump("  p= ", p );
+       log_mpidump("  q= ", q );
+       log_mpidump("phi= ", phi );
+       log_mpidump("  g= ", g );
+       log_mpidump("  f= ", f );
+       log_mpidump("  n= ", n );
+       log_mpidump("  e= ", e );
+       log_mpidump("  d= ", d );
+       log_mpidump("  u= ", u );
     }
 
     mpi_free(t1);
     mpi_free(t2);
     mpi_free(phi);
+    mpi_free(f);
+    mpi_free(g);
 
     pk->n = mpi_copy(n);
     pk->e = mpi_copy(e);
@@ -146,7 +153,7 @@ rsa_generate( RSA_public_key *pk, RSA_secret_key *sk, unsigned nbits )
     sk->u = u;
 
     /* now we can test our keys (this should never fail!) */
-    test_keys( pk, sk, nbits - 16 );
+    test_keys( pk, sk, nbits - 64 );
 }
 
 
index 1a4d6ef..e17daa8 100644 (file)
 #undef M_DEBUG
 #undef VERSION
 #undef PACKAGE
+/* RSA is only compiled in if you have these files. You can use
+ * RSA with out any restrictions, if your not in the U.S. or
+ * wait until sep 20, 2000
+ */
+#undef HAVE_RSA_CIPHER
 
 /* Define if you have the strerror function.  */
 #undef HAVE_STRERROR
index d6eeab1..f6c9f6a 100644 (file)
@@ -47,6 +47,15 @@ dnl Checks for library functions.
 AC_FUNC_VPRINTF
 AC_CHECK_FUNCS(strerror strtol strtoul)
 
+dnl
+AC_MSG_CHECKING(wether we have the rsa source)
+if test -f cipher/rsa.c && test -f cipher/rsa.h; then
+    AC_DEFINE(HAVE_RSA_CIPHER)
+    AC_MSG_RESULT(yes)
+else
+    AC_MSG_RESULT(no)
+fi
+
 AC_OUTPUT([ Makefile util/Makefile mpi/Makefile cipher/Makefile \
            g10/Makefile tools/Makefile ],
          [echo timestamp > stamp-h ])
index e01940b..7da61f7 100644 (file)
@@ -31,3 +31,6 @@ g10_SOURCES = g10.c           \
 
 LDADD = -L ../cipher -L ../mpi -L ../util -lcipher -lmpi -lutil
 
+
+$(PROGRAMS): ../cipher/libcipher.a ../mpi/libmpi.a
+
index d7f9ae2..b086d7c 100644 (file)
@@ -277,6 +277,8 @@ install-exec install-data install uninstall all installdirs \
 mostlyclean-generic distclean-generic clean-generic \
 maintainer-clean-generic clean mostlyclean distclean maintainer-clean
 
+
+$(PROGRAMS): ../cipher/libcipher.a ../mpi/libmpi.a
 .SUFFIXES:
 .SUFFIXES: .c .o
 
index b6e1b6f..229c5a4 100644 (file)
@@ -361,7 +361,7 @@ write_header( IOBUF out, int ctb, u32 len )
     if( iobuf_put(out, ctb ) )
        return -1;
     if( !len ) {
-       iobuf_set_block_mode(out, 5 /*8196*/ );
+       iobuf_set_block_mode(out, 8196 );
     }
     else {
        if( ctb & 2 ) {
index 5b599ef..ad8d3f7 100644 (file)
@@ -56,8 +56,51 @@ typedef struct {
 } cipher_filter_context_t;
 
 
+typedef struct {
+    int status;
+    int what;
+    byte buf[3];
+    int  idx, idx2;
+    u32 crc;
+} armor_filter_context_t;
+
 
 
+#define CRCINIT 0xB704CE
+#define CRCPOLY 0X864CFB
+#define CRCUPDATE(a,c) do {                                                \
+                       a = ((a) << 8) ^ crc_table[((a)&0xff >> 16) ^ (c)]; \
+                       a &= 0x00ffffff;                                    \
+                   } while(0)
+static u32 crc_table[256];
+static int crc_table_initialized;
+
+
+
+static void
+init_crc_table(void)
+{
+    int i, j;
+    u32 t;
+
+    crc_table[0] = 0;
+    for(i=j=0; j < 128; j++ ) {
+       t = crc_table[j];
+       if( t & 0x00800000 ) {
+           t <<= 1;
+           crc_table[i++] = t ^ CRCPOLY;
+           crc_table[i++] = t;
+       }
+       else {
+           t <<= 1;
+           crc_table[i++] = t;
+           crc_table[i++] = t ^ CRCPOLY;
+       }
+    }
+
+    crc_table_initialized=1;
+}
+
 
 
 /****************
@@ -106,8 +149,10 @@ encode_simple( const char *filename, int mode )
     int rc = 0;
     u32 filesize;
     cipher_filter_context_t cfx;
+    armor_filter_context_t afx;
 
     memset( &cfx, 0, sizeof cfx);
+    memset( &afx, 0, sizeof afx);
 
     /* prepare iobufs */
     if( !(inp = iobuf_open(filename)) ) {
@@ -135,7 +180,7 @@ encode_simple( const char *filename, int mode )
     }
 
     if( opt.armor )
-       iobuf_push_filter( out, armor_filter, NULL );
+       iobuf_push_filter( out, armor_filter, &afx );
 
     write_comment( out, "#Created by G10 pre-release " VERSION );
 
@@ -197,11 +242,13 @@ encode_crypt( const char *filename, STRLIST remusr )
     int last_rc, rc = 0;
     u32 filesize;
     cipher_filter_context_t cfx;
+    armor_filter_context_t afx;
     int any_names = 0;
     STRLIST local_remusr = NULL;
     char *ustr;
 
     memset( &cfx, 0, sizeof cfx);
+    memset( &afx, 0, sizeof afx);
 
     if( !remusr ) {
        remusr = NULL; /* fixme: ask */
@@ -225,7 +272,7 @@ encode_crypt( const char *filename, STRLIST remusr )
     }
 
     if( opt.armor )
-       iobuf_push_filter( out, armor_filter, NULL );
+       iobuf_push_filter( out, armor_filter, &afx );
 
     write_comment( out, "#Created by G10 pre-release " VERSION );
 
@@ -389,11 +436,121 @@ open_outfile( const char *iname )
 
 static int
 armor_filter( void *opaque, int control,
-             IOBUF chain, byte *buf, size_t *ret_len)
+             IOBUF a, byte *buffer, size_t *ret_len)
 {
-    if( control == IOBUFCTRL_DESC ) {
-       *(char**)buf = "armor_filter";
+    static byte bintoasc[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
+                            "abcdefghijklmnopqrstuvwxyz"
+                            "0123456789+/";
+    size_t size = *ret_len;
+    armor_filter_context_t *afx = opaque;
+    int rc=0, i, c;
+    byte buf[3];
+    int  idx, idx2;
+    u32 crc;
+
+
+    if( control == IOBUFCTRL_FLUSH ) {
+       if( !afx->status ) { /* write the header line */
+           if( !afx->what )
+               iobuf_writestr(a, "-----BEGIN PGP MESSAGE-----\n");
+           else
+               iobuf_writestr(a, "-----BEGIN PGP PUBLIC KEY BLOCK-----\n");
+           iobuf_writestr(a, "Version: G10 pre-release "  VERSION "\n");
+           iobuf_writestr(a, "Comment: This is a alpha test version!\n\n");
+           afx->status++;
+           afx->idx = 0;
+           afx->idx2 = 0;
+           afx->crc = CRCINIT;
+       }
+       crc = afx->crc;
+       idx = afx->idx;
+       idx2 = afx->idx2;
+       for(i=0; i < idx; i++ )
+           buf[i] = afx->buf[i];
+
+       for(i=0; i < size; i++ )
+           crc = (crc << 8) ^ crc_table[(crc >> 16)&0xff ^ buffer[i]];
+       crc &= 0x00ffffff;
+
+       for( ; size; buffer++, size-- ) {
+           buf[idx++] = *buffer;
+           if( idx > 2 ) {
+               idx = 0;
+               c = bintoasc[(*buf >> 2) & 077];
+               iobuf_put(a, c);
+               c = bintoasc[(((*buf<<4)&060)|((buf[1] >> 4)&017))&077];
+               iobuf_put(a, c);
+               c = bintoasc[(((buf[1]<<2)&074)|((buf[2]>>6)&03))&077];
+               iobuf_put(a, c);
+               c = bintoasc[buf[2]&077];
+               iobuf_put(a, c);
+               if( ++idx2 > (72/4) ) {
+                   iobuf_put(a, '\n');
+                   idx2=0;
+               }
+           }
+       }
+       for(i=0; i < idx; i++ )
+           afx->buf[i] = buf[i];
+       afx->idx = idx;
+       afx->idx2 = idx2;
+       afx->crc  = crc;
     }
+    else if( control == IOBUFCTRL_INIT ) {
+       if( !crc_table_initialized )
+           init_crc_table();
+    }
+    else if( control == IOBUFCTRL_FREE ) {
+       if( afx->status ) { /* pad, write cecksum, and bottom line */
+           crc = afx->crc;
+           idx = afx->idx;
+           idx2 = afx->idx2;
+           for(i=0; i < idx; i++ )
+               buf[i] = afx->buf[i];
+           if( idx ) {
+               c = bintoasc[(*buf>>2)&077];
+               iobuf_put(a, c);
+               if( idx == 1 ) {
+                   c = bintoasc[((*buf << 4) & 060) & 077];
+                   iobuf_put(a, c);
+                   iobuf_put(a, '=');
+                   iobuf_put(a, '=');
+               }
+               else { /* 2 */
+                   c = bintoasc[(((*buf<<4)&060)|((buf[1]>>4)&017))&077];
+                   iobuf_put(a, c);
+                   c = bintoasc[((buf[1] << 2) & 074) & 077];
+                   iobuf_put(a, c);
+                   iobuf_put(a, '=');
+               }
+               ++idx2;
+           }
+           /* may need a linefeed */
+           if( idx2 < (72/4) )
+               iobuf_put(a, '\n');
+           /* write the CRC */
+           iobuf_put(a, '=');
+           buf[0] = crc >>16;
+           buf[1] = crc >> 8;
+           buf[2] = crc;
+           c = bintoasc[(*buf >> 2) & 077];
+           iobuf_put(a, c);
+           c = bintoasc[(((*buf<<4)&060)|((buf[1] >> 4)&017))&077];
+           iobuf_put(a, c);
+           c = bintoasc[(((buf[1]<<2)&074)|((buf[2]>>6)&03))&077];
+           iobuf_put(a, c);
+           c = bintoasc[buf[2]&077];
+           iobuf_put(a, c);
+           iobuf_put(a, '\n');
+           /* and the the trailer */
+           if( !afx->what )
+               iobuf_writestr(a, "-----END PGP MESSAGE-----\n");
+           else
+               iobuf_writestr(a, "-----END PGP PUBLIC KEY BLOCK-----\n");
+       }
+    }
+    else if( control == IOBUFCTRL_DESC )
+       *(char**)buf = "armor_filter";
     return 0;
 }
 
index 1cf1d76..55ea0c2 100644 (file)
--- a/g10/g10.c
+++ b/g10/g10.c
@@ -50,7 +50,11 @@ strusage( int level )
       case 12: p =
     "\nSyntax: g10 [options] [files]\n"
     "sign, check, encrypt or decrypt\n"
-    "default operation depends on the input data\n";
+    "default operation depends on the input data\n"
+  #ifndef HAVE_RSA_CIPHER
+    "This version does not support RSA!\n"
+  #endif
+       ;
        break;
       default: p = default_strusage(level);
     }
index 0d5db8d..1f17449 100644 (file)
@@ -204,7 +204,6 @@ generate_keypair()
            m_free(answer);
        }
     }
-
     /* now check wether we a are allowed to write the keyrings */
     if( !(rc=overwrite_filep( pub_fname )) ) {
        if( !(pub_io = iobuf_create( pub_fname )) )
index ac19c3f..a19fcfd 100644 (file)
@@ -30,7 +30,9 @@
 #include "mpi.h"
 #include "../cipher/md5.h"
 #include "../cipher/rmd.h"
-#include "../cipher/rsa.h"
+#ifdef HAVE_RSA_CIPHER
+  #include "../cipher/rsa.h"
+#endif
 #include "../cipher/idea.h"
 #include "../cipher/blowfish.h"
 #include "../cipher/gost.h"
index 328cd8d..a3c64a4 100644 (file)
@@ -81,6 +81,7 @@ void iobuf_set_limit( IOBUF a, unsigned long nlimit );
 int  iobuf_readbyte(IOBUF a);
 int  iobuf_writebyte(IOBUF a, unsigned c);
 int  iobuf_write(IOBUF a, byte *buf, unsigned buflen );
+int  iobuf_writestr(IOBUF a, const char *buf );
 
 int  iobuf_write_temp( IOBUF a, IOBUF temp );
 size_t iobuf_temp_to_buffer( IOBUF a, byte *buffer, size_t buflen );
index 4470c60..096cffe 100644 (file)
@@ -40,7 +40,7 @@ int mpi_debug_mode;
   #error add definions for this machine here
 #endif
 
-typedef struct {
+typedef struct mpi_struct {
     int alloced;    /* array size (# of allocated limbs) */
     int nlimbs;     /* number of valid limbs */
     int sign;      /* indicates a negative number */
@@ -139,9 +139,10 @@ int  mpi_test_bit( MPI a, unsigned n );
 void mpi_set_bit( MPI a, unsigned n );
 void mpi_clear_bit( MPI a, unsigned n );
 void mpi_set_bytes( MPI a, unsigned nbits, byte (*fnc)(int), int opaque );
+void mpi_rshift( MPI x, MPI a, unsigned n );
 
 /*-- mpi-inv.c --*/
-int  mpi_inv_mod( MPI x, MPI u, MPI v );
+void mpi_inv_mod( MPI x, MPI u, MPI v );
 
 
 #endif /*G10_MPI_H*/
index 047a2fa..2c1aa6c 100644 (file)
@@ -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 );
index 9cb346a..9bde9f0 100644 (file)
@@ -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;
+}
 
index acde605..f37f4e5 100644 (file)
 #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
 }
 
 
index 752ce7f..4e2a090 100644 (file)
@@ -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;
 }
 
 
index a23b8d3..31ac04b 100644 (file)
@@ -7,6 +7,7 @@ bin_PROGRAMS = mpicalc
 mpicalc_SOURCES = mpicalc.c
 
 
-LDADD = -L ../cipher -L ../mpi -L ../util -lcipher -lmpi -lutil
+LDADD = -L ../cipher -L ../mpi -L ../util  -lmpi -lutil
 
+$(PROGRAMS): ../mpi/libmpi.a
 
index b9f55a8..67e3d6f 100644 (file)
@@ -44,7 +44,7 @@ bin_PROGRAMS = mpicalc
 
 mpicalc_SOURCES = mpicalc.c
 
-LDADD = -L ../cipher -L ../mpi -L ../util -lcipher -lmpi -lutil
+LDADD = -L ../cipher -L ../mpi -L ../util  -lmpi -lutil
 mkinstalldirs = $(top_srcdir)/scripts/mkinstalldirs
 CONFIG_HEADER = ../config.h
 PROGRAMS = $(bin_PROGRAMS)
@@ -244,6 +244,8 @@ install-exec install-data install uninstall all installdirs \
 mostlyclean-generic distclean-generic clean-generic \
 maintainer-clean-generic clean mostlyclean distclean maintainer-clean
 
+
+$(PROGRAMS): ../mpi/libmpi.a
 .SUFFIXES:
 .SUFFIXES: .c .o
 
index 2402695..828b475 100644 (file)
@@ -179,6 +179,16 @@ do_gcd(void)
     stackidx--;
 }
 
+static void
+do_rshift(void)
+{
+    if( stackidx < 1 ) {
+       fputs("stack underflow\n", stderr);
+       return;
+    }
+    mpi_rshift( stack[stackidx-1],stack[stackidx-1], 1 );
+}
+
 
 int
 main(int argc, char **argv)
@@ -259,6 +269,9 @@ main(int argc, char **argv)
                  case 'G':
                    do_gcd();
                    break;
+                 case '>':
+                   do_rshift();
+                   break;
                  case 'i': /* dummy */
                    if( !stackidx )
                        fputs("stack underflow\n", stderr);
index 12fc74f..6c4a5f5 100644 (file)
@@ -627,6 +627,15 @@ iobuf_write(IOBUF a, byte *buf, unsigned buflen )
     return 0;
 }
 
+int
+iobuf_writestr(IOBUF a, const char *buf )
+{
+    for( ; *buf; buf++ )
+       if( iobuf_writebyte(a, *buf) )
+           return -1;
+    return 0;
+}
+
 
 
 /****************