summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--acconfig.h6
-rw-r--r--cipher/rsa.c37
-rw-r--r--config.h.in5
-rw-r--r--configure.in9
-rw-r--r--g10/Makefile.am3
-rw-r--r--g10/Makefile.in2
-rw-r--r--g10/build-packet.c2
-rw-r--r--g10/encode.c167
-rw-r--r--g10/g10.c6
-rw-r--r--g10/keygen.c1
-rw-r--r--include/cipher.h4
-rw-r--r--include/iobuf.h1
-rw-r--r--include/mpi.h5
-rw-r--r--mpi/mpi-add.c49
-rw-r--r--mpi/mpi-bit.c21
-rw-r--r--mpi/mpi-inv.c152
-rw-r--r--mpi/mpiutil.c5
-rw-r--r--tools/Makefile.am3
-rw-r--r--tools/Makefile.in4
-rw-r--r--tools/mpicalc.c13
-rw-r--r--util/iobuf.c9
21 files changed, 392 insertions, 112 deletions
diff --git a/acconfig.h b/acconfig.h
index 01aab2a6a..fa6f986cd 100644
--- a/acconfig.h
+++ b/acconfig.h
@@ -22,10 +22,14 @@
@@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@@
diff --git a/cipher/rsa.c b/cipher/rsa.c
index ec761a953..b2694ed5e 100644
--- a/cipher/rsa.c
+++ b/cipher/rsa.c
@@ -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 );
}
diff --git a/config.h.in b/config.h.in
index 1a4d6ef7e..e17daa8c0 100644
--- a/config.h.in
+++ b/config.h.in
@@ -44,6 +44,11 @@
#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
diff --git a/configure.in b/configure.in
index d6eeab10b..f6c9f6a12 100644
--- a/configure.in
+++ b/configure.in
@@ -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 ])
diff --git a/g10/Makefile.am b/g10/Makefile.am
index e01940b99..7da61f7eb 100644
--- a/g10/Makefile.am
+++ b/g10/Makefile.am
@@ -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
+
diff --git a/g10/Makefile.in b/g10/Makefile.in
index d7f9ae267..b086d7c4d 100644
--- a/g10/Makefile.in
+++ b/g10/Makefile.in
@@ -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
diff --git a/g10/build-packet.c b/g10/build-packet.c
index b6e1b6fd4..229c5a428 100644
--- a/g10/build-packet.c
+++ b/g10/build-packet.c
@@ -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 ) {
diff --git a/g10/encode.c b/g10/encode.c
index 5b599ef00..ad8d3f720 100644
--- a/g10/encode.c
+++ b/g10/encode.c
@@ -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;
}
diff --git a/g10/g10.c b/g10/g10.c
index 1cf1d769a..55ea0c26b 100644
--- 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);
}
diff --git a/g10/keygen.c b/g10/keygen.c
index 0d5db8d85..1f174498c 100644
--- a/g10/keygen.c
+++ b/g10/keygen.c
@@ -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 )) )
diff --git a/include/cipher.h b/include/cipher.h
index ac19c3fc0..a19fcfdb7 100644
--- a/include/cipher.h
+++ b/include/cipher.h
@@ -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"
diff --git a/include/iobuf.h b/include/iobuf.h
index 328cd8da5..a3c64a44b 100644
--- a/include/iobuf.h
+++ b/include/iobuf.h
@@ -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 );
diff --git a/include/mpi.h b/include/mpi.h
index 4470c609a..096cffec9 100644
--- a/include/mpi.h
+++ b/include/mpi.h
@@ -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*/
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;
}
diff --git a/tools/Makefile.am b/tools/Makefile.am
index a23b8d349..31ac04bcb 100644
--- a/tools/Makefile.am
+++ b/tools/Makefile.am
@@ -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
diff --git a/tools/Makefile.in b/tools/Makefile.in
index b9f55a889..67e3d6f89 100644
--- a/tools/Makefile.in
+++ b/tools/Makefile.in
@@ -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
diff --git a/tools/mpicalc.c b/tools/mpicalc.c
index 2402695d7..828b475b3 100644
--- a/tools/mpicalc.c
+++ b/tools/mpicalc.c
@@ -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);
diff --git a/util/iobuf.c b/util/iobuf.c
index 12fc74ff6..6c4a5f5da 100644
--- a/util/iobuf.c
+++ b/util/iobuf.c
@@ -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;
+}
+
/****************
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-03 13:57:05 +0100