Coverage Report

Created: 2024-11-21 07:03

/src/libgcrypt/cipher/ecc-ecdsa.c
Line
Count
Source (jump to first uncovered line)
1
/* ecc-ecdsa.c  -  Elliptic Curve ECDSA signatures
2
 * Copyright (C) 2007, 2008, 2010, 2011 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
#include <errno.h>
26
27
#include "g10lib.h"
28
#include "mpi.h"
29
#include "cipher.h"
30
#include "context.h"
31
#include "ec-context.h"
32
#include "pubkey-internal.h"
33
#include "ecc-common.h"
34
35
36
/* Compute an ECDSA signature.
37
 * Return the signature struct (r,s) from the message hash.  The caller
38
 * must have allocated R and S.
39
 */
40
gpg_err_code_t
41
_gcry_ecc_ecdsa_sign (gcry_mpi_t input, gcry_mpi_t k_supplied, mpi_ec_t ec,
42
                      gcry_mpi_t r, gcry_mpi_t s,
43
                      int flags, int hashalgo)
44
320
{
45
320
  gpg_err_code_t rc = 0;
46
320
  int extraloops = 0;
47
320
  gcry_mpi_t k, dr, sum, k_1, x;
48
320
  mpi_point_struct I;
49
320
  gcry_mpi_t hash;
50
320
  const void *abuf;
51
320
  unsigned int abits, qbits;
52
320
  gcry_mpi_t b;                /* Random number needed for blinding.  */
53
320
  gcry_mpi_t bi;               /* multiplicative inverse of B.        */
54
320
  gcry_mpi_t hash_computed_internally = NULL;
55
56
320
  if (DBG_CIPHER)
57
0
    log_mpidump ("ecdsa sign hash  ", input );
58
59
320
  qbits = mpi_get_nbits (ec->n);
60
61
320
  if ((flags & PUBKEY_FLAG_PREHASH))
62
0
    {
63
0
      rc = _gcry_dsa_compute_hash (&hash_computed_internally, input, hashalgo);
64
0
      if (rc)
65
0
        return rc;
66
0
      input = hash_computed_internally;
67
0
    }
68
69
  /* Convert the INPUT into an MPI if needed.  */
70
320
  rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
71
72
320
  if (rc)
73
0
    {
74
0
      mpi_free (hash_computed_internally);
75
0
      return rc;
76
0
    }
77
78
320
  b  = mpi_snew (qbits);
79
320
  bi = mpi_snew (qbits);
80
320
  do
81
320
    {
82
320
      _gcry_mpi_randomize (b, qbits, GCRY_WEAK_RANDOM);
83
320
      mpi_mod (b, b, ec->n);
84
320
    }
85
320
  while (!mpi_invm (bi, b, ec->n));
86
87
320
  k = NULL;
88
320
  dr = mpi_alloc (0);
89
320
  sum = mpi_alloc (0);
90
320
  k_1 = mpi_alloc (0);
91
320
  x = mpi_alloc (0);
92
320
  point_init (&I);
93
94
  /* Two loops to avoid R or S are zero.  This is more of a joke than
95
     a real demand because the probability of them being zero is less
96
     than any hardware failure.  Some specs however require it.  */
97
320
  while (1)
98
320
    {
99
320
      while (1)
100
320
        {
101
320
          if (k_supplied)
102
0
            k = k_supplied;
103
320
          else
104
320
            {
105
320
              mpi_free (k);
106
320
              k = NULL;
107
320
              if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
108
113
                {
109
113
                  if (fips_mode () &&
110
113
                      (hashalgo == GCRY_MD_SHAKE128
111
0
                       || hashalgo == GCRY_MD_SHAKE256))
112
0
                    {
113
0
                      rc = GPG_ERR_DIGEST_ALGO;
114
0
                      goto leave;
115
0
                    }
116
117
                  /* Use Pornin's method for deterministic DSA.  If this
118
                     flag is set, it is expected that HASH is an opaque
119
                     MPI with the to be signed hash.  That hash is also
120
                     used as h1 from 3.2.a.  */
121
113
                  if (!mpi_is_opaque (input))
122
0
                    {
123
0
                      rc = GPG_ERR_CONFLICT;
124
0
                      goto leave;
125
0
                    }
126
127
113
                  abuf = mpi_get_opaque (input, &abits);
128
113
                  rc = _gcry_dsa_gen_rfc6979_k (&k, ec->n, ec->d,
129
113
                                                abuf, (abits+7)/8,
130
113
                                                hashalgo, extraloops);
131
113
                  if (rc)
132
9
                    goto leave;
133
104
                  extraloops++;
134
104
                }
135
207
              else
136
207
                k = _gcry_dsa_gen_k (ec->n, GCRY_STRONG_RANDOM);
137
320
            }
138
139
311
          mpi_invm (k_1, k, ec->n);     /* k_1 = k^(-1) mod n  */
140
141
311
          _gcry_dsa_modify_k (k, ec->n, qbits);
142
143
311
          _gcry_mpi_ec_mul_point (&I, k, ec->G, ec);
144
311
          if (_gcry_mpi_ec_get_affine (x, NULL, &I, ec))
145
0
            {
146
0
              if (DBG_CIPHER)
147
0
                log_debug ("ecc sign: Failed to get affine coordinates\n");
148
0
              rc = GPG_ERR_BAD_SIGNATURE;
149
0
              goto leave;
150
0
            }
151
311
          mpi_mod (r, x, ec->n);  /* r = x mod n */
152
153
311
          if (mpi_cmp_ui (r, 0))
154
311
            break;
155
156
0
          if (k_supplied)
157
0
            {
158
0
              rc = GPG_ERR_INV_VALUE;
159
0
              goto leave;
160
0
            }
161
0
        }
162
163
      /* Computation of dr, sum, and s are blinded with b.  */
164
311
      mpi_mulm (dr, b, ec->d, ec->n);
165
311
      mpi_mulm (dr, dr, r, ec->n);      /* dr = d*r mod n */
166
311
      mpi_mulm (sum, b, hash, ec->n);
167
311
      mpi_addm (sum, sum, dr, ec->n);   /* sum = hash + (d*r) mod n */
168
311
      mpi_mulm (s, k_1, sum, ec->n);    /* s = k^(-1)*(hash+(d*r)) mod n */
169
      /* Undo blinding by b^-1 */
170
311
      mpi_mulm (s, bi, s, ec->n);
171
311
      if (mpi_cmp_ui (s, 0))
172
311
        break;
173
174
0
      if (k_supplied)
175
0
        {
176
0
          rc = GPG_ERR_INV_VALUE;
177
0
          break;
178
0
        }
179
0
    }
180
181
311
  if (DBG_CIPHER)
182
0
    {
183
0
      log_mpidump ("ecdsa sign result r ", r);
184
0
      log_mpidump ("ecdsa sign result s ", s);
185
0
    }
186
187
320
 leave:
188
320
  mpi_free (b);
189
320
  mpi_free (bi);
190
320
  point_free (&I);
191
320
  mpi_free (x);
192
320
  mpi_free (k_1);
193
320
  mpi_free (sum);
194
320
  mpi_free (dr);
195
320
  if (!k_supplied)
196
320
    mpi_free (k);
197
198
320
  if (hash != input)
199
320
    mpi_free (hash);
200
320
  mpi_free (hash_computed_internally);
201
202
320
  return rc;
203
311
}
204
205
206
/* Verify an ECDSA signature.
207
 * Check if R and S verifies INPUT.
208
 */
