summaryrefslogtreecommitdiff
path: root/src/lib/libcrypto/ec/ec2_mult.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/libcrypto/ec/ec2_mult.c')
-rw-r--r--src/lib/libcrypto/ec/ec2_mult.c449
1 files changed, 0 insertions, 449 deletions
diff --git a/src/lib/libcrypto/ec/ec2_mult.c b/src/lib/libcrypto/ec/ec2_mult.c
deleted file mode 100644
index d7cbd933f2..0000000000
--- a/src/lib/libcrypto/ec/ec2_mult.c
+++ /dev/null
@@ -1,449 +0,0 @@
1/* $OpenBSD: ec2_mult.c,v 1.17 2023/04/11 18:58:20 jsing Exp $ */
2/* ====================================================================
3 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
4 *
5 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
6 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
7 * to the OpenSSL project.
8 *
9 * The ECC Code is licensed pursuant to the OpenSSL open source
10 * license provided below.
11 *
12 * The software is originally written by Sheueling Chang Shantz and
13 * Douglas Stebila of Sun Microsystems Laboratories.
14 *
15 */
16/* ====================================================================
17 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved.
18 *
19 * Redistribution and use in source and binary forms, with or without
20 * modification, are permitted provided that the following conditions
21 * are met:
22 *
23 * 1. Redistributions of source code must retain the above copyright
24 * notice, this list of conditions and the following disclaimer.
25 *
26 * 2. Redistributions in binary form must reproduce the above copyright
27 * notice, this list of conditions and the following disclaimer in
28 * the documentation and/or other materials provided with the
29 * distribution.
30 *
31 * 3. All advertising materials mentioning features or use of this
32 * software must display the following acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
35 *
36 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
37 * endorse or promote products derived from this software without
38 * prior written permission. For written permission, please contact
39 * openssl-core@openssl.org.
40 *
41 * 5. Products derived from this software may not be called "OpenSSL"
42 * nor may "OpenSSL" appear in their names without prior written
43 * permission of the OpenSSL Project.
44 *
45 * 6. Redistributions of any form whatsoever must retain the following
46 * acknowledgment:
47 * "This product includes software developed by the OpenSSL Project
48 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
49 *
50 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
51 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
52 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
53 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
54 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
55 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
56 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
57 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
59 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
60 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
61 * OF THE POSSIBILITY OF SUCH DAMAGE.
62 * ====================================================================
63 *
64 * This product includes cryptographic software written by Eric Young
65 * (eay@cryptsoft.com). This product includes software written by Tim
66 * Hudson (tjh@cryptsoft.com).
67 *
68 */
69
70#include <openssl/opensslconf.h>
71
72#include <openssl/err.h>
73
74#include "bn_local.h"
75#include "ec_local.h"
76
77#ifndef OPENSSL_NO_EC2M
78
79
80/* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective
81 * coordinates.
82 * Uses algorithm Mdouble in appendix of
83 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
84 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
85 * modified to not require precomputation of c=b^{2^{m-1}}.
86 */
87static int
88gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx)
89{
90 BIGNUM *t1;
91 int ret = 0;
92
93 /* Since Mdouble is static we can guarantee that ctx != NULL. */
94 BN_CTX_start(ctx);
95 if ((t1 = BN_CTX_get(ctx)) == NULL)
96 goto err;
97
98 if (!group->meth->field_sqr(group, x, x, ctx))
99 goto err;
100 if (!group->meth->field_sqr(group, t1, z, ctx))
101 goto err;
102 if (!group->meth->field_mul(group, z, x, t1, ctx))
103 goto err;
104 if (!group->meth->field_sqr(group, x, x, ctx))
105 goto err;
106 if (!group->meth->field_sqr(group, t1, t1, ctx))
107 goto err;
108 if (!group->meth->field_mul(group, t1, &group->b, t1, ctx))
109 goto err;
110 if (!BN_GF2m_add(x, x, t1))
111 goto err;
112
113 ret = 1;
114
115 err:
116 BN_CTX_end(ctx);
117 return ret;
118}
119
120/* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery
121 * projective coordinates.
122 * Uses algorithm Madd in appendix of
123 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
124 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
125 */
126static int
127gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1,
128 const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx)
129{
130 BIGNUM *t1, *t2;
131 int ret = 0;
132
133 /* Since Madd is static we can guarantee that ctx != NULL. */
134 BN_CTX_start(ctx);
135 if ((t1 = BN_CTX_get(ctx)) == NULL)
136 goto err;
137 if ((t2 = BN_CTX_get(ctx)) == NULL)
138 goto err;
139
140 if (!bn_copy(t1, x))
141 goto err;
142 if (!group->meth->field_mul(group, x1, x1, z2, ctx))
143 goto err;
144 if (!group->meth->field_mul(group, z1, z1, x2, ctx))
145 goto err;
146 if (!group->meth->field_mul(group, t2, x1, z1, ctx))
147 goto err;
148 if (!BN_GF2m_add(z1, z1, x1))
149 goto err;
150 if (!group->meth->field_sqr(group, z1, z1, ctx))
151 goto err;
152 if (!group->meth->field_mul(group, x1, z1, t1, ctx))
153 goto err;
154 if (!BN_GF2m_add(x1, x1, t2))
155 goto err;
156
157 ret = 1;
158
159 err:
160 BN_CTX_end(ctx);
161 return ret;
162}
163
164/* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
165 * using Montgomery point multiplication algorithm Mxy() in appendix of
166 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
167 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
168 * Returns:
169 * 0 on error
170 * 1 if return value should be the point at infinity
171 * 2 otherwise
172 */
173static int
174gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1,
175 BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx)
176{
177 BIGNUM *t3, *t4, *t5;
178 int ret = 0;
179
180 if (BN_is_zero(z1)) {
181 BN_zero(x2);
182 BN_zero(z2);
183 return 1;
184 }
185 if (BN_is_zero(z2)) {
186 if (!bn_copy(x2, x))
187 return 0;
188 if (!BN_GF2m_add(z2, x, y))
189 return 0;
190 return 2;
191 }
192 /* Since Mxy is static we can guarantee that ctx != NULL. */
193 BN_CTX_start(ctx);
194 if ((t3 = BN_CTX_get(ctx)) == NULL)
195 goto err;
196 if ((t4 = BN_CTX_get(ctx)) == NULL)
197 goto err;
198 if ((t5 = BN_CTX_get(ctx)) == NULL)
199 goto err;
200
201 if (!BN_one(t5))
202 goto err;
203
204 if (!group->meth->field_mul(group, t3, z1, z2, ctx))
205 goto err;
206
207 if (!group->meth->field_mul(group, z1, z1, x, ctx))
208 goto err;
209 if (!BN_GF2m_add(z1, z1, x1))
210 goto err;
211 if (!group->meth->field_mul(group, z2, z2, x, ctx))
212 goto err;
213 if (!group->meth->field_mul(group, x1, z2, x1, ctx))
214 goto err;
215 if (!BN_GF2m_add(z2, z2, x2))
216 goto err;
217
218 if (!group->meth->field_mul(group, z2, z2, z1, ctx))
219 goto err;
220 if (!group->meth->field_sqr(group, t4, x, ctx))
221 goto err;
222 if (!BN_GF2m_add(t4, t4, y))
223 goto err;
224 if (!group->meth->field_mul(group, t4, t4, t3, ctx))
225 goto err;
226 if (!BN_GF2m_add(t4, t4, z2))
227 goto err;
228
229 if (!group->meth->field_mul(group, t3, t3, x, ctx))
230 goto err;
231 if (!group->meth->field_div(group, t3, t5, t3, ctx))
232 goto err;
233 if (!group->meth->field_mul(group, t4, t3, t4, ctx))
234 goto err;
235 if (!group->meth->field_mul(group, x2, x1, t3, ctx))
236 goto err;
237 if (!BN_GF2m_add(z2, x2, x))
238 goto err;
239
240 if (!group->meth->field_mul(group, z2, z2, t4, ctx))
241 goto err;
242 if (!BN_GF2m_add(z2, z2, y))
243 goto err;
244
245 ret = 2;
246
247 err:
248 BN_CTX_end(ctx);
249 return ret;
250}
251
252
253/* Computes scalar*point and stores the result in r.
254 * point can not equal r.
255 * Uses a modified algorithm 2P of
256 * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
257 * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
258 *
259 * To protect against side-channel attack the function uses constant time swap,
260 * avoiding conditional branches.
261 */
262static int
263ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r,
264 const BIGNUM *scalar, const EC_POINT *point, BN_CTX *ctx)
265{
266 BIGNUM *x1, *x2, *z1, *z2;
267 int ret = 0, i;
268 BN_ULONG mask, word;
269
270 if (r == point) {
271 ECerror(EC_R_INVALID_ARGUMENT);
272 return 0;
273 }
274 /* if result should be point at infinity */
275 if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) ||
276 EC_POINT_is_at_infinity(group, point) > 0) {
277 return EC_POINT_set_to_infinity(group, r);
278 }
279 /* only support affine coordinates */
280 if (!point->Z_is_one)
281 return 0;
282
283 /* Since point_multiply is static we can guarantee that ctx != NULL. */
284 BN_CTX_start(ctx);
285 if ((x1 = BN_CTX_get(ctx)) == NULL)
286 goto err;
287 if ((z1 = BN_CTX_get(ctx)) == NULL)
288 goto err;
289
290 x2 = &r->X;
291 z2 = &r->Y;
292
293 if (!bn_wexpand(x1, group->field.top))
294 goto err;
295 if (!bn_wexpand(z1, group->field.top))
296 goto err;
297 if (!bn_wexpand(x2, group->field.top))
298 goto err;
299 if (!bn_wexpand(z2, group->field.top))
300 goto err;
301
302 if (!BN_GF2m_mod_arr(x1, &point->X, group->poly))
303 goto err; /* x1 = x */
304 if (!BN_one(z1))
305 goto err; /* z1 = 1 */
306 if (!group->meth->field_sqr(group, z2, x1, ctx))
307 goto err; /* z2 = x1^2 = x^2 */
308 if (!group->meth->field_sqr(group, x2, z2, ctx))
309 goto err;
310 if (!BN_GF2m_add(x2, x2, &group->b))
311 goto err; /* x2 = x^4 + b */
312
313 /* find top most bit and go one past it */
314 i = scalar->top - 1;
315 mask = BN_TBIT;
316 word = scalar->d[i];
317 while (!(word & mask))
318 mask >>= 1;
319 mask >>= 1;
320 /* if top most bit was at word break, go to next word */
321 if (!mask) {
322 i--;
323 mask = BN_TBIT;
324 }
325 for (; i >= 0; i--) {
326 word = scalar->d[i];
327 while (mask) {
328 if (!BN_swap_ct(word & mask, x1, x2, group->field.top))
329 goto err;
330 if (!BN_swap_ct(word & mask, z1, z2, group->field.top))
331 goto err;
332 if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx))
333 goto err;
334 if (!gf2m_Mdouble(group, x1, z1, ctx))
335 goto err;
336 if (!BN_swap_ct(word & mask, x1, x2, group->field.top))
337 goto err;
338 if (!BN_swap_ct(word & mask, z1, z2, group->field.top))
339 goto err;
340 mask >>= 1;
341 }
342 mask = BN_TBIT;
343 }
344
345 /* convert out of "projective" coordinates */
346 i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx);
347 if (i == 0)
348 goto err;
349 else if (i == 1) {
350 if (!EC_POINT_set_to_infinity(group, r))
351 goto err;
352 } else {
353 if (!BN_one(&r->Z))
354 goto err;
355 r->Z_is_one = 1;
356 }
357
358 /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
359 BN_set_negative(&r->X, 0);
360 BN_set_negative(&r->Y, 0);
361
362 ret = 1;
363
364 err:
365 BN_CTX_end(ctx);
366 return ret;
367}
368
369
370/* Computes the sum
371 * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
372 * gracefully ignoring NULL scalar values.
373 */
374int
375ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
376 size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
377{
378 EC_POINT *p = NULL;
379 EC_POINT *acc = NULL;
380 size_t i;
381 int ret = 0;
382
383 /*
384 * This implementation is more efficient than the wNAF implementation
385 * for 2 or fewer points. Use the ec_wNAF_mul implementation for 3
386 * or more points, or if we can perform a fast multiplication based
387 * on precomputation.
388 */
389 if ((scalar && (num > 1)) || (num > 2) ||
390 (num == 0 && EC_GROUP_have_precompute_mult(group))) {
391 ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
392 goto err;
393 }
394 if ((p = EC_POINT_new(group)) == NULL)
395 goto err;
396 if ((acc = EC_POINT_new(group)) == NULL)
397 goto err;
398
399 if (!EC_POINT_set_to_infinity(group, acc))
400 goto err;
401
402 if (scalar) {
403 if (!ec_GF2m_montgomery_point_multiply(group, p, scalar, group->generator, ctx))
404 goto err;
405 if (BN_is_negative(scalar))
406 if (!group->meth->invert(group, p, ctx))
407 goto err;
408 if (!group->meth->add(group, acc, acc, p, ctx))
409 goto err;
410 }
411 for (i = 0; i < num; i++) {
412 if (!ec_GF2m_montgomery_point_multiply(group, p, scalars[i], points[i], ctx))
413 goto err;
414 if (BN_is_negative(scalars[i]))
415 if (!group->meth->invert(group, p, ctx))
416 goto err;
417 if (!group->meth->add(group, acc, acc, p, ctx))
418 goto err;
419 }
420
421 if (!EC_POINT_copy(r, acc))
422 goto err;
423
424 ret = 1;
425
426 err:
427 EC_POINT_free(p);
428 EC_POINT_free(acc);
429
430 return ret;
431}
432
433
434/* Precomputation for point multiplication: fall back to wNAF methods
435 * because ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate */
436
437int
438ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
439{
440 return ec_wNAF_precompute_mult(group, ctx);
441}
442
443int
444ec_GF2m_have_precompute_mult(const EC_GROUP *group)
445{
446 return ec_wNAF_have_precompute_mult(group);
447}
448
449#endif
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-26 07:18:01 +0000