Improved prime number test
authorWerner Koch <wk@gnupg.org>
Thu, 27 Nov 1997 11:44:13 +0000 (11:44 +0000)
committerWerner Koch <wk@gnupg.org>
Thu, 27 Nov 1997 11:44:13 +0000 (11:44 +0000)
TODO
cipher/primegen.c
configure.in
g10/g10.c
g10/mainproc.c
include/mpi.h
mpi/mpi-div.c
mpi/mpi-internal.h
mpi/mpi-scan.c
util/memory.c

diff --git a/TODO b/TODO
index 3698c18..7021c4e 100644 (file)
--- 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
     * 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
index 0173b3d..d69f09a 100644 (file)
@@ -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;
 }
 
index 2f77c06..4575bc8 100644 (file)
@@ -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
index 882f84c..f3be295 100644 (file)
--- 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);
index c056ac0..9e34fbd 100644 (file)
 #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;
 }
 
index 9c5da63..cf36232 100644 (file)
@@ -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 );
index 2b39cb4..5273757 100644 (file)
@@ -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
index 2748dda..93ed688 100644 (file)
@@ -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;                  \
index 8626032..b9745e1 100644 (file)
@@ -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;
+
+}
+
+
index 683f042..54095df 100644 (file)
@@ -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++;
        }