GCM: GHASH optimizations
[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\n");
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\n");
94           continue; /* no */
95         }
96       break;    /* okay */
97     }
98   gcry_free (rndbuf);
99
100   return k;
101 }
102
103
104 /* Turn VALUE into an octet string and store it in an allocated buffer
105    at R_FRAME.  If the resulting octet string is shorter than NBYTES
106    the result will be left padded with zeroes.  If VALUE does not fit
107    into NBYTES an error code is returned.  */
108 static gpg_err_code_t
109 int2octets (unsigned char **r_frame, gcry_mpi_t value, size_t nbytes)
110 {
111   gpg_err_code_t rc;
112   size_t nframe, noff, n;
113   unsigned char *frame;
114
115   rc = gpg_err_code (gcry_mpi_print (GCRYMPI_FMT_USG, NULL, 0,
116                                       &nframe, value));
117   if (rc)
118     return rc;
119   if (nframe > nbytes)
120     return GPG_ERR_TOO_LARGE; /* Value too long to fit into NBYTES.  */
121
122   noff = (nframe < nbytes)? nbytes - nframe : 0;
123   n = nframe + noff;
124   frame = mpi_is_secure (value)? gcry_malloc_secure (n) : gcry_malloc (n);
125   if (!frame)
126     return gpg_err_code_from_syserror ();
127   if (noff)
128     memset (frame, 0, noff);
129   nframe += noff;
130   rc = gpg_err_code (gcry_mpi_print (GCRYMPI_FMT_USG, frame+noff, nframe-noff,
131                                       NULL, value));
132   if (rc)
133     {
134       gcry_free (frame);
135       return rc;
136     }
137
138   *r_frame = frame;
139   return 0;
140 }
141
142
143 /* Connert the bit string BITS of length NBITS into an octet string
144    with a length of (QBITS+7)/8 bytes.  On success store the result at
145    R_FRAME.  */
146 static gpg_err_code_t
147 bits2octets (unsigned char **r_frame,
148              const void *bits, unsigned int nbits,
149              gcry_mpi_t q, unsigned int qbits)
150 {
151   gpg_err_code_t rc;
152   gcry_mpi_t z1;
153
154   /* z1 = bits2int (b) */
155   rc = gpg_err_code (gcry_mpi_scan (&z1, GCRYMPI_FMT_USG,
156                                     bits, (nbits+7)/8, NULL));
157   if (rc)
158     return rc;
159   if (nbits > qbits)
160     gcry_mpi_rshift (z1, z1, nbits - qbits);
161
162   /* z2 - z1 mod q */
163   if (mpi_cmp (z1, q) >= 0)
164     mpi_sub (z1, z1, q);
165
166   /* Convert to an octet string.  */
167   rc = int2octets (r_frame, z1, (qbits+7)/8);
168
169   mpi_free (z1);
170   return rc;
171 }
172
173
174 /*
175  * Generate a deterministic secret exponent K less than DSA_Q.  H1 is
176  * the to be signed digest with a length of HLEN bytes.  HALGO is the
177  * algorithm used to create the hash.  On success the value for K is
178  * stored at R_K.
179  */
180 gpg_err_code_t
181 _gcry_dsa_gen_rfc6979_k (gcry_mpi_t *r_k,
182                          gcry_mpi_t dsa_q, gcry_mpi_t dsa_x,
183                          const unsigned char *h1, unsigned int hlen,
184                          int halgo, unsigned int extraloops)
185 {
186   gpg_err_code_t rc;
187   unsigned char *V = NULL;
188   unsigned char *K = NULL;
189   unsigned char *x_buf = NULL;
190   unsigned char *h1_buf = NULL;
191   gcry_md_hd_t hd = NULL;
192   unsigned char *t = NULL;
193   gcry_mpi_t k = NULL;
194   unsigned int tbits, qbits;
195   int i;
196
197   qbits = mpi_get_nbits (dsa_q);
198
199   if (!qbits || !h1 || !hlen)
200     return GPG_ERR_EINVAL;
201
202   if (gcry_md_get_algo_dlen (halgo) != hlen)
203     return GPG_ERR_DIGEST_ALGO;
204
205   /* Step b:  V = 0x01 0x01 0x01 ... 0x01 */
206   V = gcry_malloc (hlen);
207   if (!V)
208     {
209       rc = gpg_err_code_from_syserror ();
210       goto leave;
211     }
212   for (i=0; i < hlen; i++)
213     V[i] = 1;
214
215   /* Step c:  K = 0x00 0x00 0x00 ... 0x00 */
216   K = gcry_calloc (1, hlen);
217   if (!K)
218     {
219       rc = gpg_err_code_from_syserror ();
220       goto leave;
221     }
222
223   rc = int2octets (&x_buf, dsa_x, (qbits+7)/8);
224   if (rc)
225     goto leave;
226
227   rc = bits2octets (&h1_buf, h1, hlen*8, dsa_q, qbits);
228   if (rc)
229     goto leave;
230
231   /* Create a handle to compute the HMACs.  */
232   rc = gpg_err_code (gcry_md_open (&hd, halgo,
233                                    (GCRY_MD_FLAG_SECURE | GCRY_MD_FLAG_HMAC)));
234   if (rc)
235     goto leave;
236
237   /* Step d:  K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) */
238   rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
239   if (rc)
240     goto leave;
241   gcry_md_write (hd, V, hlen);
242   gcry_md_write (hd, "", 1);
243   gcry_md_write (hd, x_buf, (qbits+7)/8);
244   gcry_md_write (hd, h1_buf, (qbits+7)/8);
245   memcpy (K, gcry_md_read (hd, 0), hlen);
246
247   /* Step e:  V = HMAC_K(V) */
248   rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
249   if (rc)
250     goto leave;
251   gcry_md_write (hd, V, hlen);
252   memcpy (V, gcry_md_read (hd, 0), hlen);
253
254   /* Step f:  K = HMAC_K(V || 0x01 || int2octets(x) || bits2octets(h1) */
255   rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
256   if (rc)
257     goto leave;
258   gcry_md_write (hd, V, hlen);
259   gcry_md_write (hd, "\x01", 1);
260   gcry_md_write (hd, x_buf, (qbits+7)/8);
261   gcry_md_write (hd, h1_buf, (qbits+7)/8);
262   memcpy (K, gcry_md_read (hd, 0), hlen);
263
264   /* Step g:  V = HMAC_K(V) */
265   rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
266   if (rc)
267     goto leave;
268   gcry_md_write (hd, V, hlen);
269   memcpy (V, gcry_md_read (hd, 0), hlen);
270
271   /* Step h. */
272   t = gcry_malloc ((qbits+7)/8+hlen);
273   if (!t)
274     {
275       rc = gpg_err_code_from_syserror ();
276       goto leave;
277     }
278
279  again:
280   for (tbits = 0; tbits < qbits;)
281     {
282       /* V = HMAC_K(V) */
283       rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
284       if (rc)
285         goto leave;
286       gcry_md_write (hd, V, hlen);
287       memcpy (V, gcry_md_read (hd, 0), hlen);
288
289       /* T = T || V */
290       memcpy (t+(tbits+7)/8, V, hlen);
291       tbits += 8*hlen;
292     }
293
294   /* k = bits2int (T) */
295   mpi_free (k);
296   k = NULL;
297   rc = gpg_err_code (gcry_mpi_scan (&k, GCRYMPI_FMT_USG, t, (tbits+7)/8, NULL));
298   if (rc)
299     goto leave;
300   if (tbits > qbits)
301     gcry_mpi_rshift (k, k, tbits - qbits);
302
303   /* Check: k < q and k > 1 */
304   if (!(mpi_cmp (k, dsa_q) < 0 && mpi_cmp_ui (k, 0) > 0))
305     {
306       /* K = HMAC_K(V || 0x00) */
307       rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
308       if (rc)
309         goto leave;
310       gcry_md_write (hd, V, hlen);
311       gcry_md_write (hd, "", 1);
312       memcpy (K, gcry_md_read (hd, 0), hlen);
313
314       /* V = HMAC_K(V) */
315       rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
316       if (rc)
317         goto leave;
318       gcry_md_write (hd, V, hlen);
319       memcpy (V, gcry_md_read (hd, 0), hlen);
320
321       goto again;
322     }
323
324   /* The caller may have requested that we introduce some extra loops.
325      This is for example useful if the caller wants another value for
326      K because the last returned one yielded an R of 0.  Becuase this
327      is very unlikely we implement it in a straightforward way.  */
328   if (extraloops)
329     {
330       extraloops--;
331
332       /* K = HMAC_K(V || 0x00) */
333       rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
334       if (rc)
335         goto leave;
336       gcry_md_write (hd, V, hlen);
337       gcry_md_write (hd, "", 1);
338       memcpy (K, gcry_md_read (hd, 0), hlen);
339
340       /* V = HMAC_K(V) */
341       rc = gpg_err_code (gcry_md_setkey (hd, K, hlen));
342       if (rc)
343         goto leave;
344       gcry_md_write (hd, V, hlen);
345       memcpy (V, gcry_md_read (hd, 0), hlen);
346
347       goto again;
348     }
349
350   /* log_mpidump ("  k", k); */
351
352  leave:
353   gcry_free (t);
354   gcry_md_close (hd);
355   gcry_free (h1_buf);
356   gcry_free (x_buf);
357   gcry_free (K);
358   gcry_free (V);
359
360   if (rc)
361     mpi_free (k);
362   else
363     *r_k = k;
364   return rc;
365 }