1 |
|
|
/* $OpenBSD: ecp_smpl.c,v 1.15 2015/02/09 15:49:22 jsing Exp $ */ |
2 |
|
|
/* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de> |
3 |
|
|
* for the OpenSSL project. |
4 |
|
|
* Includes code written by Bodo Moeller for the OpenSSL project. |
5 |
|
|
*/ |
6 |
|
|
/* ==================================================================== |
7 |
|
|
* Copyright (c) 1998-2002 The OpenSSL Project. All rights reserved. |
8 |
|
|
* |
9 |
|
|
* Redistribution and use in source and binary forms, with or without |
10 |
|
|
* modification, are permitted provided that the following conditions |
11 |
|
|
* are met: |
12 |
|
|
* |
13 |
|
|
* 1. Redistributions of source code must retain the above copyright |
14 |
|
|
* notice, this list of conditions and the following disclaimer. |
15 |
|
|
* |
16 |
|
|
* 2. Redistributions in binary form must reproduce the above copyright |
17 |
|
|
* notice, this list of conditions and the following disclaimer in |
18 |
|
|
* the documentation and/or other materials provided with the |
19 |
|
|
* distribution. |
20 |
|
|
* |
21 |
|
|
* 3. All advertising materials mentioning features or use of this |
22 |
|
|
* software must display the following acknowledgment: |
23 |
|
|
* "This product includes software developed by the OpenSSL Project |
24 |
|
|
* for use in the OpenSSL Toolkit. (http://www.openssl.org/)" |
25 |
|
|
* |
26 |
|
|
* 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to |
27 |
|
|
* endorse or promote products derived from this software without |
28 |
|
|
* prior written permission. For written permission, please contact |
29 |
|
|
* openssl-core@openssl.org. |
30 |
|
|
* |
31 |
|
|
* 5. Products derived from this software may not be called "OpenSSL" |
32 |
|
|
* nor may "OpenSSL" appear in their names without prior written |
33 |
|
|
* permission of the OpenSSL Project. |
34 |
|
|
* |
35 |
|
|
* 6. Redistributions of any form whatsoever must retain the following |
36 |
|
|
* acknowledgment: |
37 |
|
|
* "This product includes software developed by the OpenSSL Project |
38 |
|
|
* for use in the OpenSSL Toolkit (http://www.openssl.org/)" |
39 |
|
|
* |
40 |
|
|
* THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY |
41 |
|
|
* EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
42 |
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
43 |
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR |
44 |
|
|
* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
45 |
|
|
* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
46 |
|
|
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
47 |
|
|
* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
48 |
|
|
* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
49 |
|
|
* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
50 |
|
|
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED |
51 |
|
|
* OF THE POSSIBILITY OF SUCH DAMAGE. |
52 |
|
|
* ==================================================================== |
53 |
|
|
* |
54 |
|
|
* This product includes cryptographic software written by Eric Young |
55 |
|
|
* (eay@cryptsoft.com). This product includes software written by Tim |
56 |
|
|
* Hudson (tjh@cryptsoft.com). |
57 |
|
|
* |
58 |
|
|
*/ |
59 |
|
|
/* ==================================================================== |
60 |
|
|
* Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED. |
61 |
|
|
* Portions of this software developed by SUN MICROSYSTEMS, INC., |
62 |
|
|
* and contributed to the OpenSSL project. |
63 |
|
|
*/ |
64 |
|
|
|
65 |
|
|
#include <openssl/err.h> |
66 |
|
|
|
67 |
|
|
#include "ec_lcl.h" |
68 |
|
|
|
69 |
|
|
const EC_METHOD * |
70 |
|
|
EC_GFp_simple_method(void) |
71 |
|
|
{ |
72 |
|
|
static const EC_METHOD ret = { |
73 |
|
|
.flags = EC_FLAGS_DEFAULT_OCT, |
74 |
|
|
.field_type = NID_X9_62_prime_field, |
75 |
|
|
.group_init = ec_GFp_simple_group_init, |
76 |
|
|
.group_finish = ec_GFp_simple_group_finish, |
77 |
|
|
.group_clear_finish = ec_GFp_simple_group_clear_finish, |
78 |
|
|
.group_copy = ec_GFp_simple_group_copy, |
79 |
|
|
.group_set_curve = ec_GFp_simple_group_set_curve, |
80 |
|
|
.group_get_curve = ec_GFp_simple_group_get_curve, |
81 |
|
|
.group_get_degree = ec_GFp_simple_group_get_degree, |
82 |
|
|
.group_check_discriminant = |
83 |
|
|
ec_GFp_simple_group_check_discriminant, |
84 |
|
|
.point_init = ec_GFp_simple_point_init, |
85 |
|
|
.point_finish = ec_GFp_simple_point_finish, |
86 |
|
|
.point_clear_finish = ec_GFp_simple_point_clear_finish, |
87 |
|
|
.point_copy = ec_GFp_simple_point_copy, |
88 |
|
|
.point_set_to_infinity = ec_GFp_simple_point_set_to_infinity, |
89 |
|
|
.point_set_Jprojective_coordinates_GFp = |
90 |
|
|
ec_GFp_simple_set_Jprojective_coordinates_GFp, |
91 |
|
|
.point_get_Jprojective_coordinates_GFp = |
92 |
|
|
ec_GFp_simple_get_Jprojective_coordinates_GFp, |
93 |
|
|
.point_set_affine_coordinates = |
94 |
|
|
ec_GFp_simple_point_set_affine_coordinates, |
95 |
|
|
.point_get_affine_coordinates = |
96 |
|
|
ec_GFp_simple_point_get_affine_coordinates, |
97 |
|
|
.add = ec_GFp_simple_add, |
98 |
|
|
.dbl = ec_GFp_simple_dbl, |
99 |
|
|
.invert = ec_GFp_simple_invert, |
100 |
|
|
.is_at_infinity = ec_GFp_simple_is_at_infinity, |
101 |
|
|
.is_on_curve = ec_GFp_simple_is_on_curve, |
102 |
|
|
.point_cmp = ec_GFp_simple_cmp, |
103 |
|
|
.make_affine = ec_GFp_simple_make_affine, |
104 |
|
|
.points_make_affine = ec_GFp_simple_points_make_affine, |
105 |
|
|
.field_mul = ec_GFp_simple_field_mul, |
106 |
|
|
.field_sqr = ec_GFp_simple_field_sqr |
107 |
|
|
}; |
108 |
|
|
|
109 |
|
|
return &ret; |
110 |
|
|
} |
111 |
|
|
|
112 |
|
|
|
113 |
|
|
/* Most method functions in this file are designed to work with |
114 |
|
|
* non-trivial representations of field elements if necessary |
115 |
|
|
* (see ecp_mont.c): while standard modular addition and subtraction |
116 |
|
|
* are used, the field_mul and field_sqr methods will be used for |
117 |
|
|
* multiplication, and field_encode and field_decode (if defined) |
118 |
|
|
* will be used for converting between representations. |
119 |
|
|
|
120 |
|
|
* Functions ec_GFp_simple_points_make_affine() and |
121 |
|
|
* ec_GFp_simple_point_get_affine_coordinates() specifically assume |
122 |
|
|
* that if a non-trivial representation is used, it is a Montgomery |
123 |
|
|
* representation (i.e. 'encoding' means multiplying by some factor R). |
124 |
|
|
*/ |
125 |
|
|
|
126 |
|
|
|
127 |
|
|
int |
128 |
|
|
ec_GFp_simple_group_init(EC_GROUP * group) |
129 |
|
262 |
{ |
130 |
|
262 |
BN_init(&group->field); |
131 |
|
262 |
BN_init(&group->a); |
132 |
|
262 |
BN_init(&group->b); |
133 |
|
262 |
group->a_is_minus3 = 0; |
134 |
|
262 |
return 1; |
135 |
|
|
} |
136 |
|
|
|
137 |
|
|
|
138 |
|
|
void |
139 |
|
|
ec_GFp_simple_group_finish(EC_GROUP * group) |
140 |
|
258 |
{ |
141 |
|
258 |
BN_free(&group->field); |
142 |
|
258 |
BN_free(&group->a); |
143 |
|
258 |
BN_free(&group->b); |
144 |
|
258 |
} |
145 |
|
|
|
146 |
|
|
|
147 |
|
|
void |
148 |
|
|
ec_GFp_simple_group_clear_finish(EC_GROUP * group) |
149 |
|
|
{ |
150 |
|
|
BN_clear_free(&group->field); |
151 |
|
|
BN_clear_free(&group->a); |
152 |
|
|
BN_clear_free(&group->b); |
153 |
|
|
} |
154 |
|
|
|
155 |
|
|
|
156 |
|
|
int |
157 |
|
|
ec_GFp_simple_group_copy(EC_GROUP * dest, const EC_GROUP * src) |
158 |
|
103 |
{ |
159 |
✗✓ |
103 |
if (!BN_copy(&dest->field, &src->field)) |
160 |
|
|
return 0; |
161 |
✗✓ |
103 |
if (!BN_copy(&dest->a, &src->a)) |
162 |
|
|
return 0; |
163 |
✗✓ |
103 |
if (!BN_copy(&dest->b, &src->b)) |
164 |
|
|
return 0; |
165 |
|
|
|
166 |
|
103 |
dest->a_is_minus3 = src->a_is_minus3; |
167 |
|
|
|
168 |
|
103 |
return 1; |
169 |
|
|
} |
170 |
|
|
|
171 |
|
|
|
172 |
|
|
int |
173 |
|
|
ec_GFp_simple_group_set_curve(EC_GROUP * group, |
174 |
|
|
const BIGNUM * p, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx) |
175 |
|
165 |
{ |
176 |
|
165 |
int ret = 0; |
177 |
|
165 |
BN_CTX *new_ctx = NULL; |
178 |
|
|
BIGNUM *tmp_a; |
179 |
|
|
|
180 |
|
|
/* p must be a prime > 3 */ |
181 |
✓✗✓✗
✗✓ |
165 |
if (BN_num_bits(p) <= 2 || !BN_is_odd(p)) { |
182 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_GROUP_SET_CURVE, EC_R_INVALID_FIELD); |
183 |
|
|
return 0; |
184 |
|
|
} |
185 |
✗✓ |
165 |
if (ctx == NULL) { |
186 |
|
|
ctx = new_ctx = BN_CTX_new(); |
187 |
|
|
if (ctx == NULL) |
188 |
|
|
return 0; |
189 |
|
|
} |
190 |
|
165 |
BN_CTX_start(ctx); |
191 |
✗✓ |
165 |
if ((tmp_a = BN_CTX_get(ctx)) == NULL) |
192 |
|
|
goto err; |
193 |
|
|
|
194 |
|
|
/* group->field */ |
195 |
✗✓ |
165 |
if (!BN_copy(&group->field, p)) |
196 |
|
|
goto err; |
197 |
|
165 |
BN_set_negative(&group->field, 0); |
198 |
|
|
|
199 |
|
|
/* group->a */ |
200 |
✗✓ |
165 |
if (!BN_nnmod(tmp_a, a, p, ctx)) |
201 |
|
|
goto err; |
202 |
✓✗ |
165 |
if (group->meth->field_encode) { |
203 |
✗✓ |
165 |
if (!group->meth->field_encode(group, &group->a, tmp_a, ctx)) |
204 |
|
|
goto err; |
205 |
|
|
} else if (!BN_copy(&group->a, tmp_a)) |
206 |
|
|
goto err; |
207 |
|
|
|
208 |
|
|
/* group->b */ |
209 |
✗✓ |
165 |
if (!BN_nnmod(&group->b, b, p, ctx)) |
210 |
|
|
goto err; |
211 |
✓✗ |
165 |
if (group->meth->field_encode) |
212 |
✗✓ |
165 |
if (!group->meth->field_encode(group, &group->b, &group->b, ctx)) |
213 |
|
|
goto err; |
214 |
|
|
|
215 |
|
|
/* group->a_is_minus3 */ |
216 |
✗✓ |
165 |
if (!BN_add_word(tmp_a, 3)) |
217 |
|
|
goto err; |
218 |
|
165 |
group->a_is_minus3 = (0 == BN_cmp(tmp_a, &group->field)); |
219 |
|
|
|
220 |
|
165 |
ret = 1; |
221 |
|
|
|
222 |
|
165 |
err: |
223 |
|
165 |
BN_CTX_end(ctx); |
224 |
|
165 |
BN_CTX_free(new_ctx); |
225 |
|
165 |
return ret; |
226 |
|
|
} |
227 |
|
|
|
228 |
|
|
|
229 |
|
|
int |
230 |
|
|
ec_GFp_simple_group_get_curve(const EC_GROUP * group, BIGNUM * p, BIGNUM * a, BIGNUM * b, BN_CTX * ctx) |
231 |
|
1 |
{ |
232 |
|
1 |
int ret = 0; |
233 |
|
1 |
BN_CTX *new_ctx = NULL; |
234 |
|
|
|
235 |
✓✗ |
1 |
if (p != NULL) { |
236 |
✗✓ |
1 |
if (!BN_copy(p, &group->field)) |
237 |
|
|
return 0; |
238 |
|
|
} |
239 |
✓✗ |
1 |
if (a != NULL || b != NULL) { |
240 |
✓✗ |
1 |
if (group->meth->field_decode) { |
241 |
✗✓ |
1 |
if (ctx == NULL) { |
242 |
|
|
ctx = new_ctx = BN_CTX_new(); |
243 |
|
|
if (ctx == NULL) |
244 |
|
|
return 0; |
245 |
|
|
} |
246 |
✓✗ |
1 |
if (a != NULL) { |
247 |
✗✓ |
1 |
if (!group->meth->field_decode(group, a, &group->a, ctx)) |
248 |
|
|
goto err; |
249 |
|
|
} |
250 |
✓✗ |
1 |
if (b != NULL) { |
251 |
✗✓ |
1 |
if (!group->meth->field_decode(group, b, &group->b, ctx)) |
252 |
|
|
goto err; |
253 |
|
|
} |
254 |
|
|
} else { |
255 |
|
|
if (a != NULL) { |
256 |
|
|
if (!BN_copy(a, &group->a)) |
257 |
|
|
goto err; |
258 |
|
|
} |
259 |
|
|
if (b != NULL) { |
260 |
|
|
if (!BN_copy(b, &group->b)) |
261 |
|
|
goto err; |
262 |
|
|
} |
263 |
|
|
} |
264 |
|
|
} |
265 |
|
1 |
ret = 1; |
266 |
|
|
|
267 |
|
1 |
err: |
268 |
|
1 |
BN_CTX_free(new_ctx); |
269 |
|
1 |
return ret; |
270 |
|
|
} |
271 |
|
|
|
272 |
|
|
|
273 |
|
|
int |
274 |
|
|
ec_GFp_simple_group_get_degree(const EC_GROUP * group) |
275 |
|
77 |
{ |
276 |
|
77 |
return BN_num_bits(&group->field); |
277 |
|
|
} |
278 |
|
|
|
279 |
|
|
|
280 |
|
|
int |
281 |
|
|
ec_GFp_simple_group_check_discriminant(const EC_GROUP * group, BN_CTX * ctx) |
282 |
|
48 |
{ |
283 |
|
48 |
int ret = 0; |
284 |
|
|
BIGNUM *a, *b, *order, *tmp_1, *tmp_2; |
285 |
|
48 |
const BIGNUM *p = &group->field; |
286 |
|
48 |
BN_CTX *new_ctx = NULL; |
287 |
|
|
|
288 |
✗✓ |
48 |
if (ctx == NULL) { |
289 |
|
|
ctx = new_ctx = BN_CTX_new(); |
290 |
|
|
if (ctx == NULL) { |
291 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_GROUP_CHECK_DISCRIMINANT, ERR_R_MALLOC_FAILURE); |
292 |
|
|
goto err; |
293 |
|
|
} |
294 |
|
|
} |
295 |
|
48 |
BN_CTX_start(ctx); |
296 |
✗✓ |
48 |
if ((a = BN_CTX_get(ctx)) == NULL) |
297 |
|
|
goto err; |
298 |
✗✓ |
48 |
if ((b = BN_CTX_get(ctx)) == NULL) |
299 |
|
|
goto err; |
300 |
✗✓ |
48 |
if ((tmp_1 = BN_CTX_get(ctx)) == NULL) |
301 |
|
|
goto err; |
302 |
✗✓ |
48 |
if ((tmp_2 = BN_CTX_get(ctx)) == NULL) |
303 |
|
|
goto err; |
304 |
✗✓ |
48 |
if ((order = BN_CTX_get(ctx)) == NULL) |
305 |
|
|
goto err; |
306 |
|
|
|
307 |
✓✗ |
48 |
if (group->meth->field_decode) { |
308 |
✗✓ |
48 |
if (!group->meth->field_decode(group, a, &group->a, ctx)) |
309 |
|
|
goto err; |
310 |
✗✓ |
48 |
if (!group->meth->field_decode(group, b, &group->b, ctx)) |
311 |
|
|
goto err; |
312 |
|
|
} else { |
313 |
|
|
if (!BN_copy(a, &group->a)) |
314 |
|
|
goto err; |
315 |
|
|
if (!BN_copy(b, &group->b)) |
316 |
|
|
goto err; |
317 |
|
|
} |
318 |
|
|
|
319 |
|
|
/* |
320 |
|
|
* check the discriminant: y^2 = x^3 + a*x + b is an elliptic curve |
321 |
|
|
* <=> 4*a^3 + 27*b^2 != 0 (mod p) 0 =< a, b < p |
322 |
|
|
*/ |
323 |
✓✓ |
48 |
if (BN_is_zero(a)) { |
324 |
✗✓ |
6 |
if (BN_is_zero(b)) |
325 |
|
|
goto err; |
326 |
✓✗ |
42 |
} else if (!BN_is_zero(b)) { |
327 |
✗✓ |
42 |
if (!BN_mod_sqr(tmp_1, a, p, ctx)) |
328 |
|
|
goto err; |
329 |
✗✓ |
42 |
if (!BN_mod_mul(tmp_2, tmp_1, a, p, ctx)) |
330 |
|
|
goto err; |
331 |
✗✓ |
42 |
if (!BN_lshift(tmp_1, tmp_2, 2)) |
332 |
|
|
goto err; |
333 |
|
|
/* tmp_1 = 4*a^3 */ |
334 |
|
|
|
335 |
✗✓ |
42 |
if (!BN_mod_sqr(tmp_2, b, p, ctx)) |
336 |
|
|
goto err; |
337 |
✗✓ |
42 |
if (!BN_mul_word(tmp_2, 27)) |
338 |
|
|
goto err; |
339 |
|
|
/* tmp_2 = 27*b^2 */ |
340 |
|
|
|
341 |
✗✓ |
42 |
if (!BN_mod_add(a, tmp_1, tmp_2, p, ctx)) |
342 |
|
|
goto err; |
343 |
✗✓ |
42 |
if (BN_is_zero(a)) |
344 |
|
|
goto err; |
345 |
|
|
} |
346 |
|
48 |
ret = 1; |
347 |
|
|
|
348 |
|
48 |
err: |
349 |
✓✗ |
48 |
if (ctx != NULL) |
350 |
|
48 |
BN_CTX_end(ctx); |
351 |
|
48 |
BN_CTX_free(new_ctx); |
352 |
|
48 |
return ret; |
353 |
|
|
} |
354 |
|
|
|
355 |
|
|
|
356 |
|
|
int |
357 |
|
|
ec_GFp_simple_point_init(EC_POINT * point) |
358 |
|
7023 |
{ |
359 |
|
7023 |
BN_init(&point->X); |
360 |
|
7023 |
BN_init(&point->Y); |
361 |
|
7023 |
BN_init(&point->Z); |
362 |
|
7023 |
point->Z_is_one = 0; |
363 |
|
|
|
364 |
|
7023 |
return 1; |
365 |
|
|
} |
366 |
|
|
|
367 |
|
|
|
368 |
|
|
void |
369 |
|
|
ec_GFp_simple_point_finish(EC_POINT * point) |
370 |
|
3206 |
{ |
371 |
|
3206 |
BN_free(&point->X); |
372 |
|
3206 |
BN_free(&point->Y); |
373 |
|
3206 |
BN_free(&point->Z); |
374 |
|
3206 |
} |
375 |
|
|
|
376 |
|
|
|
377 |
|
|
void |
378 |
|
|
ec_GFp_simple_point_clear_finish(EC_POINT * point) |
379 |
|
3809 |
{ |
380 |
|
3809 |
BN_clear_free(&point->X); |
381 |
|
3809 |
BN_clear_free(&point->Y); |
382 |
|
3809 |
BN_clear_free(&point->Z); |
383 |
|
3809 |
point->Z_is_one = 0; |
384 |
|
3809 |
} |
385 |
|
|
|
386 |
|
|
|
387 |
|
|
int |
388 |
|
|
ec_GFp_simple_point_copy(EC_POINT * dest, const EC_POINT * src) |
389 |
|
2686 |
{ |
390 |
✗✓ |
2686 |
if (!BN_copy(&dest->X, &src->X)) |
391 |
|
|
return 0; |
392 |
✗✓ |
2686 |
if (!BN_copy(&dest->Y, &src->Y)) |
393 |
|
|
return 0; |
394 |
✗✓ |
2686 |
if (!BN_copy(&dest->Z, &src->Z)) |
395 |
|
|
return 0; |
396 |
|
2686 |
dest->Z_is_one = src->Z_is_one; |
397 |
|
|
|
398 |
|
2686 |
return 1; |
399 |
|
|
} |
400 |
|
|
|
401 |
|
|
|
402 |
|
|
int |
403 |
|
|
ec_GFp_simple_point_set_to_infinity(const EC_GROUP * group, EC_POINT * point) |
404 |
|
2 |
{ |
405 |
|
2 |
point->Z_is_one = 0; |
406 |
|
2 |
BN_zero(&point->Z); |
407 |
|
2 |
return 1; |
408 |
|
|
} |
409 |
|
|
|
410 |
|
|
|
411 |
|
|
int |
412 |
|
|
ec_GFp_simple_set_Jprojective_coordinates_GFp(const EC_GROUP * group, EC_POINT * point, |
413 |
|
|
const BIGNUM * x, const BIGNUM * y, const BIGNUM * z, BN_CTX * ctx) |
414 |
|
172 |
{ |
415 |
|
172 |
BN_CTX *new_ctx = NULL; |
416 |
|
172 |
int ret = 0; |
417 |
|
|
|
418 |
✗✓ |
172 |
if (ctx == NULL) { |
419 |
|
|
ctx = new_ctx = BN_CTX_new(); |
420 |
|
|
if (ctx == NULL) |
421 |
|
|
return 0; |
422 |
|
|
} |
423 |
✓✗ |
172 |
if (x != NULL) { |
424 |
✗✓ |
172 |
if (!BN_nnmod(&point->X, x, &group->field, ctx)) |
425 |
|
|
goto err; |
426 |
✓✗ |
172 |
if (group->meth->field_encode) { |
427 |
✗✓ |
172 |
if (!group->meth->field_encode(group, &point->X, &point->X, ctx)) |
428 |
|
|
goto err; |
429 |
|
|
} |
430 |
|
|
} |
431 |
✓✗ |
172 |
if (y != NULL) { |
432 |
✗✓ |
172 |
if (!BN_nnmod(&point->Y, y, &group->field, ctx)) |
433 |
|
|
goto err; |
434 |
✓✗ |
172 |
if (group->meth->field_encode) { |
435 |
✗✓ |
172 |
if (!group->meth->field_encode(group, &point->Y, &point->Y, ctx)) |
436 |
|
|
goto err; |
437 |
|
|
} |
438 |
|
|
} |
439 |
✓✗ |
172 |
if (z != NULL) { |
440 |
|
|
int Z_is_one; |
441 |
|
|
|
442 |
✗✓ |
172 |
if (!BN_nnmod(&point->Z, z, &group->field, ctx)) |
443 |
|
|
goto err; |
444 |
✓✗✓✗
✓✗ |
172 |
Z_is_one = BN_is_one(&point->Z); |
445 |
✓✗ |
172 |
if (group->meth->field_encode) { |
446 |
✓✗✓✗
|
172 |
if (Z_is_one && (group->meth->field_set_to_one != 0)) { |
447 |
✗✓ |
172 |
if (!group->meth->field_set_to_one(group, &point->Z, ctx)) |
448 |
|
|
goto err; |
449 |
|
|
} else { |
450 |
|
|
if (!group->meth->field_encode(group, &point->Z, &point->Z, ctx)) |
451 |
|
|
goto err; |
452 |
|
|
} |
453 |
|
|
} |
454 |
|
172 |
point->Z_is_one = Z_is_one; |
455 |
|
|
} |
456 |
|
172 |
ret = 1; |
457 |
|
|
|
458 |
|
172 |
err: |
459 |
|
172 |
BN_CTX_free(new_ctx); |
460 |
|
172 |
return ret; |
461 |
|
|
} |
462 |
|
|
|
463 |
|
|
|
464 |
|
|
int |
465 |
|
|
ec_GFp_simple_get_Jprojective_coordinates_GFp(const EC_GROUP * group, const EC_POINT * point, |
466 |
|
|
BIGNUM * x, BIGNUM * y, BIGNUM * z, BN_CTX * ctx) |
467 |
|
1 |
{ |
468 |
|
1 |
BN_CTX *new_ctx = NULL; |
469 |
|
1 |
int ret = 0; |
470 |
|
|
|
471 |
✓✗ |
1 |
if (group->meth->field_decode != 0) { |
472 |
✗✓ |
1 |
if (ctx == NULL) { |
473 |
|
|
ctx = new_ctx = BN_CTX_new(); |
474 |
|
|
if (ctx == NULL) |
475 |
|
|
return 0; |
476 |
|
|
} |
477 |
✓✗ |
1 |
if (x != NULL) { |
478 |
✗✓ |
1 |
if (!group->meth->field_decode(group, x, &point->X, ctx)) |
479 |
|
|
goto err; |
480 |
|
|
} |
481 |
✓✗ |
1 |
if (y != NULL) { |
482 |
✗✓ |
1 |
if (!group->meth->field_decode(group, y, &point->Y, ctx)) |
483 |
|
|
goto err; |
484 |
|
|
} |
485 |
✓✗ |
1 |
if (z != NULL) { |
486 |
✗✓ |
1 |
if (!group->meth->field_decode(group, z, &point->Z, ctx)) |
487 |
|
|
goto err; |
488 |
|
|
} |
489 |
|
|
} else { |
490 |
|
|
if (x != NULL) { |
491 |
|
|
if (!BN_copy(x, &point->X)) |
492 |
|
|
goto err; |
493 |
|
|
} |
494 |
|
|
if (y != NULL) { |
495 |
|
|
if (!BN_copy(y, &point->Y)) |
496 |
|
|
goto err; |
497 |
|
|
} |
498 |
|
|
if (z != NULL) { |
499 |
|
|
if (!BN_copy(z, &point->Z)) |
500 |
|
|
goto err; |
501 |
|
|
} |
502 |
|
|
} |
503 |
|
|
|
504 |
|
1 |
ret = 1; |
505 |
|
|
|
506 |
|
1 |
err: |
507 |
|
1 |
BN_CTX_free(new_ctx); |
508 |
|
1 |
return ret; |
509 |
|
|
} |
510 |
|
|
|
511 |
|
|
|
512 |
|
|
int |
513 |
|
|
ec_GFp_simple_point_set_affine_coordinates(const EC_GROUP * group, EC_POINT * point, |
514 |
|
|
const BIGNUM * x, const BIGNUM * y, BN_CTX * ctx) |
515 |
|
172 |
{ |
516 |
✗✓ |
172 |
if (x == NULL || y == NULL) { |
517 |
|
|
/* unlike for projective coordinates, we do not tolerate this */ |
518 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_POINT_SET_AFFINE_COORDINATES, ERR_R_PASSED_NULL_PARAMETER); |
519 |
|
|
return 0; |
520 |
|
|
} |
521 |
|
172 |
return EC_POINT_set_Jprojective_coordinates_GFp(group, point, x, y, BN_value_one(), ctx); |
522 |
|
|
} |
523 |
|
|
|
524 |
|
|
|
525 |
|
|
int |
526 |
|
|
ec_GFp_simple_point_get_affine_coordinates(const EC_GROUP * group, const EC_POINT * point, |
527 |
|
|
BIGNUM * x, BIGNUM * y, BN_CTX * ctx) |
528 |
|
299 |
{ |
529 |
|
299 |
BN_CTX *new_ctx = NULL; |
530 |
|
|
BIGNUM *Z, *Z_1, *Z_2, *Z_3; |
531 |
|
|
const BIGNUM *Z_; |
532 |
|
299 |
int ret = 0; |
533 |
|
|
|
534 |
✗✓ |
299 |
if (EC_POINT_is_at_infinity(group, point) > 0) { |
535 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, EC_R_POINT_AT_INFINITY); |
536 |
|
|
return 0; |
537 |
|
|
} |
538 |
✗✓ |
299 |
if (ctx == NULL) { |
539 |
|
|
ctx = new_ctx = BN_CTX_new(); |
540 |
|
|
if (ctx == NULL) |
541 |
|
|
return 0; |
542 |
|
|
} |
543 |
|
299 |
BN_CTX_start(ctx); |
544 |
✗✓ |
299 |
if ((Z = BN_CTX_get(ctx)) == NULL) |
545 |
|
|
goto err; |
546 |
✗✓ |
299 |
if ((Z_1 = BN_CTX_get(ctx)) == NULL) |
547 |
|
|
goto err; |
548 |
✗✓ |
299 |
if ((Z_2 = BN_CTX_get(ctx)) == NULL) |
549 |
|
|
goto err; |
550 |
✗✓ |
299 |
if ((Z_3 = BN_CTX_get(ctx)) == NULL) |
551 |
|
|
goto err; |
552 |
|
|
|
553 |
|
|
/* transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3) */ |
554 |
|
|
|
555 |
✓✗ |
299 |
if (group->meth->field_decode) { |
556 |
✗✓ |
299 |
if (!group->meth->field_decode(group, Z, &point->Z, ctx)) |
557 |
|
|
goto err; |
558 |
|
299 |
Z_ = Z; |
559 |
|
|
} else { |
560 |
|
|
Z_ = &point->Z; |
561 |
|
|
} |
562 |
|
|
|
563 |
✓✓✓✓
✓✗ |
299 |
if (BN_is_one(Z_)) { |
564 |
✓✗ |
10 |
if (group->meth->field_decode) { |
565 |
✓✗ |
10 |
if (x != NULL) { |
566 |
✗✓ |
10 |
if (!group->meth->field_decode(group, x, &point->X, ctx)) |
567 |
|
|
goto err; |
568 |
|
|
} |
569 |
✓✗ |
10 |
if (y != NULL) { |
570 |
✗✓ |
10 |
if (!group->meth->field_decode(group, y, &point->Y, ctx)) |
571 |
|
|
goto err; |
572 |
|
|
} |
573 |
|
|
} else { |
574 |
|
|
if (x != NULL) { |
575 |
|
|
if (!BN_copy(x, &point->X)) |
576 |
|
|
goto err; |
577 |
|
|
} |
578 |
|
|
if (y != NULL) { |
579 |
|
|
if (!BN_copy(y, &point->Y)) |
580 |
|
|
goto err; |
581 |
|
|
} |
582 |
|
|
} |
583 |
|
|
} else { |
584 |
✗✓ |
289 |
if (!BN_mod_inverse(Z_1, Z_, &group->field, ctx)) { |
585 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_POINT_GET_AFFINE_COORDINATES, ERR_R_BN_LIB); |
586 |
|
|
goto err; |
587 |
|
|
} |
588 |
✗✓ |
289 |
if (group->meth->field_encode == 0) { |
589 |
|
|
/* field_sqr works on standard representation */ |
590 |
|
|
if (!group->meth->field_sqr(group, Z_2, Z_1, ctx)) |
591 |
|
|
goto err; |
592 |
|
|
} else { |
593 |
✗✓ |
289 |
if (!BN_mod_sqr(Z_2, Z_1, &group->field, ctx)) |
594 |
|
|
goto err; |
595 |
|
|
} |
596 |
|
|
|
597 |
✓✗ |
289 |
if (x != NULL) { |
598 |
|
|
/* |
599 |
|
|
* in the Montgomery case, field_mul will cancel out |
600 |
|
|
* Montgomery factor in X: |
601 |
|
|
*/ |
602 |
✗✓ |
289 |
if (!group->meth->field_mul(group, x, &point->X, Z_2, ctx)) |
603 |
|
|
goto err; |
604 |
|
|
} |
605 |
✓✓ |
289 |
if (y != NULL) { |
606 |
✗✓ |
35 |
if (group->meth->field_encode == 0) { |
607 |
|
|
/* field_mul works on standard representation */ |
608 |
|
|
if (!group->meth->field_mul(group, Z_3, Z_2, Z_1, ctx)) |
609 |
|
|
goto err; |
610 |
|
|
} else { |
611 |
✗✓ |
35 |
if (!BN_mod_mul(Z_3, Z_2, Z_1, &group->field, ctx)) |
612 |
|
|
goto err; |
613 |
|
|
} |
614 |
|
|
|
615 |
|
|
/* |
616 |
|
|
* in the Montgomery case, field_mul will cancel out |
617 |
|
|
* Montgomery factor in Y: |
618 |
|
|
*/ |
619 |
✗✓ |
35 |
if (!group->meth->field_mul(group, y, &point->Y, Z_3, ctx)) |
620 |
|
|
goto err; |
621 |
|
|
} |
622 |
|
|
} |
623 |
|
|
|
624 |
|
299 |
ret = 1; |
625 |
|
|
|
626 |
|
299 |
err: |
627 |
|
299 |
BN_CTX_end(ctx); |
628 |
|
299 |
BN_CTX_free(new_ctx); |
629 |
|
299 |
return ret; |
630 |
|
|
} |
631 |
|
|
|
632 |
|
|
int |
633 |
|
|
ec_GFp_simple_add(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx) |
634 |
|
41090 |
{ |
635 |
|
|
int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); |
636 |
|
|
int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); |
637 |
|
|
const BIGNUM *p; |
638 |
|
41090 |
BN_CTX *new_ctx = NULL; |
639 |
|
|
BIGNUM *n0, *n1, *n2, *n3, *n4, *n5, *n6; |
640 |
|
41090 |
int ret = 0; |
641 |
|
|
|
642 |
✗✓ |
41090 |
if (a == b) |
643 |
|
|
return EC_POINT_dbl(group, r, a, ctx); |
644 |
✓✓ |
41090 |
if (EC_POINT_is_at_infinity(group, a) > 0) |
645 |
|
887 |
return EC_POINT_copy(r, b); |
646 |
✗✓ |
40203 |
if (EC_POINT_is_at_infinity(group, b) > 0) |
647 |
|
|
return EC_POINT_copy(r, a); |
648 |
|
|
|
649 |
|
40203 |
field_mul = group->meth->field_mul; |
650 |
|
40203 |
field_sqr = group->meth->field_sqr; |
651 |
|
40203 |
p = &group->field; |
652 |
|
|
|
653 |
✗✓ |
40203 |
if (ctx == NULL) { |
654 |
|
|
ctx = new_ctx = BN_CTX_new(); |
655 |
|
|
if (ctx == NULL) |
656 |
|
|
return 0; |
657 |
|
|
} |
658 |
|
40203 |
BN_CTX_start(ctx); |
659 |
✗✓ |
40203 |
if ((n0 = BN_CTX_get(ctx)) == NULL) |
660 |
|
|
goto end; |
661 |
✗✓ |
40203 |
if ((n1 = BN_CTX_get(ctx)) == NULL) |
662 |
|
|
goto end; |
663 |
✗✓ |
40203 |
if ((n2 = BN_CTX_get(ctx)) == NULL) |
664 |
|
|
goto end; |
665 |
✗✓ |
40203 |
if ((n3 = BN_CTX_get(ctx)) == NULL) |
666 |
|
|
goto end; |
667 |
✗✓ |
40203 |
if ((n4 = BN_CTX_get(ctx)) == NULL) |
668 |
|
|
goto end; |
669 |
✗✓ |
40203 |
if ((n5 = BN_CTX_get(ctx)) == NULL) |
670 |
|
|
goto end; |
671 |
✗✓ |
40203 |
if ((n6 = BN_CTX_get(ctx)) == NULL) |
672 |
|
|
goto end; |
673 |
|
|
|
674 |
|
|
/* |
675 |
|
|
* Note that in this function we must not read components of 'a' or |
676 |
|
|
* 'b' once we have written the corresponding components of 'r'. ('r' |
677 |
|
|
* might be one of 'a' or 'b'.) |
678 |
|
|
*/ |
679 |
|
|
|
680 |
|
|
/* n1, n2 */ |
681 |
✓✓ |
40203 |
if (b->Z_is_one) { |
682 |
✗✓ |
35720 |
if (!BN_copy(n1, &a->X)) |
683 |
|
|
goto end; |
684 |
✗✓ |
35720 |
if (!BN_copy(n2, &a->Y)) |
685 |
|
|
goto end; |
686 |
|
|
/* n1 = X_a */ |
687 |
|
|
/* n2 = Y_a */ |
688 |
|
|
} else { |
689 |
✗✓ |
4483 |
if (!field_sqr(group, n0, &b->Z, ctx)) |
690 |
|
|
goto end; |
691 |
✗✓ |
4483 |
if (!field_mul(group, n1, &a->X, n0, ctx)) |
692 |
|
|
goto end; |
693 |
|
|
/* n1 = X_a * Z_b^2 */ |
694 |
|
|
|
695 |
✗✓ |
4483 |
if (!field_mul(group, n0, n0, &b->Z, ctx)) |
696 |
|
|
goto end; |
697 |
✗✓ |
4483 |
if (!field_mul(group, n2, &a->Y, n0, ctx)) |
698 |
|
|
goto end; |
699 |
|
|
/* n2 = Y_a * Z_b^3 */ |
700 |
|
|
} |
701 |
|
|
|
702 |
|
|
/* n3, n4 */ |
703 |
✓✓ |
40203 |
if (a->Z_is_one) { |
704 |
✗✓ |
518 |
if (!BN_copy(n3, &b->X)) |
705 |
|
|
goto end; |
706 |
✗✓ |
518 |
if (!BN_copy(n4, &b->Y)) |
707 |
|
|
goto end; |
708 |
|
|
/* n3 = X_b */ |
709 |
|
|
/* n4 = Y_b */ |
710 |
|
|
} else { |
711 |
✗✓ |
39685 |
if (!field_sqr(group, n0, &a->Z, ctx)) |
712 |
|
|
goto end; |
713 |
✗✓ |
39685 |
if (!field_mul(group, n3, &b->X, n0, ctx)) |
714 |
|
|
goto end; |
715 |
|
|
/* n3 = X_b * Z_a^2 */ |
716 |
|
|
|
717 |
✗✓ |
39685 |
if (!field_mul(group, n0, n0, &a->Z, ctx)) |
718 |
|
|
goto end; |
719 |
✗✓ |
39685 |
if (!field_mul(group, n4, &b->Y, n0, ctx)) |
720 |
|
|
goto end; |
721 |
|
|
/* n4 = Y_b * Z_a^3 */ |
722 |
|
|
} |
723 |
|
|
|
724 |
|
|
/* n5, n6 */ |
725 |
✗✓ |
40203 |
if (!BN_mod_sub_quick(n5, n1, n3, p)) |
726 |
|
|
goto end; |
727 |
✗✓ |
40203 |
if (!BN_mod_sub_quick(n6, n2, n4, p)) |
728 |
|
|
goto end; |
729 |
|
|
/* n5 = n1 - n3 */ |
730 |
|
|
/* n6 = n2 - n4 */ |
731 |
|
|
|
732 |
✓✓ |
40203 |
if (BN_is_zero(n5)) { |
733 |
✓✓ |
145 |
if (BN_is_zero(n6)) { |
734 |
|
|
/* a is the same point as b */ |
735 |
|
4 |
BN_CTX_end(ctx); |
736 |
|
4 |
ret = EC_POINT_dbl(group, r, a, ctx); |
737 |
|
4 |
ctx = NULL; |
738 |
|
4 |
goto end; |
739 |
|
|
} else { |
740 |
|
|
/* a is the inverse of b */ |
741 |
|
141 |
BN_zero(&r->Z); |
742 |
|
141 |
r->Z_is_one = 0; |
743 |
|
141 |
ret = 1; |
744 |
|
141 |
goto end; |
745 |
|
|
} |
746 |
|
|
} |
747 |
|
|
/* 'n7', 'n8' */ |
748 |
✗✓ |
40058 |
if (!BN_mod_add_quick(n1, n1, n3, p)) |
749 |
|
|
goto end; |
750 |
✗✓ |
40058 |
if (!BN_mod_add_quick(n2, n2, n4, p)) |
751 |
|
|
goto end; |
752 |
|
|
/* 'n7' = n1 + n3 */ |
753 |
|
|
/* 'n8' = n2 + n4 */ |
754 |
|
|
|
755 |
|
|
/* Z_r */ |
756 |
✓✓✓✓
|
40058 |
if (a->Z_is_one && b->Z_is_one) { |
757 |
✗✓ |
45 |
if (!BN_copy(&r->Z, n5)) |
758 |
|
|
goto end; |
759 |
|
|
} else { |
760 |
✓✓ |
40013 |
if (a->Z_is_one) { |
761 |
✗✓ |
466 |
if (!BN_copy(n0, &b->Z)) |
762 |
|
|
goto end; |
763 |
✓✓ |
39547 |
} else if (b->Z_is_one) { |
764 |
✗✓ |
35531 |
if (!BN_copy(n0, &a->Z)) |
765 |
|
|
goto end; |
766 |
|
|
} else { |
767 |
✗✓ |
4016 |
if (!field_mul(group, n0, &a->Z, &b->Z, ctx)) |
768 |
|
|
goto end; |
769 |
|
|
} |
770 |
✗✓ |
40013 |
if (!field_mul(group, &r->Z, n0, n5, ctx)) |
771 |
|
|
goto end; |
772 |
|
|
} |
773 |
|
40058 |
r->Z_is_one = 0; |
774 |
|
|
/* Z_r = Z_a * Z_b * n5 */ |
775 |
|
|
|
776 |
|
|
/* X_r */ |
777 |
✗✓ |
40058 |
if (!field_sqr(group, n0, n6, ctx)) |
778 |
|
|
goto end; |
779 |
✗✓ |
40058 |
if (!field_sqr(group, n4, n5, ctx)) |
780 |
|
|
goto end; |
781 |
✗✓ |
40058 |
if (!field_mul(group, n3, n1, n4, ctx)) |
782 |
|
|
goto end; |
783 |
✗✓ |
40058 |
if (!BN_mod_sub_quick(&r->X, n0, n3, p)) |
784 |
|
|
goto end; |
785 |
|
|
/* X_r = n6^2 - n5^2 * 'n7' */ |
786 |
|
|
|
787 |
|
|
/* 'n9' */ |
788 |
✗✓ |
40058 |
if (!BN_mod_lshift1_quick(n0, &r->X, p)) |
789 |
|
|
goto end; |
790 |
✗✓ |
40058 |
if (!BN_mod_sub_quick(n0, n3, n0, p)) |
791 |
|
|
goto end; |
792 |
|
|
/* n9 = n5^2 * 'n7' - 2 * X_r */ |
793 |
|
|
|
794 |
|
|
/* Y_r */ |
795 |
✗✓ |
40058 |
if (!field_mul(group, n0, n0, n6, ctx)) |
796 |
|
|
goto end; |
797 |
✗✓ |
40058 |
if (!field_mul(group, n5, n4, n5, ctx)) |
798 |
|
|
goto end; /* now n5 is n5^3 */ |
799 |
✗✓ |
40058 |
if (!field_mul(group, n1, n2, n5, ctx)) |
800 |
|
|
goto end; |
801 |
✗✓ |
40058 |
if (!BN_mod_sub_quick(n0, n0, n1, p)) |
802 |
|
|
goto end; |
803 |
✓✗✓✓
|
40058 |
if (BN_is_odd(n0)) |
804 |
✗✓ |
19961 |
if (!BN_add(n0, n0, p)) |
805 |
|
|
goto end; |
806 |
|
|
/* now 0 <= n0 < 2*p, and n0 is even */ |
807 |
✗✓ |
40058 |
if (!BN_rshift1(&r->Y, n0)) |
808 |
|
|
goto end; |
809 |
|
|
/* Y_r = (n6 * 'n9' - 'n8' * 'n5^3') / 2 */ |
810 |
|
|
|
811 |
|
40058 |
ret = 1; |
812 |
|
|
|
813 |
|
40203 |
end: |
814 |
✓✓ |
40203 |
if (ctx) /* otherwise we already called BN_CTX_end */ |
815 |
|
40199 |
BN_CTX_end(ctx); |
816 |
|
40203 |
BN_CTX_free(new_ctx); |
817 |
|
40203 |
return ret; |
818 |
|
|
} |
819 |
|
|
|
820 |
|
|
|
821 |
|
|
int |
822 |
|
|
ec_GFp_simple_dbl(const EC_GROUP * group, EC_POINT * r, const EC_POINT * a, BN_CTX * ctx) |
823 |
|
149787 |
{ |
824 |
|
|
int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); |
825 |
|
|
int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); |
826 |
|
|
const BIGNUM *p; |
827 |
|
149787 |
BN_CTX *new_ctx = NULL; |
828 |
|
|
BIGNUM *n0, *n1, *n2, *n3; |
829 |
|
149787 |
int ret = 0; |
830 |
|
|
|
831 |
✓✓ |
149787 |
if (EC_POINT_is_at_infinity(group, a) > 0) { |
832 |
|
7111 |
BN_zero(&r->Z); |
833 |
|
7111 |
r->Z_is_one = 0; |
834 |
|
7111 |
return 1; |
835 |
|
|
} |
836 |
|
142676 |
field_mul = group->meth->field_mul; |
837 |
|
142676 |
field_sqr = group->meth->field_sqr; |
838 |
|
142676 |
p = &group->field; |
839 |
|
|
|
840 |
✗✓ |
142676 |
if (ctx == NULL) { |
841 |
|
|
ctx = new_ctx = BN_CTX_new(); |
842 |
|
|
if (ctx == NULL) |
843 |
|
|
return 0; |
844 |
|
|
} |
845 |
|
142676 |
BN_CTX_start(ctx); |
846 |
✗✓ |
142676 |
if ((n0 = BN_CTX_get(ctx)) == NULL) |
847 |
|
|
goto err; |
848 |
✗✓ |
142676 |
if ((n1 = BN_CTX_get(ctx)) == NULL) |
849 |
|
|
goto err; |
850 |
✗✓ |
142676 |
if ((n2 = BN_CTX_get(ctx)) == NULL) |
851 |
|
|
goto err; |
852 |
✗✓ |
142676 |
if ((n3 = BN_CTX_get(ctx)) == NULL) |
853 |
|
|
goto err; |
854 |
|
|
|
855 |
|
|
/* |
856 |
|
|
* Note that in this function we must not read components of 'a' once |
857 |
|
|
* we have written the corresponding components of 'r'. ('r' might |
858 |
|
|
* the same as 'a'.) |
859 |
|
|
*/ |
860 |
|
|
|
861 |
|
|
/* n1 */ |
862 |
✓✓ |
142676 |
if (a->Z_is_one) { |
863 |
✗✓ |
982 |
if (!field_sqr(group, n0, &a->X, ctx)) |
864 |
|
|
goto err; |
865 |
✗✓ |
982 |
if (!BN_mod_lshift1_quick(n1, n0, p)) |
866 |
|
|
goto err; |
867 |
✗✓ |
982 |
if (!BN_mod_add_quick(n0, n0, n1, p)) |
868 |
|
|
goto err; |
869 |
✗✓ |
982 |
if (!BN_mod_add_quick(n1, n0, &group->a, p)) |
870 |
|
|
goto err; |
871 |
|
|
/* n1 = 3 * X_a^2 + a_curve */ |
872 |
✓✓ |
141694 |
} else if (group->a_is_minus3) { |
873 |
✗✓ |
100868 |
if (!field_sqr(group, n1, &a->Z, ctx)) |
874 |
|
|
goto err; |
875 |
✗✓ |
100868 |
if (!BN_mod_add_quick(n0, &a->X, n1, p)) |
876 |
|
|
goto err; |
877 |
✗✓ |
100868 |
if (!BN_mod_sub_quick(n2, &a->X, n1, p)) |
878 |
|
|
goto err; |
879 |
✗✓ |
100868 |
if (!field_mul(group, n1, n0, n2, ctx)) |
880 |
|
|
goto err; |
881 |
✗✓ |
100868 |
if (!BN_mod_lshift1_quick(n0, n1, p)) |
882 |
|
|
goto err; |
883 |
✗✓ |
100868 |
if (!BN_mod_add_quick(n1, n0, n1, p)) |
884 |
|
|
goto err; |
885 |
|
|
/* |
886 |
|
|
* n1 = 3 * (X_a + Z_a^2) * (X_a - Z_a^2) = 3 * X_a^2 - 3 * |
887 |
|
|
* Z_a^4 |
888 |
|
|
*/ |
889 |
|
|
} else { |
890 |
✗✓ |
40826 |
if (!field_sqr(group, n0, &a->X, ctx)) |
891 |
|
|
goto err; |
892 |
✗✓ |
40826 |
if (!BN_mod_lshift1_quick(n1, n0, p)) |
893 |
|
|
goto err; |
894 |
✗✓ |
40826 |
if (!BN_mod_add_quick(n0, n0, n1, p)) |
895 |
|
|
goto err; |
896 |
✗✓ |
40826 |
if (!field_sqr(group, n1, &a->Z, ctx)) |
897 |
|
|
goto err; |
898 |
✗✓ |
40826 |
if (!field_sqr(group, n1, n1, ctx)) |
899 |
|
|
goto err; |
900 |
✗✓ |
40826 |
if (!field_mul(group, n1, n1, &group->a, ctx)) |
901 |
|
|
goto err; |
902 |
✗✓ |
40826 |
if (!BN_mod_add_quick(n1, n1, n0, p)) |
903 |
|
|
goto err; |
904 |
|
|
/* n1 = 3 * X_a^2 + a_curve * Z_a^4 */ |
905 |
|
|
} |
906 |
|
|
|
907 |
|
|
/* Z_r */ |
908 |
✓✓ |
142676 |
if (a->Z_is_one) { |
909 |
✗✓ |
982 |
if (!BN_copy(n0, &a->Y)) |
910 |
|
|
goto err; |
911 |
|
|
} else { |
912 |
✗✓ |
141694 |
if (!field_mul(group, n0, &a->Y, &a->Z, ctx)) |
913 |
|
|
goto err; |
914 |
|
|
} |
915 |
✗✓ |
142676 |
if (!BN_mod_lshift1_quick(&r->Z, n0, p)) |
916 |
|
|
goto err; |
917 |
|
142676 |
r->Z_is_one = 0; |
918 |
|
|
/* Z_r = 2 * Y_a * Z_a */ |
919 |
|
|
|
920 |
|
|
/* n2 */ |
921 |
✗✓ |
142676 |
if (!field_sqr(group, n3, &a->Y, ctx)) |
922 |
|
|
goto err; |
923 |
✗✓ |
142676 |
if (!field_mul(group, n2, &a->X, n3, ctx)) |
924 |
|
|
goto err; |
925 |
✗✓ |
142676 |
if (!BN_mod_lshift_quick(n2, n2, 2, p)) |
926 |
|
|
goto err; |
927 |
|
|
/* n2 = 4 * X_a * Y_a^2 */ |
928 |
|
|
|
929 |
|
|
/* X_r */ |
930 |
✗✓ |
142676 |
if (!BN_mod_lshift1_quick(n0, n2, p)) |
931 |
|
|
goto err; |
932 |
✗✓ |
142676 |
if (!field_sqr(group, &r->X, n1, ctx)) |
933 |
|
|
goto err; |
934 |
✗✓ |
142676 |
if (!BN_mod_sub_quick(&r->X, &r->X, n0, p)) |
935 |
|
|
goto err; |
936 |
|
|
/* X_r = n1^2 - 2 * n2 */ |
937 |
|
|
|
938 |
|
|
/* n3 */ |
939 |
✗✓ |
142676 |
if (!field_sqr(group, n0, n3, ctx)) |
940 |
|
|
goto err; |
941 |
✗✓ |
142676 |
if (!BN_mod_lshift_quick(n3, n0, 3, p)) |
942 |
|
|
goto err; |
943 |
|
|
/* n3 = 8 * Y_a^4 */ |
944 |
|
|
|
945 |
|
|
/* Y_r */ |
946 |
✗✓ |
142676 |
if (!BN_mod_sub_quick(n0, n2, &r->X, p)) |
947 |
|
|
goto err; |
948 |
✗✓ |
142676 |
if (!field_mul(group, n0, n1, n0, ctx)) |
949 |
|
|
goto err; |
950 |
✗✓ |
142676 |
if (!BN_mod_sub_quick(&r->Y, n0, n3, p)) |
951 |
|
|
goto err; |
952 |
|
|
/* Y_r = n1 * (n2 - X_r) - n3 */ |
953 |
|
|
|
954 |
|
142676 |
ret = 1; |
955 |
|
|
|
956 |
|
142676 |
err: |
957 |
|
142676 |
BN_CTX_end(ctx); |
958 |
|
142676 |
BN_CTX_free(new_ctx); |
959 |
|
142676 |
return ret; |
960 |
|
|
} |
961 |
|
|
|
962 |
|
|
|
963 |
|
|
int |
964 |
|
|
ec_GFp_simple_invert(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx) |
965 |
|
18354 |
{ |
966 |
✓✓✗✓
|
18354 |
if (EC_POINT_is_at_infinity(group, point) > 0 || BN_is_zero(&point->Y)) |
967 |
|
|
/* point is its own inverse */ |
968 |
|
482 |
return 1; |
969 |
|
|
|
970 |
|
17872 |
return BN_usub(&point->Y, &group->field, &point->Y); |
971 |
|
|
} |
972 |
|
|
|
973 |
|
|
|
974 |
|
|
int |
975 |
|
|
ec_GFp_simple_is_at_infinity(const EC_GROUP * group, const EC_POINT * point) |
976 |
|
250167 |
{ |
977 |
|
250167 |
return BN_is_zero(&point->Z); |
978 |
|
|
} |
979 |
|
|
|
980 |
|
|
|
981 |
|
|
int |
982 |
|
|
ec_GFp_simple_is_on_curve(const EC_GROUP * group, const EC_POINT * point, BN_CTX * ctx) |
983 |
|
105 |
{ |
984 |
|
|
int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); |
985 |
|
|
int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); |
986 |
|
|
const BIGNUM *p; |
987 |
|
105 |
BN_CTX *new_ctx = NULL; |
988 |
|
|
BIGNUM *rh, *tmp, *Z4, *Z6; |
989 |
|
105 |
int ret = -1; |
990 |
|
|
|
991 |
✗✓ |
105 |
if (EC_POINT_is_at_infinity(group, point) > 0) |
992 |
|
|
return 1; |
993 |
|
|
|
994 |
|
105 |
field_mul = group->meth->field_mul; |
995 |
|
105 |
field_sqr = group->meth->field_sqr; |
996 |
|
105 |
p = &group->field; |
997 |
|
|
|
998 |
✗✓ |
105 |
if (ctx == NULL) { |
999 |
|
|
ctx = new_ctx = BN_CTX_new(); |
1000 |
|
|
if (ctx == NULL) |
1001 |
|
|
return -1; |
1002 |
|
|
} |
1003 |
|
105 |
BN_CTX_start(ctx); |
1004 |
✗✓ |
105 |
if ((rh = BN_CTX_get(ctx)) == NULL) |
1005 |
|
|
goto err; |
1006 |
✗✓ |
105 |
if ((tmp = BN_CTX_get(ctx)) == NULL) |
1007 |
|
|
goto err; |
1008 |
✗✓ |
105 |
if ((Z4 = BN_CTX_get(ctx)) == NULL) |
1009 |
|
|
goto err; |
1010 |
✗✓ |
105 |
if ((Z6 = BN_CTX_get(ctx)) == NULL) |
1011 |
|
|
goto err; |
1012 |
|
|
|
1013 |
|
|
/* |
1014 |
|
|
* We have a curve defined by a Weierstrass equation y^2 = x^3 + a*x |
1015 |
|
|
* + b. The point to consider is given in Jacobian projective |
1016 |
|
|
* coordinates where (X, Y, Z) represents (x, y) = (X/Z^2, Y/Z^3). |
1017 |
|
|
* Substituting this and multiplying by Z^6 transforms the above |
1018 |
|
|
* equation into Y^2 = X^3 + a*X*Z^4 + b*Z^6. To test this, we add up |
1019 |
|
|
* the right-hand side in 'rh'. |
1020 |
|
|
*/ |
1021 |
|
|
|
1022 |
|
|
/* rh := X^2 */ |
1023 |
✗✓ |
105 |
if (!field_sqr(group, rh, &point->X, ctx)) |
1024 |
|
|
goto err; |
1025 |
|
|
|
1026 |
✓✓ |
105 |
if (!point->Z_is_one) { |
1027 |
✗✓ |
43 |
if (!field_sqr(group, tmp, &point->Z, ctx)) |
1028 |
|
|
goto err; |
1029 |
✗✓ |
43 |
if (!field_sqr(group, Z4, tmp, ctx)) |
1030 |
|
|
goto err; |
1031 |
✗✓ |
43 |
if (!field_mul(group, Z6, Z4, tmp, ctx)) |
1032 |
|
|
goto err; |
1033 |
|
|
|
1034 |
|
|
/* rh := (rh + a*Z^4)*X */ |
1035 |
✓✓ |
43 |
if (group->a_is_minus3) { |
1036 |
✗✓ |
30 |
if (!BN_mod_lshift1_quick(tmp, Z4, p)) |
1037 |
|
|
goto err; |
1038 |
✗✓ |
30 |
if (!BN_mod_add_quick(tmp, tmp, Z4, p)) |
1039 |
|
|
goto err; |
1040 |
✗✓ |
30 |
if (!BN_mod_sub_quick(rh, rh, tmp, p)) |
1041 |
|
|
goto err; |
1042 |
✗✓ |
30 |
if (!field_mul(group, rh, rh, &point->X, ctx)) |
1043 |
|
|
goto err; |
1044 |
|
|
} else { |
1045 |
✗✓ |
13 |
if (!field_mul(group, tmp, Z4, &group->a, ctx)) |
1046 |
|
|
goto err; |
1047 |
✗✓ |
13 |
if (!BN_mod_add_quick(rh, rh, tmp, p)) |
1048 |
|
|
goto err; |
1049 |
✗✓ |
13 |
if (!field_mul(group, rh, rh, &point->X, ctx)) |
1050 |
|
|
goto err; |
1051 |
|
|
} |
1052 |
|
|
|
1053 |
|
|
/* rh := rh + b*Z^6 */ |
1054 |
✗✓ |
43 |
if (!field_mul(group, tmp, &group->b, Z6, ctx)) |
1055 |
|
|
goto err; |
1056 |
✗✓ |
43 |
if (!BN_mod_add_quick(rh, rh, tmp, p)) |
1057 |
|
|
goto err; |
1058 |
|
|
} else { |
1059 |
|
|
/* point->Z_is_one */ |
1060 |
|
|
|
1061 |
|
|
/* rh := (rh + a)*X */ |
1062 |
✗✓ |
62 |
if (!BN_mod_add_quick(rh, rh, &group->a, p)) |
1063 |
|
|
goto err; |
1064 |
✗✓ |
62 |
if (!field_mul(group, rh, rh, &point->X, ctx)) |
1065 |
|
|
goto err; |
1066 |
|
|
/* rh := rh + b */ |
1067 |
✗✓ |
62 |
if (!BN_mod_add_quick(rh, rh, &group->b, p)) |
1068 |
|
|
goto err; |
1069 |
|
|
} |
1070 |
|
|
|
1071 |
|
|
/* 'lh' := Y^2 */ |
1072 |
✗✓ |
105 |
if (!field_sqr(group, tmp, &point->Y, ctx)) |
1073 |
|
|
goto err; |
1074 |
|
|
|
1075 |
|
105 |
ret = (0 == BN_ucmp(tmp, rh)); |
1076 |
|
|
|
1077 |
|
105 |
err: |
1078 |
|
105 |
BN_CTX_end(ctx); |
1079 |
|
105 |
BN_CTX_free(new_ctx); |
1080 |
|
105 |
return ret; |
1081 |
|
|
} |
1082 |
|
|
|
1083 |
|
|
|
1084 |
|
|
int |
1085 |
|
|
ec_GFp_simple_cmp(const EC_GROUP * group, const EC_POINT * a, const EC_POINT * b, BN_CTX * ctx) |
1086 |
|
78 |
{ |
1087 |
|
|
/* |
1088 |
|
|
* return values: -1 error 0 equal (in affine coordinates) 1 |
1089 |
|
|
* not equal |
1090 |
|
|
*/ |
1091 |
|
|
|
1092 |
|
|
int (*field_mul) (const EC_GROUP *, BIGNUM *, const BIGNUM *, const BIGNUM *, BN_CTX *); |
1093 |
|
|
int (*field_sqr) (const EC_GROUP *, BIGNUM *, const BIGNUM *, BN_CTX *); |
1094 |
|
78 |
BN_CTX *new_ctx = NULL; |
1095 |
|
|
BIGNUM *tmp1, *tmp2, *Za23, *Zb23; |
1096 |
|
|
const BIGNUM *tmp1_, *tmp2_; |
1097 |
|
78 |
int ret = -1; |
1098 |
|
|
|
1099 |
✓✓ |
78 |
if (EC_POINT_is_at_infinity(group, a) > 0) { |
1100 |
|
18 |
return EC_POINT_is_at_infinity(group, b) > 0 ? 0 : 1; |
1101 |
|
|
} |
1102 |
✗✓ |
60 |
if (EC_POINT_is_at_infinity(group, b) > 0) |
1103 |
|
|
return 1; |
1104 |
|
|
|
1105 |
✓✓✓✓
|
60 |
if (a->Z_is_one && b->Z_is_one) { |
1106 |
✓✓✗✓
|
15 |
return ((BN_cmp(&a->X, &b->X) == 0) && BN_cmp(&a->Y, &b->Y) == 0) ? 0 : 1; |
1107 |
|
|
} |
1108 |
|
45 |
field_mul = group->meth->field_mul; |
1109 |
|
45 |
field_sqr = group->meth->field_sqr; |
1110 |
|
|
|
1111 |
✗✓ |
45 |
if (ctx == NULL) { |
1112 |
|
|
ctx = new_ctx = BN_CTX_new(); |
1113 |
|
|
if (ctx == NULL) |
1114 |
|
|
return -1; |
1115 |
|
|
} |
1116 |
|
45 |
BN_CTX_start(ctx); |
1117 |
✗✓ |
45 |
if ((tmp1 = BN_CTX_get(ctx)) == NULL) |
1118 |
|
|
goto end; |
1119 |
✗✓ |
45 |
if ((tmp2 = BN_CTX_get(ctx)) == NULL) |
1120 |
|
|
goto end; |
1121 |
✗✓ |
45 |
if ((Za23 = BN_CTX_get(ctx)) == NULL) |
1122 |
|
|
goto end; |
1123 |
✗✓ |
45 |
if ((Zb23 = BN_CTX_get(ctx)) == NULL) |
1124 |
|
|
goto end; |
1125 |
|
|
|
1126 |
|
|
/* |
1127 |
|
|
* We have to decide whether (X_a/Z_a^2, Y_a/Z_a^3) = (X_b/Z_b^2, |
1128 |
|
|
* Y_b/Z_b^3), or equivalently, whether (X_a*Z_b^2, Y_a*Z_b^3) = |
1129 |
|
|
* (X_b*Z_a^2, Y_b*Z_a^3). |
1130 |
|
|
*/ |
1131 |
|
|
|
1132 |
✓✓ |
45 |
if (!b->Z_is_one) { |
1133 |
✗✓ |
44 |
if (!field_sqr(group, Zb23, &b->Z, ctx)) |
1134 |
|
|
goto end; |
1135 |
✗✓ |
44 |
if (!field_mul(group, tmp1, &a->X, Zb23, ctx)) |
1136 |
|
|
goto end; |
1137 |
|
44 |
tmp1_ = tmp1; |
1138 |
|
|
} else |
1139 |
|
1 |
tmp1_ = &a->X; |
1140 |
✓✓ |
45 |
if (!a->Z_is_one) { |
1141 |
✗✓ |
44 |
if (!field_sqr(group, Za23, &a->Z, ctx)) |
1142 |
|
|
goto end; |
1143 |
✗✓ |
44 |
if (!field_mul(group, tmp2, &b->X, Za23, ctx)) |
1144 |
|
|
goto end; |
1145 |
|
44 |
tmp2_ = tmp2; |
1146 |
|
|
} else |
1147 |
|
1 |
tmp2_ = &b->X; |
1148 |
|
|
|
1149 |
|
|
/* compare X_a*Z_b^2 with X_b*Z_a^2 */ |
1150 |
✗✓ |
45 |
if (BN_cmp(tmp1_, tmp2_) != 0) { |
1151 |
|
|
ret = 1; /* points differ */ |
1152 |
|
|
goto end; |
1153 |
|
|
} |
1154 |
✓✓ |
45 |
if (!b->Z_is_one) { |
1155 |
✗✓ |
44 |
if (!field_mul(group, Zb23, Zb23, &b->Z, ctx)) |
1156 |
|
|
goto end; |
1157 |
✗✓ |
44 |
if (!field_mul(group, tmp1, &a->Y, Zb23, ctx)) |
1158 |
|
|
goto end; |
1159 |
|
|
/* tmp1_ = tmp1 */ |
1160 |
|
|
} else |
1161 |
|
1 |
tmp1_ = &a->Y; |
1162 |
✓✓ |
45 |
if (!a->Z_is_one) { |
1163 |
✗✓ |
44 |
if (!field_mul(group, Za23, Za23, &a->Z, ctx)) |
1164 |
|
|
goto end; |
1165 |
✗✓ |
44 |
if (!field_mul(group, tmp2, &b->Y, Za23, ctx)) |
1166 |
|
|
goto end; |
1167 |
|
|
/* tmp2_ = tmp2 */ |
1168 |
|
|
} else |
1169 |
|
1 |
tmp2_ = &b->Y; |
1170 |
|
|
|
1171 |
|
|
/* compare Y_a*Z_b^3 with Y_b*Z_a^3 */ |
1172 |
✗✓ |
45 |
if (BN_cmp(tmp1_, tmp2_) != 0) { |
1173 |
|
|
ret = 1; /* points differ */ |
1174 |
|
|
goto end; |
1175 |
|
|
} |
1176 |
|
|
/* points are equal */ |
1177 |
|
45 |
ret = 0; |
1178 |
|
|
|
1179 |
|
45 |
end: |
1180 |
|
45 |
BN_CTX_end(ctx); |
1181 |
|
45 |
BN_CTX_free(new_ctx); |
1182 |
|
45 |
return ret; |
1183 |
|
|
} |
1184 |
|
|
|
1185 |
|
|
|
1186 |
|
|
int |
1187 |
|
|
ec_GFp_simple_make_affine(const EC_GROUP * group, EC_POINT * point, BN_CTX * ctx) |
1188 |
|
|
{ |
1189 |
|
|
BN_CTX *new_ctx = NULL; |
1190 |
|
|
BIGNUM *x, *y; |
1191 |
|
|
int ret = 0; |
1192 |
|
|
|
1193 |
|
|
if (point->Z_is_one || EC_POINT_is_at_infinity(group, point) > 0) |
1194 |
|
|
return 1; |
1195 |
|
|
|
1196 |
|
|
if (ctx == NULL) { |
1197 |
|
|
ctx = new_ctx = BN_CTX_new(); |
1198 |
|
|
if (ctx == NULL) |
1199 |
|
|
return 0; |
1200 |
|
|
} |
1201 |
|
|
BN_CTX_start(ctx); |
1202 |
|
|
if ((x = BN_CTX_get(ctx)) == NULL) |
1203 |
|
|
goto err; |
1204 |
|
|
if ((y = BN_CTX_get(ctx)) == NULL) |
1205 |
|
|
goto err; |
1206 |
|
|
|
1207 |
|
|
if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) |
1208 |
|
|
goto err; |
1209 |
|
|
if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) |
1210 |
|
|
goto err; |
1211 |
|
|
if (!point->Z_is_one) { |
1212 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_MAKE_AFFINE, ERR_R_INTERNAL_ERROR); |
1213 |
|
|
goto err; |
1214 |
|
|
} |
1215 |
|
|
ret = 1; |
1216 |
|
|
|
1217 |
|
|
err: |
1218 |
|
|
BN_CTX_end(ctx); |
1219 |
|
|
BN_CTX_free(new_ctx); |
1220 |
|
|
return ret; |
1221 |
|
|
} |
1222 |
|
|
|
1223 |
|
|
|
1224 |
|
|
int |
1225 |
|
|
ec_GFp_simple_points_make_affine(const EC_GROUP * group, size_t num, EC_POINT * points[], BN_CTX * ctx) |
1226 |
|
546 |
{ |
1227 |
|
546 |
BN_CTX *new_ctx = NULL; |
1228 |
|
|
BIGNUM *tmp0, *tmp1; |
1229 |
|
546 |
size_t pow2 = 0; |
1230 |
|
546 |
BIGNUM **heap = NULL; |
1231 |
|
|
size_t i; |
1232 |
|
546 |
int ret = 0; |
1233 |
|
|
|
1234 |
✓✓ |
546 |
if (num == 0) |
1235 |
|
6 |
return 1; |
1236 |
|
|
|
1237 |
✗✓ |
540 |
if (ctx == NULL) { |
1238 |
|
|
ctx = new_ctx = BN_CTX_new(); |
1239 |
|
|
if (ctx == NULL) |
1240 |
|
|
return 0; |
1241 |
|
|
} |
1242 |
|
540 |
BN_CTX_start(ctx); |
1243 |
✗✓ |
540 |
if ((tmp0 = BN_CTX_get(ctx)) == NULL) |
1244 |
|
|
goto err; |
1245 |
✗✓ |
540 |
if ((tmp1 = BN_CTX_get(ctx)) == NULL) |
1246 |
|
|
goto err; |
1247 |
|
|
|
1248 |
|
|
/* |
1249 |
|
|
* Before converting the individual points, compute inverses of all Z |
1250 |
|
|
* values. Modular inversion is rather slow, but luckily we can do |
1251 |
|
|
* with a single explicit inversion, plus about 3 multiplications per |
1252 |
|
|
* input value. |
1253 |
|
|
*/ |
1254 |
|
|
|
1255 |
|
540 |
pow2 = 1; |
1256 |
✓✓ |
2560 |
while (num > pow2) |
1257 |
|
1480 |
pow2 <<= 1; |
1258 |
|
|
/* |
1259 |
|
|
* Now pow2 is the smallest power of 2 satifsying pow2 >= num. We |
1260 |
|
|
* need twice that. |
1261 |
|
|
*/ |
1262 |
|
540 |
pow2 <<= 1; |
1263 |
|
|
|
1264 |
|
540 |
heap = reallocarray(NULL, pow2, sizeof heap[0]); |
1265 |
✗✓ |
540 |
if (heap == NULL) |
1266 |
|
|
goto err; |
1267 |
|
|
|
1268 |
|
|
/* |
1269 |
|
|
* The array is used as a binary tree, exactly as in heapsort: |
1270 |
|
|
* |
1271 |
|
|
* heap[1] heap[2] heap[3] heap[4] heap[5] |
1272 |
|
|
* heap[6] heap[7] heap[8]heap[9] heap[10]heap[11] |
1273 |
|
|
* heap[12]heap[13] heap[14] heap[15] |
1274 |
|
|
* |
1275 |
|
|
* We put the Z's in the last line; then we set each other node to the |
1276 |
|
|
* product of its two child-nodes (where empty or 0 entries are |
1277 |
|
|
* treated as ones); then we invert heap[1]; then we invert each |
1278 |
|
|
* other node by replacing it by the product of its parent (after |
1279 |
|
|
* inversion) and its sibling (before inversion). |
1280 |
|
|
*/ |
1281 |
|
540 |
heap[0] = NULL; |
1282 |
✓✓ |
6376 |
for (i = pow2 / 2 - 1; i > 0; i--) |
1283 |
|
5836 |
heap[i] = NULL; |
1284 |
✓✓ |
6101 |
for (i = 0; i < num; i++) |
1285 |
|
5561 |
heap[pow2 / 2 + i] = &points[i]->Z; |
1286 |
✓✓ |
1355 |
for (i = pow2 / 2 + num; i < pow2; i++) |
1287 |
|
815 |
heap[i] = NULL; |
1288 |
|
|
|
1289 |
|
|
/* set each node to the product of its children */ |
1290 |
✓✓ |
6376 |
for (i = pow2 / 2 - 1; i > 0; i--) { |
1291 |
|
5836 |
heap[i] = BN_new(); |
1292 |
✗✓ |
5836 |
if (heap[i] == NULL) |
1293 |
|
|
goto err; |
1294 |
|
|
|
1295 |
✓✓ |
5836 |
if (heap[2 * i] != NULL) { |
1296 |
✓✓✓✓
|
5429 |
if ((heap[2 * i + 1] == NULL) || BN_is_zero(heap[2 * i + 1])) { |
1297 |
✗✓ |
510 |
if (!BN_copy(heap[i], heap[2 * i])) |
1298 |
|
|
goto err; |
1299 |
|
|
} else { |
1300 |
✗✓ |
4919 |
if (BN_is_zero(heap[2 * i])) { |
1301 |
|
|
if (!BN_copy(heap[i], heap[2 * i + 1])) |
1302 |
|
|
goto err; |
1303 |
|
|
} else { |
1304 |
✗✓ |
4919 |
if (!group->meth->field_mul(group, heap[i], |
1305 |
|
|
heap[2 * i], heap[2 * i + 1], ctx)) |
1306 |
|
|
goto err; |
1307 |
|
|
} |
1308 |
|
|
} |
1309 |
|
|
} |
1310 |
|
|
} |
1311 |
|
|
|
1312 |
|
|
/* invert heap[1] */ |
1313 |
✓✓ |
540 |
if (!BN_is_zero(heap[1])) { |
1314 |
✗✓ |
522 |
if (!BN_mod_inverse(heap[1], heap[1], &group->field, ctx)) { |
1315 |
|
|
ECerr(EC_F_EC_GFP_SIMPLE_POINTS_MAKE_AFFINE, ERR_R_BN_LIB); |
1316 |
|
|
goto err; |
1317 |
|
|
} |
1318 |
|
|
} |
1319 |
✓✗ |
540 |
if (group->meth->field_encode != 0) { |
1320 |
|
|
/* |
1321 |
|
|
* in the Montgomery case, we just turned R*H (representing |
1322 |
|
|
* H) into 1/(R*H), but we need R*(1/H) (representing |
1323 |
|
|
* 1/H); i.e. we have need to multiply by the Montgomery |
1324 |
|
|
* factor twice |
1325 |
|
|
*/ |
1326 |
✗✓ |
540 |
if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) |
1327 |
|
|
goto err; |
1328 |
✗✓ |
540 |
if (!group->meth->field_encode(group, heap[1], heap[1], ctx)) |
1329 |
|
|
goto err; |
1330 |
|
|
} |
1331 |
|
|
/* set other heap[i]'s to their inverses */ |
1332 |
✓✓ |
5969 |
for (i = 2; i < pow2 / 2 + num; i += 2) { |
1333 |
|
|
/* i is even */ |
1334 |
✓✓✓✓
|
5429 |
if ((heap[i + 1] != NULL) && !BN_is_zero(heap[i + 1])) { |
1335 |
✗✓ |
4919 |
if (!group->meth->field_mul(group, tmp0, heap[i / 2], heap[i + 1], ctx)) |
1336 |
|
|
goto err; |
1337 |
✗✓ |
4919 |
if (!group->meth->field_mul(group, tmp1, heap[i / 2], heap[i], ctx)) |
1338 |
|
|
goto err; |
1339 |
✗✓ |
4919 |
if (!BN_copy(heap[i], tmp0)) |
1340 |
|
|
goto err; |
1341 |
✗✓ |
4919 |
if (!BN_copy(heap[i + 1], tmp1)) |
1342 |
|
|
goto err; |
1343 |
|
|
} else { |
1344 |
✗✓ |
510 |
if (!BN_copy(heap[i], heap[i / 2])) |
1345 |
|
|
goto err; |
1346 |
|
|
} |
1347 |
|
|
} |
1348 |
|
|
|
1349 |
|
|
/* |
1350 |
|
|
* we have replaced all non-zero Z's by their inverses, now fix up |
1351 |
|
|
* all the points |
1352 |
|
|
*/ |
1353 |
✓✓ |
6101 |
for (i = 0; i < num; i++) { |
1354 |
|
5561 |
EC_POINT *p = points[i]; |
1355 |
|
|
|
1356 |
✓✓ |
5561 |
if (!BN_is_zero(&p->Z)) { |
1357 |
|
|
/* turn (X, Y, 1/Z) into (X/Z^2, Y/Z^3, 1) */ |
1358 |
|
|
|
1359 |
✗✓ |
5441 |
if (!group->meth->field_sqr(group, tmp1, &p->Z, ctx)) |
1360 |
|
|
goto err; |
1361 |
✗✓ |
5441 |
if (!group->meth->field_mul(group, &p->X, &p->X, tmp1, ctx)) |
1362 |
|
|
goto err; |
1363 |
|
|
|
1364 |
✗✓ |
5441 |
if (!group->meth->field_mul(group, tmp1, tmp1, &p->Z, ctx)) |
1365 |
|
|
goto err; |
1366 |
✗✓ |
5441 |
if (!group->meth->field_mul(group, &p->Y, &p->Y, tmp1, ctx)) |
1367 |
|
|
goto err; |
1368 |
|
|
|
1369 |
✓✗ |
5441 |
if (group->meth->field_set_to_one != 0) { |
1370 |
✗✓ |
5441 |
if (!group->meth->field_set_to_one(group, &p->Z, ctx)) |
1371 |
|
|
goto err; |
1372 |
|
|
} else { |
1373 |
|
|
if (!BN_one(&p->Z)) |
1374 |
|
|
goto err; |
1375 |
|
|
} |
1376 |
|
5441 |
p->Z_is_one = 1; |
1377 |
|
|
} |
1378 |
|
|
} |
1379 |
|
|
|
1380 |
|
540 |
ret = 1; |
1381 |
|
|
|
1382 |
|
540 |
err: |
1383 |
|
540 |
BN_CTX_end(ctx); |
1384 |
|
540 |
BN_CTX_free(new_ctx); |
1385 |
✓✗ |
540 |
if (heap != NULL) { |
1386 |
|
|
/* |
1387 |
|
|
* heap[pow2/2] .. heap[pow2-1] have not been allocated |
1388 |
|
|
* locally! |
1389 |
|
|
*/ |
1390 |
✓✓ |
6376 |
for (i = pow2 / 2 - 1; i > 0; i--) { |
1391 |
|
5836 |
BN_clear_free(heap[i]); |
1392 |
|
|
} |
1393 |
|
540 |
free(heap); |
1394 |
|
|
} |
1395 |
|
540 |
return ret; |
1396 |
|
|
} |
1397 |
|
|
|
1398 |
|
|
|
1399 |
|
|
int |
1400 |
|
|
ec_GFp_simple_field_mul(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, const BIGNUM * b, BN_CTX * ctx) |
1401 |
|
|
{ |
1402 |
|
|
return BN_mod_mul(r, a, b, &group->field, ctx); |
1403 |
|
|
} |
1404 |
|
|
|
1405 |
|
|
|
1406 |
|
|
int |
1407 |
|
|
ec_GFp_simple_field_sqr(const EC_GROUP * group, BIGNUM * r, const BIGNUM * a, BN_CTX * ctx) |
1408 |
|
|
{ |
1409 |
|
|
return BN_mod_sqr(r, a, &group->field, ctx); |
1410 |
|
|
} |