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