summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorjsing <>2025-05-25 05:19:26 +0000
committerjsing <>2025-05-25 05:19:26 +0000
commit26512301343d2b40a68a67d4f4175ddec368d2fe (patch)
tree158af8a3059a17256965840a4bec7c251f8c6151 /src
parent2f7bf75477a5741ad76c3c793c7ed887b41fcceb (diff)
downloadopenbsd-26512301343d2b40a68a67d4f4175ddec368d2fe.tar.gz
openbsd-26512301343d2b40a68a67d4f4175ddec368d2fe.tar.bz2
openbsd-26512301343d2b40a68a67d4f4175ddec368d2fe.zip
Provide an EC method that uses homogeneous projective coordinates.
This makes use of EC_FIELD_ELEMENT to perform fixed width constant time operations. Addition and doubling of points makes use of the formulas from "Complete addition formulas for prime order elliptic curves" (https://eprint.iacr.org/2015/1060). These are complete and operate in constant time. Further work will continue in tree. ok tb@
Diffstat (limited to 'src')
-rw-r--r--src/lib/libcrypto/Makefile3
-rw-r--r--src/lib/libcrypto/ec/ec_local.h11
-rw-r--r--src/lib/libcrypto/ec/ecp_hp_methods.c858
3 files changed, 870 insertions, 2 deletions
diff --git a/src/lib/libcrypto/Makefile b/src/lib/libcrypto/Makefile
index 7564001961..6adfe45e6f 100644
--- a/src/lib/libcrypto/Makefile
+++ b/src/lib/libcrypto/Makefile
@@ -1,4 +1,4 @@
1# $OpenBSD: Makefile,v 1.234 2025/05/25 05:12:05 jsing Exp $ 1# $OpenBSD: Makefile,v 1.235 2025/05/25 05:19:26 jsing Exp $
2 2
3LIB= crypto 3LIB= crypto
4LIBREBUILD=y 4LIBREBUILD=y
@@ -289,6 +289,7 @@ SRCS+= ec_lib.c
289SRCS+= ec_mult.c 289SRCS+= ec_mult.c
290SRCS+= ec_pmeth.c 290SRCS+= ec_pmeth.c
291SRCS+= eck_prn.c 291SRCS+= eck_prn.c
292SRCS+= ecp_hp_methods.c
292SRCS+= ecp_methods.c 293SRCS+= ecp_methods.c
293SRCS+= ecx_methods.c 294SRCS+= ecx_methods.c
294 295
diff --git a/src/lib/libcrypto/ec/ec_local.h b/src/lib/libcrypto/ec/ec_local.h
index c0ff026fb2..75a3e25247 100644
--- a/src/lib/libcrypto/ec/ec_local.h
+++ b/src/lib/libcrypto/ec/ec_local.h
@@ -1,4 +1,4 @@
1/* $OpenBSD: ec_local.h,v 1.68 2025/05/24 08:25:58 jsing Exp $ */ 1/* $OpenBSD: ec_local.h,v 1.69 2025/05/25 05:19:26 jsing Exp $ */
2/* 2/*
3 * Originally written by Bodo Moeller for the OpenSSL project. 3 * Originally written by Bodo Moeller for the OpenSSL project.
4 */ 4 */
@@ -76,6 +76,7 @@
76#include <openssl/objects.h> 76#include <openssl/objects.h>
77 77
78#include "bn_local.h" 78#include "bn_local.h"
79#include "ec_internal.h"
79 80
80__BEGIN_HIDDEN_DECLS 81__BEGIN_HIDDEN_DECLS
81 82
@@ -158,6 +159,10 @@ struct ec_group_st {
158 159
159 /* Montgomery context used by EC_GFp_mont_method. */ 160 /* Montgomery context used by EC_GFp_mont_method. */
160 BN_MONT_CTX *mont_ctx; 161 BN_MONT_CTX *mont_ctx;
162
163 EC_FIELD_MODULUS fm;
164 EC_FIELD_ELEMENT fe_a;
165 EC_FIELD_ELEMENT fe_b;
161} /* EC_GROUP */; 166} /* EC_GROUP */;
162 167
163struct ec_point_st { 168struct ec_point_st {
@@ -171,6 +176,10 @@ struct ec_point_st {
171 BIGNUM *Y; 176 BIGNUM *Y;
172 BIGNUM *Z; 177 BIGNUM *Z;
173 int Z_is_one; /* enable optimized point arithmetics for special case */ 178 int Z_is_one; /* enable optimized point arithmetics for special case */
179
180 EC_FIELD_ELEMENT fe_x;
181 EC_FIELD_ELEMENT fe_y;
182 EC_FIELD_ELEMENT fe_z;
174} /* EC_POINT */; 183} /* EC_POINT */;
175 184
176const EC_METHOD *EC_GFp_simple_method(void); 185const EC_METHOD *EC_GFp_simple_method(void);
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..0c6b095765
--- /dev/null
+++ b/src/lib/libcrypto/ec/ecp_hp_methods.c
@@ -0,0 +1,858 @@
1/* $OpenBSD: ecp_hp_methods.c,v 1.1 2025/05/25 05:19:26 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 "ec_local.h"
26#include "ec_internal.h"
27#include "err_local.h"
28
29/*
30 * TODO:
31 * - Constant time and blinding for scalar multiplication
32 */
33
34static int
35ec_group_set_curve(EC_GROUP *group, const BIGNUM *p, const BIGNUM *a,
36 const BIGNUM *b, BN_CTX *ctx)
37{
38 BIGNUM *t;
39 int ret = 0;
40
41 BN_CTX_start(ctx);
42
43 /* XXX - p must be a prime > 3. */
44
45 if (!bn_copy(group->p, p))
46 goto err;
47 if (!bn_copy(group->a, a))
48 goto err;
49 if (!bn_copy(group->b, b))
50 goto err;
51
52 /* XXX */
53 BN_set_negative(group->p, 0);
54
55 /* XXX */
56 if (!BN_nnmod(group->a, group->a, group->p, ctx))
57 goto err;
58 if (!BN_nnmod(group->b, group->b, group->p, ctx))
59 goto err;
60
61 if ((t = BN_CTX_get(ctx)) == NULL)
62 goto err;
63 if (!BN_set_word(t, 3))
64 goto err;
65 if (!BN_mod_add(t, t, a, group->p, ctx))
66 goto err;
67
68 group->a_is_minus3 = BN_is_zero(t);
69
70 if (!ec_field_modulus_from_bn(&group->fm, group->p, ctx))
71 goto err;
72 if (!ec_field_element_from_bn(&group->fm, group, &group->fe_a, group->a, ctx))
73 goto err;
74 if (!ec_field_element_from_bn(&group->fm, group, &group->fe_b, group->b, ctx))
75 goto err;
76
77 ret = 1;
78
79 err:
80 BN_CTX_end(ctx);
81
82 return ret;
83}
84
85static int
86ec_group_get_curve(const EC_GROUP *group, BIGNUM *p, BIGNUM *a,
87 BIGNUM *b, BN_CTX *ctx)
88{
89 if (p != NULL) {
90 if (!bn_copy(p, group->p))
91 return 0;
92 }
93 if (a != NULL) {
94 if (!bn_copy(a, group->a))
95 return 0;
96 }
97 if (b != NULL) {
98 if (!bn_copy(b, group->b))
99 return 0;
100 }
101 return 1;
102}
103
104static int
105ec_point_is_at_infinity(const EC_GROUP *group, const EC_POINT *point)
106{
107 /* Check if Z is equal to zero. */
108 return ec_field_element_is_zero(&group->fm, &point->fe_z);
109}
110
111static int
112ec_point_set_to_infinity(const EC_GROUP *group, EC_POINT *point)
113{
114 /* Infinity is (x = 0, y = 1, z = 0). */
115
116 memset(&point->fe_x, 0, sizeof(point->fe_x));
117 memset(&point->fe_y, 0, sizeof(point->fe_y));
118 memset(&point->fe_z, 0, sizeof(point->fe_z));
119
120 point->fe_y.w[0] = 1;
121
122 return 1;
123}
124
125static int
126ec_point_set_affine_coordinates(const EC_GROUP *group, EC_POINT *point,
127 const BIGNUM *x, const BIGNUM *y, BN_CTX *ctx)
128{
129 if (x == NULL || y == NULL) {
130 ECerror(ERR_R_PASSED_NULL_PARAMETER);
131 return 0;
132 }
133
134 if (!bn_copy(point->X, x))
135 return 0;
136 if (!bn_copy(point->Y, y))
137 return 0;
138 if (!BN_one(point->Z))
139 return 0;
140
141 /* XXX */
142 if (!BN_nnmod(point->X, point->X, group->p, ctx))
143 return 0;
144 if (!BN_nnmod(point->Y, point->Y, group->p, ctx))
145 return 0;
146
147 if (!ec_field_element_from_bn(&group->fm, group, &point->fe_x, point->X, ctx))
148 return 0;
149 if (!ec_field_element_from_bn(&group->fm, group, &point->fe_y, point->Y, ctx))
150 return 0;
151 if (!ec_field_element_from_bn(&group->fm, group, &point->fe_z, point->Z, ctx))
152 return 0;
153
154 return 1;
155}
156
157static int
158ec_point_get_affine_coordinates(const EC_GROUP *group, const EC_POINT *point,
159 BIGNUM *x, BIGNUM *y, BN_CTX *ctx)
160{
161 BIGNUM *zinv;
162 int ret = 0;
163
164 /*
165 * Convert homogeneous projective coordinates (XZ, YZ, Z) to affine
166 * coordinates (x = X/Z, y = Y/Z).
167 */
168 if (!ec_field_element_to_bn(&group->fm, &point->fe_x, point->X, ctx))
169 return 0;
170 if (!ec_field_element_to_bn(&group->fm, &point->fe_y, point->Y, ctx))
171 return 0;
172 if (!ec_field_element_to_bn(&group->fm, &point->fe_z, point->Z, ctx))
173 return 0;
174
175 BN_CTX_start(ctx);
176
177 if ((zinv = BN_CTX_get(ctx)) == NULL)
178 goto err;
179
180 if (BN_mod_inverse_ct(zinv, point->Z, group->p, ctx) == NULL)
181 goto err;
182
183 if (x != NULL) {
184 if (!BN_mod_mul(x, point->X, zinv, group->p, ctx))
185 goto err;
186 }
187 if (y != NULL) {
188 if (!BN_mod_mul(y, point->Y, zinv, group->p, ctx))
189 goto err;
190 }
191
192 ret = 1;
193
194 err:
195 BN_CTX_end(ctx);
196
197 return ret;
198}
199
200static int
201ec_point_add_a1(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
202 const EC_POINT *b, BN_CTX *ctx)
203{
204 EC_FIELD_ELEMENT X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3;
205 EC_FIELD_ELEMENT b3, t0, t1, t2, t3, t4, t5;
206 EC_FIELD_ELEMENT ga, gb;
207
208 /*
209 * Complete, projective point addition for arbitrary prime order short
210 * Weierstrass curves with arbitrary a - see
211 * https://eprint.iacr.org/2015/1060, algorithm 1 and appendix A.1.
212 */
213
214 ec_field_element_copy(&ga, &group->fe_a);
215 ec_field_element_copy(&gb, &group->fe_b);
216
217 ec_field_element_copy(&X1, &a->fe_x);
218 ec_field_element_copy(&Y1, &a->fe_y);
219 ec_field_element_copy(&Z1, &a->fe_z);
220
221 ec_field_element_copy(&X2, &b->fe_x);
222 ec_field_element_copy(&Y2, &b->fe_y);
223 ec_field_element_copy(&Z2, &b->fe_z);
224
225 /* b3 := 3 * b ; */
226 ec_field_element_add(&group->fm, &b3, &gb, &gb);
227 ec_field_element_add(&group->fm, &b3, &b3, &gb);
228
229 /* t0 := X1 * X2 ; t1 := Y1 * Y2 ; t2 := Z1 * Z2 ; */
230 ec_field_element_mul(&group->fm, &t0, &X1, &X2);
231 ec_field_element_mul(&group->fm, &t1, &Y1, &Y2);
232 ec_field_element_mul(&group->fm, &t2, &Z1, &Z2);
233
234 /* t3 := X1 + Y1 ; t4 := X2 + Y2 ; t3 := t3 * t4 ; */
235 ec_field_element_add(&group->fm, &t3, &X1, &Y1);
236 ec_field_element_add(&group->fm, &t4, &X2, &Y2);
237 ec_field_element_mul(&group->fm, &t3, &t3, &t4);
238
239 /* t4 := t0 + t1 ; t3 := t3 - t4 ; t4 := X1 + Z1 ; */
240 ec_field_element_add(&group->fm, &t4, &t0, &t1);
241 ec_field_element_sub(&group->fm, &t3, &t3, &t4);
242 ec_field_element_add(&group->fm, &t4, &X1, &Z1);
243
244 /* t5 := X2 + Z2 ; t4 := t4 * t5 ; t5 := t0 + t2 ; */
245 ec_field_element_add(&group->fm, &t5, &X2, &Z2);
246 ec_field_element_mul(&group->fm, &t4, &t4, &t5);
247 ec_field_element_add(&group->fm, &t5, &t0, &t2);
248
249 /* t4 := t4 - t5 ; t5 := Y1 + Z1 ; X3 := Y2 + Z2 ; */
250 ec_field_element_sub(&group->fm, &t4, &t4, &t5);
251 ec_field_element_add(&group->fm, &t5, &Y1, &Z1);
252 ec_field_element_add(&group->fm, &X3, &Y2, &Z2);
253
254 /* t5 := t5 * X3 ; X3 := t1 + t2 ; t5 := t5 - X3 ; */
255 ec_field_element_mul(&group->fm, &t5, &t5, &X3);
256 ec_field_element_add(&group->fm, &X3, &t1, &t2);
257 ec_field_element_sub(&group->fm, &t5, &t5, &X3);
258
259 /* Z3 := a * t4 ; X3 := b3 * t2 ; Z3 := X3 + Z3 ; */
260 ec_field_element_mul(&group->fm, &Z3, &ga, &t4);
261 ec_field_element_mul(&group->fm, &X3, &b3, &t2);
262 ec_field_element_add(&group->fm, &Z3, &X3, &Z3);
263
264 /* X3 := t1 - Z3 ; Z3 := t1 + Z3 ; Y3 := X3 * Z3 ; */
265 ec_field_element_sub(&group->fm, &X3, &t1, &Z3);
266 ec_field_element_add(&group->fm, &Z3, &t1, &Z3);
267 ec_field_element_mul(&group->fm, &Y3, &X3, &Z3);
268
269 /* t1 := t0 + t0 ; t1 := t1 + t0 ; t2 := a * t2 ; */
270 ec_field_element_add(&group->fm, &t1, &t0, &t0);
271 ec_field_element_add(&group->fm, &t1, &t1, &t0);
272 ec_field_element_mul(&group->fm, &t2, &ga, &t2);
273
274 /* t4 := b3 * t4 ; t1 := t1 + t2 ; t2 := t0 - t2 ; */
275 ec_field_element_mul(&group->fm, &t4, &b3, &t4);
276 ec_field_element_add(&group->fm, &t1, &t1, &t2);
277 ec_field_element_sub(&group->fm, &t2, &t0, &t2);
278
279 /* t2 := a * t2 ; t4 := t4 + t2 ; t0 := t1 * t4 ; */
280 ec_field_element_mul(&group->fm, &t2, &ga, &t2);
281 ec_field_element_add(&group->fm, &t4, &t4, &t2);
282 ec_field_element_mul(&group->fm, &t0, &t1, &t4);
283
284 /* Y3 := Y3 + t0 ; t0 := t5 * t4 ; X3 := t3 * X3 ; */
285 ec_field_element_add(&group->fm, &Y3, &Y3, &t0);
286 ec_field_element_mul(&group->fm, &t0, &t5, &t4);
287 ec_field_element_mul(&group->fm, &X3, &t3, &X3);
288
289 /* X3 := X3 - t0 ; t0 := t3 * t1 ; Z3 := t5 * Z3 ; */
290 ec_field_element_sub(&group->fm, &X3, &X3, &t0);
291 ec_field_element_mul(&group->fm, &t0, &t3, &t1);
292 ec_field_element_mul(&group->fm, &Z3, &t5, &Z3);
293
294 /* Z3 := Z3 + t0 ; */
295 ec_field_element_add(&group->fm, &Z3, &Z3, &t0);
296
297 ec_field_element_copy(&r->fe_x, &X3);
298 ec_field_element_copy(&r->fe_y, &Y3);
299 ec_field_element_copy(&r->fe_z, &Z3);
300
301 return 1;
302}
303
304static int
305ec_point_add_a2(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
306 const EC_POINT *b, BN_CTX *ctx)
307{
308 EC_FIELD_ELEMENT X1, Y1, Z1, X2, Y2, Z2, X3, Y3, Z3;
309 EC_FIELD_ELEMENT t0, t1, t2, t3, t4;
310 EC_FIELD_ELEMENT gb;
311
312 /*
313 * Complete, projective point addition for arbitrary prime order short
314 * Weierstrass curves with a = -3 - see https://eprint.iacr.org/2015/1060,
315 * algorithm 4 and appendix A.2.
316 */
317
318 ec_field_element_copy(&gb, &group->fe_b);
319
320 ec_field_element_copy(&X1, &a->fe_x);
321 ec_field_element_copy(&Y1, &a->fe_y);
322 ec_field_element_copy(&Z1, &a->fe_z);
323
324 ec_field_element_copy(&X2, &b->fe_x);
325 ec_field_element_copy(&Y2, &b->fe_y);
326 ec_field_element_copy(&Z2, &b->fe_z);
327
328 /* t0 := X1 * X2 ; t1 := Y1 * Y2 ; t2 := Z1 * Z2 ; */
329 ec_field_element_mul(&group->fm, &t0, &X1, &X2);
330 ec_field_element_mul(&group->fm, &t1, &Y1, &Y2);
331 ec_field_element_mul(&group->fm, &t2, &Z1, &Z2);
332
333 /* t3 := X1 + Y1 ; t4 := X2 + Y2 ; t3 := t3 * t4 ; */
334 ec_field_element_add(&group->fm, &t3, &X1, &Y1);
335 ec_field_element_add(&group->fm, &t4, &X2, &Y2);
336 ec_field_element_mul(&group->fm, &t3, &t3, &t4);
337
338 /* t4 := t0 + t1 ; t3 := t3 - t4 ; t4 := Y1 + Z1 ; */
339 ec_field_element_add(&group->fm, &t4, &t0, &t1);
340 ec_field_element_sub(&group->fm, &t3, &t3, &t4);
341 ec_field_element_add(&group->fm, &t4, &Y1, &Z1);
342
343 /* X3 := Y2 + Z2 ; t4 := t4 * X3 ; X3 := t1 + t2 ; */
344 ec_field_element_add(&group->fm, &X3, &Y2, &Z2);
345 ec_field_element_mul(&group->fm, &t4, &t4, &X3);
346 ec_field_element_add(&group->fm, &X3, &t1, &t2);
347
348 /* t4 := t4 - X3 ; X3 := X1 + Z1 ; Y3 := X2 + Z2 ; */
349 ec_field_element_sub(&group->fm, &t4, &t4, &X3);
350 ec_field_element_add(&group->fm, &X3, &X1, &Z1);
351 ec_field_element_add(&group->fm, &Y3, &X2, &Z2);
352
353 /* X3 := X3 * Y3 ; Y3 := t0 + t2 ; Y3 := X3 - Y3 ; */
354 ec_field_element_mul(&group->fm, &X3, &X3, &Y3);
355 ec_field_element_add(&group->fm, &Y3, &t0, &t2);
356 ec_field_element_sub(&group->fm, &Y3, &X3, &Y3);
357
358 /* Z3 := b * t2 ; X3 := Y3 - Z3 ; Z3 := X3 + X3 ; */
359 ec_field_element_mul(&group->fm, &Z3, &gb, &t2);
360 ec_field_element_sub(&group->fm, &X3, &Y3, &Z3);
361 ec_field_element_add(&group->fm, &Z3, &X3, &X3);
362
363 /* X3 := X3 + Z3 ; Z3 := t1 - X3 ; X3 := t1 + X3 ; */
364 ec_field_element_add(&group->fm, &X3, &X3, &Z3);
365 ec_field_element_sub(&group->fm, &Z3, &t1, &X3);
366 ec_field_element_add(&group->fm, &X3, &t1, &X3);
367
368 /* Y3 := b * Y3 ; t1 := t2 + t2 ; t2 := t1 + t2 ; */
369 ec_field_element_mul(&group->fm, &Y3, &gb, &Y3);
370 ec_field_element_add(&group->fm, &t1, &t2, &t2);
371 ec_field_element_add(&group->fm, &t2, &t1, &t2);
372
373 /* Y3 := Y3 - t2 ; Y3 := Y3 - t0 ; t1 := Y3 + Y3 ; */
374 ec_field_element_sub(&group->fm, &Y3, &Y3, &t2);
375 ec_field_element_sub(&group->fm, &Y3, &Y3, &t0);
376 ec_field_element_add(&group->fm, &t1, &Y3, &Y3);
377
378 /* Y3 := t1 + Y3 ; t1 := t0 + t0 ; t0 := t1 + t0 ; */
379 ec_field_element_add(&group->fm, &Y3, &t1, &Y3);
380 ec_field_element_add(&group->fm, &t1, &t0, &t0);
381 ec_field_element_add(&group->fm, &t0, &t1, &t0);
382
383 /* t0 := t0 - t2 ; t1 := t4 * Y3 ; t2 := t0 * Y3 ; */
384 ec_field_element_sub(&group->fm, &t0, &t0, &t2);
385 ec_field_element_mul(&group->fm, &t1, &t4, &Y3);
386 ec_field_element_mul(&group->fm, &t2, &t0, &Y3);
387
388 /* Y3 := X3 * Z3 ; Y3 := Y3 + t2 ; X3 := t3 * X3 ; */
389 ec_field_element_mul(&group->fm, &Y3, &X3, &Z3);
390 ec_field_element_add(&group->fm, &Y3, &Y3, &t2);
391 ec_field_element_mul(&group->fm, &X3, &t3, &X3);
392
393 /* X3 := X3 - t1 ; Z3 := t4 * Z3 ; t1 := t3 * t0 ; */
394 ec_field_element_sub(&group->fm, &X3, &X3, &t1);
395 ec_field_element_mul(&group->fm, &Z3, &t4, &Z3);
396 ec_field_element_mul(&group->fm, &t1, &t3, &t0);
397
398 /* Z3 := Z3 + t1 ; */
399 ec_field_element_add(&group->fm, &Z3, &Z3, &t1);
400
401 ec_field_element_copy(&r->fe_x, &X3);
402 ec_field_element_copy(&r->fe_y, &Y3);
403 ec_field_element_copy(&r->fe_z, &Z3);
404
405 return 1;
406}
407
408static int
409ec_point_add(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a,
410 const EC_POINT *b, BN_CTX *ctx)
411{
412 if (group->a_is_minus3)
413 return ec_point_add_a2(group, r, a, b, ctx);
414
415 return ec_point_add_a1(group, r, a, b, ctx);
416}
417
418static int
419ec_point_dbl_a1(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
420{
421 EC_FIELD_ELEMENT X1, Y1, Z1, X3, Y3, Z3;
422 EC_FIELD_ELEMENT b3, t0, t1, t2, t3;
423 EC_FIELD_ELEMENT ga, gb;
424
425 /*
426 * Exception-free point doubling for arbitrary prime order short
427 * Weierstrass curves with arbitrary a - see
428 * https://eprint.iacr.org/2015/1060, algorithm 3 and appendix A.1.
429 */
430
431 ec_field_element_copy(&ga, &group->fe_a);
432 ec_field_element_copy(&gb, &group->fe_b);
433
434 ec_field_element_copy(&X1, &a->fe_x);
435 ec_field_element_copy(&Y1, &a->fe_y);
436 ec_field_element_copy(&Z1, &a->fe_z);
437
438 /* b3 := 3 * b ; */
439 ec_field_element_add(&group->fm, &b3, &gb, &gb);
440 ec_field_element_add(&group->fm, &b3, &b3, &gb);
441
442 /* b3 := 3 * b ; */
443 ec_field_element_add(&group->fm, &b3, &gb, &gb);
444 ec_field_element_add(&group->fm, &b3, &b3, &gb);
445
446 /* t0 := X^2; t1 := Y^2; t2 := Z^2 ; */
447 ec_field_element_sqr(&group->fm, &t0, &X1);
448 ec_field_element_sqr(&group->fm, &t1, &Y1);
449 ec_field_element_sqr(&group->fm, &t2, &Z1);
450
451 /* t3 := X * Y ; t3 := t3 + t3 ; Z3 := X * Z ; */
452 ec_field_element_mul(&group->fm, &t3, &X1, &Y1);
453 ec_field_element_add(&group->fm, &t3, &t3, &t3);
454 ec_field_element_mul(&group->fm, &Z3, &X1, &Z1);
455
456 /* Z3 := Z3 + Z3 ; X3 := a * Z3 ; Y3 := b3 * t2 ; */
457 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
458 ec_field_element_mul(&group->fm, &X3, &ga, &Z3);
459 ec_field_element_mul(&group->fm, &Y3, &b3, &t2);
460
461 /* Y3 := X3 + Y3 ; X3 := t1 - Y3 ; Y3 := t1 + Y3 ; */
462 ec_field_element_add(&group->fm, &Y3, &X3, &Y3);
463 ec_field_element_sub(&group->fm, &X3, &t1, &Y3);
464 ec_field_element_add(&group->fm, &Y3, &t1, &Y3);
465
466 /* Y3 := X3 * Y3 ; X3 := t3 * X3 ; Z3 := b3 * Z3 ; */
467 ec_field_element_mul(&group->fm, &Y3, &X3, &Y3);
468 ec_field_element_mul(&group->fm, &X3, &t3, &X3);
469 ec_field_element_mul(&group->fm, &Z3, &b3, &Z3);
470
471 /* t2 := a * t2 ; t3 := t0 - t2 ; t3 := a * t3 ; */
472 ec_field_element_mul(&group->fm, &t2, &ga, &t2);
473 ec_field_element_sub(&group->fm, &t3, &t0, &t2);
474 ec_field_element_mul(&group->fm, &t3, &ga, &t3);
475
476 /* t3 := t3 + Z3 ; Z3 := t0 + t0 ; t0 := Z3 + t0 ; */
477 ec_field_element_add(&group->fm, &t3, &t3, &Z3);
478 ec_field_element_add(&group->fm, &Z3, &t0, &t0);
479 ec_field_element_add(&group->fm, &t0, &Z3, &t0);
480
481 /* t0 := t0 + t2 ; t0 := t0 * t3 ; Y3 := Y3 + t0 ; */
482 ec_field_element_add(&group->fm, &t0, &t0, &t2);
483 ec_field_element_mul(&group->fm, &t0, &t0, &t3);
484 ec_field_element_add(&group->fm, &Y3, &Y3, &t0);
485
486 /* t2 := Y * Z ; t2 := t2 + t2 ; t0 := t2 * t3 ; */
487 ec_field_element_mul(&group->fm, &t2, &Y1, &Z1);
488 ec_field_element_add(&group->fm, &t2, &t2, &t2);
489 ec_field_element_mul(&group->fm, &t0, &t2, &t3);
490
491 /* X3 := X3 - t0 ; Z3 := t2 * t1 ; Z3 := Z3 + Z3 ; */
492 ec_field_element_sub(&group->fm, &X3, &X3, &t0);
493 ec_field_element_mul(&group->fm, &Z3, &t2, &t1);
494 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
495
496 /* Z3 := Z3 + Z3 ; */
497 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
498
499 ec_field_element_copy(&r->fe_x, &X3);
500 ec_field_element_copy(&r->fe_y, &Y3);
501 ec_field_element_copy(&r->fe_z, &Z3);
502
503 return 1;
504}
505
506static int
507ec_point_dbl_a2(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
508{
509 EC_FIELD_ELEMENT X1, Y1, Z1, X3, Y3, Z3;
510 EC_FIELD_ELEMENT t0, t1, t2, t3;
511 EC_FIELD_ELEMENT ga, gb;
512
513 /*
514 * Exception-free point doubling for arbitrary prime order short
515 * Weierstrass curves with a = -3 - see https://eprint.iacr.org/2015/1060,
516 * algorithm 6 and appendix A.2.
517 */
518
519 ec_field_element_copy(&ga, &group->fe_a);
520 ec_field_element_copy(&gb, &group->fe_b);
521
522 ec_field_element_copy(&X1, &a->fe_x);
523 ec_field_element_copy(&Y1, &a->fe_y);
524 ec_field_element_copy(&Z1, &a->fe_z);
525
526 /* t0 := X^2; t1 := Y^2; t2 := Z^2 ; */
527 ec_field_element_sqr(&group->fm, &t0, &X1);
528 ec_field_element_sqr(&group->fm, &t1, &Y1);
529 ec_field_element_sqr(&group->fm, &t2, &Z1);
530
531 /* t3 := X * Y ; t3 := t3 + t3 ; Z3 := X * Z ; */
532 ec_field_element_mul(&group->fm, &t3, &X1, &Y1);
533 ec_field_element_add(&group->fm, &t3, &t3, &t3);
534 ec_field_element_mul(&group->fm, &Z3, &X1, &Z1);
535
536 /* Z3 := Z3 + Z3 ; Y3 := b * t2 ; Y3 := Y3 - Z3 ; */
537 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
538 ec_field_element_mul(&group->fm, &Y3, &gb, &t2);
539 ec_field_element_sub(&group->fm, &Y3, &Y3, &Z3);
540
541 /* X3 := Y3 + Y3 ; Y3 := X3 + Y3 ; X3 := t1 - Y3 ; */
542 ec_field_element_add(&group->fm, &X3, &Y3, &Y3);
543 ec_field_element_add(&group->fm, &Y3, &X3, &Y3);
544 ec_field_element_sub(&group->fm, &X3, &t1, &Y3);
545
546 /* Y3 := t1 + Y3 ; Y3 := X3 * Y3 ; X3 := X3 * t3 ; */
547 ec_field_element_add(&group->fm, &Y3, &t1, &Y3);
548 ec_field_element_mul(&group->fm, &Y3, &X3, &Y3);
549 ec_field_element_mul(&group->fm, &X3, &X3, &t3);
550
551 /* t3 := t2 + t2 ; t2 := t2 + t3 ; Z3 := b * Z3 ; */
552 ec_field_element_add(&group->fm, &t3, &t2, &t2);
553 ec_field_element_add(&group->fm, &t2, &t2, &t3);
554 ec_field_element_mul(&group->fm, &Z3, &gb, &Z3);
555
556 /* Z3 := Z3 - t2 ; Z3 := Z3 - t0 ; t3 := Z3 + Z3 ; */
557 ec_field_element_sub(&group->fm, &Z3, &Z3, &t2);
558 ec_field_element_sub(&group->fm, &Z3, &Z3, &t0);
559 ec_field_element_add(&group->fm, &t3, &Z3, &Z3);
560
561 /* Z3 := Z3 + t3 ; t3 := t0 + t0 ; t0 := t3 + t0 ; */
562 ec_field_element_add(&group->fm, &Z3, &Z3, &t3);
563 ec_field_element_add(&group->fm, &t3, &t0, &t0);
564 ec_field_element_add(&group->fm, &t0, &t3, &t0);
565
566 /* t0 := t0 - t2 ; t0 := t0 * Z3 ; Y3 := Y3 + t0 ; */
567 ec_field_element_sub(&group->fm, &t0, &t0, &t2);
568 ec_field_element_mul(&group->fm, &t0, &t0, &Z3);
569 ec_field_element_add(&group->fm, &Y3, &Y3, &t0);
570
571 /* t0 := Y * Z ; t0 := t0 + t0 ; Z3 := t0 * Z3 ; */
572 ec_field_element_mul(&group->fm, &t0, &Y1, &Z1);
573 ec_field_element_add(&group->fm, &t0, &t0, &t0);
574 ec_field_element_mul(&group->fm, &Z3, &t0, &Z3);
575
576 /* X3 := X3 - Z3 ; Z3 := t0 * t1 ; Z3 := Z3 + Z3 ; */
577 ec_field_element_sub(&group->fm, &X3, &X3, &Z3);
578 ec_field_element_mul(&group->fm, &Z3, &t0, &t1);
579 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
580
581 /* Z3 := Z3 + Z3 ; */
582 ec_field_element_add(&group->fm, &Z3, &Z3, &Z3);
583
584 ec_field_element_copy(&r->fe_x, &X3);
585 ec_field_element_copy(&r->fe_y, &Y3);
586 ec_field_element_copy(&r->fe_z, &Z3);
587
588 return 1;
589}
590
591static int
592ec_point_dbl(const EC_GROUP *group, EC_POINT *r, const EC_POINT *a, BN_CTX *ctx)
593{
594 if (group->a_is_minus3)
595 return ec_point_dbl_a2(group, r, a, ctx);
596
597 return ec_point_dbl_a1(group, r, a, ctx);
598}
599
600static int
601ec_point_invert(const EC_GROUP *group, EC_POINT *point, BN_CTX *ctx)
602{
603 EC_FIELD_ELEMENT y;
604 BN_ULONG mask;
605 int i;
606
607 /*
608 * Invert the point by setting Y = p - Y, if Y is non-zero and the point
609 * is not at infinity.
610 */
611
612 mask = ~(0 - (ec_point_is_at_infinity(group, point) |
613 ec_field_element_is_zero(&group->fm, &point->fe_y)));
614
615 /* XXX - masked/conditional subtraction? */
616 ec_field_element_sub(&group->fm, &y, &group->fm.m, &point->fe_y);
617
618 for (i = 0; i < group->fm.n; i++)
619 point->fe_y.w[i] = (point->fe_y.w[i] & ~mask) | (y.w[i] & mask);
620
621 return 1;
622}
623
624static int
625ec_point_is_on_curve(const EC_GROUP *group, const EC_POINT *point, BN_CTX *ctx)
626{
627 EC_FIELD_ELEMENT sum, axz2, bz3, x3, y2z, z2;
628
629 /*
630 * Curve is defined by a Weierstrass equation y^2 = x^3 + a*x + b.
631 * The given point is in homogeneous projective coordinates
632 * (x = X/Z, y = Y/Z). Substitute and multiply by Z^3 in order to
633 * evaluate as zy^2 = x^3 + axz^2 + bz^3.
634 */
635
636 ec_field_element_sqr(&group->fm, &z2, &point->fe_z);
637
638 ec_field_element_sqr(&group->fm, &y2z, &point->fe_y);
639 ec_field_element_mul(&group->fm, &y2z, &y2z, &point->fe_z);
640
641 ec_field_element_sqr(&group->fm, &x3, &point->fe_x);
642 ec_field_element_mul(&group->fm, &x3, &x3, &point->fe_x);
643
644 ec_field_element_mul(&group->fm, &axz2, &group->fe_a, &point->fe_x);
645 ec_field_element_mul(&group->fm, &axz2, &axz2, &z2);
646
647 ec_field_element_mul(&group->fm, &bz3, &group->fe_b, &point->fe_z);
648 ec_field_element_mul(&group->fm, &bz3, &bz3, &z2);
649
650 ec_field_element_add(&group->fm, &sum, &x3, &axz2);
651 ec_field_element_add(&group->fm, &sum, &sum, &bz3);
652
653 return ec_field_element_equal(&group->fm, &y2z, &sum) |
654 ec_point_is_at_infinity(group, point);
655}
656
657static int
658ec_point_cmp(const EC_GROUP *group, const EC_POINT *a, const EC_POINT *b, BN_CTX *ctx)
659{
660 EC_FIELD_ELEMENT ax, ay, bx, by;
661
662 /*
663 * Compare two points that have homogeneous projection coordinates, that
664 * is (X_a/Z_a, Y_a/Z_a) == (X_b/Z_b, Y_b/Z_b). Return -1 on error, 0 on
665 * equality and 1 on inequality.
666 *
667 * If a and b are both at infinity, Z_a and Z_b will both be zero,
668 * resulting in all values becoming zero, resulting in equality. If a is
669 * at infinity and b is not, then Y_a will be one and Z_b will be
670 * non-zero, hence Y_a * Z_b will be non-zero. Z_a will be zero, hence
671 * Y_b * Z_a will be zero, resulting in inequality. The same applies if
672 * b is at infinity and a is not.
673 */
674
675 ec_field_element_mul(&group->fm, &ax, &a->fe_x, &b->fe_z);
676 ec_field_element_mul(&group->fm, &ay, &a->fe_y, &b->fe_z);
677 ec_field_element_mul(&group->fm, &bx, &b->fe_x, &a->fe_z);
678 ec_field_element_mul(&group->fm, &by, &b->fe_y, &a->fe_z);
679
680 return 1 - (ec_field_element_equal(&group->fm, &ax, &bx) &
681 ec_field_element_equal(&group->fm, &ay, &by));
682}
683
684#if 0
685static int
686ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
687 BN_CTX *ctx)
688{
689 size_t i;
690
691 /* XXX */
692 for (i = 0; i < num; i++) {
693 if (!EC_POINT_make_affine(group, points[0], ctx))
694 return 0;
695 }
696
697 return 1;
698}
699#else
700
701static int
702ec_points_make_affine(const EC_GROUP *group, size_t num, EC_POINT *points[],
703 BN_CTX *ctx)
704{
705 BIGNUM **prod_Z = NULL;
706 BIGNUM *tmp, *tmp_Z;
707 size_t i;
708 int ret = 0;
709
710 if (num == 0)
711 return 1;
712
713 BN_CTX_start(ctx);
714
715 if ((tmp = BN_CTX_get(ctx)) == NULL)
716 goto err;
717 if ((tmp_Z = BN_CTX_get(ctx)) == NULL)
718 goto err;
719
720 if ((prod_Z = calloc(num, sizeof *prod_Z)) == NULL)
721 goto err;
722 for (i = 0; i < num; i++) {
723 if ((prod_Z[i] = BN_CTX_get(ctx)) == NULL)
724 goto err;
725 }
726
727 if (!BN_is_zero(points[0]->Z)) {
728 if (!bn_copy(prod_Z[0], points[0]->Z))
729 goto err;
730 } else {
731 if (!BN_one(prod_Z[0]))
732 goto err;
733 }
734
735 for (i = 1; i < num; i++) {
736 if (!BN_is_zero(points[i]->Z)) {
737 if (!BN_mod_mul(prod_Z[i], prod_Z[i - 1], points[i]->Z,
738 group->p, ctx))
739 goto err;
740 } else {
741 if (!bn_copy(prod_Z[i], prod_Z[i - 1]))
742 goto err;
743 }
744 }
745
746 if (!BN_mod_inverse_nonct(tmp, prod_Z[num - 1], group->p, ctx)) {
747 ECerror(ERR_R_BN_LIB);
748 goto err;
749 }
750
751 for (i = num - 1; i > 0; i--) {
752 if (BN_is_zero(points[i]->Z))
753 continue;
754
755 if (!BN_mod_mul(tmp_Z, prod_Z[i - 1], tmp, group->p, ctx))
756 goto err;
757 if (!BN_mod_mul(tmp, tmp, points[i]->Z, group->p, ctx))
758 goto err;
759 if (!bn_copy(points[i]->Z, tmp_Z))
760 goto err;
761 }
762
763 for (i = 0; i < num; i++) {
764 EC_POINT *p = points[i];
765
766 if (BN_is_zero(p->Z))
767 continue;
768
769 if (!BN_mod_mul(p->X, p->X, p->Z, group->p, ctx))
770 goto err;
771 if (!BN_mod_mul(p->Y, p->Y, p->Z, group->p, ctx))
772 goto err;
773
774 if (!BN_one(p->Z))
775 goto err;
776 }
777
778 ret = 1;
779
780 err:
781 return ret;
782}
783#endif
784
785static int
786ec_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar, const EC_POINT *point,
787 BN_CTX *ctx)
788{
789 EC_POINT *rr;
790 int bits, i;
791 int ret = 0;
792
793 /* XXX - need constant time and blinding. */
794
795 if ((rr = EC_POINT_new(group)) == NULL)
796 goto err;
797
798 bits = BN_num_bits(scalar);
799
800 EC_POINT_copy(rr, point);
801
802 for (i = bits - 2; i >= 0; i--) {
803 if (!EC_POINT_dbl(group, rr, rr, ctx))
804 goto err;
805 if (BN_is_bit_set(scalar, i)) {
806 if (!EC_POINT_add(group, rr, rr, point, ctx))
807 goto err;
808 }
809 }
810
811 EC_POINT_copy(r, rr);
812
813 ret = 1;
814
815 err:
816 EC_POINT_free(rr);
817
818 return ret;
819}
820
821static int
822ec_mul_single_ct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
823 const EC_POINT *point, BN_CTX *ctx)
824{
825 return ec_mul(group, r, scalar, point, ctx);
826}
827
828static int
829ec_mul_double_nonct(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar1,
830 const EC_POINT *point1, const BIGNUM *scalar2, const EC_POINT *point2,
831 BN_CTX *ctx)
832{
833 return ec_wnaf_mul(group, r, scalar1, point1, scalar2, point2, ctx);
834}
835
836static const EC_METHOD ec_GFp_homogeneous_projective_method = {
837 .group_set_curve = ec_group_set_curve,
838 .group_get_curve = ec_group_get_curve,
839 .point_set_to_infinity = ec_point_set_to_infinity,
840 .point_is_at_infinity = ec_point_is_at_infinity,
841 .point_set_affine_coordinates = ec_point_set_affine_coordinates,
842 .point_get_affine_coordinates = ec_point_get_affine_coordinates,
843 .add = ec_point_add,
844 .dbl = ec_point_dbl,
845 .invert = ec_point_invert,
846 .point_is_on_curve = ec_point_is_on_curve,
847 .point_cmp = ec_point_cmp,
848 .points_make_affine = ec_points_make_affine,
849 .mul_single_ct = ec_mul_single_ct,
850 .mul_double_nonct = ec_mul_double_nonct,
851};
852
853const EC_METHOD *
854EC_GFp_homogeneous_projective_method(void)
855{
856 return &ec_GFp_homogeneous_projective_method;
857}
858LCRYPTO_ALIAS(EC_GFp_simple_method);
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-11-20 07:43:50 +0000