209
gpg_err_code_t
210
_gcry_ecc_ecdsa_verify (gcry_mpi_t input, mpi_ec_t ec,
211
                        gcry_mpi_t r, gcry_mpi_t s, int flags, int hashalgo)
212
126
{
213
126
  gpg_err_code_t err = 0;
214
126
  gcry_mpi_t hash, h, h1, h2, x;
215
126
  mpi_point_struct Q, Q1, Q2;
216
126
  unsigned int nbits;
217
126
  gcry_mpi_t hash_computed_internally = NULL;
218
219
126
  if (!_gcry_mpi_ec_curve_point (ec->Q, ec))
220
1
    return GPG_ERR_BROKEN_PUBKEY;
221
222
125
  if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, ec->n) < 0) )
223
1
    return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n  failed.  */
224
124
  if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, ec->n) < 0) )
225
0
    return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
226
227
124
  nbits = mpi_get_nbits (ec->n);
228
124
  if ((flags & PUBKEY_FLAG_PREHASH))
229
0
    {
230
0
      err = _gcry_dsa_compute_hash (&hash_computed_internally, input,
231
0
                                    hashalgo);
232
0
      if (err)
233
0
        return err;
234
0
      input = hash_computed_internally;
235
0
    }
236
237
124
  err = _gcry_dsa_normalize_hash (input, &hash, nbits);
