Finished RSA X9.31 key generation.

6 files changed, 218 insertions, 41 deletions

diff --git a/cipher/ChangeLog b/cipher/ChangeLog
index b93ac023..bfb20ae7 100644
--- a/cipher/ChangeLog
+++ b/cipher/ChangeLog
@@ -1,5 +1,15 @@
 2008-11-24  Werner Koch  <wk@g10code.com>
 
+	* pubkey.c (gcry_pk_genkey): Insert code to output extrainfo.
+	(pubkey_generate): Add arg R_EXTRAINFO and pass it to the extended
+	key generation function.
+	* rsa.c (gen_x931_parm_xp, gen_x931_parm_xi): New.
+	(generate_x931): Generate params if not given.
+	(rsa_generate_ext): Parse use-x931 flag.  Return p-q-swapped
+	indicator.
+	* dsa.c (dsa_generate_ext): Put RETFACTORS into R_EXTRAINFO if
+	possible.
+
 	* pubkey.c (gcry_pk_genkey): Remove parsing of almost all
 	parameters and pass the parameter S-expression to pubkey_generate.
 	(pubkey_generate): Simplify by requitring modules to parse the
diff --git a/cipher/dsa.c b/cipher/dsa.c
index fb5654e8..639c1a9e 100644
--- a/cipher/dsa.c
+++ b/cipher/dsa.c
@@ -461,7 +461,8 @@ verify (gcry_mpi_t r, gcry_mpi_t s, gcry_mpi_t hash, DSA_public_key *pkey )
 static gcry_err_code_t
 dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
                   const gcry_sexp_t genparms,
-                  gcry_mpi_t *skey, gcry_mpi_t **retfactors)
+                  gcry_mpi_t *skey, gcry_mpi_t **retfactors,
+                  gcry_sexp_t *r_extrainfo)
 {
   gpg_err_code_t ec;
   DSA_secret_key sk;
@@ -502,6 +503,77 @@ dsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
       skey[2] = sk.g;
       skey[3] = sk.y;
       skey[4] = sk.x;
+
+      if (!r_extrainfo)
+        {
+          /* Old style interface - return the factors - if any - at
+             retfactors.  */
+        }
+      else if (r_extrainfo && !*retfactors)
+        {
+          /* No factors, thus there is nothing to return.  */
+          *r_extrainfo = NULL;
+        }
+      else
+        {
+          /* Put the factors into extrainfo and set retfactors to NULL
+             to make use of the new interface.  Note that the factors
+             are not confidential thus we can store them in standard
+             memory.  */
+          int nfactors, i;
+          char *p;
+          char *format = NULL;
+          void **arg_list = NULL;
+
+          for (nfactors=0; (*retfactors)[nfactors]; nfactors++)
+            ;
+          /* Allocate space for the format string:
+               "(misc-key-info(pm1-factors%m))"
+             with one "%m" for each factor and build the string  */
+          format = gcry_malloc (40 + 2*nfactors);
+          if (!format)
+            ec = gpg_err_code_from_syserror ();
+          else
+            {
+              p = stpcpy (format, "(misc-key-info(pm1-factors");
+              for (i=0; i < nfactors; i++)
+                p = stpcpy (p, "%m");
+              p = stpcpy (p, "))");
+              
+              /* Allocate space for the argument list plus an extra
+                 NULL entry for safety and fill it with the
+                 factors.  */
+              arg_list = gcry_calloc (nfactors+1, sizeof *arg_list);
+              if (!arg_list)
+                ec = gpg_err_code_from_syserror ();
+              else
+                {
+                  for (i=0; i < nfactors; i++)
+                    arg_list[i] = (*retfactors) + i;
+                  arg_list[i] = NULL;
+                  
+                  ec = gpg_err_code (gcry_sexp_build_array 
+                                     (r_extrainfo, NULL, format, arg_list));
+                }
+            }
+
+          gcry_free (arg_list);
+          gcry_free (format);
+          for (i=0; i < nfactors; i++)
+            {
+              gcry_mpi_release ((*retfactors)[i]);
+              (*retfactors)[i] = NULL;
+            }
+          *retfactors = NULL;
+          if (ec)
+            {
+              for (i=0; i < 5; i++)
+                {
+                  gcry_mpi_release (skey[i]);
+                  skey[i] = NULL;
+                }
+            }
+        }
     }
 
   return ec;
