]>
Commit | Line | Data |
---|---|---|
1 | /* crypto/ecdsa/ecs_ossl.c */ | |
2 | /* | |
3 | * Written by Nils Larsch for the OpenSSL project | |
4 | */ | |
5 | /* ==================================================================== | |
6 | * Copyright (c) 1998-2004 The OpenSSL Project. All rights reserved. | |
7 | * | |
8 | * Redistribution and use in source and binary forms, with or without | |
9 | * modification, are permitted provided that the following conditions | |
10 | * are met: | |
11 | * | |
12 | * 1. Redistributions of source code must retain the above copyright | |
13 | * notice, this list of conditions and the following disclaimer. | |
14 | * | |
15 | * 2. Redistributions in binary form must reproduce the above copyright | |
16 | * notice, this list of conditions and the following disclaimer in | |
17 | * the documentation and/or other materials provided with the | |
18 | * distribution. | |
19 | * | |
20 | * 3. All advertising materials mentioning features or use of this | |
21 | * software must display the following acknowledgment: | |
22 | * "This product includes software developed by the OpenSSL Project | |
23 | * for use in the OpenSSL Toolkit. (http://www.OpenSSL.org/)" | |
24 | * | |
25 | * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to | |
26 | * endorse or promote products derived from this software without | |
27 | * prior written permission. For written permission, please contact | |
28 | * openssl-core@OpenSSL.org. | |
29 | * | |
30 | * 5. Products derived from this software may not be called "OpenSSL" | |
31 | * nor may "OpenSSL" appear in their names without prior written | |
32 | * permission of the OpenSSL Project. | |
33 | * | |
34 | * 6. Redistributions of any form whatsoever must retain the following | |
35 | * acknowledgment: | |
36 | * "This product includes software developed by the OpenSSL Project | |
37 | * for use in the OpenSSL Toolkit (http://www.OpenSSL.org/)" | |
38 | * | |
39 | * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY | |
40 | * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
41 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | |
42 | * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR | |
43 | * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
44 | * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT | |
45 | * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; | |
46 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
47 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, | |
48 | * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) | |
49 | * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED | |
50 | * OF THE POSSIBILITY OF SUCH DAMAGE. | |
51 | * ==================================================================== | |
52 | * | |
53 | * This product includes cryptographic software written by Eric Young | |
54 | * (eay@cryptsoft.com). This product includes software written by Tim | |
55 | * Hudson (tjh@cryptsoft.com). | |
56 | * | |
57 | */ | |
58 | ||
59 | #include "ecs_locl.h" | |
60 | #include <openssl/err.h> | |
61 | #include <openssl/obj_mac.h> | |
62 | #include <openssl/bn.h> | |
63 | #include <openssl/rand.h> | |
64 | ||
65 | static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dlen, | |
66 | const BIGNUM *, const BIGNUM *, | |
67 | EC_KEY *eckey); | |
68 | static int ecdsa_sign_setup_no_digest(EC_KEY *eckey, BN_CTX *ctx_in, | |
69 | BIGNUM **kinvp, BIGNUM **rp); | |
70 | static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp, | |
71 | BIGNUM **rp, const unsigned char *dgst, int dlen); | |
72 | static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, | |
73 | const ECDSA_SIG *sig, EC_KEY *eckey); | |
74 | ||
75 | static ECDSA_METHOD openssl_ecdsa_meth = { | |
76 | "OpenSSL ECDSA method", | |
77 | ecdsa_do_sign, | |
78 | ecdsa_sign_setup_no_digest, | |
79 | ecdsa_do_verify, | |
80 | ECDSA_FLAG_FIPS_METHOD, /* flags */ | |
81 | NULL /* app_data */ | |
82 | }; | |
83 | ||
84 | const ECDSA_METHOD *ECDSA_OpenSSL(void) | |
85 | { | |
86 | return &openssl_ecdsa_meth; | |
87 | } | |
88 | ||
89 | static int ecdsa_sign_setup_no_digest(EC_KEY *eckey, | |
90 | BN_CTX *ctx_in, BIGNUM **kinvp, | |
91 | BIGNUM **rp) | |
92 | { | |
93 | return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0); | |
94 | } | |
95 | ||
96 | static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, | |
97 | BIGNUM **kinvp, BIGNUM **rp, | |
98 | const unsigned char *dgst, int dlen) | |
99 | { | |
100 | BN_CTX *ctx = NULL; | |
101 | BIGNUM *k = NULL, *r = NULL, *order = NULL, *X = NULL; | |
102 | EC_POINT *tmp_point = NULL; | |
103 | const EC_GROUP *group; | |
104 | int ret = 0; | |
105 | ||
106 | if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) { | |
107 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER); | |
108 | return 0; | |
109 | } | |
110 | ||
111 | if (ctx_in == NULL) { | |
112 | if ((ctx = BN_CTX_new()) == NULL) { | |
113 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); | |
114 | return 0; | |
115 | } | |
116 | } else | |
117 | ctx = ctx_in; | |
118 | ||
119 | k = BN_new(); /* this value is later returned in *kinvp */ | |
120 | r = BN_new(); /* this value is later returned in *rp */ | |
121 | order = BN_new(); | |
122 | X = BN_new(); | |
123 | if (!k || !r || !order || !X) { | |
124 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE); | |
125 | goto err; | |
126 | } | |
127 | if ((tmp_point = EC_POINT_new(group)) == NULL) { | |
128 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); | |
129 | goto err; | |
130 | } | |
131 | if (!EC_GROUP_get_order(group, order, ctx)) { | |
132 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); | |
133 | goto err; | |
134 | } | |
135 | ||
136 | do { | |
137 | /* get random k */ | |
138 | do | |
139 | if (dgst != NULL) { | |
140 | if (!BN_generate_dsa_nonce | |
141 | (k, order, EC_KEY_get0_private_key(eckey), dgst, dlen, | |
142 | ctx)) { | |
143 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, | |
144 | ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); | |
145 | goto err; | |
146 | } | |
147 | } else { | |
148 | if (!BN_rand_range(k, order)) { | |
149 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, | |
150 | ECDSA_R_RANDOM_NUMBER_GENERATION_FAILED); | |
151 | goto err; | |
152 | } | |
153 | } | |
154 | while (BN_is_zero(k)); | |
155 | ||
156 | /* | |
157 | * We do not want timing information to leak the length of k, so we | |
158 | * compute G*k using an equivalent scalar of fixed bit-length. | |
159 | */ | |
160 | ||
161 | if (!BN_add(k, k, order)) | |
162 | goto err; | |
163 | if (BN_num_bits(k) <= BN_num_bits(order)) | |
164 | if (!BN_add(k, k, order)) | |
165 | goto err; | |
166 | ||
167 | /* compute r the x-coordinate of generator * k */ | |
168 | if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) { | |
169 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); | |
170 | goto err; | |
171 | } | |
172 | if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == | |
173 | NID_X9_62_prime_field) { | |
174 | if (!EC_POINT_get_affine_coordinates_GFp | |
175 | (group, tmp_point, X, NULL, ctx)) { | |
176 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); | |
177 | goto err; | |
178 | } | |
179 | } | |
180 | #ifndef OPENSSL_NO_EC2M | |
181 | else { /* NID_X9_62_characteristic_two_field */ | |
182 | ||
183 | if (!EC_POINT_get_affine_coordinates_GF2m(group, | |
184 | tmp_point, X, NULL, | |
185 | ctx)) { | |
186 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB); | |
187 | goto err; | |
188 | } | |
189 | } | |
190 | #endif | |
191 | if (!BN_nnmod(r, X, order, ctx)) { | |
192 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); | |
193 | goto err; | |
194 | } | |
195 | } | |
196 | while (BN_is_zero(r)); | |
197 | ||
198 | /* compute the inverse of k */ | |
199 | if (EC_GROUP_get_mont_data(group) != NULL) { | |
200 | /* | |
201 | * We want inverse in constant time, therefore we utilize the fact | |
202 | * order must be prime and use Fermats Little Theorem instead. | |
203 | */ | |
204 | if (!BN_set_word(X, 2)) { | |
205 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); | |
206 | goto err; | |
207 | } | |
208 | if (!BN_mod_sub(X, order, X, order, ctx)) { | |
209 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); | |
210 | goto err; | |
211 | } | |
212 | BN_set_flags(X, BN_FLG_CONSTTIME); | |
213 | if (!BN_mod_exp_mont_consttime | |
214 | (k, k, X, order, ctx, EC_GROUP_get_mont_data(group))) { | |
215 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); | |
216 | goto err; | |
217 | } | |
218 | } else { | |
219 | if (!BN_mod_inverse(k, k, order, ctx)) { | |
220 | ECDSAerr(ECDSA_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB); | |
221 | goto err; | |
222 | } | |
223 | } | |
224 | ||
225 | /* clear old values if necessary */ | |
226 | BN_clear_free(*rp); | |
227 | BN_clear_free(*kinvp); | |
228 | /* save the pre-computed values */ | |
229 | *rp = r; | |
230 | *kinvp = k; | |
231 | ret = 1; | |
232 | err: | |
233 | if (!ret) { | |
234 | BN_clear_free(k); | |
235 | BN_clear_free(r); | |
236 | } | |
237 | if (ctx != ctx_in) | |
238 | BN_CTX_free(ctx); | |
239 | BN_free(order); | |
240 | EC_POINT_free(tmp_point); | |
241 | BN_clear_free(X); | |
242 | return (ret); | |
243 | } | |
244 | ||
245 | static ECDSA_SIG *ecdsa_do_sign(const unsigned char *dgst, int dgst_len, | |
246 | const BIGNUM *in_kinv, const BIGNUM *in_r, | |
247 | EC_KEY *eckey) | |
248 | { | |
249 | int ok = 0, i; | |
250 | BIGNUM *kinv = NULL, *s, *m = NULL, *tmp = NULL, *order = NULL; | |
251 | const BIGNUM *ckinv; | |
252 | BN_CTX *ctx = NULL; | |
253 | const EC_GROUP *group; | |
254 | ECDSA_SIG *ret; | |
255 | ECDSA_DATA *ecdsa; | |
256 | const BIGNUM *priv_key; | |
257 | ||
258 | ecdsa = ecdsa_check(eckey); | |
259 | group = EC_KEY_get0_group(eckey); | |
260 | priv_key = EC_KEY_get0_private_key(eckey); | |
261 | ||
262 | if (group == NULL || priv_key == NULL || ecdsa == NULL) { | |
263 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_PASSED_NULL_PARAMETER); | |
264 | return NULL; | |
265 | } | |
266 | ||
267 | ret = ECDSA_SIG_new(); | |
268 | if (!ret) { | |
269 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); | |
270 | return NULL; | |
271 | } | |
272 | s = ret->s; | |
273 | ||
274 | if ((ctx = BN_CTX_new()) == NULL || (order = BN_new()) == NULL || | |
275 | (tmp = BN_new()) == NULL || (m = BN_new()) == NULL) { | |
276 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); | |
277 | goto err; | |
278 | } | |
279 | ||
280 | if (!EC_GROUP_get_order(group, order, ctx)) { | |
281 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_EC_LIB); | |
282 | goto err; | |
283 | } | |
284 | i = BN_num_bits(order); | |
285 | /* | |
286 | * Need to truncate digest if it is too long: first truncate whole bytes. | |
287 | */ | |
288 | if (8 * dgst_len > i) | |
289 | dgst_len = (i + 7) / 8; | |
290 | if (!BN_bin2bn(dgst, dgst_len, m)) { | |
291 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); | |
292 | goto err; | |
293 | } | |
294 | /* If still too long truncate remaining bits with a shift */ | |
295 | if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { | |
296 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); | |
297 | goto err; | |
298 | } | |
299 | do { | |
300 | if (in_kinv == NULL || in_r == NULL) { | |
301 | if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) { | |
302 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_ECDSA_LIB); | |
303 | goto err; | |
304 | } | |
305 | ckinv = kinv; | |
306 | } else { | |
307 | ckinv = in_kinv; | |
308 | if (BN_copy(ret->r, in_r) == NULL) { | |
309 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_MALLOC_FAILURE); | |
310 | goto err; | |
311 | } | |
312 | } | |
313 | ||
314 | if (!BN_mod_mul(tmp, priv_key, ret->r, order, ctx)) { | |
315 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); | |
316 | goto err; | |
317 | } | |
318 | if (!BN_mod_add_quick(s, tmp, m, order)) { | |
319 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); | |
320 | goto err; | |
321 | } | |
322 | if (!BN_mod_mul(s, s, ckinv, order, ctx)) { | |
323 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, ERR_R_BN_LIB); | |
324 | goto err; | |
325 | } | |
326 | if (BN_is_zero(s)) { | |
327 | /* | |
328 | * if kinv and r have been supplied by the caller don't to | |
329 | * generate new kinv and r values | |
330 | */ | |
331 | if (in_kinv != NULL && in_r != NULL) { | |
332 | ECDSAerr(ECDSA_F_ECDSA_DO_SIGN, | |
333 | ECDSA_R_NEED_NEW_SETUP_VALUES); | |
334 | goto err; | |
335 | } | |
336 | } else | |
337 | /* s != 0 => we have a valid signature */ | |
338 | break; | |
339 | } | |
340 | while (1); | |
341 | ||
342 | ok = 1; | |
343 | err: | |
344 | if (!ok) { | |
345 | ECDSA_SIG_free(ret); | |
346 | ret = NULL; | |
347 | } | |
348 | BN_CTX_free(ctx); | |
349 | BN_clear_free(m); | |
350 | BN_clear_free(tmp); | |
351 | BN_free(order); | |
352 | BN_clear_free(kinv); | |
353 | return ret; | |
354 | } | |
355 | ||
356 | static int ecdsa_do_verify(const unsigned char *dgst, int dgst_len, | |
357 | const ECDSA_SIG *sig, EC_KEY *eckey) | |
358 | { | |
359 | int ret = -1, i; | |
360 | BN_CTX *ctx; | |
361 | BIGNUM *order, *u1, *u2, *m, *X; | |
362 | EC_POINT *point = NULL; | |
363 | const EC_GROUP *group; | |
364 | const EC_POINT *pub_key; | |
365 | ||
366 | /* check input values */ | |
367 | if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL || | |
368 | (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) { | |
369 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_MISSING_PARAMETERS); | |
370 | return -1; | |
371 | } | |
372 | ||
373 | ctx = BN_CTX_new(); | |
374 | if (!ctx) { | |
375 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); | |
376 | return -1; | |
377 | } | |
378 | BN_CTX_start(ctx); | |
379 | order = BN_CTX_get(ctx); | |
380 | u1 = BN_CTX_get(ctx); | |
381 | u2 = BN_CTX_get(ctx); | |
382 | m = BN_CTX_get(ctx); | |
383 | X = BN_CTX_get(ctx); | |
384 | if (!X) { | |
385 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
386 | goto err; | |
387 | } | |
388 | ||
389 | if (!EC_GROUP_get_order(group, order, ctx)) { | |
390 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); | |
391 | goto err; | |
392 | } | |
393 | ||
394 | if (BN_is_zero(sig->r) || BN_is_negative(sig->r) || | |
395 | BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) || | |
396 | BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) { | |
397 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ECDSA_R_BAD_SIGNATURE); | |
398 | ret = 0; /* signature is invalid */ | |
399 | goto err; | |
400 | } | |
401 | /* calculate tmp1 = inv(S) mod order */ | |
402 | if (!BN_mod_inverse(u2, sig->s, order, ctx)) { | |
403 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
404 | goto err; | |
405 | } | |
406 | /* digest -> m */ | |
407 | i = BN_num_bits(order); | |
408 | /* | |
409 | * Need to truncate digest if it is too long: first truncate whole bytes. | |
410 | */ | |
411 | if (8 * dgst_len > i) | |
412 | dgst_len = (i + 7) / 8; | |
413 | if (!BN_bin2bn(dgst, dgst_len, m)) { | |
414 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
415 | goto err; | |
416 | } | |
417 | /* If still too long truncate remaining bits with a shift */ | |
418 | if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) { | |
419 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
420 | goto err; | |
421 | } | |
422 | /* u1 = m * tmp mod order */ | |
423 | if (!BN_mod_mul(u1, m, u2, order, ctx)) { | |
424 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
425 | goto err; | |
426 | } | |
427 | /* u2 = r * w mod q */ | |
428 | if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) { | |
429 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
430 | goto err; | |
431 | } | |
432 | ||
433 | if ((point = EC_POINT_new(group)) == NULL) { | |
434 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_MALLOC_FAILURE); | |
435 | goto err; | |
436 | } | |
437 | if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) { | |
438 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); | |
439 | goto err; | |
440 | } | |
441 | if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) == | |
442 | NID_X9_62_prime_field) { | |
443 | if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, ctx)) { | |
444 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); | |
445 | goto err; | |
446 | } | |
447 | } | |
448 | #ifndef OPENSSL_NO_EC2M | |
449 | else { /* NID_X9_62_characteristic_two_field */ | |
450 | ||
451 | if (!EC_POINT_get_affine_coordinates_GF2m(group, point, X, NULL, ctx)) { | |
452 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_EC_LIB); | |
453 | goto err; | |
454 | } | |
455 | } | |
456 | #endif | |
457 | if (!BN_nnmod(u1, X, order, ctx)) { | |
458 | ECDSAerr(ECDSA_F_ECDSA_DO_VERIFY, ERR_R_BN_LIB); | |
459 | goto err; | |
460 | } | |
461 | /* if the signature is correct u1 is equal to sig->r */ | |
462 | ret = (BN_ucmp(u1, sig->r) == 0); | |
463 | err: | |
464 | BN_CTX_end(ctx); | |
465 | BN_CTX_free(ctx); | |
466 | EC_POINT_free(point); | |
467 | return ret; | |
468 | } |