238
124
  if (err)
239
0
    {
240
0
      mpi_free (hash_computed_internally);
241
0
      return err;
242
0
    }
243
244
124
  h  = mpi_alloc (0);
245
124
  h1 = mpi_alloc (0);
246
124
  h2 = mpi_alloc (0);
247
124
  x = mpi_alloc (0);
248
124
  point_init (&Q);
249
124
  point_init (&Q1);
250
124
  point_init (&Q2);
251
252
  /* h  = s^(-1) (mod n) */
253
124
  mpi_invm (h, s, ec->n);
254
  /* h1 = hash * s^(-1) (mod n) */
255
124
  mpi_mulm (h1, hash, h, ec->n);
256
  /* Q1 = [ hash * s^(-1) ]G  */
257
124
  _gcry_mpi_ec_mul_point (&Q1, h1, ec->G, ec);
258
  /* h2 = r * s^(-1) (mod n) */
259
124
  mpi_mulm (h2, r, h, ec->n);
260
  /* Q2 = [ r * s^(-1) ]Q */
261
124
  _gcry_mpi_ec_mul_point (&Q2, h2, ec->Q, ec);
262
  /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
263
124
  _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ec);
264
265
124
  if (!mpi_cmp_ui (Q.z, 0))
266
0
    {
267
0
      if (DBG_CIPHER)
268
0
          log_debug ("ecc verify: Rejected\n");
269
0
      err = GPG_ERR_BAD_SIGNATURE;
270
0
      goto leave;
271
0
    }
272
124
  if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ec))
273
0
    {
274
0
      if (DBG_CIPHER)
275
0
        log_debug ("ecc verify: Failed to get affine coordinates\n");
276
0
      err = GPG_ERR_BAD_SIGNATURE;
277
0
      goto leave;
278
0
    }
279
124
  mpi_mod (x, x, ec->n); /* x = x mod E_n */
280
124
  if (mpi_cmp (x, r))   /* x != r */
281
0
    {
282
0
      if (DBG_CIPHER)
283
0
        {
284
0
          log_mpidump ("     x", x);
285
0
          log_mpidump ("     r", r);
286
0
          log_mpidump ("     s", s);
287
0
        }
288
0
      err = GPG_ERR_BAD_SIGNATURE;
289
0
      goto leave;
290
0
    }
291
292
124
 leave:
293
124
  point_free (&Q2);
294
124
  point_free (&Q1);
295
124
  point_free (&Q);
296
124
  mpi_free (x);
297
124
  mpi_free (h2);
298
124
  mpi_free (h1);
299
124
  mpi_free (h);
300
124
  if (hash != input)
301
0
    mpi_free (hash);
302
124
  mpi_free (hash_computed_internally);
303
304
124
  return err;
305
124
}