add DSA key generation
authorWerner Koch <wk@gnupg.org>
Tue, 5 May 1998 20:34:17 +0000 (20:34 +0000)
committerWerner Koch <wk@gnupg.org>
Tue, 5 May 1998 20:34:17 +0000 (20:34 +0000)
THANKS
cipher/ChangeLog
cipher/dsa.c
cipher/dsa.h
cipher/elgamal.c
cipher/primegen.c
cipher/tiger.c

diff --git a/THANKS b/THANKS
index 7bff6b5..5078c65 100644 (file)
--- a/THANKS
+++ b/THANKS
@@ -24,6 +24,8 @@ Ulf M
 Walter Koch            walterk@ddorf.rhein-ruhr.de
 Werner Koch            werner.koch@guug.de
 Wim Vandeputte         bunbun@reptile.rug.ac.be
+                       tzeruch@ceddec.com
+
 
 Thanks to the German Unix User Group for providing FTP space and
 Martin Hamilton for hosting the mailing list.
index a44abae..ae96007 100644 (file)
@@ -1,3 +1,13 @@
+Tue May  5 21:28:55 1998  Werner Koch  (wk@isil.d.shuttle.de)
+
+       * elgamal.c (elg_generate): choosing x was not correct, could
+       yield 6 bytes which are not from the random pool, tsss, tsss..
+
+Tue May  5 14:09:06 1998  Werner Koch  (wk@isil.d.shuttle.de)
+
+       * primegen.c (generate_elg_prime): Add arg mode, changed all
+       callers and implemented mode 1.
+
 Mon Apr 27 14:41:58 1998  Werner Koch  (wk@isil.d.shuttle.de)
 
        * cipher.c (cipher_get_keylen): New.
index f32fee6..d1c15c4 100644 (file)
@@ -22,6 +22,7 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
+#include <assert.h>
 #include "util.h"
 #include "mpi.h"
 #include "cipher.h"
@@ -74,6 +75,123 @@ dsa_free_secret_key( DSA_secret_key *sk )
 }
 
 
