dsa-keygen.c

   1 /* dsa-keygen.c
   2  *
   3  * Generation of DSA keypairs
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2002 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  23  * MA 02111-1307, USA.
  24  */
  25
  26 #if HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <assert.h>
  31 #include <stdlib.h>
  32
  33 #include "dsa.h"
  34
  35 #include "bignum.h"
  36 #include "nettle-internal.h"
  37
  38
  39 /* Valid sizes, according to FIPS 186-3 are (1024, 160), (2048. 224),
  40    (2048, 256), (3072, 256). Currenty, we use only q_bits of 160 or
  41    256. */
  42 int
  43 dsa_generate_keypair(struct dsa_public_key *pub,
  44                      struct dsa_private_key *key,
  45                      void *random_ctx, nettle_random_func random,
  46                      void *progress_ctx, nettle_progress_func progress,
  47                      unsigned p_bits, unsigned q_bits)
  48 {
  49   mpz_t p0, p0q, r;
  50   unsigned p0_bits;
  51   unsigned a;
  52
  53   switch (q_bits)
  54     {
  55     case 160:
  56       if (p_bits < DSA_SHA1_MIN_P_BITS)
  57         return 0;
  58       break;
  59     case 256:
  60       if (p_bits < DSA_SHA256_MIN_P_BITS)
  61         return 0;
  62       break;
  63     default:
  64       return 0;
  65     }
  66
  67   mpz_init (p0);
  68   mpz_init (p0q);
  69   mpz_init (r);
  70
  71   nettle_random_prime (pub->q, q_bits, 0, random_ctx, random,
  72                        progress_ctx, progress);
  73
  74   p0_bits = (p_bits + 3)/2;
  75
  76   nettle_random_prime (p0, p0_bits, 0,
  77                        random_ctx, random,
  78                        progress_ctx, progress);
  79
  80   if (progress)
  81     progress (progress_ctx, 'q');
  82
  83   /* Generate p = 2 r q p0 + 1, such that 2^{n-1} < p < 2^n.
  84    *
  85    * We select r in the range i + 1 < r <= 2i, with i = floor (2^{n-2} / (p0 q). */
  86
  87   mpz_mul (p0q, p0, pub->q);
  88
  89   _nettle_generate_pocklington_prime (pub->p, r, p_bits, 0,
  90                                       random_ctx, random,
  91                                       p0, pub->q, p0q);
  92
  93   if (progress)
  94     progress (progress_ctx, 'p');
  95
  96   mpz_mul (r, r, p0);
  97
  98   for (a = 2; ; a++)
  99     {
 100       mpz_set_ui (pub->g, a);
 101       mpz_powm (pub->g, pub->g, r, pub->p);
 102       if (mpz_cmp_ui (pub->g, 1) != 0)
 103         break;
 104     }
 105
 106   if (progress)
 107     progress (progress_ctx, 'g');
 108
 109   mpz_init_set(r, pub->q);
 110   mpz_sub_ui(r, r, 2);
 111   nettle_mpz_random(key->x, random_ctx, random, r);
 112
 113   mpz_add_ui(key->x, key->x, 1);
 114
 115   mpz_powm(pub->y, pub->g, key->x, pub->p);
 116
 117   if (progress)
 118     progress (progress_ctx, '\n');
 119
 120   mpz_clear (p0);
 121   mpz_clear (p0q);
 122   mpz_clear (r);
 123
 124   return 1;
 125 }