1/* Originally written by Bodo Moeller and Nils Larsch for the OpenSSL project.
2 * ====================================================================
3 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. All advertising materials mentioning features or use of this
18 * software must display the following acknowledgment:
19 * "This product includes software developed by the OpenSSL Project
20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21 *
22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23 * endorse or promote products derived from this software without
24 * prior written permission. For written permission, please contact
25 * openssl-core@openssl.org.
26 *
27 * 5. Products derived from this software may not be called "OpenSSL"
28 * nor may "OpenSSL" appear in their names without prior written
29 * permission of the OpenSSL Project.
30 *
31 * 6. Redistributions of any form whatsoever must retain the following
32 * acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35 *
36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47 * OF THE POSSIBILITY OF SUCH DAMAGE.
48 * ====================================================================
49 *
50 * This product includes cryptographic software written by Eric Young
51 * (eay@cryptsoft.com). This product includes software written by Tim
52 * Hudson (tjh@cryptsoft.com).
53 *
54 */
55/* ====================================================================
56 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57 *
58 * Portions of the attached software ("Contribution") are developed by
59 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60 *
61 * The Contribution is licensed pursuant to the OpenSSL open source
62 * license provided above.
63 *
64 * The elliptic curve binary polynomial software is originally written by
65 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66 * Laboratories. */
67
68#include <openssl/ec.h>
69
70#include <openssl/bn.h>
71#include <openssl/err.h>
72#include <openssl/mem.h>
73
74#include "../bn/internal.h"
75#include "../delocate.h"
76#include "internal.h"
77
78
79int ec_GFp_mont_group_init(EC_GROUP *group) {
80 int ok;
81
82 ok = ec_GFp_simple_group_init(group);
83 group->mont = NULL;
84 return ok;
85}
86
87void ec_GFp_mont_group_finish(EC_GROUP *group) {
88 BN_MONT_CTX_free(group->mont);
89 group->mont = NULL;
90 ec_GFp_simple_group_finish(group);
91}
92
93int ec_GFp_mont_group_set_curve(EC_GROUP *group, const BIGNUM *p,
94 const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) {
95 BN_CTX *new_ctx = NULL;
96 int ret = 0;
97
98 BN_MONT_CTX_free(group->mont);
99 group->mont = NULL;
100
101 if (ctx == NULL) {
102 ctx = new_ctx = BN_CTX_new();
103 if (ctx == NULL) {
104 return 0;
105 }
106 }
107
108 group->mont = BN_MONT_CTX_new_for_modulus(p, ctx);
109 if (group->mont == NULL) {
110 OPENSSL_PUT_ERROR(EC, ERR_R_BN_LIB);
111 goto err;
112 }
113
114 ret = ec_GFp_simple_group_set_curve(group, p, a, b, ctx);
115
116 if (!ret) {
117 BN_MONT_CTX_free(group->mont);
118 group->mont = NULL;
119 }
120
121err:
122 BN_CTX_free(new_ctx);
123 return ret;
124}
125
126static void ec_GFp_mont_felem_to_montgomery(const EC_GROUP *group,
127 EC_FELEM *out, const EC_FELEM *in) {
128 bn_to_montgomery_small(out->words, in->words, group->field.width,
129 group->mont);
130}
131
132static void ec_GFp_mont_felem_from_montgomery(const EC_GROUP *group,
133 EC_FELEM *out,
134 const EC_FELEM *in) {
135 bn_from_montgomery_small(out->words, in->words, group->field.width,
136 group->mont);
137}
138
139static void ec_GFp_mont_felem_inv(const EC_GROUP *group, EC_FELEM *out,
140 const EC_FELEM *a) {
141 bn_mod_inverse_prime_mont_small(out->words, a->words, group->field.width,
142 group->mont);
143}
144
145void ec_GFp_mont_felem_mul(const EC_GROUP *group, EC_FELEM *r,
146 const EC_FELEM *a, const EC_FELEM *b) {
147 bn_mod_mul_montgomery_small(r->words, a->words, b->words, group->field.width,
148 group->mont);
149}
150
151void ec_GFp_mont_felem_sqr(const EC_GROUP *group, EC_FELEM *r,
152 const EC_FELEM *a) {
153 bn_mod_mul_montgomery_small(r->words, a->words, a->words, group->field.width,
154 group->mont);
155}
156
157int ec_GFp_mont_bignum_to_felem(const EC_GROUP *group, EC_FELEM *out,
158 const BIGNUM *in) {
159 if (group->mont == NULL) {
160 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
161 return 0;
162 }
163
164 if (!bn_copy_words(out->words, group->field.width, in)) {
165 return 0;
166 }
167 ec_GFp_mont_felem_to_montgomery(group, out, out);
168 return 1;
169}
170
171int ec_GFp_mont_felem_to_bignum(const EC_GROUP *group, BIGNUM *out,
172 const EC_FELEM *in) {
173 if (group->mont == NULL) {
174 OPENSSL_PUT_ERROR(EC, EC_R_NOT_INITIALIZED);
175 return 0;
176 }
177
178 EC_FELEM tmp;
179 ec_GFp_mont_felem_from_montgomery(group, &tmp, in);
180 return bn_set_words(out, tmp.words, group->field.width);
181}
182
183static int ec_GFp_mont_point_get_affine_coordinates(const EC_GROUP *group,
184 const EC_RAW_POINT *point,
185 EC_FELEM *x, EC_FELEM *y) {
186 if (ec_GFp_simple_is_at_infinity(group, point)) {
187 OPENSSL_PUT_ERROR(EC, EC_R_POINT_AT_INFINITY);
188 return 0;
189 }
190
191 // Transform (X, Y, Z) into (x, y) := (X/Z^2, Y/Z^3).
192
193 EC_FELEM z1, z2;
194 ec_GFp_mont_felem_inv(group, &z2, &point->Z);
195 ec_GFp_mont_felem_sqr(group, &z1, &z2);
196
197 // Instead of using |ec_GFp_mont_felem_from_montgomery| to convert the |x|
198 // coordinate and then calling |ec_GFp_mont_felem_from_montgomery| again to
199 // convert the |y| coordinate below, convert the common factor |z1| once now,
200 // saving one reduction.
201 ec_GFp_mont_felem_from_montgomery(group, &z1, &z1);
202
203 if (x != NULL) {
204 ec_GFp_mont_felem_mul(group, x, &point->X, &z1);
205 }
206
207 if (y != NULL) {
208 ec_GFp_mont_felem_mul(group, &z1, &z1, &z2);
209 ec_GFp_mont_felem_mul(group, y, &point->Y, &z1);
210 }
211
212 return 1;
213}
214
215void ec_GFp_mont_add(const EC_GROUP *group, EC_RAW_POINT *out,
216 const EC_RAW_POINT *a, const EC_RAW_POINT *b) {
217 if (a == b) {
218 ec_GFp_mont_dbl(group, out, a);
219 return;
220 }
221
222 // The method is taken from:
223 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#addition-add-2007-bl
224 //
225 // Coq transcription and correctness proof:
226 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L467>
227 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L544>
228 EC_FELEM x_out, y_out, z_out;
229 BN_ULONG z1nz = ec_felem_non_zero_mask(group, &a->Z);
230 BN_ULONG z2nz = ec_felem_non_zero_mask(group, &b->Z);
231
232 // z1z1 = z1z1 = z1**2
233 EC_FELEM z1z1;
234 ec_GFp_mont_felem_sqr(group, &z1z1, &a->Z);
235
236 // z2z2 = z2**2
237 EC_FELEM z2z2;
238 ec_GFp_mont_felem_sqr(group, &z2z2, &b->Z);
239
240 // u1 = x1*z2z2
241 EC_FELEM u1;
242 ec_GFp_mont_felem_mul(group, &u1, &a->X, &z2z2);
243
244 // two_z1z2 = (z1 + z2)**2 - (z1z1 + z2z2) = 2z1z2
245 EC_FELEM two_z1z2;
246 ec_felem_add(group, &two_z1z2, &a->Z, &b->Z);
247 ec_GFp_mont_felem_sqr(group, &two_z1z2, &two_z1z2);
248 ec_felem_sub(group, &two_z1z2, &two_z1z2, &z1z1);
249 ec_felem_sub(group, &two_z1z2, &two_z1z2, &z2z2);
250
251 // s1 = y1 * z2**3
252 EC_FELEM s1;
253 ec_GFp_mont_felem_mul(group, &s1, &b->Z, &z2z2);
254 ec_GFp_mont_felem_mul(group, &s1, &s1, &a->Y);
255
256 // u2 = x2*z1z1
257 EC_FELEM u2;
258 ec_GFp_mont_felem_mul(group, &u2, &b->X, &z1z1);
259
260 // h = u2 - u1
261 EC_FELEM h;
262 ec_felem_sub(group, &h, &u2, &u1);
263
264 BN_ULONG xneq = ec_felem_non_zero_mask(group, &h);
265
266 // z_out = two_z1z2 * h
267 ec_GFp_mont_felem_mul(group, &z_out, &h, &two_z1z2);
268
269 // z1z1z1 = z1 * z1z1
270 EC_FELEM z1z1z1;
271 ec_GFp_mont_felem_mul(group, &z1z1z1, &a->Z, &z1z1);
272
273 // s2 = y2 * z1**3
274 EC_FELEM s2;
275 ec_GFp_mont_felem_mul(group, &s2, &b->Y, &z1z1z1);
276
277 // r = (s2 - s1)*2
278 EC_FELEM r;
279 ec_felem_sub(group, &r, &s2, &s1);
280 ec_felem_add(group, &r, &r, &r);
281
282 BN_ULONG yneq = ec_felem_non_zero_mask(group, &r);
283
284 // This case will never occur in the constant-time |ec_GFp_mont_mul|.
285 BN_ULONG is_nontrivial_double = ~xneq & ~yneq & z1nz & z2nz;
286 if (is_nontrivial_double) {
287 ec_GFp_mont_dbl(group, out, a);
288 return;
289 }
290
291 // I = (2h)**2
292 EC_FELEM i;
293 ec_felem_add(group, &i, &h, &h);
294 ec_GFp_mont_felem_sqr(group, &i, &i);
295
296 // J = h * I
297 EC_FELEM j;
298 ec_GFp_mont_felem_mul(group, &j, &h, &i);
299
300 // V = U1 * I
301 EC_FELEM v;
302 ec_GFp_mont_felem_mul(group, &v, &u1, &i);
303
304 // x_out = r**2 - J - 2V
305 ec_GFp_mont_felem_sqr(group, &x_out, &r);
306 ec_felem_sub(group, &x_out, &x_out, &j);
307 ec_felem_sub(group, &x_out, &x_out, &v);
308 ec_felem_sub(group, &x_out, &x_out, &v);
309
310 // y_out = r(V-x_out) - 2 * s1 * J
311 ec_felem_sub(group, &y_out, &v, &x_out);
312 ec_GFp_mont_felem_mul(group, &y_out, &y_out, &r);
313 EC_FELEM s1j;
314 ec_GFp_mont_felem_mul(group, &s1j, &s1, &j);
315 ec_felem_sub(group, &y_out, &y_out, &s1j);
316 ec_felem_sub(group, &y_out, &y_out, &s1j);
317
318 ec_felem_select(group, &x_out, z1nz, &x_out, &b->X);
319 ec_felem_select(group, &out->X, z2nz, &x_out, &a->X);
320 ec_felem_select(group, &y_out, z1nz, &y_out, &b->Y);
321 ec_felem_select(group, &out->Y, z2nz, &y_out, &a->Y);
322 ec_felem_select(group, &z_out, z1nz, &z_out, &b->Z);
323 ec_felem_select(group, &out->Z, z2nz, &z_out, &a->Z);
324}
325
326void ec_GFp_mont_dbl(const EC_GROUP *group, EC_RAW_POINT *r,
327 const EC_RAW_POINT *a) {
328 if (group->a_is_minus3) {
329 // The method is taken from:
330 // http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html#doubling-dbl-2001-b
331 //
332 // Coq transcription and correctness proof:
333 // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L93>
334 // <https://github.com/mit-plv/fiat-crypto/blob/79f8b5f39ed609339f0233098dee1a3c4e6b3080/src/Curves/Weierstrass/Jacobian.v#L201>
335 EC_FELEM delta, gamma, beta, ftmp, ftmp2, tmptmp, alpha, fourbeta;
336 // delta = z^2
337 ec_GFp_mont_felem_sqr(group, &delta, &a->Z);
338 // gamma = y^2
339 ec_GFp_mont_felem_sqr(group, &gamma, &a->Y);
340 // beta = x*gamma
341 ec_GFp_mont_felem_mul(group, &beta, &a->X, &gamma);
342
343 // alpha = 3*(x-delta)*(x+delta)
344 ec_felem_sub(group, &ftmp, &a->X, &delta);
345 ec_felem_add(group, &ftmp2, &a->X, &delta);
346
347 ec_felem_add(group, &tmptmp, &ftmp2, &ftmp2);
348 ec_felem_add(group, &ftmp2, &ftmp2, &tmptmp);
349 ec_GFp_mont_felem_mul(group, &alpha, &ftmp, &ftmp2);
350
351 // x' = alpha^2 - 8*beta
352 ec_GFp_mont_felem_sqr(group, &r->X, &alpha);
353 ec_felem_add(group, &fourbeta, &beta, &beta);
354 ec_felem_add(group, &fourbeta, &fourbeta, &fourbeta);
355 ec_felem_add(group, &tmptmp, &fourbeta, &fourbeta);
356 ec_felem_sub(group, &r->X, &r->X, &tmptmp);
357
358 // z' = (y + z)^2 - gamma - delta
359 ec_felem_add(group, &delta, &gamma, &delta);
360 ec_felem_add(group, &ftmp, &a->Y, &a->Z);
361 ec_GFp_mont_felem_sqr(group, &r->Z, &ftmp);
362 ec_felem_sub(group, &r->Z, &r->Z, &delta);
363
364 // y' = alpha*(4*beta - x') - 8*gamma^2
365 ec_felem_sub(group, &r->Y, &fourbeta, &r->X);
366 ec_felem_add(group, &gamma, &gamma, &gamma);
367 ec_GFp_mont_felem_sqr(group, &gamma, &gamma);
368 ec_GFp_mont_felem_mul(group, &r->Y, &alpha, &r->Y);
369 ec_felem_add(group, &gamma, &gamma, &gamma);
370 ec_felem_sub(group, &r->Y, &r->Y, &gamma);
371 } else {
372 // The method is taken from:
373 // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian.html#doubling-dbl-2007-bl
374 //
375 // Coq transcription and correctness proof:
376 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L102>
377 // <https://github.com/davidben/fiat-crypto/blob/c7b95f62b2a54b559522573310e9b487327d219a/src/Curves/Weierstrass/Jacobian.v#L534>
378 EC_FELEM xx, yy, yyyy, zz;
379 ec_GFp_mont_felem_sqr(group, &xx, &a->X);
380 ec_GFp_mont_felem_sqr(group, &yy, &a->Y);
381 ec_GFp_mont_felem_sqr(group, &yyyy, &yy);
382 ec_GFp_mont_felem_sqr(group, &zz, &a->Z);
383
384 // s = 2*((x_in + yy)^2 - xx - yyyy)
385 EC_FELEM s;
386 ec_felem_add(group, &s, &a->X, &yy);
387 ec_GFp_mont_felem_sqr(group, &s, &s);
388 ec_felem_sub(group, &s, &s, &xx);
389 ec_felem_sub(group, &s, &s, &yyyy);
390 ec_felem_add(group, &s, &s, &s);
391
392 // m = 3*xx + a*zz^2
393 EC_FELEM m;
394 ec_GFp_mont_felem_sqr(group, &m, &zz);
395 ec_GFp_mont_felem_mul(group, &m, &group->a, &m);
396 ec_felem_add(group, &m, &m, &xx);
397 ec_felem_add(group, &m, &m, &xx);
398 ec_felem_add(group, &m, &m, &xx);
399
400 // x_out = m^2 - 2*s
401 ec_GFp_mont_felem_sqr(group, &r->X, &m);
402 ec_felem_sub(group, &r->X, &r->X, &s);
403 ec_felem_sub(group, &r->X, &r->X, &s);
404
405 // z_out = (y_in + z_in)^2 - yy - zz
406 ec_felem_add(group, &r->Z, &a->Y, &a->Z);
407 ec_GFp_mont_felem_sqr(group, &r->Z, &r->Z);
408 ec_felem_sub(group, &r->Z, &r->Z, &yy);
409 ec_felem_sub(group, &r->Z, &r->Z, &zz);
410
411 // y_out = m*(s-x_out) - 8*yyyy
412 ec_felem_add(group, &yyyy, &yyyy, &yyyy);
413 ec_felem_add(group, &yyyy, &yyyy, &yyyy);
414 ec_felem_add(group, &yyyy, &yyyy, &yyyy);
415 ec_felem_sub(group, &r->Y, &s, &r->X);
416 ec_GFp_mont_felem_mul(group, &r->Y, &r->Y, &m);
417 ec_felem_sub(group, &r->Y, &r->Y, &yyyy);
418 }
419}
420
421static int ec_GFp_mont_cmp_x_coordinate(const EC_GROUP *group,
422 const EC_RAW_POINT *p,
423 const EC_SCALAR *r) {
424 if (!group->field_greater_than_order ||
425 group->field.width != group->order.width) {
426 // Do not bother optimizing this case. p > order in all commonly-used
427 // curves.
428 return ec_GFp_simple_cmp_x_coordinate(group, p, r);
429 }
430
431 if (ec_GFp_simple_is_at_infinity(group, p)) {
432 return 0;
433 }
434
435 // We wish to compare X/Z^2 with r. This is equivalent to comparing X with
436 // r*Z^2. Note that X and Z are represented in Montgomery form, while r is
437 // not.
438 EC_FELEM r_Z2, Z2_mont, X;
439 ec_GFp_mont_felem_mul(group, &Z2_mont, &p->Z, &p->Z);
440 // r < order < p, so this is valid.
441 OPENSSL_memcpy(r_Z2.words, r->words, group->field.width * sizeof(BN_ULONG));
442 ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont);
443 ec_GFp_mont_felem_from_montgomery(group, &X, &p->X);
444
445 if (ec_felem_equal(group, &r_Z2, &X)) {
446 return 1;
447 }
448
449 // During signing the x coefficient is reduced modulo the group order.
450 // Therefore there is a small possibility, less than 1/2^128, that group_order
451 // < p.x < P. in that case we need not only to compare against |r| but also to
452 // compare against r+group_order.
453 if (bn_less_than_words(r->words, group->field_minus_order.words,
454 group->field.width)) {
455 // We can ignore the carry because: r + group_order < p < 2^256.
456 bn_add_words(r_Z2.words, r->words, group->order.d, group->field.width);
457 ec_GFp_mont_felem_mul(group, &r_Z2, &r_Z2, &Z2_mont);
458 if (ec_felem_equal(group, &r_Z2, &X)) {
459 return 1;
460 }
461 }
462
463 return 0;
464}
465
466DEFINE_METHOD_FUNCTION(EC_METHOD, EC_GFp_mont_method) {
467 out->group_init = ec_GFp_mont_group_init;
468 out->group_finish = ec_GFp_mont_group_finish;
469 out->group_set_curve = ec_GFp_mont_group_set_curve;
470 out->point_get_affine_coordinates = ec_GFp_mont_point_get_affine_coordinates;
471 out->add = ec_GFp_mont_add;
472 out->dbl = ec_GFp_mont_dbl;
473 out->mul = ec_GFp_mont_mul;
474 out->mul_base = ec_GFp_mont_mul_base;
475 out->mul_public = ec_GFp_mont_mul_public;
476 out->felem_mul = ec_GFp_mont_felem_mul;
477 out->felem_sqr = ec_GFp_mont_felem_sqr;
478 out->bignum_to_felem = ec_GFp_mont_bignum_to_felem;
479 out->felem_to_bignum = ec_GFp_mont_felem_to_bignum;
480 out->scalar_inv_montgomery = ec_simple_scalar_inv_montgomery;
481 out->scalar_inv_montgomery_vartime = ec_GFp_simple_mont_inv_mod_ord_vartime;
482 out->cmp_x_coordinate = ec_GFp_mont_cmp_x_coordinate;
483}
484