* options.h, g10.c (main), keylist.c (list_keyblock_print): Add
[gnupg.git] / cipher / primegen.c
index 2f16b08..1f30957 100644 (file)
@@ -1,5 +1,5 @@
 /* primegen.c - prime number generator
- *     Copyright (C) 1998 Free Software Foundation, Inc.
+ *     Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
  *
  * This file is part of GnuPG.
  *
@@ -28,7 +28,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <assert.h>
-#include "g10lib.h"
+#include "util.h"
 #include "mpi.h"
 #include "cipher.h"
 
@@ -38,11 +38,24 @@ static int check_prime( MPI prime, MPI val_2 );
 static int is_prime( MPI n, int steps, int *count );
 static void m_out_of_n( char *array, int m, int n );
 
+static void (*progress_cb) ( void *, int );
+static void *progress_cb_data;
+
+void
+register_primegen_progress ( void (*cb)( void *, int), void *cb_data )
+{
+    progress_cb = cb;
+    progress_cb_data = cb_data;
+}
+
 
 static void
 progress( int c )
 {
-    fputc( c, stderr );
+    if ( progress_cb )
+       progress_cb ( progress_cb_data, c );
+    else
+       fputc( c, stderr );
 }
 
 
@@ -117,11 +130,11 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
        log_debug("gen prime: pbits=%u qbits=%u fbits=%u/%u n=%d\n",
                    pbits, req_qbits, qbits, fbits, n  );
     prime = mpi_alloc( (pbits + BITS_PER_MPI_LIMB - 1) /  BITS_PER_MPI_LIMB );
-    q = gen_prime( qbits, 0, 1 );
-    q_factor = mode==1? gen_prime( req_qbits, 0, 1 ) : NULL;
+    q = gen_prime( qbits, 0, 0 );
+    q_factor = mode==1? gen_prime( req_qbits, 0, 0 ) : NULL;
 
     /* allocate an array to hold the factors + 2 for later usage */
-    factors = g10_xcalloc( n+2, sizeof *factors );
+    factors = m_alloc_clear( (n+2) * sizeof *factors );
 
     /* make a pool of 3n+5 primes (this is an arbitrary value) */
     m = n*3+5;
@@ -129,7 +142,7 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
        m += 5; /* need some more for DSA */
     if( m < 25 )
        m = 25;
-    pool = g10_xcalloc( m , sizeof *pool );
+    pool = m_alloc_clear( m * sizeof *pool );
 
     /* permutate over the pool of primes */
     count1=count2=0;
@@ -142,10 +155,10 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
                pool[i] = NULL;
            }
            /* init m_out_of_n() */
-           perms = g10_xcalloc( 1, m );
+           perms = m_alloc_clear( m );
            for(i=0; i < n; i++ ) {
                perms[i] = 1;
-               pool[i] = gen_prime( fbits, 0, 1 );
+               pool[i] = gen_prime( fbits, 0, 0 );
                factors[i] = pool[i];
            }
        }
@@ -154,11 +167,11 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
            for(i=j=0; i < m && j < n ; i++ )
                if( perms[i] ) {
                    if( !pool[i] )
-                       pool[i] = gen_prime( fbits, 0, 1 );
+                       pool[i] = gen_prime( fbits, 0, 0 );
                    factors[j++] = pool[i];
                }
            if( i == n ) {
-               g10_free(perms); perms = NULL;
+               m_free(perms); perms = NULL;
                progress('!');
                goto next_try;  /* allocate new primes */
            }
@@ -177,7 +190,8 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
                count1 = 0;
                qbits++;
                progress('>');
-               q = gen_prime( qbits, 0, 1 );
+                mpi_free (q);
+               q = gen_prime( qbits, 0, 0 );
                goto next_try;
            }
        }
@@ -188,7 +202,8 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
                count2 = 0;
                qbits--;
                progress('<');
-               q = gen_prime( qbits, 0, 1 );
+                mpi_free (q);
+               q = gen_prime( qbits, 0, 0 );
                goto next_try;
            }
        }
@@ -213,15 +228,15 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
     }
 
     if( ret_factors ) { /* caller wants the factors */
-       *ret_factors = g10_xcalloc( n+2 , sizeof **ret_factors);
+       *ret_factors = m_alloc_clear( (n+2) * sizeof **ret_factors);
+        i = 0;
        if( mode == 1 ) {
-           i = 0;
            (*ret_factors)[i++] = mpi_copy( q_factor );
            for(; i <= n; i++ )
-               (*ret_factors)[i] = mpi_copy( factors[i] );
+               (*ret_factors)[i] = mpi_copy( factors[i-1] );
        }
        else {
-           for(i=0; i < n; i++ )
+           for(; i < n; i++ )
                (*ret_factors)[i] = mpi_copy( factors[i] );
        }
     }
@@ -241,8 +256,7 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
            mpi_add_ui(g, g, 1);
            if( DBG_CIPHER ) {
                log_debug("checking g: ");
-               /*mpi_print( stderr, g, 1 );*/
-               #warning we need an internal mpi_print for debugging
+               mpi_print( stderr, g, 1 );
            }
            else
                progress('^');
@@ -250,7 +264,7 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
                /*fputc('~', stderr);*/
                mpi_fdiv_q(tmp, pmin1, factors[i] );
                /* (no mpi_pow(), but it is okay to use this with mod prime) */
