pkgconfig: Fix libgcrypt.pc.
[libgcrypt.git] / cipher / ecc-ecdsa.c
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, ECC_secret_key *skey,
42                       gcry_mpi_t r, gcry_mpi_t s,
43                       int flags, int hashalgo)
44 {
45   gpg_err_code_t rc = 0;
46   int extraloops = 0;
47   gcry_mpi_t k, dr, sum, k_1, x;
48   mpi_point_struct I;
49   gcry_mpi_t hash;
50   const void *abuf;
51   unsigned int abits, qbits;
52   mpi_ec_t ctx;
53   gcry_mpi_t b;                /* Random number needed for blinding.  */
54   gcry_mpi_t bi;               /* multiplicative inverse of B.        */
55
56   if (DBG_CIPHER)
57     log_mpidump ("ecdsa sign hash  ", input );
58
59   qbits = mpi_get_nbits (skey->E.n);
60
61   /* Convert the INPUT into an MPI if needed.  */
62   rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
63   if (rc)
64     return rc;
65
66   b  = mpi_snew (qbits);
67   bi = mpi_snew (qbits);
68   do
69     {
70       _gcry_mpi_randomize (b, qbits, GCRY_WEAK_RANDOM);
71       mpi_mod (b, b, skey->E.n);
72     }
73   while (!mpi_invm (bi, b, skey->E.n));
74
75   k = NULL;
76   dr = mpi_alloc (0);
77   sum = mpi_alloc (0);
78   k_1 = mpi_alloc (0);
79   x = mpi_alloc (0);
80   point_init (&I);
81
82   ctx = _gcry_mpi_ec_p_internal_new (skey->E.model, skey->E.dialect, 0,
83                                      skey->E.p, skey->E.a, skey->E.b);
84
85   /* Two loops to avoid R or S are zero.  This is more of a joke than
86      a real demand because the probability of them being zero is less
87      than any hardware failure.  Some specs however require it.  */
88   do
89     {
90       do
91         {
92           mpi_free (k);
93           k = NULL;
94           if ((flags & PUBKEY_FLAG_RFC6979) && hashalgo)
95             {
96               /* Use Pornin's method for deterministic DSA.  If this
97                  flag is set, it is expected that HASH is an opaque
98                  MPI with the to be signed hash.  That hash is also
99                  used as h1 from 3.2.a.  */
100               if (!mpi_is_opaque (input))
101                 {
102                   rc = GPG_ERR_CONFLICT;
103                   goto leave;
104                 }
105
106               abuf = mpi_get_opaque (input, &abits);
107               rc = _gcry_dsa_gen_rfc6979_k (&k, skey->E.n, skey->d,
108                                             abuf, (abits+7)/8,
109                                             hashalgo, extraloops);
110               if (rc)
111                 goto leave;
112               extraloops++;
113             }
114           else
115             k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
116
117           _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
118           if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
119             {
120               if (DBG_CIPHER)
121                 log_debug ("ecc sign: Failed to get affine coordinates\n");
122               rc = GPG_ERR_BAD_SIGNATURE;
123               goto leave;
124             }
125           mpi_mod (r, x, skey->E.n);  /* r = x mod n */
126         }
127       while (!mpi_cmp_ui (r, 0));
128
129       mpi_mulm (dr, b, skey->d, skey->E.n);
130       mpi_mulm (dr, dr, r, skey->E.n);      /* dr = d*r mod n (blinded with b) */
131       mpi_mulm (sum, b, hash, skey->E.n);
132       mpi_addm (sum, sum, dr, skey->E.n);   /* sum = hash + (d*r) mod n  (blinded with b) */
133       mpi_mulm (sum, bi, sum, skey->E.n);   /* undo blinding by b^-1 */
134       mpi_invm (k_1, k, skey->E.n);         /* k_1 = k^(-1) mod n  */
135       mpi_mulm (s, k_1, sum, skey->E.n);    /* s = k^(-1)*(hash+(d*r)) mod n */
136     }
137   while (!mpi_cmp_ui (s, 0));
138
139   if (DBG_CIPHER)
140     {
141       log_mpidump ("ecdsa sign result r ", r);
142       log_mpidump ("ecdsa sign result s ", s);
143     }
144
145  leave:
146   mpi_free (b);
147   mpi_free (bi);
148   _gcry_mpi_ec_free (ctx);
149   point_free (&I);
150   mpi_free (x);
151   mpi_free (k_1);
152   mpi_free (sum);
153   mpi_free (dr);
154   mpi_free (k);
155
156   if (hash != input)
157     mpi_free (hash);
158
159   return rc;
160 }
161
162
163 /* Verify an ECDSA signature.
164  * Check if R and S verifies INPUT.
165  */
166 gpg_err_code_t
167 _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
168                         gcry_mpi_t r, gcry_mpi_t s)
169 {
170   gpg_err_code_t err = 0;
171   gcry_mpi_t hash, h, h1, h2, x;
172   mpi_point_struct Q, Q1, Q2;
173   mpi_ec_t ctx;
174   unsigned int nbits;
175
176   if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
177     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < r < n  failed.  */
178   if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
179     return GPG_ERR_BAD_SIGNATURE; /* Assertion  0 < s < n  failed.  */
180
181   nbits = mpi_get_nbits (pkey->E.n);
182   err = _gcry_dsa_normalize_hash (input, &hash, nbits);
183   if (err)
184     return err;
185
186   h  = mpi_alloc (0);
187   h1 = mpi_alloc (0);
188   h2 = mpi_alloc (0);
189   x = mpi_alloc (0);
190   point_init (&Q);
191   point_init (&Q1);
192   point_init (&Q2);
193
194   ctx = _gcry_mpi_ec_p_internal_new (pkey->E.model, pkey->E.dialect, 0,
195                                      pkey->E.p, pkey->E.a, pkey->E.b);
196
197   /* h  = s^(-1) (mod n) */
198   mpi_invm (h, s, pkey->E.n);
199   /* h1 = hash * s^(-1) (mod n) */
200   mpi_mulm (h1, hash, h, pkey->E.n);
201   /* Q1 = [ hash * s^(-1) ]G  */
202   _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
203   /* h2 = r * s^(-1) (mod n) */
204   mpi_mulm (h2, r, h, pkey->E.n);
205   /* Q2 = [ r * s^(-1) ]Q */
206   _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
207   /* Q  = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
208   _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
209
210   if (!mpi_cmp_ui (Q.z, 0))
211     {
212       if (DBG_CIPHER)
213           log_debug ("ecc verify: Rejected\n");
214       err = GPG_ERR_BAD_SIGNATURE;
215       goto leave;
216     }
217   if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
218     {
219       if (DBG_CIPHER)
220         log_debug ("ecc verify: Failed to get affine coordinates\n");
221       err = GPG_ERR_BAD_SIGNATURE;
222       goto leave;
223     }
224   mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
225   if (mpi_cmp (x, r))   /* x != r */
226     {
227       if (DBG_CIPHER)
228         {
229           log_mpidump ("     x", x);
230           log_mpidump ("     r", r);
231           log_mpidump ("     s", s);
232         }
233       err = GPG_ERR_BAD_SIGNATURE;
234       goto leave;
235     }
236
237  leave:
238   _gcry_mpi_ec_free (ctx);
239   point_free (&Q2);
240   point_free (&Q1);
241   point_free (&Q);
242   mpi_free (x);
243   mpi_free (h2);
244   mpi_free (h1);
245   mpi_free (h);
246   if (hash != input)
247     mpi_free (hash);
248
249   return err;
250 }