1 | /*
|
---|
2 | * Copyright 2002-2016 The OpenSSL Project Authors. All Rights Reserved.
|
---|
3 | *
|
---|
4 | * Licensed under the OpenSSL license (the "License"). You may not use
|
---|
5 | * this file except in compliance with the License. You can obtain a copy
|
---|
6 | * in the file LICENSE in the source distribution or at
|
---|
7 | * https://www.openssl.org/source/license.html
|
---|
8 | */
|
---|
9 |
|
---|
10 | /* ====================================================================
|
---|
11 | * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
|
---|
12 | *
|
---|
13 | * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
|
---|
14 | * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
|
---|
15 | * to the OpenSSL project.
|
---|
16 | *
|
---|
17 | * The ECC Code is licensed pursuant to the OpenSSL open source
|
---|
18 | * license provided below.
|
---|
19 | *
|
---|
20 | * The software is originally written by Sheueling Chang Shantz and
|
---|
21 | * Douglas Stebila of Sun Microsystems Laboratories.
|
---|
22 | *
|
---|
23 | */
|
---|
24 |
|
---|
25 | #include <openssl/err.h>
|
---|
26 |
|
---|
27 | #include "internal/bn_int.h"
|
---|
28 | #include "ec_lcl.h"
|
---|
29 |
|
---|
30 | #ifndef OPENSSL_NO_EC2M
|
---|
31 |
|
---|
32 | /*-
|
---|
33 | * Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective
|
---|
34 | * coordinates.
|
---|
35 | * Uses algorithm Mdouble in appendix of
|
---|
36 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
|
---|
37 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
|
---|
38 | * modified to not require precomputation of c=b^{2^{m-1}}.
|
---|
39 | */
|
---|
40 | static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z,
|
---|
41 | BN_CTX *ctx)
|
---|
42 | {
|
---|
43 | BIGNUM *t1;
|
---|
44 | int ret = 0;
|
---|
45 |
|
---|
46 | /* Since Mdouble is static we can guarantee that ctx != NULL. */
|
---|
47 | BN_CTX_start(ctx);
|
---|
48 | t1 = BN_CTX_get(ctx);
|
---|
49 | if (t1 == NULL)
|
---|
50 | goto err;
|
---|
51 |
|
---|
52 | if (!group->meth->field_sqr(group, x, x, ctx))
|
---|
53 | goto err;
|
---|
54 | if (!group->meth->field_sqr(group, t1, z, ctx))
|
---|
55 | goto err;
|
---|
56 | if (!group->meth->field_mul(group, z, x, t1, ctx))
|
---|
57 | goto err;
|
---|
58 | if (!group->meth->field_sqr(group, x, x, ctx))
|
---|
59 | goto err;
|
---|
60 | if (!group->meth->field_sqr(group, t1, t1, ctx))
|
---|
61 | goto err;
|
---|
62 | if (!group->meth->field_mul(group, t1, group->b, t1, ctx))
|
---|
63 | goto err;
|
---|
64 | if (!BN_GF2m_add(x, x, t1))
|
---|
65 | goto err;
|
---|
66 |
|
---|
67 | ret = 1;
|
---|
68 |
|
---|
69 | err:
|
---|
70 | BN_CTX_end(ctx);
|
---|
71 | return ret;
|
---|
72 | }
|
---|
73 |
|
---|
74 | /*-
|
---|
75 | * Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery
|
---|
76 | * projective coordinates.
|
---|
77 | * Uses algorithm Madd in appendix of
|
---|
78 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
|
---|
79 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
|
---|
80 | */
|
---|
81 | static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1,
|
---|
82 | BIGNUM *z1, const BIGNUM *x2, const BIGNUM *z2,
|
---|
83 | BN_CTX *ctx)
|
---|
84 | {
|
---|
85 | BIGNUM *t1, *t2;
|
---|
86 | int ret = 0;
|
---|
87 |
|
---|
88 | /* Since Madd is static we can guarantee that ctx != NULL. */
|
---|
89 | BN_CTX_start(ctx);
|
---|
90 | t1 = BN_CTX_get(ctx);
|
---|
91 | t2 = BN_CTX_get(ctx);
|
---|
92 | if (t2 == NULL)
|
---|
93 | goto err;
|
---|
94 |
|
---|
95 | if (!BN_copy(t1, x))
|
---|
96 | goto err;
|
---|
97 | if (!group->meth->field_mul(group, x1, x1, z2, ctx))
|
---|
98 | goto err;
|
---|
99 | if (!group->meth->field_mul(group, z1, z1, x2, ctx))
|
---|
100 | goto err;
|
---|
101 | if (!group->meth->field_mul(group, t2, x1, z1, ctx))
|
---|
102 | goto err;
|
---|
103 | if (!BN_GF2m_add(z1, z1, x1))
|
---|
104 | goto err;
|
---|
105 | if (!group->meth->field_sqr(group, z1, z1, ctx))
|
---|
106 | goto err;
|
---|
107 | if (!group->meth->field_mul(group, x1, z1, t1, ctx))
|
---|
108 | goto err;
|
---|
109 | if (!BN_GF2m_add(x1, x1, t2))
|
---|
110 | goto err;
|
---|
111 |
|
---|
112 | ret = 1;
|
---|
113 |
|
---|
114 | err:
|
---|
115 | BN_CTX_end(ctx);
|
---|
116 | return ret;
|
---|
117 | }
|
---|
118 |
|
---|
119 | /*-
|
---|
120 | * Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
|
---|
121 | * using Montgomery point multiplication algorithm Mxy() in appendix of
|
---|
122 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
|
---|
123 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
|
---|
124 | * Returns:
|
---|
125 | * 0 on error
|
---|
126 | * 1 if return value should be the point at infinity
|
---|
127 | * 2 otherwise
|
---|
128 | */
|
---|
129 | static int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y,
|
---|
130 | BIGNUM *x1, BIGNUM *z1, BIGNUM *x2, BIGNUM *z2,
|
---|
131 | BN_CTX *ctx)
|
---|
132 | {
|
---|
133 | BIGNUM *t3, *t4, *t5;
|
---|
134 | int ret = 0;
|
---|
135 |
|
---|
136 | if (BN_is_zero(z1)) {
|
---|
137 | BN_zero(x2);
|
---|
138 | BN_zero(z2);
|
---|
139 | return 1;
|
---|
140 | }
|
---|
141 |
|
---|
142 | if (BN_is_zero(z2)) {
|
---|
143 | if (!BN_copy(x2, x))
|
---|
144 | return 0;
|
---|
145 | if (!BN_GF2m_add(z2, x, y))
|
---|
146 | return 0;
|
---|
147 | return 2;
|
---|
148 | }
|
---|
149 |
|
---|
150 | /* Since Mxy is static we can guarantee that ctx != NULL. */
|
---|
151 | BN_CTX_start(ctx);
|
---|
152 | t3 = BN_CTX_get(ctx);
|
---|
153 | t4 = BN_CTX_get(ctx);
|
---|
154 | t5 = BN_CTX_get(ctx);
|
---|
155 | if (t5 == NULL)
|
---|
156 | goto err;
|
---|
157 |
|
---|
158 | if (!BN_one(t5))
|
---|
159 | goto err;
|
---|
160 |
|
---|
161 | if (!group->meth->field_mul(group, t3, z1, z2, ctx))
|
---|
162 | goto err;
|
---|
163 |
|
---|
164 | if (!group->meth->field_mul(group, z1, z1, x, ctx))
|
---|
165 | goto err;
|
---|
166 | if (!BN_GF2m_add(z1, z1, x1))
|
---|
167 | goto err;
|
---|
168 | if (!group->meth->field_mul(group, z2, z2, x, ctx))
|
---|
169 | goto err;
|
---|
170 | if (!group->meth->field_mul(group, x1, z2, x1, ctx))
|
---|
171 | goto err;
|
---|
172 | if (!BN_GF2m_add(z2, z2, x2))
|
---|
173 | goto err;
|
---|
174 |
|
---|
175 | if (!group->meth->field_mul(group, z2, z2, z1, ctx))
|
---|
176 | goto err;
|
---|
177 | if (!group->meth->field_sqr(group, t4, x, ctx))
|
---|
178 | goto err;
|
---|
179 | if (!BN_GF2m_add(t4, t4, y))
|
---|
180 | goto err;
|
---|
181 | if (!group->meth->field_mul(group, t4, t4, t3, ctx))
|
---|
182 | goto err;
|
---|
183 | if (!BN_GF2m_add(t4, t4, z2))
|
---|
184 | goto err;
|
---|
185 |
|
---|
186 | if (!group->meth->field_mul(group, t3, t3, x, ctx))
|
---|
187 | goto err;
|
---|
188 | if (!group->meth->field_div(group, t3, t5, t3, ctx))
|
---|
189 | goto err;
|
---|
190 | if (!group->meth->field_mul(group, t4, t3, t4, ctx))
|
---|
191 | goto err;
|
---|
192 | if (!group->meth->field_mul(group, x2, x1, t3, ctx))
|
---|
193 | goto err;
|
---|
194 | if (!BN_GF2m_add(z2, x2, x))
|
---|
195 | goto err;
|
---|
196 |
|
---|
197 | if (!group->meth->field_mul(group, z2, z2, t4, ctx))
|
---|
198 | goto err;
|
---|
199 | if (!BN_GF2m_add(z2, z2, y))
|
---|
200 | goto err;
|
---|
201 |
|
---|
202 | ret = 2;
|
---|
203 |
|
---|
204 | err:
|
---|
205 | BN_CTX_end(ctx);
|
---|
206 | return ret;
|
---|
207 | }
|
---|
208 |
|
---|
209 | /*-
|
---|
210 | * Computes scalar*point and stores the result in r.
|
---|
211 | * point can not equal r.
|
---|
212 | * Uses a modified algorithm 2P of
|
---|
213 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
|
---|
214 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
|
---|
215 | *
|
---|
216 | * To protect against side-channel attack the function uses constant time swap,
|
---|
217 | * avoiding conditional branches.
|
---|
218 | */
|
---|
219 | static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group,
|
---|
220 | EC_POINT *r,
|
---|
221 | const BIGNUM *scalar,
|
---|
222 | const EC_POINT *point,
|
---|
223 | BN_CTX *ctx)
|
---|
224 | {
|
---|
225 | BIGNUM *x1, *x2, *z1, *z2;
|
---|
226 | int ret = 0, i, group_top;
|
---|
227 | BN_ULONG mask, word;
|
---|
228 |
|
---|
229 | if (r == point) {
|
---|
230 | ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT);
|
---|
231 | return 0;
|
---|
232 | }
|
---|
233 |
|
---|
234 | /* if result should be point at infinity */
|
---|
235 | if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) ||
|
---|
236 | EC_POINT_is_at_infinity(group, point)) {
|
---|
237 | return EC_POINT_set_to_infinity(group, r);
|
---|
238 | }
|
---|
239 |
|
---|
240 | /* only support affine coordinates */
|
---|
241 | if (!point->Z_is_one)
|
---|
242 | return 0;
|
---|
243 |
|
---|
244 | /*
|
---|
245 | * Since point_multiply is static we can guarantee that ctx != NULL.
|
---|
246 | */
|
---|
247 | BN_CTX_start(ctx);
|
---|
248 | x1 = BN_CTX_get(ctx);
|
---|
249 | z1 = BN_CTX_get(ctx);
|
---|
250 | if (z1 == NULL)
|
---|
251 | goto err;
|
---|
252 |
|
---|
253 | x2 = r->X;
|
---|
254 | z2 = r->Y;
|
---|
255 |
|
---|
256 | group_top = bn_get_top(group->field);
|
---|
257 | if (bn_wexpand(x1, group_top) == NULL
|
---|
258 | || bn_wexpand(z1, group_top) == NULL
|
---|
259 | || bn_wexpand(x2, group_top) == NULL
|
---|
260 | || bn_wexpand(z2, group_top) == NULL)
|
---|
261 | goto err;
|
---|
262 |
|
---|
263 | if (!BN_GF2m_mod_arr(x1, point->X, group->poly))
|
---|
264 | goto err; /* x1 = x */
|
---|
265 | if (!BN_one(z1))
|
---|
266 | goto err; /* z1 = 1 */
|
---|
267 | if (!group->meth->field_sqr(group, z2, x1, ctx))
|
---|
268 | goto err; /* z2 = x1^2 = x^2 */
|
---|
269 | if (!group->meth->field_sqr(group, x2, z2, ctx))
|
---|
270 | goto err;
|
---|
271 | if (!BN_GF2m_add(x2, x2, group->b))
|
---|
272 | goto err; /* x2 = x^4 + b */
|
---|
273 |
|
---|
274 | /* find top most bit and go one past it */
|
---|
275 | i = bn_get_top(scalar) - 1;
|
---|
276 | mask = BN_TBIT;
|
---|
277 | word = bn_get_words(scalar)[i];
|
---|
278 | while (!(word & mask))
|
---|
279 | mask >>= 1;
|
---|
280 | mask >>= 1;
|
---|
281 | /* if top most bit was at word break, go to next word */
|
---|
282 | if (!mask) {
|
---|
283 | i--;
|
---|
284 | mask = BN_TBIT;
|
---|
285 | }
|
---|
286 |
|
---|
287 | for (; i >= 0; i--) {
|
---|
288 | word = bn_get_words(scalar)[i];
|
---|
289 | while (mask) {
|
---|
290 | BN_consttime_swap(word & mask, x1, x2, group_top);
|
---|
291 | BN_consttime_swap(word & mask, z1, z2, group_top);
|
---|
292 | if (!gf2m_Madd(group, point->X, x2, z2, x1, z1, ctx))
|
---|
293 | goto err;
|
---|
294 | if (!gf2m_Mdouble(group, x1, z1, ctx))
|
---|
295 | goto err;
|
---|
296 | BN_consttime_swap(word & mask, x1, x2, group_top);
|
---|
297 | BN_consttime_swap(word & mask, z1, z2, group_top);
|
---|
298 | mask >>= 1;
|
---|
299 | }
|
---|
300 | mask = BN_TBIT;
|
---|
301 | }
|
---|
302 |
|
---|
303 | /* convert out of "projective" coordinates */
|
---|
304 | i = gf2m_Mxy(group, point->X, point->Y, x1, z1, x2, z2, ctx);
|
---|
305 | if (i == 0)
|
---|
306 | goto err;
|
---|
307 | else if (i == 1) {
|
---|
308 | if (!EC_POINT_set_to_infinity(group, r))
|
---|
309 | goto err;
|
---|
310 | } else {
|
---|
311 | if (!BN_one(r->Z))
|
---|
312 | goto err;
|
---|
313 | r->Z_is_one = 1;
|
---|
314 | }
|
---|
315 |
|
---|
316 | /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
|
---|
317 | BN_set_negative(r->X, 0);
|
---|
318 | BN_set_negative(r->Y, 0);
|
---|
319 |
|
---|
320 | ret = 1;
|
---|
321 |
|
---|
322 | err:
|
---|
323 | BN_CTX_end(ctx);
|
---|
324 | return ret;
|
---|
325 | }
|
---|
326 |
|
---|
327 | /*-
|
---|
328 | * Computes the sum
|
---|
329 | * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
|
---|
330 | * gracefully ignoring NULL scalar values.
|
---|
331 | */
|
---|
332 | int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r,
|
---|
333 | const BIGNUM *scalar, size_t num,
|
---|
334 | const EC_POINT *points[], const BIGNUM *scalars[],
|
---|
335 | BN_CTX *ctx)
|
---|
336 | {
|
---|
337 | BN_CTX *new_ctx = NULL;
|
---|
338 | int ret = 0;
|
---|
339 | size_t i;
|
---|
340 | EC_POINT *p = NULL;
|
---|
341 | EC_POINT *acc = NULL;
|
---|
342 |
|
---|
343 | if (ctx == NULL) {
|
---|
344 | ctx = new_ctx = BN_CTX_new();
|
---|
345 | if (ctx == NULL)
|
---|
346 | return 0;
|
---|
347 | }
|
---|
348 |
|
---|
349 | /*
|
---|
350 | * This implementation is more efficient than the wNAF implementation for
|
---|
351 | * 2 or fewer points. Use the ec_wNAF_mul implementation for 3 or more
|
---|
352 | * points, or if we can perform a fast multiplication based on
|
---|
353 | * precomputation.
|
---|
354 | */
|
---|
355 | if ((scalar && (num > 1)) || (num > 2)
|
---|
356 | || (num == 0 && EC_GROUP_have_precompute_mult(group))) {
|
---|
357 | ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
|
---|
358 | goto err;
|
---|
359 | }
|
---|
360 |
|
---|
361 | if ((p = EC_POINT_new(group)) == NULL)
|
---|
362 | goto err;
|
---|
363 | if ((acc = EC_POINT_new(group)) == NULL)
|
---|
364 | goto err;
|
---|
365 |
|
---|
366 | if (!EC_POINT_set_to_infinity(group, acc))
|
---|
367 | goto err;
|
---|
368 |
|
---|
369 | if (scalar) {
|
---|
370 | if (!ec_GF2m_montgomery_point_multiply
|
---|
371 | (group, p, scalar, group->generator, ctx))
|
---|
372 | goto err;
|
---|
373 | if (BN_is_negative(scalar))
|
---|
374 | if (!group->meth->invert(group, p, ctx))
|
---|
375 | goto err;
|
---|
376 | if (!group->meth->add(group, acc, acc, p, ctx))
|
---|
377 | goto err;
|
---|
378 | }
|
---|
379 |
|
---|
380 | for (i = 0; i < num; i++) {
|
---|
381 | if (!ec_GF2m_montgomery_point_multiply
|
---|
382 | (group, p, scalars[i], points[i], ctx))
|
---|
383 | goto err;
|
---|
384 | if (BN_is_negative(scalars[i]))
|
---|
385 | if (!group->meth->invert(group, p, ctx))
|
---|
386 | goto err;
|
---|
387 | if (!group->meth->add(group, acc, acc, p, ctx))
|
---|
388 | goto err;
|
---|
389 | }
|
---|
390 |
|
---|
391 | if (!EC_POINT_copy(r, acc))
|
---|
392 | goto err;
|
---|
393 |
|
---|
394 | ret = 1;
|
---|
395 |
|
---|
396 | err:
|
---|
397 | EC_POINT_free(p);
|
---|
398 | EC_POINT_free(acc);
|
---|
399 | BN_CTX_free(new_ctx);
|
---|
400 | return ret;
|
---|
401 | }
|
---|
402 |
|
---|
403 | /*
|
---|
404 | * Precomputation for point multiplication: fall back to wNAF methods because
|
---|
405 | * ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate
|
---|
406 | */
|
---|
407 |
|
---|
408 | int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
|
---|
409 | {
|
---|
410 | return ec_wNAF_precompute_mult(group, ctx);
|
---|
411 | }
|
---|
412 |
|
---|
413 | int ec_GF2m_have_precompute_mult(const EC_GROUP *group)
|
---|
414 | {
|
---|
415 | return ec_wNAF_have_precompute_mult(group);
|
---|
416 | }
|
---|
417 |
|
---|
418 | #endif
|
---|