ad7a6f752523bfb8171c51ed94e185bf4c5975e6
[openssl.git] / crypto / ec / ecdsa_ossl.c
1 /*
2  * Copyright 2002-2018 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the OpenSSL license (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <string.h>
11 #include <openssl/err.h>
12 #include <openssl/obj_mac.h>
13 #include <openssl/rand.h>
14 #include "internal/bn_int.h"
15 #include "ec_lcl.h"
16
17 int ossl_ecdsa_sign(int type, const unsigned char *dgst, int dlen,
18                     unsigned char *sig, unsigned int *siglen,
19                     const BIGNUM *kinv, const BIGNUM *r, EC_KEY *eckey)
20 {
21     ECDSA_SIG *s;
22
23     s = ECDSA_do_sign_ex(dgst, dlen, kinv, r, eckey);
24     if (s == NULL) {
25         *siglen = 0;
26         return 0;
27     }
28     *siglen = i2d_ECDSA_SIG(s, &sig);
29     ECDSA_SIG_free(s);
30     return 1;
31 }
32
33 static int ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in,
34                             BIGNUM **kinvp, BIGNUM **rp,
35                             const unsigned char *dgst, int dlen)
36 {
37     BN_CTX *ctx = NULL;
38     BIGNUM *k = NULL, *r = NULL, *X = NULL;
39     const BIGNUM *order;
40     EC_POINT *tmp_point = NULL;
41     const EC_GROUP *group;
42     int ret = 0;
43     int order_bits;
44
45     if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL) {
46         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_PASSED_NULL_PARAMETER);
47         return 0;
48     }
49
50     if (!EC_KEY_can_sign(eckey)) {
51         ECerr(EC_F_ECDSA_SIGN_SETUP, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
52         return 0;
53     }
54
55     if ((ctx = ctx_in) == NULL) {
56         if ((ctx = BN_CTX_new()) == NULL) {
57             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
58             return 0;
59         }
60     }
61
62     k = BN_new();               /* this value is later returned in *kinvp */
63     r = BN_new();               /* this value is later returned in *rp */
64     X = BN_new();
65     if (k == NULL || r == NULL || X == NULL) {
66         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_MALLOC_FAILURE);
67         goto err;
68     }
69     if ((tmp_point = EC_POINT_new(group)) == NULL) {
70         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
71         goto err;
72     }
73     order = EC_GROUP_get0_order(group);
74
75     /* Preallocate space */
76     order_bits = BN_num_bits(order);
77     if (!BN_set_bit(k, order_bits)
78         || !BN_set_bit(r, order_bits)
79         || !BN_set_bit(X, order_bits))
80         goto err;
81
82     do {
83         /* get random k */
84         do {
85             if (dgst != NULL) {
86                 if (!BN_generate_dsa_nonce(k, order,
87                                            EC_KEY_get0_private_key(eckey),
88                                            dgst, dlen, ctx)) {
89                     ECerr(EC_F_ECDSA_SIGN_SETUP,
90                           EC_R_RANDOM_NUMBER_GENERATION_FAILED);
91                     goto err;
92                 }
93             } else {
94                 if (!BN_priv_rand_range(k, order)) {
95                     ECerr(EC_F_ECDSA_SIGN_SETUP,
96                           EC_R_RANDOM_NUMBER_GENERATION_FAILED);
97                     goto err;
98                 }
99             }
100         } while (BN_is_zero(k));
101
102         /* compute r the x-coordinate of generator * k */
103         if (!EC_POINT_mul(group, tmp_point, k, NULL, NULL, ctx)) {
104             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
105             goto err;
106         }
107         if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
108             NID_X9_62_prime_field) {
109             if (!EC_POINT_get_affine_coordinates_GFp(group, tmp_point, X,
110                                                      NULL, ctx)) {
111                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
112                 goto err;
113             }
114         }
115 #ifndef OPENSSL_NO_EC2M
116         else {                  /* NID_X9_62_characteristic_two_field */
117             if (!EC_POINT_get_affine_coordinates_GF2m(group, tmp_point, X,
118                                                       NULL, ctx)) {
119                 ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_EC_LIB);
120                 goto err;
121             }
122         }
123 #endif
124         if (!BN_nnmod(r, X, order, ctx)) {
125             ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
126             goto err;
127         }
128     } while (BN_is_zero(r));
129
130     /* compute the inverse of k */
131     if (!ec_group_do_inverse_ord(group, k, k, ctx)) {
132         ECerr(EC_F_ECDSA_SIGN_SETUP, ERR_R_BN_LIB);
133         goto err;
134     }
135
136     /* clear old values if necessary */
137     BN_clear_free(*rp);
138     BN_clear_free(*kinvp);
139     /* save the pre-computed values  */
140     *rp = r;
141     *kinvp = k;
142     ret = 1;
143  err:
144     if (!ret) {
145         BN_clear_free(k);
146         BN_clear_free(r);
147     }
148     if (ctx != ctx_in)
149         BN_CTX_free(ctx);
150     EC_POINT_free(tmp_point);
151     BN_clear_free(X);
152     return ret;
153 }
154
155 int ossl_ecdsa_sign_setup(EC_KEY *eckey, BN_CTX *ctx_in, BIGNUM **kinvp,
156                           BIGNUM **rp)
157 {
158     return ecdsa_sign_setup(eckey, ctx_in, kinvp, rp, NULL, 0);
159 }
160
161 ECDSA_SIG *ossl_ecdsa_sign_sig(const unsigned char *dgst, int dgst_len,
162                                const BIGNUM *in_kinv, const BIGNUM *in_r,
163                                EC_KEY *eckey)
164 {
165     int ok = 0, i;
166     BIGNUM *kinv = NULL, *s, *m = NULL;
167     const BIGNUM *order, *ckinv;
168     BN_CTX *ctx = NULL;
169     const EC_GROUP *group;
170     ECDSA_SIG *ret;
171     const BIGNUM *priv_key;
172
173     group = EC_KEY_get0_group(eckey);
174     priv_key = EC_KEY_get0_private_key(eckey);
175
176     if (group == NULL || priv_key == NULL) {
177         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_PASSED_NULL_PARAMETER);
178         return NULL;
179     }
180
181     if (!EC_KEY_can_sign(eckey)) {
182         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
183         return NULL;
184     }
185
186     ret = ECDSA_SIG_new();
187     if (ret == NULL) {
188         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
189         return NULL;
190     }
191     ret->r = BN_new();
192     ret->s = BN_new();
193     if (ret->r == NULL || ret->s == NULL) {
194         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
195         goto err;
196     }
197     s = ret->s;
198
199     if ((ctx = BN_CTX_new()) == NULL
200         || (m = BN_new()) == NULL) {
201         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
202         goto err;
203     }
204
205     order = EC_GROUP_get0_order(group);
206     i = BN_num_bits(order);
207     /*
208      * Need to truncate digest if it is too long: first truncate whole bytes.
209      */
210     if (8 * dgst_len > i)
211         dgst_len = (i + 7) / 8;
212     if (!BN_bin2bn(dgst, dgst_len, m)) {
213         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
214         goto err;
215     }
216     /* If still too long, truncate remaining bits with a shift */
217     if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
218         ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
219         goto err;
220     }
221     do {
222         if (in_kinv == NULL || in_r == NULL) {
223             if (!ecdsa_sign_setup(eckey, ctx, &kinv, &ret->r, dgst, dgst_len)) {
224                 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_ECDSA_LIB);
225                 goto err;
226             }
227             ckinv = kinv;
228         } else {
229             ckinv = in_kinv;
230             if (BN_copy(ret->r, in_r) == NULL) {
231                 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_MALLOC_FAILURE);
232                 goto err;
233             }
234         }
235
236         /*
237          * With only one multiplicant being in Montgomery domain
238          * multiplication yields real result without post-conversion.
239          * Also note that all operations but last are performed with
240          * zero-padded vectors. Last operation, BN_mod_mul_montgomery
241          * below, returns user-visible value with removed zero padding.
242          */
243         if (!bn_to_mont_fixed_top(s, ret->r, group->mont_data, ctx)
244             || !bn_mul_mont_fixed_top(s, s, priv_key, group->mont_data, ctx)) {
245             ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
246             goto err;
247         }
248         if (!bn_mod_add_fixed_top(s, s, m, order)) {
249             ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
250             goto err;
251         }
252         /*
253          * |s| can still be larger than modulus, because |m| can be. In
254          * such case we count on Montgomery reduction to tie it up.
255          */
256         if (!bn_to_mont_fixed_top(s, s, group->mont_data, ctx)
257             || !BN_mod_mul_montgomery(s, s, ckinv, group->mont_data, ctx)) {
258             ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, ERR_R_BN_LIB);
259             goto err;
260         }
261
262         if (BN_is_zero(s)) {
263             /*
264              * if kinv and r have been supplied by the caller, don't
265              * generate new kinv and r values
266              */
267             if (in_kinv != NULL && in_r != NULL) {
268                 ECerr(EC_F_OSSL_ECDSA_SIGN_SIG, EC_R_NEED_NEW_SETUP_VALUES);
269                 goto err;
270             }
271         } else {
272             /* s != 0 => we have a valid signature */
273             break;
274         }
275     } while (1);
276
277     ok = 1;
278  err:
279     if (!ok) {
280         ECDSA_SIG_free(ret);
281         ret = NULL;
282     }
283     BN_CTX_free(ctx);
284     BN_clear_free(m);
285     BN_clear_free(kinv);
286     return ret;
287 }
288
289 /*-
290  * returns
291  *      1: correct signature
292  *      0: incorrect signature
293  *     -1: error
294  */
295 int ossl_ecdsa_verify(int type, const unsigned char *dgst, int dgst_len,
296                       const unsigned char *sigbuf, int sig_len, EC_KEY *eckey)
297 {
298     ECDSA_SIG *s;
299     const unsigned char *p = sigbuf;
300     unsigned char *der = NULL;
301     int derlen = -1;
302     int ret = -1;
303
304     s = ECDSA_SIG_new();
305     if (s == NULL)
306         return ret;
307     if (d2i_ECDSA_SIG(&s, &p, sig_len) == NULL)
308         goto err;
309     /* Ensure signature uses DER and doesn't have trailing garbage */
310     derlen = i2d_ECDSA_SIG(s, &der);
311     if (derlen != sig_len || memcmp(sigbuf, der, derlen) != 0)
312         goto err;
313     ret = ECDSA_do_verify(dgst, dgst_len, s, eckey);
314  err:
315     OPENSSL_clear_free(der, derlen);
316     ECDSA_SIG_free(s);
317     return ret;
318 }
319
320 int ossl_ecdsa_verify_sig(const unsigned char *dgst, int dgst_len,
321                           const ECDSA_SIG *sig, EC_KEY *eckey)
322 {
323     int ret = -1, i;
324     BN_CTX *ctx;
325     const BIGNUM *order;
326     BIGNUM *u1, *u2, *m, *X;
327     EC_POINT *point = NULL;
328     const EC_GROUP *group;
329     const EC_POINT *pub_key;
330
331     /* check input values */
332     if (eckey == NULL || (group = EC_KEY_get0_group(eckey)) == NULL ||
333         (pub_key = EC_KEY_get0_public_key(eckey)) == NULL || sig == NULL) {
334         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_MISSING_PARAMETERS);
335         return -1;
336     }
337
338     if (!EC_KEY_can_sign(eckey)) {
339         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_CURVE_DOES_NOT_SUPPORT_SIGNING);
340         return -1;
341     }
342
343     ctx = BN_CTX_new();
344     if (ctx == NULL) {
345         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_MALLOC_FAILURE);
346         return -1;
347     }
348     BN_CTX_start(ctx);
349     u1 = BN_CTX_get(ctx);
350     u2 = BN_CTX_get(ctx);
351     m = BN_CTX_get(ctx);
352     X = BN_CTX_get(ctx);
353     if (X == NULL) {
354         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
355         goto err;
356     }
357
358     order = EC_GROUP_get0_order(group);
359     if (order == NULL) {
360         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
361         goto err;
362     }
363
364     if (BN_is_zero(sig->r) || BN_is_negative(sig->r) ||
365         BN_ucmp(sig->r, order) >= 0 || BN_is_zero(sig->s) ||
366         BN_is_negative(sig->s) || BN_ucmp(sig->s, order) >= 0) {
367         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, EC_R_BAD_SIGNATURE);
368         ret = 0;                /* signature is invalid */
369         goto err;
370     }
371     /* calculate tmp1 = inv(S) mod order */
372     if (!ec_group_do_inverse_ord(group, u2, sig->s, ctx)) {
373         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
374         goto err;
375     }
376     /* digest -> m */
377     i = BN_num_bits(order);
378     /*
379      * Need to truncate digest if it is too long: first truncate whole bytes.
380      */
381     if (8 * dgst_len > i)
382         dgst_len = (i + 7) / 8;
383     if (!BN_bin2bn(dgst, dgst_len, m)) {
384         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
385         goto err;
386     }
387     /* If still too long truncate remaining bits with a shift */
388     if ((8 * dgst_len > i) && !BN_rshift(m, m, 8 - (i & 0x7))) {
389         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
390         goto err;
391     }
392     /* u1 = m * tmp mod order */
393     if (!BN_mod_mul(u1, m, u2, order, ctx)) {
394         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
395         goto err;
396     }
397     /* u2 = r * w mod q */
398     if (!BN_mod_mul(u2, sig->r, u2, order, ctx)) {
399         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
400         goto err;
401     }
402
403     if ((point = EC_POINT_new(group)) == NULL) {
404         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_MALLOC_FAILURE);
405         goto err;
406     }
407     if (!EC_POINT_mul(group, point, u1, pub_key, u2, ctx)) {
408         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
409         goto err;
410     }
411     if (EC_METHOD_get_field_type(EC_GROUP_method_of(group)) ==
412         NID_X9_62_prime_field) {
413         if (!EC_POINT_get_affine_coordinates_GFp(group, point, X, NULL, ctx)) {
414             ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
415             goto err;
416         }
417     }
418 #ifndef OPENSSL_NO_EC2M
419     else {                      /* NID_X9_62_characteristic_two_field */
420
421         if (!EC_POINT_get_affine_coordinates_GF2m(group, point, X, NULL, ctx)) {
422             ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_EC_LIB);
423             goto err;
424         }
425     }
426 #endif
427     if (!BN_nnmod(u1, X, order, ctx)) {
428         ECerr(EC_F_OSSL_ECDSA_VERIFY_SIG, ERR_R_BN_LIB);
429         goto err;
430     }
431     /*  if the signature is correct u1 is equal to sig->r */
432     ret = (BN_ucmp(u1, sig->r) == 0);
433  err:
434     BN_CTX_end(ctx);
435     BN_CTX_free(ctx);
436     EC_POINT_free(point);
437     return ret;
438 }