ecc: Fix a minor flaw in the generation of K.
[libgcrypt.git] / cipher / dsa-common.c
1 /* dsa-common.c - Common code for DSA
2  * Copyright (C) 1998, 1999 Free Software Foundation, Inc.
3  * Copyright (C) 2013  g10 Code GmbH
4  *
5  * This file is part of Libgcrypt.
6  *
7  * Libgcrypt is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU Lesser General Public License as
9  * published by the Free Software Foundation; either version 2.1 of
10  * the License, or (at your option) any later version.
11  *
12  * Libgcrypt is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU Lesser General Public License for more details.
16  *
17  * You should have received a copy of the GNU Lesser General Public
18  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <string.h>
25
26 #include "g10lib.h"
27 #include "mpi.h"
28 #include "cipher.h"
29 #include "pubkey-internal.h"
30
31
32 /*
33  * Generate a random secret exponent K less than Q.
34  * Note that ECDSA uses this code also to generate D.
35  */
36 gcry_mpi_t
37 _gcry_dsa_gen_k (gcry_mpi_t q, int security_level)
38 {
39   gcry_mpi_t k        = mpi_alloc_secure (mpi_get_nlimbs (q));
40   unsigned int nbits  = mpi_get_nbits (q);
41   unsigned int nbytes = (nbits+7)/8;
42   char *rndbuf = NULL;
43
44   /* To learn why we don't use mpi_mod to get the requested bit size,
45      read the paper: "The Insecurity of the Digital Signature
46      Algorithm with Partially Known Nonces" by Nguyen and Shparlinski.
47      Journal of Cryptology, New York. Vol 15, nr 3 (2003)  */
48
49   if (DBG_CIPHER)
50     log_debug ("choosing a random k of %u bits at seclevel %d\n",
51                nbits, security_level);
52   for (;;)
53     {
54       if ( !rndbuf || nbits < 32 )
55         {
56           gcry_free (rndbuf);
57           rndbuf = gcry_random_bytes_secure (nbytes, security_level);
58         }
59       else
60         { /* Change only some of the higher bits.  We could improve
61              this by directly requesting more memory at the first call
62              to get_random_bytes() and use these extra bytes here.
63              However the required management code is more complex and
64              thus we better use this simple method.  */
65           char *pp = gcry_random_bytes_secure (4, security_level);
66           memcpy (rndbuf, pp, 4);
67           gcry_free (pp);
68         }
69       _gcry_mpi_set_buffer (k, rndbuf, nbytes, 0);
70
71       /* Make sure we have the requested number of bits.  This code
72          looks a bit funny but it is easy to understand if you
73          consider that mpi_set_highbit clears all higher bits.  We
74          don't have a clear_highbit, thus we first set the high bit
75          and then clear it again.  */
76       if (mpi_test_bit (k, nbits-1))
77         mpi_set_highbit (k, nbits-1);
78       else
79         {
80           mpi_set_highbit (k, nbits-1);
81           mpi_clear_bit (k, nbits-1);
82         }
83
84       if (!(mpi_cmp (k, q) < 0))    /* check: k < q */
85         {
86           if (DBG_CIPHER)
87             log_debug ("\tk too large - again");
88           continue; /* no  */
89         }
90       if (!(mpi_cmp_ui (k, 0) > 0)) /* check: k > 0 */
91         {
92           if (DBG_CIPHER)
93             log_debug ("\tk is zero - again");
94           continue; /* no */
95         }
96       break;    /* okay */
97     }
98   gcry_free (rndbuf);
99
100   return k;
101 }