+static void
+test_keys( DSA_public_key *pk, DSA_secret_key *sk, unsigned qbits )
+{
+    MPI test = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
+    MPI out1_a = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
+    MPI out1_b = mpi_alloc( qbits / BITS_PER_MPI_LIMB );
+
+    mpi_set_bytes( test, qbits, get_random_byte, 0 );
+
+    dsa_sign( out1_a, out1_b, test, sk );
+    if( !dsa_verify( out1_a, out1_b, test, pk ) )
+       log_fatal("DSA:: sign, verify failed\n");
+
+    mpi_free( test );
+    mpi_free( out1_a );
+    mpi_free( out1_b );
+}
+
+
+
+/****************
+ * Generate a DSA key pair with a key of size NBITS
+ * Returns: 2 structures filled with all needed values
+ *         and an array with the n-1 factors of (p-1)
+ */
+void
+dsa_generate( DSA_public_key *pk, DSA_secret_key *sk,
+             unsigned nbits, MPI **ret_factors )
+{
+    MPI p;    /* the prime */
+    MPI q;    /* the 160 bit prime factor */
+    MPI g;    /* the generator */
+    MPI y;    /* g^x mod p */
+    MPI x;    /* the secret exponent */
+    MPI h, e;  /* helper */
+    unsigned qbits;
+    byte *rndbuf;
+
+    assert( nbits >= 512 && nbits <= 1024 );
+
+    qbits = 160;
+    p = generate_elg_prime( 1, nbits, qbits, NULL, ret_factors );
+    /* get q out of factors */
+    q = mpi_copy((*ret_factors)[0]);
+    if( mpi_get_nbits(q) != qbits )
+       BUG();
+
+    /* find a generator g (h and e are helpers)*/
+    /* e = (p-1)/q */
+    e = mpi_alloc( mpi_get_nlimbs(p) );
+    mpi_sub_ui( e, p, 1 );
+    mpi_fdiv_q( e, e, q );
+    g = mpi_alloc( mpi_get_nlimbs(p) );
+    h = mpi_alloc_set_ui( 1 ); /* we start with 2 */
+    do {
+       mpi_add_ui( h, h, 1 );
+       /* g = h^e mod p */
+       mpi_powm( g, h, e, p );
+    } while( !mpi_cmp_ui( g, 1 ) );  /* continue until g != 1 */
+
+    /* select a random number which has these properties:
+     *  0 < x < q-1
+     * This must be a very good random number because this
+     * is the secret part. */
+    if( DBG_CIPHER )
+       log_debug("choosing a random x ");
+    assert( qbits >= 16 );
+    x = mpi_alloc_secure( mpi_get_nlimbs(q) );
+    mpi_sub_ui( h, q, 1 );  /* put q-1 into h */
+    rndbuf = NULL;
+    do {
+       if( DBG_CIPHER )
+           fputc('.', stderr);
+       if( !rndbuf )
+           rndbuf = get_random_bits( qbits, 2, 1 );
+       else { /* change only some of the higher bits (= 2 bytes)*/
+           char *r = get_random_bits( 16, 2, 1 );
+           memcpy(rndbuf, r, 16/8 );
+           m_free(r);
+       }
+       mpi_set_buffer( x, rndbuf, (qbits+7)/8, 0 );
+       mpi_clear_highbit( x, qbits+1 );
+    } while( !( mpi_cmp_ui( x, 0 )>0 && mpi_cmp( x, h )<0 ) );
+    m_free(rndbuf);
+    mpi_free( e );
+    mpi_free( h );
+
+    /* y = g^x mod p */
+    y = mpi_alloc( mpi_get_nlimbs(p) );
+    mpi_powm( y, g, x, p );
+
+    if( DBG_CIPHER ) {
+       fputc('\n', stderr);
+       log_mpidump("dsa  p= ", p );
+       log_mpidump("dsa  q= ", q );
+       log_mpidump("dsa  g= ", g );
+       log_mpidump("dsa  y= ", y );
+       log_mpidump("dsa  x= ", x );
+    }
+
+    /* copy the stuff to the key structures */
+    pk->p = mpi_copy(p);
+    pk->q = mpi_copy(q);
+    pk->g = mpi_copy(g);
+    pk->y = mpi_copy(y);
+    sk->p = p;
+    sk->q = q;
+    sk->g = g;
+    sk->y = y;
+    sk->x = x;
+
+    /* now we can test our keys (this should never fail!) */
+    test_keys( pk, sk, qbits );
+}
+
+
+
 /****************
  * Test whether the secret key is valid.
  * Returns: if this is a valid key.
index 07a41ae..2d38a73 100644 (file)
@@ -41,8 +41,9 @@ typedef struct {
 
 void dsa_free_public_key( DSA_public_key *pk );
 void dsa_free_secret_key( DSA_secret_key *sk );
-void dsa_generate( DSA_public_key *pk, DSA_secret_key *sk, unsigned nbits );
 int  dsa_check_secret_key( DSA_secret_key *sk );
+void dsa_generate( DSA_public_key *pk, DSA_secret_key *sk,
+                  unsigned nbits, MPI **ret_factors );
 void dsa_sign(MPI r, MPI s, MPI input, DSA_secret_key *skey);
 int  dsa_verify(MPI r, MPI s, MPI input, DSA_public_key *pkey);
 
index ac02bde..7fad35c 100644 (file)
@@ -139,7 +139,7 @@ elg_generate( ELG_public_key *pk, ELG_secret_key *sk,
     else
        qbits = 240;
     g = mpi_alloc(1);
-    p = generate_elg_prime( nbits, qbits, g, ret_factors );
+    p = generate_elg_prime( 0, nbits, qbits, g, ret_factors );
     mpi_sub_ui(p_min1, p, 1);
 
 
@@ -163,7 +163,7 @@ elg_generate( ELG_public_key *pk, ELG_secret_key *sk,
            }
            else {
                char *r = get_random_bits( 16, 2, 1 );
-               memcpy(rndbuf, r, 16 );
+               memcpy(rndbuf, r, 16/8 );
                m_free(r);
            }
        }
index 6ebaffe..26d21ac 100644 (file)
@@ -63,37 +63,49 @@ generate_public_prime( unsigned  nbits )
  * security from it - The prime number is public and we could also
  * offer the factors for those who are willing to check that it is
  * indeed a strong prime.
+ *
+ * mode 0: Standard
+ *     1: Make sure that at least one factor is of size qbits.
  */
 MPI
