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