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