Improved prime number test

10 files changed, 392 insertions, 267 deletions

diff --git a/TODO b/TODO
index 3698c1833..7021c4e38 100644
--- a/TODO
+++ b/TODO
@@ -1,5 +1,5 @@
 
-    * write the assembler function for mpihelp ....
+    * add assembler support for more CPUs. (work, but easy)
     * improve iobuf by reading more than one byte at once,
       this shoud espceially done for the buffer in the chain.
     * add a way to difference between errors and eof in the underflow/flush
@@ -17,12 +17,10 @@
     * fix the memory stuff (secure memory)
     * add real secure memory
     * look for a way to reuse RSA signatures
-    * add ElGamal and make it the default one.
     * find a way to remove the armor filter after it
       has detected, that the data is not armored.
     * Use the Chines Remainder Theorem to speed up RSA calculations.
     * remove all "Fixmes"
-    * add credits for the MPI lib.
     * speed up the RIPE-MD-160
     * add signal handling
     * enable a SIGSEGV handler while using zlib functions
diff --git a/cipher/primegen.c b/cipher/primegen.c
index 0173b3d0b..d69f09ac3 100644
--- a/cipher/primegen.c
+++ b/cipher/primegen.c
@@ -28,7 +28,7 @@
 #include "cipher.h"
 
 static int no_of_small_prime_numbers;
-static int rabin_miller( MPI n );
+static int is_not_prime( MPI n, unsigned nbits, int steps, int *count );
 static MPI gen_prime( unsigned	nbits, int mode );
 
 
