add DSA key generation

6 files changed, 178 insertions, 19 deletions

diff --git a/cipher/ChangeLog b/cipher/ChangeLog
index a44abae94..ae96007a1 100644
--- a/cipher/ChangeLog
+++ b/cipher/ChangeLog
@@ -1,3 +1,13 @@
+Tue May  5 21:28:55 1998  Werner Koch  ([email protected])
+
+	* 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  ([email protected])
+
+	* primegen.c (generate_elg_prime): Add arg mode, changed all
+	callers and implemented mode 1.
+
 Mon Apr 27 14:41:58 1998  Werner Koch  ([email protected])
 
 	* cipher.c (cipher_get_keylen): New.
diff --git a/cipher/dsa.c b/cipher/dsa.c
index f32fee649..d1c15c41c 100644
--- a/cipher/dsa.c
+++ b/cipher/dsa.c
@@ -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.
diff --git a/cipher/dsa.h b/cipher/dsa.h
index 07a41ae6c..2d38a7388 100644
--- a/cipher/dsa.h
+++ b/cipher/dsa.h
@@ -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);
 
diff --git a/cipher/elgamal.c b/cipher/elgamal.c
index ac02bde52..7fad35c56 100644
--- a/cipher/elgamal.c
+++ b/cipher/elgamal.c
@@ -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);
 	    }
 	}
diff --git a/cipher/primegen.c b/cipher/primegen.c
index 6ebaffe6a..26d21acb9 100644
--- a/cipher/primegen.c
+++ b/cipher/primegen.c
@@ -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 )
 {
diff --git a/cipher/tiger.c b/cipher/tiger.c
index 3ceeb9fdd..69770258c 100644
--- a/cipher/tiger.c
+++ b/cipher/tiger.c
@@ -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);