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