@@ -50,7 +50,6 @@ generate_public_prime( unsigned  nbits )
 static MPI
 gen_prime( unsigned  nbits, int secret )
 {
-
     unsigned  nlimbs;
     MPI prime, val_2, val_3, result;
     int i;
@@ -111,22 +110,9 @@ gen_prime( unsigned  nbits, int secret )
 		continue;  /* stepping (fermat test failed) */
 	    if( DBG_CIPHER )
 		fputc('+', stderr);
-	    /* and a second one */
-	    count2++;
-	    mpi_powm( result, val_3, prime, prime );
-	    if( mpi_cmp_ui(result, 3) )
-		continue;  /* stepping (fermat test failed) */
-	    if( DBG_CIPHER )
-		fputc('+', stderr);
 
-	    /* perform Rabin-Miller tests */
-	    for(i=5; i > 0; i-- ) {
-		if( DBG_CIPHER )
-		    fputc('+', stderr);
-		if( rabin_miller(prime) )
-		    break;
-	    }
-	    if( !i ) {
+	    /* perform stronger tests */
+	    if( !is_not_prime(prime, nbits, 5, &count2 ) ) {
 		if( !mpi_test_bit( prime, nbits-1 ) ) {
 		    if( DBG_CIPHER ) {
 			fputc('\n', stderr);
@@ -136,7 +122,7 @@ gen_prime( unsigned  nbits, int secret )
 		}
 		if( DBG_CIPHER ) {
 		    fputc('\n', stderr);
-		    log_debug("performed %u simple and %u Fermat/Rabin-Miller tests\n",
+		    log_debug("performed %u simple and %u stronger tests\n",
 					count1, count2 );
 		    log_mpidump("found prime: ", prime );
 		}
@@ -158,8 +144,53 @@ gen_prime( unsigned  nbits, int secret )
  * Return 1 if n is not a prime
  */
 static int
-rabin_miller( MPI n )
+is_not_prime( MPI n, unsigned nbits, int steps, int *count )
 {
-    return 0;
+    MPI x = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI y = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI z = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI nminus1 = mpi_alloc( mpi_get_nlimbs( n ) );
+    MPI a2 = mpi_alloc_set_ui( 2 );
+    MPI q;
+    unsigned i, j, k;
+    int rc = 1;
+
+    mpi_sub_ui( nminus1, n, 1 );
+
+    /* find q and k, so that n = 1 + 2^k * q */
+    q = mpi_copy( nminus1 );
+    k = mpi_trailing_zeros( q );
+    mpi_tdiv_q_2exp(q, q, k);
+
+    for(i=0 ; i < steps; i++ ) {
+	++*count;
+	do {
+	    mpi_set_bytes( x, nbits, get_random_byte, 0 );
+	} while( mpi_cmp( x, n ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
+	mpi_powm( y, x, q, n);
+	if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
+	    for( j=1; j < k; j++ ) {
+		mpi_powm(y, y, a2, n);
+		if( !mpi_cmp_ui( y, 1 ) )
+		    goto leave; /* not a prime */
+		if( !mpi_cmp( y, nminus1 ) )
+		    break;  /* may be a prime */
+	    }
+	    if( j == k )
+		goto leave;
+	}
+	if( DBG_CIPHER )
+	    fputc('+', stderr);
+    }
+    rc = 0; /* may be a prime */
+
+  leave:
+    mpi_free( x );
+    mpi_free( y );
+    mpi_free( z );
+    mpi_free( nminus1 );
+    mpi_free( q );
+
+    return rc;
 }
 
diff --git a/configure.in b/configure.in
index 2f77c0689..4575bc888 100644
--- a/configure.in
+++ b/configure.in
@@ -18,8 +18,8 @@ AC_ARG_ENABLE(m-debug,
 [  --enable-m-debug    Enable debugging of memory allocation])
 if test "$enableval" = y || test "$enableval" = yes; then
     AC_DEFINE(M_DEBUG)
-    CFLAGS="-g"
 fi
+CFLAGS="-g"
 
 dnl
 AC_CANONICAL_HOST
diff --git a/g10/g10.c b/g10/g10.c
index 882f84c88..f3be29575 100644
--- a/g10/g10.c
+++ b/g10/g10.c
@@ -33,7 +33,7 @@
 #include "cipher.h"
 #include "filter.h"
 
-static void do_test(void);
+static void do_test(int);
 
 const char *
 strusage( int level )
@@ -114,7 +114,7 @@ main( int argc, char **argv )
     { 's', "sign",      0, "make a signature"},
     { 'e', "encrypt",   0, "encrypt data" },
     { 'd', "decrypt",   0, "decrypt data (default)" },
-    { 'c', "check",     0, "check a signature (default)" },
+  /*{ 'c', "check",     0, "check a signature (default)" }, */
     { 'l', "local-user",2, "use this user-id to sign or decrypt" },
     { 'r', "remote-user", 2, "use this user-id for encryption" },
     { 510, "debug"     ,4|16, "set debugging flags" },
@@ -246,7 +246,7 @@ main( int argc, char **argv )
 	generate_keypair();
 	break;
 
-      case aTest: do_test(); break;
+      case aTest: do_test( atoi(*argv) ); break;
 
       default:
 	if( argc > 1 )
@@ -270,7 +270,7 @@ main( int argc, char **argv )
 
 
 static void
-do_test()
+do_test(int times)
 {
     MPI t = mpi_alloc( 50 );
     MPI m = mpi_alloc( 50 );
@@ -278,22 +278,17 @@ do_test()
     MPI b = mpi_alloc( 50 );
     MPI p = mpi_alloc( 50 );
     MPI x = mpi_alloc( 50 );
-    mpi_fromstr(a, "0xef45678343589854354a4545545454554545455"
-		   "aaaaaaaaaaaaa44444fffdecb33434343443331" );
-    mpi_fromstr(b, "0x8765765589854354a4545545454554545455"
-		   "aaaaaaa466577778decb36666343443331" );
-    mpi_fromstr(p, "0xcccddd456700000012222222222222254545455"
-		   "aaaaaaaaaaaaa44444fffdecb33434343443337" );
-    mpi_fromstr(x, "0x100004545543656456656545545454554545455"
-		    "aaa33aaaa465456544fffdecb33434bbbac3331" );
 
     /* output = b/(a^x) mod p */
-    log_debug("powm ..\n");
-    mpi_powm( t, a, x, p );
-    log_debug("invm ..\n");
-    mpi_invm( t, t, p );
-    log_debug("mulm ..\n");
-    mpi_mulm( m, b, t, p );
+    log_debug("invm %d times ", times);
+    for( ; times > 0; times -- ) {
+	mpi_fromstr(a, "0xef45678343589854354a4545545454554545455"
+		       "aaaaaaaaaaaaa44444fffdecb33434343443331" );
+	mpi_fromstr(b, "0x8765765589854354a4545545454554545455"
+		       "aaaaaaa466577778decb36666343443331" );
+	mpi_invm( t, a, b );
+	fputc('.', stderr); fflush(stderr);
+    }
 
 
     m_check(NULL);
diff --git a/g10/mainproc.c b/g10/mainproc.c
index c056ac0af..9e34fbd0e 100644
--- a/g10/mainproc.c
+++ b/g10/mainproc.c
@@ -32,8 +32,21 @@
 #include "filter.h"
 #include "main.h"
 
+
+typedef struct {
+    PKT_pubkey_cert *last_pubkey;
+    PKT_seckey_cert *last_seckey;
+    PKT_user_id     *last_user_id;
+    md_filter_context_t mfx;
+    DEK *dek;
+    int last_was_pubkey_enc;
+} *CTX;
+
+
+
+
 static int opt_list=1;	/* and list the data packets to stdout */
-#if 0
+#if 1
 static void
 do_free_last_user_id( CTX c )
 {
@@ -62,10 +75,15 @@ do_free_last_seckey( CTX c )
 static void
 proc_pubkey_cert( CTX c, PACKET *pkt )
 {
+    u32 keyid[2];
+    char *ustr;
+    int lvl0 = opt.check_sigs? 1:0; /* stdout or /dev/null */
+
     do_free_last_user_id( c );
     do_free_last_seckey( c );
     if( opt.check_sigs ) {
-	char *ustr = get_user_id_string(sig->keyid); /* sig ???? */
+	keyid_from_pkc( pkt->pkt.pubkey_cert, keyid );
+	ustr = get_user_id_string(keyid);
 	printstr(lvl0, "pub: %s\n", ustr );
 	m_free(ustr);
     }
@@ -104,36 +122,246 @@ proc_seckey_cert( CTX c, PACKET *pkt )
 }
 
 
+static void
+proc_user_id( CTX c, PACKET *pkt )
+{
+    u32 keyid[2];
+
+    do_free_last_user_id( c );
+    if( opt_list ) {
+	 printf("uid: '%.*s'\n", pkt->pkt.user_id->len,
+				 pkt->pkt.user_id->name );
+	 if( !pkt->pkc_parent && !pkt->skc_parent )
+	     puts("      (orphaned)");
+    }
+    if( pkt->pkc_parent ) {
+	if( pkt->pkc_parent->pubkey_algo == PUBKEY_ALGO_ELGAMAL
+	    || pkt->pkc_parent->pubkey_algo == PUBKEY_ALGO_RSA ) {
+	    keyid_from_pkc( pkt->pkc_parent, keyid );
+	    cache_user_id( pkt->pkt.user_id, keyid );
+	}
+    }
+
+    c->last_user_id = pkt->pkt.user_id;  /* save */
+    pkt->pkt.user_id = NULL;
+    free_packet(pkt);
+    pkt->user_parent = c->last_user_id;  /* and set this as user */
+}
+
+
+static void
+proc_signature( CTX c, PACKET *pkt )
+{
+    PKT_signature *sig;
+    MD_HANDLE md_handle; /* union to pass handles down */
+    char *ustr;
+    int result = -1;
+    int lvl0 = opt.check_sigs? 1:0; /* stdout or /dev/null */
+    int lvl1 = opt.check_sigs? 1:3; /* stdout or error */
+
+    sig = pkt->pkt.signature;
+    ustr = get_user_id_string(sig->keyid);
+    if( sig->sig_class == 0x00 ) {
+	if( c->mfx.rmd160 )
+	    result = 0;
+	else
+	    printstr(lvl1,"sig?: %s: no plaintext for signature\n", ustr);
+    }
+    else if( sig->sig_class != 0x10 )
+	printstr(lvl1,"sig?: %s: unknown signature class %02x\n",
+				ustr, sig->sig_class);
+    else if( !pkt->pkc_parent || !pkt->user_parent )
+	printstr(lvl1,"sig?: %s: orphaned encoded packet\n", ustr);
+    else
+	result = 0;
+
+    if( result )
+	;
+    else if( !opt.check_sigs && sig->sig_class != 0x00 ) {
+	result = -1;
+	printstr(lvl0, "sig: from %s\n", ustr );
+    }
+    else if(sig->pubkey_algo == PUBKEY_ALGO_ELGAMAL ) {
+	md_handle.algo = sig->d.elg.digest_algo;
+	if( sig->d.elg.digest_algo == DIGEST_ALGO_RMD160 ) {
+	    if( sig->sig_class == 0x00 )
+		md_handle.u.rmd = rmd160_copy( c->mfx.rmd160 );
+	    else {
+		md_handle.u.rmd = rmd160_copy(pkt->pkc_parent->mfx.rmd160);
+		rmd160_write(md_handle.u.rmd, pkt->user_parent->name,
+					      pkt->user_parent->len);
+	    }
+	    result = signature_check( sig, md_handle );
+	    rmd160_close(md_handle.u.rmd);
+	}
+	else if( sig->d.elg.digest_algo == DIGEST_ALGO_MD5
+		 && sig->sig_class != 0x00 ) {
+	    md_handle.u.md5 = md5_copy(pkt->pkc_parent->mfx.md5);
+	    md5_write(md_handle.u.md5, pkt->user_parent->name,
+					  pkt->user_parent->len);
+	    result = signature_check( sig, md_handle );
+	    md5_close(md_handle.u.md5);
+	}
+	else
+	    result = G10ERR_DIGEST_ALGO;
+    }
+    else if(sig->pubkey_algo == PUBKEY_ALGO_RSA ) {
+	md_handle.algo = sig->d.rsa.digest_algo;
+	if( sig->d.rsa.digest_algo == DIGEST_ALGO_RMD160 ) {
+	    if( sig->sig_class == 0x00 )
+		md_handle.u.rmd = rmd160_copy( c->mfx.rmd160 );
+	    else {
+		md_handle.u.rmd = rmd160_copy(pkt->pkc_parent->mfx.rmd160);
+		rmd160_write(md_handle.u.rmd, pkt->user_parent->name,
+						 pkt->user_parent->len);
+	    }
+	    result = signature_check( sig, md_handle );
+	    rmd160_close(md_handle.u.rmd);
+	}
+	else if( sig->d.rsa.digest_algo == DIGEST_ALGO_MD5
+		 && sig->sig_class != 0x00 ) {
+	    md_handle.u.md5 = md5_copy(pkt->pkc_parent->mfx.md5);
+	    md5_write(md_handle.u.md5, pkt->user_parent->name,
+				       pkt->user_parent->len);
+	    result = signature_check( sig, md_handle );
+	    md5_close(md_handle.u.md5);
+	}
+	else
+	    result = G10ERR_DIGEST_ALGO;
+    }
+    else
+	result = G10ERR_PUBKEY_ALGO;
+
+    if( result == -1 )
+	;
+    else if( !result && sig->sig_class == 0x00 )
+	printstr(1,    "sig: good signature from %s\n", ustr );
+    else if( !result )
+	printstr(lvl0, "sig: good signature from %s\n", ustr );
+    else
+	printstr(lvl1, "sig? %s: %s\n", ustr, g10_errstr(result));
+    free_packet(pkt);
+    m_free(ustr);
+}
+
+
+static void
+proc_pubkey_enc( CTX c, PACKET *pkt )
+{
+    PKT_pubkey_enc *enc;
+    int result = 0;
+
+    c->last_was_pubkey_enc = 1;
+    enc = pkt->pkt.pubkey_enc;
+    printf("enc: encrypted by a pubkey with keyid %08lX\n", enc->keyid[1] );
+    if( enc->pubkey_algo == PUBKEY_ALGO_ELGAMAL
+	|| enc->pubkey_algo == PUBKEY_ALGO_RSA	) {
+	m_free(c->dek ); /* paranoid: delete a pending DEK */
+	c->dek = m_alloc_secure( sizeof *c->dek );
+	if( (result = get_session_key( enc, c->dek )) ) {
+	    /* error: delete the DEK */
+	    m_free(c->dek); c->dek = NULL;
+	}
+    }
+    else
+	result = G10ERR_PUBKEY_ALGO;
+
+    if( result == -1 )
+	;
+    else if( !result )
+	fputs(	"     DEK is good", stdout );
+    else
+	printf( "     %s", g10_errstr(result));
+    putchar('\n');
+    free_packet(pkt);
+}
+
+
+
+static void
+proc_encr_data( CTX c, PACKET *pkt )
+{
+    int result = 0;
+
+    printf("dat: %sencrypted data\n", c->dek?"":"conventional ");
+    if( !c->dek && !c->last_was_pubkey_enc ) {
+	/* assume this is conventional encrypted data */
+	c->dek = m_alloc_secure( sizeof *c->dek );
+	c->dek->algo = DEFAULT_CIPHER_ALGO;
+	result = make_dek_from_passphrase( c->dek, 0 );
+    }
+    else if( !c->dek )
+	result = G10ERR_NO_SECKEY;
+    if( !result )
+	result = decrypt_data( pkt->pkt.encr_data, c->dek );
+    m_free(c->dek); c->dek = NULL;
+    if( result == -1 )
+	;
+    else if( !result )
+	fputs(	"     encryption okay",stdout);
+    else
+	printf( "     %s", g10_errstr(result));
+    putchar('\n');
+    free_packet(pkt);
+    c->last_was_pubkey_enc = 0;
+}
+
+
+static void
+proc_plaintext( CTX c, PACKET *pkt )
+{
+    PKT_plaintext *pt = pkt->pkt.plaintext;
+    int result;
+
+    printf("txt: plain text data name='%.*s'\n", pt->namelen, pt->name);
+    free_md_filter_context( &c->mfx );
+    c->mfx.rmd160 = rmd160_open(0);
+    result = handle_plaintext( pt, &c->mfx );
+    if( !result )
+	fputs(	"     okay", stdout);
+    else
+	printf( "     %s", g10_errstr(result));
+    putchar('\n');
+    free_packet(pkt);
+    c->last_was_pubkey_enc = 0;
+}
+
+
+static void
+proc_compr_data( CTX c, PACKET *pkt )
+{
+    PKT_compressed *zd = pkt->pkt.compressed;
+    int result;
+
+    printf("zip: compressed data packet\n");
+    result = handle_compressed( zd );
+    if( !result )
+	fputs(	"     okay", stdout);
+    else
+	printf( "     %s", g10_errstr(result));
+    putchar('\n');
+    free_packet(pkt);
+    c->last_was_pubkey_enc = 0;
+}
 
 
 
 int
 proc_packets( IOBUF a )
 {
-    PACKET *pkt;
-    PKT_pubkey_cert *last_pubkey = NULL;
-    PKT_seckey_cert *last_seckey = NULL;
-    PKT_user_id     *last_user_id = NULL;
-    DEK *dek = NULL;
-    PKT_signature *sig; /* CHECK: "might be used uninitialied" */
+    CTX c = m_alloc_clear( sizeof *c );
+    PACKET *pkt = m_alloc( sizeof *pkt );
     int rc, result;
-    MD_HANDLE md_handle; /* union to pass handles */
     char *ustr;
     int lvl0, lvl1;
-    int last_was_pubkey_enc = 0;
     u32 keyid[2];
-    md_filter_context_t mfx;
 
-    memset( &mfx, 0, sizeof mfx );
-    lvl0 = opt.check_sigs? 1:0; /* stdout or /dev/null */
-    lvl1 = opt.check_sigs? 1:3; /* stdout or error */
-    pkt = m_alloc( sizeof *pkt );
     init_packet(pkt);
     while( (rc=parse_packet(a, pkt)) != -1 ) {
 	/* cleanup if we have an illegal data structure */
-	if( dek && pkt->pkttype != PKT_ENCR_DATA ) {
+	if( c->dek && pkt->pkttype != PKT_ENCR_DATA ) {
 	    log_error("oops: valid pubkey enc packet not followed by data\n");
-	    m_free(dek); dek = NULL; /* burn it */
+	    m_free(c->dek); c->dek = NULL; /* burn it */
 	}
 
 	if( rc ) {
@@ -143,217 +371,24 @@ proc_packets( IOBUF a )
 	switch( pkt->pkttype ) {
 	  case PKT_PUBKEY_CERT: proc_pubkey_cert( c, pkt ); break;
 	  case PKT_SECKEY_CERT: proc_seckey_cert( c, pkt ); break;
-	  case PKT_USER_ID:
-	    if( last_user_id ) {
-		free_user_id( last_user_id );
-		last_user_id = NULL;
-	    }
-	    if( opt_list ) {
-		 printf("uid: '%.*s'\n", pkt->pkt.user_id->len,
-					 pkt->pkt.user_id->name );
-		 if( !pkt->pkc_parent && !pkt->skc_parent )
-		     puts("      (orphaned)");
-	    }
-	    if( pkt->pkc_parent ) {
-		if( pkt->pkc_parent->pubkey_algo == PUBKEY_ALGO_ELGAMAL
-		    || pkt->pkc_parent->pubkey_algo == PUBKEY_ALGO_RSA ) {
-		    keyid_from_pkc( pkt->pkc_parent, keyid );
-		    cache_user_id( pkt->pkt.user_id, keyid );
-		}
-	    }
-
-	    last_user_id = pkt->pkt.user_id;  /* save */
-	    pkt->pkt.user_id = NULL;
-	    free_packet(pkt);	/* fixme: free_packet is not a good name */
-	    pkt->user_parent = last_user_id;  /* and set this as user */
-	    break;
-
-	  case PKT_SIGNATURE:
-	    sig = pkt->pkt.signature;
-	    ustr = get_user_id_string(sig->keyid);
-	    result = -1;
-	    if( sig->sig_class == 0x00 ) {
-		if( mfx.rmd160 )
-		    result = 0;
-		else
-		    printstr(lvl1,"sig?: %s: no plaintext for signature\n",
-							ustr);
-	    }
-	    else if( sig->sig_class != 0x10 )
-		printstr(lvl1,"sig?: %s: unknown signature class %02x\n",
-					ustr, sig->sig_class);
-	    else if( !pkt->pkc_parent || !pkt->user_parent )
-		printstr(lvl1,"sig?: %s: orphaned encoded packet\n", ustr);
-	    else
-		result = 0;
-
-	    if( result )
-		;
-	    else if( !opt.check_sigs && sig->sig_class != 0x00 ) {
-		result = -1;
-		printstr(lvl0, "sig: from %s\n", ustr );
-	    }
-	    else if(sig->pubkey_algo == PUBKEY_ALGO_ELGAMAL ) {
-		md_handle.algo = sig->d.elg.digest_algo;
-		if( sig->d.elg.digest_algo == DIGEST_ALGO_RMD160 ) {
-		    if( sig->sig_class == 0x00 )
-			md_handle.u.rmd = rmd160_copy( mfx.rmd160 );
-		    else {
-			md_handle.u.rmd = rmd160_copy(pkt->pkc_parent->mfx.rmd160);
-			rmd160_write(md_handle.u.rmd, pkt->user_parent->name,
-						      pkt->user_parent->len);
-		    }
-		    result = signature_check( sig, md_handle );
-		    rmd160_close(md_handle.u.rmd);
-		}
-		else if( sig->d.elg.digest_algo == DIGEST_ALGO_MD5
-			 && sig->sig_class != 0x00 ) {
-		    md_handle.u.md5 = md5_copy(pkt->pkc_parent->mfx.md5);
-		    md5_write(md_handle.u.md5, pkt->user_parent->name,
-					       pkt->user_parent->len);
-		    result = signature_check( sig, md_handle );
-		    md5_close(md_handle.u.md5);
-		}
-		else
-		    result = G10ERR_DIGEST_ALGO;
-	    }
-	    else if(sig->pubkey_algo == PUBKEY_ALGO_RSA ) {
-		md_handle.algo = sig->d.rsa.digest_algo;
-		if( sig->d.rsa.digest_algo == DIGEST_ALGO_RMD160 ) {
-		    if( sig->sig_class == 0x00 )
-			md_handle.u.rmd = rmd160_copy( mfx.rmd160 );
-		    else {
-			md_handle.u.rmd = rmd160_copy(pkt->pkc_parent->mfx.rmd160);
-			rmd160_write(md_handle.u.rmd, pkt->user_parent->name,
-						      pkt->user_parent->len);
-		    }
-		    result = signature_check( sig, md_handle );
-		    rmd160_close(md_handle.u.rmd);
-		}
-		else if( sig->d.rsa.digest_algo == DIGEST_ALGO_MD5
-			 && sig->sig_class != 0x00 ) {
-		    md_handle.u.md5 = md5_copy(pkt->pkc_parent->mfx.md5);
-		    md5_write(md_handle.u.md5, pkt->user_parent->name,
-					       pkt->user_parent->len);
-		    result = signature_check( sig, md_handle );
-		    md5_close(md_handle.u.md5);
-		}
-		else
-		    result = G10ERR_DIGEST_ALGO;
-	    }
-	    else
-		result = G10ERR_PUBKEY_ALGO;
-
-	    if( result == -1 )
-		;
-	    else if( !result && sig->sig_class == 0x00 )
-		printstr(1,    "sig: good signature from %s\n", ustr );
-	    else if( !result )
-		printstr(lvl0, "sig: good signature from %s\n", ustr );
-	    else
-		printstr(lvl1, "sig? %s: %s\n", ustr, g10_errstr(result));
-	    free_packet(pkt);
-	    m_free(ustr);
-	    break;
-
-	  case PKT_PUBKEY_ENC:
-	    PKT_pubkey_enc *enc;
-
-	    last_was_pubkey_enc = 1;
-	    result = 0;
-	    enc = pkt->pkt.pubkey_enc;
-	    printf("enc: encrypted by a pubkey with keyid %08lX\n",
-							enc->keyid[1] );
-	    if( enc->pubkey_algo == PUBKEY_ALGO_ELGAMAL
-		|| enc->pubkey_algo == PUBKEY_ALGO_RSA	) {
-		m_free(dek ); /* paranoid: delete a pending DEK */
-		dek = m_alloc_secure( sizeof *dek );
-		if( (result = get_session_key( enc, dek )) ) {
-		    /* error: delete the DEK */
-		    m_free(dek); dek = NULL;
-		}
-	    }
-	    else
-		result = G10ERR_PUBKEY_ALGO;
-
-	    if( result == -1 )
-		;
-	    else if( !result )
-		fputs(	"     DEK is good", stdout );
-	    else
-		printf( "     %s", g10_errstr(result));
-	    putchar('\n');
-	    free_packet(pkt);
-	    break;
-
-	  case PKT_ENCR_DATA:
-	    result = 0;
-	    printf("dat: %sencrypted data\n", dek?"":"conventional ");
-	    if( !dek && !last_was_pubkey_enc ) {
-		/* assume this is conventional encrypted data */
-		dek = m_alloc_secure( sizeof *dek );
-		dek->algo = DEFAULT_CIPHER_ALGO;
-		result = make_dek_from_passphrase( dek, 0 );
-	    }
-	    else if( !dek )
-		result = G10ERR_NO_SECKEY;
-	    if( !result )
-		result = decrypt_data( pkt->pkt.encr_data, dek );
-	    m_free(dek); dek = NULL;
-	    if( result == -1 )
-		;
-	    else if( !result )
-		fputs(	"     encryption okay",stdout);
-	    else
-		printf( "     %s", g10_errstr(result));
-	    putchar('\n');
-	    free_packet(pkt);
-	    last_was_pubkey_enc = 0;
-	    break;
-
-	  case PKT_PLAINTEXT:
-	    PKT_plaintext *pt = pkt->pkt.plaintext;
-	    printf("txt: plain text data name='%.*s'\n", pt->namelen, pt->name);
-	    free_md_filter_context( &mfx );
-	    mfx.rmd160 = rmd160_open(0);
-	    result = handle_plaintext( pt, &mfx );
-	    if( !result )
-		fputs(	"     okay",stdout);
-	    else
-		printf( "     %s", g10_errstr(result));
-	    putchar('\n');
-	    free_packet(pkt);
-	    last_was_pubkey_enc = 0;
-	    break;
-
-	  case PKT_COMPR_DATA:
-	    PKT_compressed *zd = pkt->pkt.compressed;
-	    printf("zip: compressed data packet\n");
-	    result = handle_compressed( zd );
-	    if( !result )
-		fputs(	"     okay",stdout);
-	    else
-		printf( "     %s", g10_errstr(result));
-	    putchar('\n');
-	    free_packet(pkt);
-	    last_was_pubkey_enc = 0;
-	    break;
-
-	  default:
-	    free_packet(pkt);
+	  case PKT_USER_ID:	proc_user_id( c, pkt ); break;
+	  case PKT_SIGNATURE:	proc_signature( c, pkt ); break;
+	  case PKT_PUBKEY_ENC:	proc_pubkey_enc( c, pkt ); break;
+	  case PKT_ENCR_DATA:	proc_encr_data( c, pkt ); break;
+	  case PKT_PLAINTEXT:	proc_plaintext( c, pkt ); break;
+	  case PKT_COMPR_DATA:	proc_compr_data( c, pkt ); break;
+	  default: free_packet(pkt);
 	}
     }
 
-    if( last_user_id )
-	free_user_id( last_user_id );
-    if( last_seckey )
-	free_seckey_cert( last_seckey );
-    if( last_pubkey )
-	free_pubkey_cert( last_pubkey );
-    m_free(dek);
+    do_free_last_user_id( c );
+    do_free_last_seckey( c );
+    do_free_last_pubkey( c );
+    m_free(c->dek);
     free_packet( pkt );
     m_free( pkt );
-    free_md_filter_context( &mfx );
+    free_md_filter_context( &c->mfx );
+    m_free( c );
     return 0;
 }
 
diff --git a/include/mpi.h b/include/mpi.h
index 9c5da6337..cf3623273 100644
--- a/include/mpi.h
+++ b/include/mpi.h
@@ -129,6 +129,7 @@ void  mpi_fdiv_q( MPI quot, MPI dividend, MPI divisor );
 void  mpi_fdiv_qr( MPI quot, MPI rem, MPI dividend, MPI divisor );
 void  mpi_tdiv_r( MPI rem, MPI num, MPI den);
 void  mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den);
+void  mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count );
 int   mpi_divisible_ui(MPI dividend, ulong divisor );
 
 /*-- mpi-gcd.c --*/
@@ -145,6 +146,7 @@ int mpi_cmp( MPI u, MPI v );
 /*-- mpi-scan.c --*/
 int mpi_getbyte( MPI a, unsigned index );
 void mpi_putbyte( MPI a, unsigned index, int value );
+unsigned mpi_trailing_zeros( MPI a );
 
 /*-- mpi-bit.c --*/
 unsigned mpi_get_nbits( MPI a );
diff --git a/mpi/mpi-div.c b/mpi/mpi-div.c
index 2b39cb4cf..527375748 100644
--- a/mpi/mpi-div.c
+++ b/mpi/mpi-div.c
@@ -278,6 +278,37 @@ mpi_tdiv_qr( MPI quot, MPI rem, MPI num, MPI den)
 	mpi_free_limb_space(marker[--markidx]);
 }
 
+void
+mpi_tdiv_q_2exp( MPI w, MPI u, unsigned count )
+{
+    mpi_size_t usize, wsize;
+    mpi_size_t limb_cnt;
+
+    usize = u->nlimbs;
+    limb_cnt = count / BITS_PER_MPI_LIMB;
+    wsize = usize - limb_cnt;
+    if( limb_cnt >= usize )
+	w->nlimbs = 0;
+    else {
+	mpi_ptr_t wp;
+	mpi_ptr_t up;
+
+	RESIZE_IF_NEEDED( w, wsize );
+	wp = w->d;
+	up = u->d;
+
+	count %= BITS_PER_MPI_LIMB;
+	if( count ) {
+	    mpihelp_rshift( wp, up + limb_cnt, wsize, count );
+	    wsize -= !wp[wsize - 1];
+	}
+	else {
+	    MPN_COPY_INCR( wp, up + limb_cnt, wsize);
+	}
+
+	w->nlimbs = wsize;
+    }
+}
 
 /****************
  * Check wether dividend is divisible by divisor
diff --git a/mpi/mpi-internal.h b/mpi/mpi-internal.h
index 2748ddad9..93ed688ae 100644
--- a/mpi/mpi-internal.h
+++ b/mpi/mpi-internal.h
@@ -54,6 +54,13 @@ typedef int mpi_size_t;        /* (must be a signed type) */
 	    (d)[_i] = (s)[_i];		\
     } while(0)
 
+#define MPN_COPY_INCR( d, s, n) 	\
+    do {				\
+	mpi_size_t _i;			\
+	for( _i = 0; _i < (n); _i++ )	\
+	    (d)[_i] = (d)[_i];		\
+    } while (0)
+
 #define MPN_COPY_DECR( d, s, n ) \
     do {				\
 	mpi_size_t _i;			\
diff --git a/mpi/mpi-scan.c b/mpi/mpi-scan.c
index 8626032a0..b9745e1af 100644
--- a/mpi/mpi-scan.c
+++ b/mpi/mpi-scan.c
@@ -22,6 +22,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include "mpi-internal.h"
+#include "longlong.h"
 
 /****************
  * Scan through an mpi and return byte for byte. a -1 is returned to indicate
@@ -86,3 +87,28 @@ mpi_putbyte( MPI a, unsigned index, int c )
     abort(); /* index out of range */
 }
 
+
+/****************
+ * Count the number of zerobits at the low end of A
+ */
+unsigned
+mpi_trailing_zeros( MPI a )
+{
+    unsigned n, count = 0;
+
+    for(n=0; n < a->nlimbs; n++ ) {
+	if( a->d[n] ) {
+	    unsigned nn;
+	    mpi_limb_t alimb = a->d[n];
+
+	    count_trailing_zeros( nn, alimb );
+	    count += nn;
+	    break;
+	}
+	count += BITS_PER_MPI_LIMB;
+    }
+    return count;
+
+}
+
+
diff --git a/util/memory.c b/util/memory.c
index 683f042d6..54095df17 100644
--- a/util/memory.c
+++ b/util/memory.c
@@ -264,15 +264,15 @@ dump_entry(struct memtbl_entry *e )
 }
 
 static void
-dump_table(void)
+dump_table( void)
 {
     unsigned n;
     struct memtbl_entry *e;
     ulong sum = 0, chunks =0;
 
     for( e = memtbl, n = 0; n < memtbl_len; n++, e++ ) {
-	dump_entry(e);
 	if(e->inuse) {
+	    dump_entry(e);
 	    sum += e->user_n;
 	    chunks++;
 	}