@@ -513,7 +585,7 @@ dsa_generate (int algo, unsigned int nbits, unsigned long evalue,
               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
 {
   (void)evalue;
-  return dsa_generate_ext (algo, nbits, 0, NULL, skey, retfactors);
+  return dsa_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
 }
 
 
diff --git a/cipher/ecc.c b/cipher/ecc.c
index 5df22b01..978c6d12 100644
--- a/cipher/ecc.c
+++ b/cipher/ecc.c
@@ -954,7 +954,8 @@ os2ec (mpi_point_t *result, gcry_mpi_t value)
 static gcry_err_code_t
 ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
                   const gcry_sexp_t genparms,
-                  gcry_mpi_t *skey, gcry_mpi_t **retfactors)
+                  gcry_mpi_t *skey, gcry_mpi_t **retfactors,
+                  gcry_sexp_t *r_extrainfo)
 {
   gpg_err_code_t ec;
   ECC_secret_key sk;
@@ -964,6 +965,7 @@ ecc_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
 
   (void)algo;
   (void)evalue;
+  (void)r_extrainfo;
 
   if (genparms)
     {
@@ -1018,7 +1020,7 @@ ecc_generate (int algo, unsigned int nbits, unsigned long evalue,
               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
 {
   (void)evalue;
-  return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors);
+  return ecc_generate_ext (algo, nbits, 0, NULL, skey, retfactors, NULL);
 }
 
 
diff --git a/cipher/elgamal.c b/cipher/elgamal.c
index a3eaf2ae..0b0c07cb 100644
--- a/cipher/elgamal.c
+++ b/cipher/elgamal.c
@@ -615,7 +615,8 @@ verify(gcry_mpi_t a, gcry_mpi_t b, gcry_mpi_t input, ELG_public_key *pkey )
 static gpg_err_code_t
 elg_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
                   const gcry_sexp_t genparms,
-                  gcry_mpi_t *skey, gcry_mpi_t **retfactors)
+                  gcry_mpi_t *skey, gcry_mpi_t **retfactors,
+                  gcry_sexp_t *r_extrainfo)
 {
   gpg_err_code_t ec;
   ELG_secret_key sk;
@@ -624,6 +625,7 @@ elg_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
 
   (void)algo;
   (void)evalue;
+  (void)r_extrainfo;
 
   if (genparms)
     {
diff --git a/cipher/pubkey.c b/cipher/pubkey.c
index 6bc248c3..08abcbfd 100644
--- a/cipher/pubkey.c
+++ b/cipher/pubkey.c
@@ -542,7 +542,8 @@ pubkey_generate (int algorithm,
                  unsigned int nbits,
                  unsigned long use_e,
                  gcry_sexp_t genparms,
-                 gcry_mpi_t *skey, gcry_mpi_t **retfactors)
+                 gcry_mpi_t *skey, gcry_mpi_t **retfactors,
+                 gcry_sexp_t *r_extrainfo)
 {
   gcry_err_code_t ec = GPG_ERR_PUBKEY_ALGO;
   gcry_module_t pubkey;
@@ -559,7 +560,7 @@ pubkey_generate (int algorithm,
         {
           /* Use the extended generate function.  */
           ec = extraspec->ext_generate 
-            (algorithm, nbits, use_e, genparms, skey, retfactors);
+            (algorithm, nbits, use_e, genparms, skey, retfactors, r_extrainfo);
         }
       else
         {
@@ -2076,7 +2077,9 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
   const char *algo_name = NULL;
   int algo;
   const char *sec_elems = NULL, *pub_elems = NULL;
-  gcry_mpi_t skey[12], *factors = NULL;
+  gcry_mpi_t skey[12];
+  gcry_mpi_t *factors = NULL;
+  gcry_sexp_t extrainfo = NULL;
   unsigned int nbits = 0;
   unsigned long use_e = 0;
 
@@ -2132,7 +2135,7 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
 
   /* Handle the optional rsa-use-e element.  Actually this belong into
      the algorithm module but we have this parameter in the public
-     moudle API, so we need to parse it right here.  */
+     module API, so we need to parse it right here.  */
   l2 = gcry_sexp_find_token (list, "rsa-use-e", 0);
   if (l2)
     {
@@ -2177,7 +2180,8 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
     nbits = 0;
 
   /* Pass control to the algorithm module. */
-  rc = pubkey_generate (module->mod_id, nbits, use_e, list, skey, &factors);
+  rc = pubkey_generate (module->mod_id, nbits, use_e, list, skey, 
+                        &factors, &extrainfo);
   gcry_sexp_release (list); list = NULL;
   if (rc)
     goto leave;
@@ -2188,13 +2192,18 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
     size_t nelem=0, nelem_cp = 0, needed=0;
     gcry_mpi_t mpis[30];
     
+    /* Estimate size of format string.  */
     nelem = strlen (pub_elems) + strlen (sec_elems);
-    for (i = 0; factors[i]; i++)
-      nelem++;
+    if (factors)
+      {
+        for (i = 0; factors[i]; i++)
+          nelem++;
+      }
     nelem_cp = nelem;
 
     needed += nelem * 10;
-    needed += 2 * strlen (algo_name) + 300;
+    /* (+5 is for EXTRAINFO ("%S")).  */
+    needed += 2 * strlen (algo_name) + 300 + 5;
     if (nelem > DIM (mpis))
       BUG ();
 
@@ -2231,7 +2240,12 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
     /* Hack to make release_mpi_array() work.  */
     skey[i] = NULL;
 
-    if (factors[0])
+    if (extrainfo)
+      {
+        /* If we have extrainfo we should not have any factors.  */
+        p = stpcpy (p, "%S");
+      }
+    else if (factors && factors[0])
       {
         p = stpcpy (p, "(misc-key-info(pm1-factors");
         for(i = 0; factors[i]; i++)
@@ -2251,7 +2265,8 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
       int elem_n = strlen (pub_elems) + strlen (sec_elems);
       void **arg_list;
 
-      arg_list = malloc (nelem_cp * sizeof *arg_list);
+      /* Allocate one extra for EXTRAINFO ("%S").  */
+      arg_list = gcry_calloc (nelem_cp+1, sizeof *arg_list);
       if (!arg_list)
         {
           rc = gpg_err_code_from_errno (errno);
@@ -2259,11 +2274,16 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
         }
       for (i = 0; i < elem_n; i++)
         arg_list[i] = mpis + i;
-      for (; i < nelem_cp; i++)
-        arg_list[i] = factors + i - elem_n;
+      if (extrainfo)
+        arg_list[i] = &extrainfo;
+      else if (factors && factors[0])
+        {
+          for (; i < nelem_cp; i++)
+            arg_list[i] = factors + i - elem_n;
+        }
       
       rc = gcry_sexp_build_array (r_key, NULL, string, arg_list);
-      free (arg_list);
+      gcry_free (arg_list);
       if (rc)
 	BUG ();
       gcry_assert (DIM (mpis) == 30); /* Reminder to make sure that
@@ -2275,6 +2295,7 @@ gcry_pk_genkey (gcry_sexp_t *r_key, gcry_sexp_t s_parms)
 
  leave:
   gcry_free (name);
+  gcry_sexp_release (extrainfo);
   release_mpi_array (skey);
   /* Don't free SKEY itself, it is an stack allocated array. */
 
diff --git a/cipher/rsa.c b/cipher/rsa.c
index 8823af7e..967b6934 100644
--- a/cipher/rsa.c
+++ b/cipher/rsa.c
@@ -328,6 +328,46 @@ generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e,
 }
 
 
+/* Helper for generate_x931.  */
+static gcry_mpi_t 
+gen_x931_parm_xp (unsigned int nbits)
+{
+  gcry_mpi_t xp;
+
+  xp = gcry_mpi_snew (nbits);
+  gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM);
+      
+  /* The requirement for Xp is:
+
+       sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1
+
+     We set the two high order bits to 1 to satisfy the lower bound.
+     By using mpi_set_highbit we make sure that the upper bound is
+     satisfied as well.  */
+  mpi_set_highbit (xp, nbits-1);
+  mpi_set_bit (xp, nbits-2);
+  gcry_assert ( mpi_get_nbits (xp) == nbits );
+  
+  return xp;
+}     
+
+
+/* Helper for generate_x931.  */
+static gcry_mpi_t 
+gen_x931_parm_xi (void)
+{
+  gcry_mpi_t xi;
+
+  xi = gcry_mpi_snew (101);
+  gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM);
+  mpi_set_highbit (xi, 100);
+  gcry_assert ( mpi_get_nbits (xi) == 101 );
+  
+  return xi;
+}     
+
+
+
 /* Variant of the standard key generation code using the algorithm
    from X9.31.  Using this algorithm has the advantage that the
    generation can be made deterministic which is required for CAVS
@@ -378,14 +418,32 @@ generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
     gcry_mpi_t xq1 = NULL;
     gcry_mpi_t xq2 = NULL;
     gcry_mpi_t xq  = NULL;
+    gcry_mpi_t tmpval;
 
     if (!deriveparms)
       {
-        /* Fixme: Create them.  */
-        return GPG_ERR_INV_VALUE;
+        /* Not given: Generate them.  */
+        xp = gen_x931_parm_xp (nbits/2);
+        /* Make sure that |xp - xq| > 2^{nbits - 100} holds.  */
+        tmpval = gcry_mpi_snew (nbits/2);
+        do
+          {
+            gcry_mpi_release (xq);
+            xq = gen_x931_parm_xp (nbits/2);
+            mpi_sub (tmpval, xp, xq);
+          }
+        while (mpi_get_nbits (tmpval) <= (nbits/2 - 100));
+        gcry_mpi_release (tmpval);
+
+        xp1 = gen_x931_parm_xi ();
+        xp2 = gen_x931_parm_xi ();
+        xq1 = gen_x931_parm_xi ();
+        xq2 = gen_x931_parm_xi ();
+
       }
     else
       {
+        /* Parameters to derive the key are given.  */
         struct { const char *name; gcry_mpi_t *value; } tbl[] = {
           { "Xp1", &xp1 },
           { "Xp2", &xp2 },
@@ -478,7 +536,7 @@ generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value,
 
   if( DBG_CIPHER )
     {
-      if (swapped)
+      if (*swapped)
         log_debug ("p and q are swapped\n");
       log_mpidump("  p", p );
       log_mpidump("  q", q );
@@ -717,25 +775,52 @@ rsa_unblind (gcry_mpi_t x, gcry_mpi_t ri, gcry_mpi_t n)
 static gcry_err_code_t
 rsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
                   const gcry_sexp_t genparms,
-                  gcry_mpi_t *skey, gcry_mpi_t **retfactors)
+                  gcry_mpi_t *skey, gcry_mpi_t **retfactors,
+                  gcry_sexp_t *r_extrainfo)
 {
   RSA_secret_key sk;
   gpg_err_code_t ec;
   gcry_sexp_t deriveparms;
   int transient_key = 0;
+  int use_x931 = 0;
   gcry_sexp_t l1;
-  int swapped;
-  int i;
 
   (void)algo;
+  
+  *retfactors = NULL; /* We don't return them.  */
 
   deriveparms = (genparms?
                  gcry_sexp_find_token (genparms, "derive-parms", 0) : NULL);
+  if (!deriveparms)
+    {
+      /* Parse the optional "rsa-use-x931" flag. */
+      l1 = gcry_sexp_find_token (genparms, "use-x931", 0);
+      if (l1)
+        {
+          use_x931 = 1;
+          gcry_sexp_release (l1);
+        }
+    }
 
-  if (deriveparms || fips_mode ())
+  if (deriveparms || use_x931 || fips_mode ())
     {
+      int swapped;
       ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped);
       gcry_sexp_release (deriveparms);
+      if (!ec && r_extrainfo && swapped)
+        {
+          ec = gcry_sexp_new (r_extrainfo, 
+                              "(misc-key-info(p-q-swapped))", 0, 1);
+          if (ec)
+            {
+              gcry_mpi_release (sk.n); sk.n = NULL;
+              gcry_mpi_release (sk.e); sk.e = NULL;
+              gcry_mpi_release (sk.p); sk.p = NULL;
+              gcry_mpi_release (sk.q); sk.q = NULL;
+              gcry_mpi_release (sk.d); sk.d = NULL;
+              gcry_mpi_release (sk.u); sk.u = NULL;
+            }
+        }
     }
   else
     {
@@ -745,7 +830,6 @@ rsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
         {
           transient_key = 1;
           gcry_sexp_release (l1);
-          l1 = NULL;
         }
       /* Generate.  */
       ec = generate_std (&sk, nbits, evalue, transient_key);
@@ -759,20 +843,6 @@ rsa_generate_ext (int algo, unsigned int nbits, unsigned long evalue,
       skey[3] = sk.p;
       skey[4] = sk.q;
       skey[5] = sk.u;
-  
-      /* Make an empty list of factors.  */
-      *retfactors = gcry_calloc ( 1, sizeof **retfactors );
-      if (!*retfactors)
-        {
-          ec = gpg_err_code_from_syserror ();
-          for (i=0; i <= 5; i++)
-            {
-              gcry_mpi_release (skey[i]);
-              skey[i] = NULL;
-            }
-        }
-      else
-        ec = 0;
     }
   
   return ec;
@@ -783,7 +853,7 @@ static gcry_err_code_t
 rsa_generate (int algo, unsigned int nbits, unsigned long evalue,
               gcry_mpi_t *skey, gcry_mpi_t **retfactors)
 {
-  return rsa_generate_ext (algo, nbits, evalue, NULL, skey, retfactors);
+  return rsa_generate_ext (algo, nbits, evalue, NULL, skey, retfactors, NULL);
 }