summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/ec/ecp_hp_methods.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/lib/libcrypto/ec/ecp_hp_methods.c943
1 files changed, 943 insertions, 0 deletions
diff --git a/src/lib/libcrypto/ec/ecp_hp_methods.c b/src/lib/libcrypto/ec/ecp_hp_methods.c
new file mode 100644
index 0000000000..0b34a55b9d
--- /dev/null
+++ b/src/lib/libcrypto/ec/ecp_hp_methods.c
@@ -0,0 +1,943 @@
1/* $OpenBSD: ecp_hp_methods.c,v 1.5 2025/08/03 15:44:00 jsing Exp $ */
2/*
3 * Copyright (c) 2024-2025 Joel Sing <jsing@openbsd.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18#include <string.h>
19
20#include <openssl/bn.h>
21#include <openssl/ec.h>
22#include <openssl/err.h>
23
24#include "bn_internal.h"
25#include "crypto_internal.h"
26#include "ec_local.h"
27#include "ec_internal.h"
28#include "err_local.h"
29
30static int
31ec_group_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
32 const BIGNUM *b, BN_CTX *ctx)
33{
34 BIGNUM *t;
35 int ret = 0;
36
37 BN_CTX_start(ctx);
38
39 /* XXX - p must be a prime > 3. */
40
41 if (!bn_copy(group->p, p))
42 goto err;
43 if (!bn_copy(group->a, a))
44 goto err;
45 if (!bn_copy(group->b, b))
46 goto err;
47
48 /* XXX */
49 BN_set_negative(group->p, 0);
50
51 /* XXX */
52 if (!BN_nnmod(group->a, group->a, group->p, ctx))
53 goto err;
54 if (!BN_nnmod(group->b, group->b, group->p, ctx))
55 goto err;
56
57 if ((t = BN_CTX_get(ctx)) == NULL)
58 goto err;
59 if (!BN_set_word(t, 3))
60 goto err;
61 if (!BN_mod_add(t, t, a, group->p, ctx))
62 goto err;
63
64 group->a_is_minus3 = BN_is_zero(t);
65
66 if (!ec_field_modulus_from_bn(&group->fm, group->p, ctx))
67 goto err;
68 if (!ec_field_element_from_bn(&group->fm, group, &group->fe_a, group->a, ctx))
69 goto err;
70 if (!ec_field_element_from_bn(&group->fm, group, &group->fe_b, group->b, ctx))
71 goto err;
72
73 ret = 1;
74
75 err:
76 BN_CTX_end(ctx);
77
78 return ret;
79}
80
81static int
82ec_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
83 BIGNUM *b, BN_CTX *ctx)
84{
85 if (p != NULL) {
86 if (!bn_copy(p, group->p))
87 return 0;
88 }
89 if (a != NULL) {
90 if (!bn_copy(a, group->a))
91 return 0;
92 }
93 if (b != NULL) {
94 if (!bn_copy(b, group->b))
95 return 0;
96 }
97 return 1;
98}
99
100static int
101ec_point_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
102{
103 /* Check if Z is equal to zero. */
104 return ec_field_element_is_zero(&group->fm, &point->fe_z);
105}
106
107static int
108ec_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
109{
110 /* Infinity is (x = 0, y = 1, z = 0). */
111
112 memset(&point->fe_x, 0, sizeof(point->fe_x));
113 memset(&point->fe_y, 0, sizeof(point->fe_y));
114 memset(&point->fe_z, 0, sizeof(point->fe_z));
115
116 point->fe_y.w[0] = 1;
117
118 return 1;
119}
120
121static int
122ec_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
123 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
124{
125 if (x == NULL || y == NULL) {
126 ECerror(ERR_R_PASSED_NULL_PARAMETER);
127 return 0;
128 }
129
130 if (!bn_copy(point->X, x))
131 return 0;
132 if (!bn_copy(point->Y, y))
133 return 0;
134 if (!BN_one(point->Z))
135 return 0;
136
137 /* XXX */
138 if (!BN_nnmod(point->X, point->X, group->p, ctx))
139 return 0;
140 if (!BN_nnmod(point->Y, point->Y, group->p, ctx))
141 return 0;
142
143 if (!ec_field_element_from_bn(&group->fm, group, &point->fe_x, point->X, ctx))
144 return 0;
145 if (!ec_field_element_from_bn(&group->fm, group, &point->fe_y, point->Y, ctx))
146 return 0;
147 if (!ec_field_element_from_bn(&group->fm, group, &point->fe_z, point->Z, ctx))
148 return 0;
149
150 return 1;
151}
152
153static int
154ec_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
155 BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
156{
157 BIGNUM *zinv;
158 int ret = 0;
159
160 /*
161 * Convert homogeneous projective coordinates (XZ, YZ, Z) to affine
162 * coordinates (x = X/Z, y = Y/Z).
163 */
164 if (!ec_field_element_to_bn(&group->fm, &point->fe_x, point->X, ctx))
165 return 0;
166 if (!ec_field_element_to_bn(&group->fm, &point->fe_y, point->Y, ctx))
167 return 0;
168 if (!ec_field_element_to_bn(&group->fm, &point->fe_z, point->Z, ctx))
169 return 0;
170
171 BN_CTX_start(ctx);
172
173 if ((zinv = BN_CTX_get(ctx)) == NULL)
174 goto err;
175
176 if (BN_mod_inverse_ct(zinv, point->Z, group->p, ctx) == NULL)
177 goto err;
178
179 if (x != NULL) {
180 if (!BN_mod_mul(x, point->X, zinv, group->p, ctx))
181 goto err;
182 }
183 if (y != NULL) {
184 if (!BN_mod_mul(y, point->Y, zinv, group->p, ctx))
185 goto err;
186 }
187
188 ret = 1;
189
190 err:
191 BN_CTX_end(ctx);
192
193 return ret;
194}
195
196static int
197ec_point_add_a1(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
198 const EC_POINT *b, BN_CTX *ctx)
199{
200 EC_FIELD_ELEMENT X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3;
201 EC_FIELD_ELEMENT b3, t0, t1, t2, t3, t4, t5;
202 EC_FIELD_ELEMENT ga, gb;
203
204 /*
205 * Complete, projective point addition for arbitrary prime order short
206 * Weierstrass curves with arbitrary a - see
207 * https://eprint.iacr.org/2015/1060, algorithm 1 and appendix A.1.
208 */
209
210 ec_field_element_copy(&ga, &group->fe_a);
211 ec_field_element_copy(&gb, &group->fe_b);
212
213 ec_field_element_copy(&X1, &a->fe_x);
214 ec_field_element_copy(&Y1, &a->fe_y);
215 ec_field_element_copy(&Z1, &a->fe_z);
216
217 ec_field_element_copy(&X2, &b->fe_x);
218 ec_field_element_copy(&Y2, &b->fe_y);
219 ec_field_element_copy(&Z2, &b->fe_z);
220
221 /* b3 := 3 * b ; */
222 ec_field_element_add(&group->fm, &b3, &gb, &gb);
223 ec_field_element_add(&group->fm, &b3, &b3, &gb);
224
225 /* t0 := X1 * X2 ; t1 := Y1 * Y2 ; t2 := Z1 * Z2 ; */
226 ec_field_element_mul(&group->fm, &t0, &X1, &X2);
227 ec_field_element_mul(&group->fm, &t1, &Y1, &Y2);
228 ec_field_element_mul(&group->fm, &t2, &Z1, &Z2);
229
230 /* t3 := X1 + Y1 ; t4 := X2 + Y2 ; t3 := t3 * t4 ; */
231 ec_field_element_add(&group->fm, &t3, &X1, &Y1);
232 ec_field_element_add(&group->fm, &t4, &X2, &Y2);
233 ec_field_element_mul(&group->fm, &t3, &t3, &t4);
234
235 /* t4 := t0 + t1 ; t3 := t3 - t4 ; t4 := X1 + Z1 ; */
236 ec_field_element_add(&group->fm, &t4, &t0, &t1);
237 ec_field_element_sub(&group->fm, &t3, &t3, &t4);
238 ec_field_element_add(&group->fm, &t4, &X1, &Z1);
239
240 /* t5 := X2 + Z2 ; t4 := t4 * t5 ; t5 := t0 + t2 ; */
241 ec_field_element_add(&group->fm, &t5, &X2, &Z2);
242 ec_field_element_mul(&group->fm, &t4, &t4, &t5);
243 ec_field_element_add(&group->fm, &t5, &t0, &t2);
244
245 /* t4 := t4 - t5 ; t5 := Y1 + Z1 ; X3 := Y2 + Z2 ; */
246 ec_field_element_sub(&group->fm, &t4, &t4, &t5);
247 ec_field_element_add(&group->fm, &t5, &Y1, &Z1);
248 ec_field_element_add(&group->fm, &X3, &Y2, &Z2);
249
250 /* t5 := t5 * X3 ; X3 := t1 + t2 ; t5 := t5 - X3 ; */
251 ec_field_element_mul(&group->fm, &t5, &t5, &X3);
252 ec_field_element_add(&group->fm, &X3, &t1, &t2);
253 ec_field_element_sub(&group->fm, &t5, &t5, &X3);
254
255 /* Z3 := a * t4 ; X3 := b3 * t2 ; Z3 := X3 + Z3 ; */
256 ec_field_element_mul(&group->fm, &Z3, &ga, &t4);
257 ec_field_element_mul(&group->fm, &X3, &b3, &t2);
258 ec_field_element_add(&group->fm, &Z3, &X3, &Z3);
259
260 /* X3 := t1 - Z3 ; Z3 := t1 + Z3 ; Y3 := X3 * Z3 ; */
261 ec_field_element_sub(&group->fm, &X3, &t1, &Z3);
262 ec_field_element_add(&group->fm, &Z3, &t1, &Z3);
263 ec_field_element_mul(&group->fm, &Y3, &X3, &Z3);
264
265 /* t1 := t0 + t0 ; t1 := t1 + t0 ; t2 := a * t2 ; */
266 ec_field_element_add(&group->fm, &t1, &t0, &t0);
267 ec_field_element_add(&group->fm, &t1, &t1, &t0);
268 ec_field_element_mul(&group->fm, &t2, &ga, &t2);
269
270 /* t4 := b3 * t4 ; t1 := t1 + t2 ; t2 := t0 - t2 ; */
271 ec_field_element_mul(&group->fm, &t4, &b3, &t4);
272 ec_field_element_add(&group->fm, &t1, &t1, &t2);
273 ec_field_element_sub(&group->fm, &t2, &t0, &t2);
274
275 /* t2 := a * t2 ; t4 := t4 + t2 ; t0 := t1 * t4 ; */
276 ec_field_element_mul(&group->fm, &t2, &ga, &t2);
277 ec_field_element_add(&group->fm, &t4, &t4, &t2);
278 ec_field_element_mul(&group->fm, &t0, &t1, &t4);
279
280 /* Y3 := Y3 + t0 ; t0 := t5 * t4 ; X3 := t3 * X3 ; */
281 ec_field_element_add(&group->fm, &Y3, &Y3, &t0);
282 ec_field_element_mul(&group->fm, &t0, &t5, &t4);
283 ec_field_element_mul(&group->fm, &X3, &t3, &X3);
284
285 /* X3 := X3 - t0 ; t0 := t3 * t1 ; Z3 := t5 * Z3 ; */
286 ec_field_element_sub(&group->fm, &X3, &X3, &t0);
287 ec_field_element_mul(&group->fm, &t0, &t3, &t1);
288 ec_field_element_mul(&group->fm, &Z3, &t5, &Z3);
289
290 /* Z3 := Z3 + t0 ; */
291 ec_field_element_add(&group->fm, &Z3, &Z3, &t0);
292
293 ec_field_element_copy(&r->fe_x, &X3);
294 ec_field_element_copy(&r->fe_y, &Y3);
295 ec_field_element_copy(&r->fe_z, &Z3);
296
297 return 1;
298}
299
300static int
301ec_point_add_a2(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
302 const EC_POINT *b, BN_CTX *ctx)
303{
304 EC_FIELD_ELEMENT X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3;
305 EC_FIELD_ELEMENT t0, t1, t2, t3, t4;
306 EC_FIELD_ELEMENT gb;
307
308 /*
309 * Complete, projective point addition for arbitrary prime order short
310 * Weierstrass curves with a = -3 - see https://eprint.iacr.org/2015/1060,
311 * algorithm 4 and appendix A.2.
312 */
313
314 ec_field_element_copy(&gb, &group->fe_b);
315
316 ec_field_element_copy(&X1, &a->fe_x);
317 ec_field_element_copy(&Y1, &a->fe_y);
318 ec_field_element_copy(&Z1, &a->fe_z);
319
320 ec_field_element_copy(&X2, &b->fe_x);
321 ec_field_element_copy(&Y2, &b->fe_y);
322 ec_field_element_copy(&Z2, &b->fe_z);
323
324 /* t0 := X1 * X2 ; t1 := Y1 * Y2 ; t2 := Z1 * Z2 ; */
325 ec_field_element_mul(&group->fm, &t0, &X1, &X2);
326 ec_field_element_mul(&group->fm, &t1, &Y1, &Y2);
327 ec_field_element_mul(&group->fm, &t2, &Z1, &Z2);
328
329 /* t3 := X1 + Y1 ; t4 := X2 + Y2 ; t3 := t3 * t4 ; */
330 ec_field_element_add(&group->fm, &t3, &X1, &Y1);
331 ec_field_element_add(&group->fm, &t4, &X2, &Y2);
332 ec_field_element_mul(&group->fm, &t3, &t3, &t4);
333
334 /* t4 := t0 + t1 ; t3 := t3 - t4 ; t4 := Y1 + Z1 ; */
335 ec_field_element_add(&group->fm, &t4, &t0, &t1);
336 ec_field_element_sub(&group->fm, &t3, &t3, &t4);
337 ec_field_element_add(&group->fm, &t4, &Y1, &Z1);
338
339 /* X3 := Y2 + Z2 ; t4 := t4 * X3 ; X3 := t1 + t2 ; */
340 ec_field_element_add(&group->fm, &X3, &Y2, &Z2);
341 ec_field_element_mul(&group->fm, &t4, &t4, &X3);
342 ec_field_element_add(&group->fm, &X3, &t1, &t2);
343
344 /* t4 := t4 - X3 ; X3 := X1 + Z1 ; Y3 := X2 + Z2 ; */
345 ec_field_element_sub(&group->fm, &t4, &t4, &X3);
346 ec_field_element_add(&group->fm, &X3, &X1, &Z1);
347 ec_field_element_add(&group->fm, &Y3, &X2, &Z2);
348
349 /* X3 := X3 * Y3 ; Y3 := t0 + t2 ; Y3 := X3 - Y3 ; */
350 ec_field_element_mul(&group->fm, &X3, &X3, &Y3);
351 ec_field_element_add(&group->fm, &Y3, &t0, &t2);
352 ec_field_element_sub(&group->fm, &Y3, &X3, &Y3);
353
354 /* Z3 := b * t2 ; X3 := Y3 - Z3 ; Z3 := X3 + X3 ; */
355 ec_field_element_mul(&group->fm, &Z3, &gb, &t2);
356 ec_field_element_sub(&group->fm, &X3, &Y3, &Z3);
357 ec_field_element_add(&group->fm, &Z3, &X3, &X3);
358
359 /* X3 := X3 + Z3 ; Z3 := t1 - X3 ; X3 := t1 + X3 ; */
360 ec_field_element_add(&group->fm, &X3, &X3, &Z3);
361 ec_field_element_sub(&group->fm, &Z3, &t1, &X3);
362 ec_field_element_add(&group->fm, &X3, &t1, &X3);
363
364 /* Y3 := b * Y3 ; t1 := t2 + t2 ; t2 := t1 + t2 ; */
365 ec_field_element_mul(&group->fm, &Y3, &gb, &Y3);
366 ec_field_element_add(&group->fm, &t1, &t2, &t2);
367 ec_field_element_add(&group->fm, &t2, &t1, &t2);
368
369 /* Y3 := Y3 - t2 ; Y3 := Y3 - t0 ; t1 := Y3 + Y3 ; */
370 ec_field_element_sub(&group->fm, &Y3, &Y3, &t2);
371 ec_field_element_sub(&group->fm, &Y3, &Y3, &t0);
372 ec_field_element_add(&group->fm, &t1, &Y3, &Y3);
373
374 /* Y3 := t1 + Y3 ; t1 := t0 + t0 ; t0 := t1 + t0 ; */
375 ec_field_element_add(&group->fm, &Y3, &t1, &Y3);
376 ec_field_element_add(&group->fm, &t1, &t0, &t0);
377 ec_field_element_add(&group->fm, &t0, &t1, &t0);
378
379 /* t0 := t0 - t2 ; t1 := t4 * Y3 ; t2 := t0 * Y3 ; */
380 ec_field_element_sub(&group->fm, &t0, &t0, &t2);
381 ec_field_element_mul(&group->fm, &t1, &t4, &Y3);
382 ec_field_element_mul(&group->fm, &t2, &t0, &Y3);
383
384 /* Y3 := X3 * Z3 ; Y3 := Y3 + t2 ; X3 := t3 * X3 ; */
385 ec_field_element_mul(&group->fm, &Y3, &X3, &Z3);
386 ec_field_element_add(&group->fm, &Y3, &Y3, &t2);
387 ec_field_element_mul(&group->fm, &X3, &t3, &X3);
388
389 /* X3 := X3 - t1 ; Z3 := t4 * Z3 ; t1 := t3 * t0 ; */
390 ec_field_element_sub(&group->fm, &X3, &X3, &t1);
391 ec_field_element_mul(&group->fm, &Z3, &t4, &Z3);
392 ec_field_element_mul(&group->fm, &t1, &t3, &t0);
393
394 /* Z3 := Z3 + t1 ; */
395 ec_field_element_add(&group->fm, &Z3, &Z3, &t1);
396
397 ec_field_element_copy(&r->fe_x, &X3);
398 ec_field_element_copy(&r->fe_y, &Y3);
399 ec_field_element_copy(&r->fe_z, &Z3);
400
401 return 1;
402}
403
404static int
405ec_point_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
406 const EC_POINT *b, BN_CTX *ctx)
407{
408 if (group->a_is_minus3)
409 return ec_point_add_a2(group, r, a, b, ctx);
410
411 return ec_point_add_a1(group, r, a, b, ctx);
412}
413
414static int
415ec_point_dbl_a1(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
416{
417 EC_FIELD_ELEMENT X1, Y1, Z1, X3, Y3, Z3;
418 EC_FIELD_ELEMENT b3, t0, t1, t2, t3;
419 EC_FIELD_ELEMENT ga, gb;
420
421 /*
422 * Exception-free point doubling for arbitrary prime order short
423 * Weierstrass curves with arbitrary a - see
424 * https://eprint.iacr.org/2015/1060, algorithm 3 and appendix A.1.
425 */
426
427 ec_field_element_copy(&ga, &group->fe_a);
428 ec_field_element_copy(&gb, &group->fe_b);
429
430 ec_field_element_copy(&X1, &a->fe_x);
431 ec_field_element_copy(&Y1, &a->fe_y);
432 ec_field_element_copy(&Z1, &a->fe_z);
433
434 /* b3 := 3 * b ; */
435 ec_field_element_add(&group->fm, &b3, &gb, &gb);
436 ec_field_element_add(&group->fm, &b3, &b3, &gb);
437
438 /* t0 := X^2; t1 := Y^2; t2 := Z^2 ; */
439 ec_field_element_sqr(&group->fm, &t0, &X1);
440 ec_field_element_sqr(&group->fm, &t1, &Y1);
441 ec_field_element_sqr(&group->fm, &t2, &Z1);
442
443 /* t3 := X * Y ; t3 := t3 + t3 ; Z3 := X * Z ; */
444 ec_field_element_mul(&group->fm, &t3, &X1, &Y1);
445 ec_field_element_add(&group->fm, &t3, &t3, &t3);
446 ec_field_element_mul(&group->fm, &Z3, &X1, &Z1);
447
448 /* Z3 := Z3 + Z3 ; X3 := a * Z3 ; Y3 := b3 * t2 ; */
449 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
450 ec_field_element_mul(&group->fm, &X3, &ga, &Z3);
451 ec_field_element_mul(&group->fm, &Y3, &b3, &t2);
452
453 /* Y3 := X3 + Y3 ; X3 := t1 - Y3 ; Y3 := t1 + Y3 ; */
454 ec_field_element_add(&group->fm, &Y3, &X3, &Y3);
455 ec_field_element_sub(&group->fm, &X3, &t1, &Y3);
456 ec_field_element_add(&group->fm, &Y3, &t1, &Y3);
457
458 /* Y3 := X3 * Y3 ; X3 := t3 * X3 ; Z3 := b3 * Z3 ; */
459 ec_field_element_mul(&group->fm, &Y3, &X3, &Y3);
460 ec_field_element_mul(&group->fm, &X3, &t3, &X3);
461 ec_field_element_mul(&group->fm, &Z3, &b3, &Z3);
462
463 /* t2 := a * t2 ; t3 := t0 - t2 ; t3 := a * t3 ; */
464 ec_field_element_mul(&group->fm, &t2, &ga, &t2);
465 ec_field_element_sub(&group->fm, &t3, &t0, &t2);
466 ec_field_element_mul(&group->fm, &t3, &ga, &t3);
467
468 /* t3 := t3 + Z3 ; Z3 := t0 + t0 ; t0 := Z3 + t0 ; */
469 ec_field_element_add(&group->fm, &t3, &t3, &Z3);
470 ec_field_element_add(&group->fm, &Z3, &t0, &t0);
471 ec_field_element_add(&group->fm, &t0, &Z3, &t0);
472
473 /* t0 := t0 + t2 ; t0 := t0 * t3 ; Y3 := Y3 + t0 ; */
474 ec_field_element_add(&group->fm, &t0, &t0, &t2);
475 ec_field_element_mul(&group->fm, &t0, &t0, &t3);
476 ec_field_element_add(&group->fm, &Y3, &Y3, &t0);
477
478 /* t2 := Y * Z ; t2 := t2 + t2 ; t0 := t2 * t3 ; */
479 ec_field_element_mul(&group->fm, &t2, &Y1, &Z1);
480 ec_field_element_add(&group->fm, &t2, &t2, &t2);
481 ec_field_element_mul(&group->fm, &t0, &t2, &t3);
482
483 /* X3 := X3 - t0 ; Z3 := t2 * t1 ; Z3 := Z3 + Z3 ; */
484 ec_field_element_sub(&group->fm, &X3, &X3, &t0);
485 ec_field_element_mul(&group->fm, &Z3, &t2, &t1);
486 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
487
488 /* Z3 := Z3 + Z3 ; */
489 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
490
491 ec_field_element_copy(&r->fe_x, &X3);
492 ec_field_element_copy(&r->fe_y, &Y3);
493 ec_field_element_copy(&r->fe_z, &Z3);
494
495 return 1;
496}
497
498static int
499ec_point_dbl_a2(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
500{
501 EC_FIELD_ELEMENT X1, Y1, Z1, X3, Y3, Z3;
502 EC_FIELD_ELEMENT t0, t1, t2, t3;
503 EC_FIELD_ELEMENT ga, gb;
504
505 /*
506 * Exception-free point doubling for arbitrary prime order short
507 * Weierstrass curves with a = -3 - see https://eprint.iacr.org/2015/1060,
508 * algorithm 6 and appendix A.2.
509 */
510
511 ec_field_element_copy(&ga, &group->fe_a);
512 ec_field_element_copy(&gb, &group->fe_b);
513
514 ec_field_element_copy(&X1, &a->fe_x);
515 ec_field_element_copy(&Y1, &a->fe_y);
516 ec_field_element_copy(&Z1, &a->fe_z);
517
518 /* t0 := X^2; t1 := Y^2; t2 := Z^2 ; */
519 ec_field_element_sqr(&group->fm, &t0, &X1);
520 ec_field_element_sqr(&group->fm, &t1, &Y1);
521 ec_field_element_sqr(&group->fm, &t2, &Z1);
522
523 /* t3 := X * Y ; t3 := t3 + t3 ; Z3 := X * Z ; */
524 ec_field_element_mul(&group->fm, &t3, &X1, &Y1);
525 ec_field_element_add(&group->fm, &t3, &t3, &t3);
526 ec_field_element_mul(&group->fm, &Z3, &X1, &Z1);
527
528 /* Z3 := Z3 + Z3 ; Y3 := b * t2 ; Y3 := Y3 - Z3 ; */
529 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
530 ec_field_element_mul(&group->fm, &Y3, &gb, &t2);
531 ec_field_element_sub(&group->fm, &Y3, &Y3, &Z3);
532
533 /* X3 := Y3 + Y3 ; Y3 := X3 + Y3 ; X3 := t1 - Y3 ; */
534 ec_field_element_add(&group->fm, &X3, &Y3, &Y3);
535 ec_field_element_add(&group->fm, &Y3, &X3, &Y3);
536 ec_field_element_sub(&group->fm, &X3, &t1, &Y3);
537
538 /* Y3 := t1 + Y3 ; Y3 := X3 * Y3 ; X3 := X3 * t3 ; */
539 ec_field_element_add(&group->fm, &Y3, &t1, &Y3);
540 ec_field_element_mul(&group->fm, &Y3, &X3, &Y3);
541 ec_field_element_mul(&group->fm, &X3, &X3, &t3);
542
543 /* t3 := t2 + t2 ; t2 := t2 + t3 ; Z3 := b * Z3 ; */
544 ec_field_element_add(&group->fm, &t3, &t2, &t2);
545 ec_field_element_add(&group->fm, &t2, &t2, &t3);
546 ec_field_element_mul(&group->fm, &Z3, &gb, &Z3);
547
548 /* Z3 := Z3 - t2 ; Z3 := Z3 - t0 ; t3 := Z3 + Z3 ; */
549 ec_field_element_sub(&group->fm, &Z3, &Z3, &t2);
550 ec_field_element_sub(&group->fm, &Z3, &Z3, &t0);
551 ec_field_element_add(&group->fm, &t3, &Z3, &Z3);
552
553 /* Z3 := Z3 + t3 ; t3 := t0 + t0 ; t0 := t3 + t0 ; */
554 ec_field_element_add(&group->fm, &Z3, &Z3, &t3);
555 ec_field_element_add(&group->fm, &t3, &t0, &t0);
556 ec_field_element_add(&group->fm, &t0, &t3, &t0);
557
558 /* t0 := t0 - t2 ; t0 := t0 * Z3 ; Y3 := Y3 + t0 ; */
559 ec_field_element_sub(&group->fm, &t0, &t0, &t2);
560 ec_field_element_mul(&group->fm, &t0, &t0, &Z3);
561 ec_field_element_add(&group->fm, &Y3, &Y3, &t0);
562
563 /* t0 := Y * Z ; t0 := t0 + t0 ; Z3 := t0 * Z3 ; */
564 ec_field_element_mul(&group->fm, &t0, &Y1, &Z1);
565 ec_field_element_add(&group->fm, &t0, &t0, &t0);
566 ec_field_element_mul(&group->fm, &Z3, &t0, &Z3);
567
568 /* X3 := X3 - Z3 ; Z3 := t0 * t1 ; Z3 := Z3 + Z3 ; */
569 ec_field_element_sub(&group->fm, &X3, &X3, &Z3);
570 ec_field_element_mul(&group->fm, &Z3, &t0, &t1);
571 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
572
573 /* Z3 := Z3 + Z3 ; */
574 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
575
576 ec_field_element_copy(&r->fe_x, &X3);
577 ec_field_element_copy(&r->fe_y, &Y3);
578 ec_field_element_copy(&r->fe_z, &Z3);
579
580 return 1;
581}
582
583static int
584ec_point_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
585{
586 if (group->a_is_minus3)
587 return ec_point_dbl_a2(group, r, a, ctx);
588
589 return ec_point_dbl_a1(group, r, a, ctx);
590}
591
592static int
593ec_point_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
594{
595 EC_FIELD_ELEMENT y;
596 BN_ULONG mask;
597 int i;
598
599 /*
600 * Invert the point by setting Y = p - Y, if Y is non-zero and the point
601 * is not at infinity.
602 */
603
604 mask = ~(0 - (ec_point_is_at_infinity(group, point) |
605 ec_field_element_is_zero(&group->fm, &point->fe_y)));
606
607 /* XXX - masked/conditional subtraction? */
608 ec_field_element_sub(&group->fm, &y, &group->fm.m, &point->fe_y);
609
610 for (i = 0; i < group->fm.n; i++)
611 point->fe_y.w[i] = (point->fe_y.w[i] & ~mask) | (y.w[i] & mask);
612
613 return 1;
614}
615
616static int
617ec_point_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
618{
619 EC_FIELD_ELEMENT sum, axz2, bz3, x3, y2z, z2;
620
621 /*
622 * Curve is defined by a Weierstrass equation y^2 = x^3 + a*x + b.
623 * The given point is in homogeneous projective coordinates
624 * (x = X/Z, y = Y/Z). Substitute and multiply by Z^3 in order to
625 * evaluate as zy^2 = x^3 + axz^2 + bz^3.
626 */
627
628 ec_field_element_sqr(&group->fm, &z2, &point->fe_z);
629
630 ec_field_element_sqr(&group->fm, &y2z, &point->fe_y);
631 ec_field_element_mul(&group->fm, &y2z, &y2z, &point->fe_z);
632
633 ec_field_element_sqr(&group->fm, &x3, &point->fe_x);
634 ec_field_element_mul(&group->fm, &x3, &x3, &point->fe_x);
635
636 ec_field_element_mul(&group->fm, &axz2, &group->fe_a, &point->fe_x);
637 ec_field_element_mul(&group->fm, &axz2, &axz2, &z2);
638
639 ec_field_element_mul(&group->fm, &bz3, &group->fe_b, &point->fe_z);
640 ec_field_element_mul(&group->fm, &bz3, &bz3, &z2);
641
642 ec_field_element_add(&group->fm, &sum, &x3, &axz2);
643 ec_field_element_add(&group->fm, &sum, &sum, &bz3);
644
645 return ec_field_element_equal(&group->fm, &y2z, &sum) |
646 ec_point_is_at_infinity(group, point);
647}
648
649static int
650ec_point_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
651{
652 EC_FIELD_ELEMENT ax, ay, bx, by;
653
654 /*
655 * Compare two points that have homogeneous projection coordinates, that
656 * is (X_a/Z_a, Y_a/Z_a) == (X_b/Z_b, Y_b/Z_b). Return -1 on error, 0 on
657 * equality and 1 on inequality.
658 *
659 * If a and b are both at infinity, Z_a and Z_b will both be zero,
660 * resulting in all values becoming zero, resulting in equality. If a is
661 * at infinity and b is not, then Y_a will be one and Z_b will be
662 * non-zero, hence Y_a * Z_b will be non-zero. Z_a will be zero, hence
663 * Y_b * Z_a will be zero, resulting in inequality. The same applies if
664 * b is at infinity and a is not.
665 */
666
667 ec_field_element_mul(&group->fm, &ax, &a->fe_x, &b->fe_z);
668 ec_field_element_mul(&group->fm, &ay, &a->fe_y, &b->fe_z);
669 ec_field_element_mul(&group->fm, &bx, &b->fe_x, &a->fe_z);
670 ec_field_element_mul(&group->fm, &by, &b->fe_y, &a->fe_z);
671
672 return 1 - (ec_field_element_equal(&group->fm, &ax, &bx) &
673 ec_field_element_equal(&group->fm, &ay, &by));
674}
675
676#if 0
677static int
678ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
679 BN_CTX *ctx)
680{
681 size_t i;
682
683 /* XXX */
684 for (i = 0; i < num; i++) {
685 if (!EC_POINT_make_affine(group, points[0], ctx))
686 return 0;
687 }
688
689 return 1;
690}
691#else
692
693static int
694ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
695 BN_CTX *ctx)
696{
697 BIGNUM **prod_Z = NULL;
698 BIGNUM *tmp, *tmp_Z;
699 size_t i;
700 int ret = 0;
701
702 if (num == 0)
703 return 1;
704
705 BN_CTX_start(ctx);
706
707 if ((tmp = BN_CTX_get(ctx)) == NULL)
708 goto err;
709 if ((tmp_Z = BN_CTX_get(ctx)) == NULL)
710 goto err;
711
712 if ((prod_Z = calloc(num, sizeof *prod_Z)) == NULL)
713 goto err;
714 for (i = 0; i < num; i++) {
715 if ((prod_Z[i] = BN_CTX_get(ctx)) == NULL)
716 goto err;
717 }
718
719 if (!BN_is_zero(points[0]->Z)) {
720 if (!bn_copy(prod_Z[0], points[0]->Z))
721 goto err;
722 } else {
723 if (!BN_one(prod_Z[0]))
724 goto err;
725 }
726
727 for (i = 1; i < num; i++) {
728 if (!BN_is_zero(points[i]->Z)) {
729 if (!BN_mod_mul(prod_Z[i], prod_Z[i - 1], points[i]->Z,
730 group->p, ctx))
731 goto err;
732 } else {
733 if (!bn_copy(prod_Z[i], prod_Z[i - 1]))
734 goto err;
735 }
736 }
737
738 if (!BN_mod_inverse_nonct(tmp, prod_Z[num - 1], group->p, ctx)) {
739 ECerror(ERR_R_BN_LIB);
740 goto err;
741 }
742
743 for (i = num - 1; i > 0; i--) {
744 if (BN_is_zero(points[i]->Z))
745 continue;
746
747 if (!BN_mod_mul(tmp_Z, prod_Z[i - 1], tmp, group->p, ctx))
748 goto err;
749 if (!BN_mod_mul(tmp, tmp, points[i]->Z, group->p, ctx))
750 goto err;
751 if (!bn_copy(points[i]->Z, tmp_Z))
752 goto err;
753 }
754
755 for (i = 0; i < num; i++) {
756 EC_POINT *p = points[i];
757
758 if (BN_is_zero(p->Z))
759 continue;
760
761 if (!BN_mod_mul(p->X, p->X, p->Z, group->p, ctx))
762 goto err;
763 if (!BN_mod_mul(p->Y, p->Y, p->Z, group->p, ctx))
764 goto err;
765
766 if (!BN_one(p->Z))
767 goto err;
768 }
769
770 ret = 1;
771
772 err:
773 BN_CTX_end(ctx);
774 free(prod_Z);
775
776 return ret;
777}
778#endif
779
780static void
781ec_point_select(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
782 const EC_POINT *b, int conditional)
783{
784 ec_field_element_select(&group->fm, &r->fe_x, &a->fe_x, &b->fe_x, conditional);
785 ec_field_element_select(&group->fm, &r->fe_y, &a->fe_y, &b->fe_y, conditional);
786 ec_field_element_select(&group->fm, &r->fe_z, &a->fe_z, &b->fe_z, conditional);
787}
788
789static int
790ec_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, const EC_POINT *point,
791 BN_CTX *ctx)
792{
793 BIGNUM *cardinality;
794 EC_POINT *multiples[15];
795 EC_POINT *rr = NULL, *t = NULL;
796 uint8_t *scalar_bytes = NULL;
797 int scalar_len = 0;
798 uint8_t j, wv;
799 int conditional, i;
800 int ret = 0;
801
802 memset(multiples, 0, sizeof(multiples));
803
804 BN_CTX_start(ctx);
805
806 /* XXX - consider blinding. */
807
808 if ((cardinality = BN_CTX_get(ctx)) == NULL)
809 goto err;
810 if (!BN_mul(cardinality, group->order, group->cofactor, ctx))
811 goto err;
812
813 /* XXX - handle scalar > cardinality and/or negative. */
814
815 /* Convert scalar into big endian bytes. */
816 scalar_len = BN_num_bytes(cardinality);
817 if ((scalar_bytes = calloc(1, scalar_len)) == NULL)
818 goto err;
819 if (!BN_bn2binpad(scalar, scalar_bytes, scalar_len))
820 goto err;
821
822 /* Compute multiples of point. */
823 if ((multiples[0] = EC_POINT_dup(point, group)) == NULL)
824 goto err;
825 for (i = 1; i < 15; i += 2) {
826 if ((multiples[i] = EC_POINT_new(group)) == NULL)
827 goto err;
828 if (!EC_POINT_dbl(group, multiples[i], multiples[i / 2], ctx))
829 goto err;
830 if ((multiples[i + 1] = EC_POINT_new(group)) == NULL)
831 goto err;
832 if (!EC_POINT_add(group, multiples[i + 1], multiples[i], point, ctx))
833 goto err;
834 }
835
836 if ((rr = EC_POINT_new(group)) == NULL)
837 goto err;
838 if ((t = EC_POINT_new(group)) == NULL)
839 goto err;
840
841 if (!EC_POINT_set_to_infinity(group, rr))
842 goto err;
843
844 for (i = 0; i < scalar_len; i++) {
845 if (i != 0) {
846 if (!EC_POINT_dbl(group, rr, rr, ctx))
847 goto err;
848 if (!EC_POINT_dbl(group, rr, rr, ctx))
849 goto err;
850 if (!EC_POINT_dbl(group, rr, rr, ctx))
851 goto err;
852 if (!EC_POINT_dbl(group, rr, rr, ctx))
853 goto err;
854 }
855
856 if (!EC_POINT_set_to_infinity(group, t))
857 goto err;
858
859 wv = scalar_bytes[i] >> 4;
860 for (j = 1; j < 16; j++) {
861 conditional = crypto_ct_eq_u8(j, wv);
862 ec_point_select(group, t, t, multiples[j - 1], conditional);
863 }
864 if (!EC_POINT_add(group, rr, rr, t, ctx))
865 goto err;
866
867 if (!EC_POINT_dbl(group, rr, rr, ctx))
868 goto err;
869 if (!EC_POINT_dbl(group, rr, rr, ctx))
870 goto err;
871 if (!EC_POINT_dbl(group, rr, rr, ctx))
872 goto err;
873 if (!EC_POINT_dbl(group, rr, rr, ctx))
874 goto err;
875
876 if (!EC_POINT_set_to_infinity(group, t))
877 goto err;
878
879 wv = scalar_bytes[i] & 0xf;
880 for (j = 1; j < 16; j++) {
881 conditional = crypto_ct_eq_u8(j, wv);
882 ec_point_select(group, t, t, multiples[j - 1], conditional);
883 }
884 if (!EC_POINT_add(group, rr, rr, t, ctx))
885 goto err;
886 }
887
888 if (!EC_POINT_copy(r, rr))
889 goto err;
890
891 ret = 1;
892
893 err:
894 for (i = 0; i < 15; i++)
895 EC_POINT_free(multiples[i]);
896
897 EC_POINT_free(rr);
898 EC_POINT_free(t);
899
900 freezero(scalar_bytes, scalar_len);
901
902 BN_CTX_end(ctx);
903
904 return ret;
905}
906
907static int
908ec_mul_single_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
909 const EC_POINT *point, BN_CTX *ctx)
910{
911 return ec_mul(group, r, scalar, point, ctx);
912}
913
914static int
915ec_mul_double_nonct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar1,
916 const EC_POINT *point1, const BIGNUM *scalar2, const EC_POINT *point2,
917 BN_CTX *ctx)
918{
919 return ec_wnaf_mul(group, r, scalar1, point1, scalar2, point2, ctx);
920}
921
922static const EC_METHOD ec_GFp_homogeneous_projective_method = {
923 .group_set_curve = ec_group_set_curve,
924 .group_get_curve = ec_group_get_curve,
925 .point_set_to_infinity = ec_point_set_to_infinity,
926 .point_is_at_infinity = ec_point_is_at_infinity,
927 .point_set_affine_coordinates = ec_point_set_affine_coordinates,
928 .point_get_affine_coordinates = ec_point_get_affine_coordinates,
929 .add = ec_point_add,
930 .dbl = ec_point_dbl,
931 .invert = ec_point_invert,
932 .point_is_on_curve = ec_point_is_on_curve,
933 .point_cmp = ec_point_cmp,
934 .points_make_affine = ec_points_make_affine,
935 .mul_single_ct = ec_mul_single_ct,
936 .mul_double_nonct = ec_mul_double_nonct,
937};
938
939const EC_METHOD *
940EC_GFp_homogeneous_projective_method(void)
941{
942 return &ec_GFp_homogeneous_projective_method;
943}
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-08-14 11:54:53 +0000