-generate_elg_prime( unsigned pbits, unsigned qbits, MPI g, MPI **ret_factors )
+generate_elg_prime( int mode, unsigned pbits, unsigned qbits,
+                   MPI g, MPI **ret_factors )
 {
     int n;  /* number of factors */
     int m;  /* number of primes in pool */
     unsigned fbits; /* length of prime factors */
     MPI *factors; /* current factors */
     MPI *pool; /* pool of primes */
-    MPI q;     /* first prime factor */
+    MPI q;     /* first prime factor (variable)*/
     MPI prime; /* prime test value */
+    MPI q_factor; /* used for mode 1 */
     byte *perms = NULL;
     int i, j;
     int count1, count2;
     unsigned nprime;
+    unsigned req_qbits = qbits; /* the requested q bits size */
 
     /* find number of needed prime factors */
     for(n=1; (pbits - qbits - 1) / n  >= qbits; n++ )
        ;
     n--;
-    if( !n )
+    if( !n || (mode==1 && n < 2) )
        log_fatal("can't gen prime with pbits=%u qbits=%u\n", pbits, qbits );
-    fbits = (pbits - qbits -1) / n;
-    while( qbits + n*fbits < pbits )
-       qbits++;
+    if( mode == 1 ) {
+       n--;
+       fbits = (pbits - 2*req_qbits -1) / n;
+       qbits =  pbits - req_qbits - n*fbits;
+    }
+    else {
+       fbits = (pbits - req_qbits -1) / n;
+       qbits = pbits - n*fbits;
+    }
     if( DBG_CIPHER )
-       log_debug("gen prime: pbits=%u qbits=%u fbits=%u n=%d\n",
-                   pbits, qbits, fbits, n  );
-
+       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;
 
     /* allocate an array to hold the factors + 2 for later usage */
     factors = m_alloc_clear( (n+2) * sizeof *factors );
@@ -139,6 +151,8 @@ generate_elg_prime( unsigned pbits, unsigned qbits, MPI g, MPI **ret_factors )
 
        mpi_set( prime, q );
        mpi_mul_ui( prime, prime, 2 );
+       if( mode == 1 )
+           mpi_mul( prime, prime, q_factor );
        for(i=0; i < n; i++ )
            mpi_mul( prime, prime, factors[i] );
        mpi_add_ui( prime, prime, 1 );
@@ -171,18 +185,30 @@ generate_elg_prime( unsigned pbits, unsigned qbits, MPI g, MPI **ret_factors )
        putc('\n', stderr);
        log_mpidump( "prime    : ", prime );
        log_mpidump( "factor  q: ", q );
+       if( mode == 1 )
+           log_mpidump( "factor q0: ", q_factor );
        for(i=0; i < n; i++ )
            log_mpidump( "factor pi: ", factors[i] );
        log_debug("bit sizes: prime=%u, q=%u", mpi_get_nbits(prime), mpi_get_nbits(q) );
+       if( mode == 1 )
+           fprintf(stderr, ", q0=%u", mpi_get_nbits(q_factor) );
        for(i=0; i < n; i++ )
            fprintf(stderr, ", p%d=%u", i, mpi_get_nbits(factors[i]) );
        putc('\n', stderr);
     }
 
     if( ret_factors ) { /* caller wants the factors */
-       *ret_factors = m_alloc_clear( (n+1) * sizeof **ret_factors );
-       for(i=0; i < n; i++ )
-           (*ret_factors)[i] = mpi_copy( factors[i] );
+       *ret_factors = m_alloc_clear( (n+2) * sizeof **ret_factors);
+       if( mode == 1 ) {
+           i = 0;
+           (*ret_factors)[i++] = mpi_copy( q_factor );
+           for(; i <= n; i++ )
+               (*ret_factors)[i] = mpi_copy( factors[i] );
+       }
+       else {
+           for(; i < n; i++ )
+               (*ret_factors)[i] = mpi_copy( factors[i] );
+       }
     }
 
     if( g ) { /* create a generator (start with 3)*/
@@ -190,6 +216,8 @@ generate_elg_prime( unsigned pbits, unsigned qbits, MPI g, MPI **ret_factors )
        MPI b     = mpi_alloc( mpi_get_nlimbs(prime) );
        MPI pmin1 = mpi_alloc( mpi_get_nlimbs(prime) );
 
+       if( mode == 1 )
+           BUG(); /* not yet implemented */
        factors[n] = q;
        factors[n+1] = mpi_alloc_set_ui(2);
        mpi_sub_ui( pmin1, prime, 1 );
@@ -230,6 +258,7 @@ generate_elg_prime( unsigned pbits, unsigned qbits, MPI g, MPI **ret_factors )
 }
 
 
+
 static MPI
 gen_prime( unsigned  nbits, int secret, int randomlevel )
 {
index 3ceeb9f..6977025 100644 (file)
@@ -702,10 +702,11 @@ transform( TIGER_CONTEXT *hd, byte *data )
     u64 a,b,c,aa,bb,cc;
     u64 x[8];
   #ifdef BIG_ENDIAN_HOST
-    #define MKWORD(d,n) (  (d)[8*(n)+0] << 56 | (d)[8*(n)+1] << 48  \
-                        | (d)[8*(n)+2] << 40 | (d)[8*(n)+3] << 32  \
-                        | (d)[8*(n)+4] << 24 | (d)[8*(n)+5] << 16  \
-                        | (d)[8*(n)+6] << 8  | (d)[8*(n)+7]       )
+    #define MKWORD(d,n) \
+               (  ((u64)(d)[8*(n)+0]) << 56 | ((u64)(d)[8*(n)+1]) << 48  \
+                | ((u64)(d)[8*(n)+2]) << 40 | ((u64)(d)[8*(n)+3]) << 32  \
+                | ((u64)(d)[8*(n)+4]) << 24 | ((u64)(d)[8*(n)+5]) << 16  \
+                | ((u64)(d)[8*(n)+6]) << 8  | ((u64)(d)[8*(n)+7])       )
     x[0] = MKWORD(data, 0);
     x[1] = MKWORD(data, 1);
     x[2] = MKWORD(data, 2);