1 /*
2  * Copyright 2001-2019 The OpenSSL Project Authors. All Rights Reserved.
3  * Copyright (c) 2002, Oracle and/or its affiliates. All rights reserved
4  *
5  * Licensed under the OpenSSL license (the "License").  You may not use
6  * this file except in compliance with the License.  You can obtain a copy
7  * in the file LICENSE in the source distribution or at
8  * https://www.openssl.org/source/license.html
9  */
10 
11 #include <openssl/err.h>
12 
13 #include "ec_local.h"
14 
EC_GFp_mont_method(void)15 const EC_METHOD *EC_GFp_mont_method(void)
16 {
17     static const EC_METHOD ret = {
18         EC_FLAGS_DEFAULT_OCT,
19         NID_X9_62_prime_field,
20         ec_GFp_mont_group_init,
21         ec_GFp_mont_group_finish,
22         ec_GFp_mont_group_clear_finish,
23         ec_GFp_mont_group_copy,
24         ec_GFp_mont_group_set_curve,
25         ec_GFp_simple_group_get_curve,
26         ec_GFp_simple_group_get_degree,
27         ec_group_simple_order_bits,
28         ec_GFp_simple_group_check_discriminant,
29         ec_GFp_simple_point_init,
30         ec_GFp_simple_point_finish,
31         ec_GFp_simple_point_clear_finish,
32         ec_GFp_simple_point_copy,
33         ec_GFp_simple_point_set_to_infinity,
34         ec_GFp_simple_set_Jprojective_coordinates_GFp,
35         ec_GFp_simple_get_Jprojective_coordinates_GFp,
36         ec_GFp_simple_point_set_affine_coordinates,
37         ec_GFp_simple_point_get_affine_coordinates,
38         0, 0, 0,
39         ec_GFp_simple_add,
40         ec_GFp_simple_dbl,
41         ec_GFp_simple_invert,
42         ec_GFp_simple_is_at_infinity,
43         ec_GFp_simple_is_on_curve,
44         ec_GFp_simple_cmp,
45         ec_GFp_simple_make_affine,
46         ec_GFp_simple_points_make_affine,
47         0 /* mul */ ,
48         0 /* precompute_mult */ ,
49         0 /* have_precompute_mult */ ,
50         ec_GFp_mont_field_mul,
51         ec_GFp_mont_field_sqr,
52         0 /* field_div */ ,
53         ec_GFp_mont_field_inv,
54         ec_GFp_mont_field_encode,
55         ec_GFp_mont_field_decode,
56         ec_GFp_mont_field_set_to_one,
57         ec_key_simple_priv2oct,
58         ec_key_simple_oct2priv,
59         0, /* set private */
60         ec_key_simple_generate_key,
61         ec_key_simple_check_key,
62         ec_key_simple_generate_public_key,
63         0, /* keycopy */
64         0, /* keyfinish */
65         ecdh_simple_compute_key,
66         0, /* field_inverse_mod_ord */
67         ec_GFp_simple_blind_coordinates,
68         ec_GFp_simple_ladder_pre,
69         ec_GFp_simple_ladder_step,
70         ec_GFp_simple_ladder_post
71     };
72 
73     return &ret;
74 }
75 
ec_GFp_mont_group_init(EC_GROUP * group)76 int ec_GFp_mont_group_init(EC_GROUP *group)
77 {
78     int ok;
79 
80     ok = ec_GFp_simple_group_init(group);
81     group->field_data1 = NULL;
82     group->field_data2 = NULL;
83     return ok;
84 }
85 
ec_GFp_mont_group_finish(EC_GROUP * group)86 void ec_GFp_mont_group_finish(EC_GROUP *group)
87 {
88     BN_MONT_CTX_free(group->field_data1);
89     group->field_data1 = NULL;
90     BN_free(group->field_data2);
91     group->field_data2 = NULL;
92     ec_GFp_simple_group_finish(group);
93 }
94 
ec_GFp_mont_group_clear_finish(EC_GROUP * group)95 void ec_GFp_mont_group_clear_finish(EC_GROUP *group)
96 {
97     BN_MONT_CTX_free(group->field_data1);
98     group->field_data1 = NULL;
99     BN_clear_free(group->field_data2);
100     group->field_data2 = NULL;
101     ec_GFp_simple_group_clear_finish(group);
102 }
103 
ec_GFp_mont_group_copy(EC_GROUP * dest,const EC_GROUP * src)104 int ec_GFp_mont_group_copy(EC_GROUP *dest, const EC_GROUP *src)
105 {
106     BN_MONT_CTX_free(dest->field_data1);
107     dest->field_data1 = NULL;
108     BN_clear_free(dest->field_data2);
109     dest->field_data2 = NULL;
110 
111     if (!ec_GFp_simple_group_copy(dest, src))
112         return 0;
113 
114     if (src->field_data1 != NULL) {
115         dest->field_data1 = BN_MONT_CTX_new();
116         if (dest->field_data1 == NULL)
117             return 0;
118         if (!BN_MONT_CTX_copy(dest->field_data1, src->field_data1))
119             goto err;
120     }
121     if (src->field_data2 != NULL) {
122         dest->field_data2 = BN_dup(src->field_data2);
123         if (dest->field_data2 == NULL)
124             goto err;
125     }
126 
127     return 1;
128 
129  err:
130     BN_MONT_CTX_free(dest->field_data1);
131     dest->field_data1 = NULL;
132     return 0;
133 }
134 
ec_GFp_mont_group_set_curve(EC_GROUP * group,const BIGNUM * p,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)135 int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p,
136                                 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
137 {
138     BN_CTX *new_ctx = NULL;
139     BN_MONT_CTX *mont = NULL;
140     BIGNUM *one = NULL;
141     int ret = 0;
142 
143     BN_MONT_CTX_free(group->field_data1);
144     group->field_data1 = NULL;
145     BN_free(group->field_data2);
146     group->field_data2 = NULL;
147 
148     if (ctx == NULL) {
149         ctx = new_ctx = BN_CTX_new();
150         if (ctx == NULL)
151             return 0;
152     }
153 
154     mont = BN_MONT_CTX_new();
155     if (mont == NULL)
156         goto err;
157     if (!BN_MONT_CTX_set(mont, p, ctx)) {
158         ECerr(EC_F_EC_GFP_MONT_GROUP_SET_CURVE, ERR_R_BN_LIB);
159         goto err;
160     }
161     one = BN_new();
162     if (one == NULL)
163         goto err;
164     if (!BN_to_montgomery(one, BN_value_one(), mont, ctx))
165         goto err;
166 
167     group->field_data1 = mont;
168     mont = NULL;
169     group->field_data2 = one;
170     one = NULL;
171 
172     ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
173 
174     if (!ret) {
175         BN_MONT_CTX_free(group->field_data1);
176         group->field_data1 = NULL;
177         BN_free(group->field_data2);
178         group->field_data2 = NULL;
179     }
180 
181  err:
182     BN_free(one);
183     BN_CTX_free(new_ctx);
184     BN_MONT_CTX_free(mont);
185     return ret;
186 }
187 
ec_GFp_mont_field_mul(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,const BIGNUM * b,BN_CTX * ctx)188 int ec_GFp_mont_field_mul(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
189                           const BIGNUM *b, BN_CTX *ctx)
190 {
191     if (group->field_data1 == NULL) {
192         ECerr(EC_F_EC_GFP_MONT_FIELD_MUL, EC_R_NOT_INITIALIZED);
193         return 0;
194     }
195 
196     return BN_mod_mul_montgomery(r, a, b, group->field_data1, ctx);
197 }
198 
ec_GFp_mont_field_sqr(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)199 int ec_GFp_mont_field_sqr(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
200                           BN_CTX *ctx)
201 {
202     if (group->field_data1 == NULL) {
203         ECerr(EC_F_EC_GFP_MONT_FIELD_SQR, EC_R_NOT_INITIALIZED);
204         return 0;
205     }
206 
207     return BN_mod_mul_montgomery(r, a, a, group->field_data1, ctx);
208 }
209 
210 /*-
211  * Computes the multiplicative inverse of a in GF(p), storing the result in r.
212  * If a is zero (or equivalent), you'll get a EC_R_CANNOT_INVERT error.
213  * We have a Mont structure, so SCA hardening is FLT inversion.
214  */
ec_GFp_mont_field_inv(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)215 int ec_GFp_mont_field_inv(const EC_GROUP *group, BIGNUM *r, const BIGNUM *a,
216                             BN_CTX *ctx)
217 {
218     BIGNUM *e = NULL;
219     BN_CTX *new_ctx = NULL;
220     int ret = 0;
221 
222     if (group->field_data1 == NULL)
223         return 0;
224 
225     if (ctx == NULL && (ctx = new_ctx = BN_CTX_secure_new()) == NULL)
226         return 0;
227 
228     BN_CTX_start(ctx);
229     if ((e = BN_CTX_get(ctx)) == NULL)
230         goto err;
231 
232     /* Inverse in constant time with Fermats Little Theorem */
233     if (!BN_set_word(e, 2))
234         goto err;
235     if (!BN_sub(e, group->field, e))
236         goto err;
237     /*-
238      * Exponent e is public.
239      * No need for scatter-gather or BN_FLG_CONSTTIME.
240      */
241     if (!BN_mod_exp_mont(r, a, e, group->field, ctx, group->field_data1))
242         goto err;
243 
244     /* throw an error on zero */
245     if (BN_is_zero(r)) {
246         ECerr(EC_F_EC_GFP_MONT_FIELD_INV, EC_R_CANNOT_INVERT);
247         goto err;
248     }
249 
250     ret = 1;
251 
252   err:
253     BN_CTX_end(ctx);
254     BN_CTX_free(new_ctx);
255     return ret;
256 }
257 
ec_GFp_mont_field_encode(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)258 int ec_GFp_mont_field_encode(const EC_GROUP *group, BIGNUM *r,
259                              const BIGNUM *a, BN_CTX *ctx)
260 {
261     if (group->field_data1 == NULL) {
262         ECerr(EC_F_EC_GFP_MONT_FIELD_ENCODE, EC_R_NOT_INITIALIZED);
263         return 0;
264     }
265 
266     return BN_to_montgomery(r, a, (BN_MONT_CTX *)group->field_data1, ctx);
267 }
268 
ec_GFp_mont_field_decode(const EC_GROUP * group,BIGNUM * r,const BIGNUM * a,BN_CTX * ctx)269 int ec_GFp_mont_field_decode(const EC_GROUP *group, BIGNUM *r,
270                              const BIGNUM *a, BN_CTX *ctx)
271 {
272     if (group->field_data1 == NULL) {
273         ECerr(EC_F_EC_GFP_MONT_FIELD_DECODE, EC_R_NOT_INITIALIZED);
274         return 0;
275     }
276 
277     return BN_from_montgomery(r, a, group->field_data1, ctx);
278 }
279 
ec_GFp_mont_field_set_to_one(const EC_GROUP * group,BIGNUM * r,BN_CTX * ctx)280 int ec_GFp_mont_field_set_to_one(const EC_GROUP *group, BIGNUM *r,
281                                  BN_CTX *ctx)
282 {
283     if (group->field_data2 == NULL) {
284         ECerr(EC_F_EC_GFP_MONT_FIELD_SET_TO_ONE, EC_R_NOT_INITIALIZED);
285         return 0;
286     }
287 
288     if (!BN_copy(r, group->field_data2))
289         return 0;
290     return 1;
291 }
292