-               gcry_mpi_powm(b, g, tmp, prime );
+               mpi_powm(b, g, tmp, prime );
                if( !mpi_cmp_ui(b, 1) )
                    break;
            }
@@ -265,12 +279,13 @@ generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
     if( !DBG_CIPHER )
        progress('\n');
 
-    g10_free( factors );  /* (factors are shallow copies) */
+    m_free( factors ); /* (factors are shallow copies) */
     for(i=0; i < m; i++ )
        mpi_free( pool[i] );
-    g10_free( pool );
-    g10_free(perms);
+    m_free( pool );
+    m_free(perms);
     mpi_free(val_2);
+    mpi_free(q);
     return prime;
 }
 
@@ -283,7 +298,7 @@ gen_prime( unsigned  nbits, int secret, int randomlevel )
     MPI prime, ptest, pminus1, val_2, val_3, result;
     int i;
     unsigned x, step;
-    unsigned count1, count2;
+    int count1, count2;
     int *mods;
 
     if( 0 && DBG_CIPHER )
@@ -293,7 +308,7 @@ gen_prime( unsigned  nbits, int secret, int randomlevel )
        for(i=0; small_prime_numbers[i]; i++ )
            no_of_small_prime_numbers++;
     }
-    mods = g10_xmalloc( no_of_small_prime_numbers * sizeof *mods );
+    mods = m_alloc( no_of_small_prime_numbers * sizeof *mods );
     /* make nbits fit into MPI implementation */
     nlimbs = (nbits + BITS_PER_MPI_LIMB - 1) / BITS_PER_MPI_LIMB;
     val_2  = mpi_alloc_set_ui( 2 );
@@ -307,10 +322,18 @@ gen_prime( unsigned  nbits, int secret, int randomlevel )
        int dotcount=0;
 
        /* generate a random number */
-       gcry_mpi_randomize( prime, nbits, randomlevel );
+       {   char *p = get_random_bits( nbits, randomlevel, secret );
+           mpi_set_buffer( prime, p, (nbits+7)/8, 0 );
+           m_free(p);
+       }
 
-       /* set high order bit to 1, set low order bit to 1 */
+       /* Set high order bit to 1, set low order bit to 0.
+           If we are generating a secret prime we are most probably
+           doing that for RSA, to make sure that the modulus does have
+           the requested keysize we set the 2 high order bits */
        mpi_set_highbit( prime, nbits-1 );
+        if (secret)
+          mpi_set_bit (prime, nbits-2);
        mpi_set_bit( prime, 0 );
 
        /* calculate all remainders */
@@ -335,7 +358,7 @@ gen_prime( unsigned  nbits, int secret, int randomlevel )
            /* do a faster Fermat test */
            count2++;
            mpi_sub_ui( pminus1, ptest, 1);
-           gcry_mpi_powm( result, val_2, pminus1, ptest );
+           mpi_powm( result, val_2, pminus1, ptest );
            if( !mpi_cmp_ui( result, 1 ) ) { /* not composite */
                /* perform stronger tests */
                if( is_prime(ptest, 5, &count2 ) ) {
@@ -350,7 +373,7 @@ gen_prime( unsigned  nbits, int secret, int randomlevel )
                    mpi_free(result);
                    mpi_free(pminus1);
                    mpi_free(prime);
-                   g10_free(mods);
+                   m_free(mods);
                    return ptest;
                }
            }
@@ -384,7 +407,7 @@ check_prime( MPI prime, MPI val_2 )
        MPI result = mpi_alloc_like( prime );
        MPI pminus1 = mpi_alloc_like( prime );
        mpi_sub_ui( pminus1, prime, 1);
-       gcry_mpi_powm( result, val_2, pminus1, prime );
+       mpi_powm( result, val_2, pminus1, prime );
        mpi_free( pminus1 );
        if( mpi_cmp_ui( result, 1 ) ) { /* if composite */
            mpi_free( result );
@@ -431,8 +454,11 @@ is_prime( MPI n, int steps, int *count )
            mpi_set_ui( x, 2 );
        }
        else {
-           gcry_mpi_randomize( x, nbits, GCRY_WEAK_RANDOM );
-
+           /*mpi_set_bytes( x, nbits-1, get_random_byte, 0 );*/
+           {   char *p = get_random_bits( nbits, 0, 0 );
+               mpi_set_buffer( x, p, (nbits+7)/8, 0 );
+               m_free(p);
+           }
            /* make sure that the number is smaller than the prime
             * and keep the randomness of the high bit */
            if( mpi_test_bit( x, nbits-2 ) ) {
@@ -444,10 +470,10 @@ is_prime( MPI n, int steps, int *count )
            }
            assert( mpi_cmp( x, nminus1 ) < 0 && mpi_cmp_ui( x, 1 ) > 0 );
        }
-       gcry_mpi_powm( y, x, q, n);
+       mpi_powm( y, x, q, n);
        if( mpi_cmp_ui(y, 1) && mpi_cmp( y, nminus1 ) ) {
            for( j=1; j < k && mpi_cmp( y, nminus1 ); j++ ) {
-               gcry_mpi_powm(y, y, a2, n);
+               mpi_powm(y, y, a2, n);
                if( !mpi_cmp_ui( y, 1 ) )
                    goto leave; /* not a prime */
            }