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