Line data Source code
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 143 : _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 143 : gpg_err_code_t rc = 0;
46 143 : 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 143 : if (DBG_CIPHER)
55 0 : log_mpidump ("ecdsa sign hash ", input );
56 :
57 143 : qbits = mpi_get_nbits (skey->E.n);
58 :
59 : /* Convert the INPUT into an MPI if needed. */
60 143 : rc = _gcry_dsa_normalize_hash (input, &hash, qbits);
61 143 : if (rc)
62 0 : return rc;
63 :
64 143 : k = NULL;
65 143 : dr = mpi_alloc (0);
66 143 : sum = mpi_alloc (0);
67 143 : k_1 = mpi_alloc (0);
68 143 : x = mpi_alloc (0);
69 143 : point_init (&I);
70 :
71 143 : 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 143 : mpi_free (k);
82 143 : k = NULL;
83 143 : 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 54 : if (!mpi_is_opaque (input))
90 : {
91 0 : rc = GPG_ERR_CONFLICT;
92 0 : goto leave;
93 : }
94 :
95 54 : abuf = mpi_get_opaque (input, &abits);
96 108 : rc = _gcry_dsa_gen_rfc6979_k (&k, skey->E.n, skey->d,
97 54 : abuf, (abits+7)/8,
98 : hashalgo, extraloops);
99 54 : if (rc)
100 0 : goto leave;
101 54 : extraloops++;
102 : }
103 : else
104 89 : k = _gcry_dsa_gen_k (skey->E.n, GCRY_STRONG_RANDOM);
105 :
106 143 : _gcry_mpi_ec_mul_point (&I, k, &skey->E.G, ctx);
107 143 : if (_gcry_mpi_ec_get_affine (x, NULL, &I, ctx))
108 : {
109 0 : if (DBG_CIPHER)
110 0 : log_debug ("ecc sign: Failed to get affine coordinates\n");
111 0 : rc = GPG_ERR_BAD_SIGNATURE;
112 0 : goto leave;
113 : }
114 143 : mpi_mod (r, x, skey->E.n); /* r = x mod n */
115 : }
116 143 : while (!mpi_cmp_ui (r, 0));
117 :
118 143 : mpi_mulm (dr, skey->d, r, skey->E.n); /* dr = d*r mod n */
119 143 : mpi_addm (sum, hash, dr, skey->E.n); /* sum = hash + (d*r) mod n */
120 143 : mpi_invm (k_1, k, skey->E.n); /* k_1 = k^(-1) mod n */
121 143 : mpi_mulm (s, k_1, sum, skey->E.n); /* s = k^(-1)*(hash+(d*r)) mod n */
122 : }
123 143 : while (!mpi_cmp_ui (s, 0));
124 :
125 143 : if (DBG_CIPHER)
126 : {
127 0 : log_mpidump ("ecdsa sign result r ", r);
128 0 : log_mpidump ("ecdsa sign result s ", s);
129 : }
130 :
131 : leave:
132 143 : _gcry_mpi_ec_free (ctx);
133 143 : point_free (&I);
134 143 : mpi_free (x);
135 143 : mpi_free (k_1);
136 143 : mpi_free (sum);
137 143 : mpi_free (dr);
138 143 : mpi_free (k);
139 :
140 143 : if (hash != input)
141 62 : mpi_free (hash);
142 :
143 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 167 : _gcry_ecc_ecdsa_verify (gcry_mpi_t input, ECC_public_key *pkey,
152 : gcry_mpi_t r, gcry_mpi_t s)
153 : {
154 167 : 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 167 : if( !(mpi_cmp_ui (r, 0) > 0 && mpi_cmp (r, pkey->E.n) < 0) )
161 0 : return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < r < n failed. */
162 167 : if( !(mpi_cmp_ui (s, 0) > 0 && mpi_cmp (s, pkey->E.n) < 0) )
163 0 : return GPG_ERR_BAD_SIGNATURE; /* Assertion 0 < s < n failed. */
164 :
165 167 : nbits = mpi_get_nbits (pkey->E.n);
166 167 : err = _gcry_dsa_normalize_hash (input, &hash, nbits);
167 167 : if (err)
168 0 : return err;
169 :
170 167 : h = mpi_alloc (0);
171 167 : h1 = mpi_alloc (0);
172 167 : h2 = mpi_alloc (0);
173 167 : x = mpi_alloc (0);
174 167 : point_init (&Q);
175 167 : point_init (&Q1);
176 167 : point_init (&Q2);
177 :
178 167 : 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 167 : mpi_invm (h, s, pkey->E.n);
183 : /* h1 = hash * s^(-1) (mod n) */
184 167 : mpi_mulm (h1, hash, h, pkey->E.n);
185 : /* Q1 = [ hash * s^(-1) ]G */
186 167 : _gcry_mpi_ec_mul_point (&Q1, h1, &pkey->E.G, ctx);
187 : /* h2 = r * s^(-1) (mod n) */
188 167 : mpi_mulm (h2, r, h, pkey->E.n);
189 : /* Q2 = [ r * s^(-1) ]Q */
190 167 : _gcry_mpi_ec_mul_point (&Q2, h2, &pkey->Q, ctx);
191 : /* Q = ([hash * s^(-1)]G) + ([r * s^(-1)]Q) */
192 167 : _gcry_mpi_ec_add_points (&Q, &Q1, &Q2, ctx);
193 :
194 167 : if (!mpi_cmp_ui (Q.z, 0))
195 : {
196 0 : if (DBG_CIPHER)
197 0 : log_debug ("ecc verify: Rejected\n");
198 0 : err = GPG_ERR_BAD_SIGNATURE;
199 0 : goto leave;
200 : }
201 167 : if (_gcry_mpi_ec_get_affine (x, NULL, &Q, ctx))
202 : {
203 0 : if (DBG_CIPHER)
204 0 : log_debug ("ecc verify: Failed to get affine coordinates\n");
205 0 : err = GPG_ERR_BAD_SIGNATURE;
206 0 : goto leave;
207 : }
208 167 : mpi_mod (x, x, pkey->E.n); /* x = x mod E_n */
209 167 : if (mpi_cmp (x, r)) /* x != r */
210 : {
211 22 : if (DBG_CIPHER)
212 : {
213 0 : log_mpidump (" x", x);
214 0 : log_mpidump (" r", r);
215 0 : log_mpidump (" s", s);
216 : }
217 22 : err = GPG_ERR_BAD_SIGNATURE;
218 22 : goto leave;
219 : }
220 :
221 : leave:
222 167 : _gcry_mpi_ec_free (ctx);
223 167 : point_free (&Q2);
224 167 : point_free (&Q1);
225 167 : point_free (&Q);
226 167 : mpi_free (x);
227 167 : mpi_free (h2);
228 167 : mpi_free (h1);
229 167 : mpi_free (h);
230 167 : if (hash != input)
231 0 : mpi_free (hash);
232 :
233 167 : return err;
234 : }
|
