Branch data Line data Source code
1 : : /* crypto/ec/ec2_mult.c */
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 : : #define OPENSSL_FIPSAPI
71 : :
72 : : #include <openssl/err.h>
73 : :
74 : : #include "ec_lcl.h"
75 : :
76 : : #ifndef OPENSSL_NO_EC2M
77 : :
78 : :
79 : : /* Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective
80 : : * coordinates.
81 : : * Uses algorithm Mdouble in appendix of
82 : : * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
83 : : * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
84 : : * modified to not require precomputation of c=b^{2^{m-1}}.
85 : : */
86 : 569811 : static int gf2m_Mdouble(const EC_GROUP *group, BIGNUM *x, BIGNUM *z, BN_CTX *ctx)
87 : : {
88 : : BIGNUM *t1;
89 : 569811 : int ret = 0;
90 : :
91 : : /* Since Mdouble is static we can guarantee that ctx != NULL. */
92 : 569811 : BN_CTX_start(ctx);
93 : 569811 : t1 = BN_CTX_get(ctx);
94 [ + - ]: 569811 : if (t1 == NULL) goto err;
95 : :
96 [ + - ]: 569811 : if (!group->meth->field_sqr(group, x, x, ctx)) goto err;
97 [ + - ]: 569811 : if (!group->meth->field_sqr(group, t1, z, ctx)) goto err;
98 [ + - ]: 569811 : if (!group->meth->field_mul(group, z, x, t1, ctx)) goto err;
99 [ + - ]: 569811 : if (!group->meth->field_sqr(group, x, x, ctx)) goto err;
100 [ + - ]: 569811 : if (!group->meth->field_sqr(group, t1, t1, ctx)) goto err;
101 [ + - ]: 569811 : if (!group->meth->field_mul(group, t1, &group->b, t1, ctx)) goto err;
102 [ + - ]: 569811 : if (!BN_GF2m_add(x, x, t1)) goto err;
103 : :
104 : 569811 : ret = 1;
105 : :
106 : : err:
107 : 569811 : BN_CTX_end(ctx);
108 : 569811 : return ret;
109 : : }
110 : :
111 : : /* Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery
112 : : * projective coordinates.
113 : : * Uses algorithm Madd in appendix of
114 : : * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
115 : : * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
116 : : */
117 : 569811 : static int gf2m_Madd(const EC_GROUP *group, const BIGNUM *x, BIGNUM *x1, BIGNUM *z1,
118 : : const BIGNUM *x2, const BIGNUM *z2, BN_CTX *ctx)
119 : : {
120 : : BIGNUM *t1, *t2;
121 : 569811 : int ret = 0;
122 : :
123 : : /* Since Madd is static we can guarantee that ctx != NULL. */
124 : 569811 : BN_CTX_start(ctx);
125 : 569811 : t1 = BN_CTX_get(ctx);
126 : 569811 : t2 = BN_CTX_get(ctx);
127 [ + - ]: 569811 : if (t2 == NULL) goto err;
128 : :
129 [ + - ]: 569811 : if (!BN_copy(t1, x)) goto err;
130 [ + - ]: 569811 : if (!group->meth->field_mul(group, x1, x1, z2, ctx)) goto err;
131 [ + - ]: 569811 : if (!group->meth->field_mul(group, z1, z1, x2, ctx)) goto err;
132 [ + - ]: 569811 : if (!group->meth->field_mul(group, t2, x1, z1, ctx)) goto err;
133 [ + - ]: 569811 : if (!BN_GF2m_add(z1, z1, x1)) goto err;
134 [ + - ]: 569811 : if (!group->meth->field_sqr(group, z1, z1, ctx)) goto err;
135 [ + - ]: 569811 : if (!group->meth->field_mul(group, x1, z1, t1, ctx)) goto err;
136 [ + - ]: 569811 : if (!BN_GF2m_add(x1, x1, t2)) goto err;
137 : :
138 : 569811 : ret = 1;
139 : :
140 : : err:
141 : 569811 : BN_CTX_end(ctx);
142 : 569811 : return ret;
143 : : }
144 : :
145 : : /* Compute the x, y affine coordinates from the point (x1, z1) (x2, z2)
146 : : * using Montgomery point multiplication algorithm Mxy() in appendix of
147 : : * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
148 : : * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
149 : : * Returns:
150 : : * 0 on error
151 : : * 1 if return value should be the point at infinity
152 : : * 2 otherwise
153 : : */
154 : 3191 : static int gf2m_Mxy(const EC_GROUP *group, const BIGNUM *x, const BIGNUM *y, BIGNUM *x1,
155 : : BIGNUM *z1, BIGNUM *x2, BIGNUM *z2, BN_CTX *ctx)
156 : : {
157 : : BIGNUM *t3, *t4, *t5;
158 : 3191 : int ret = 0;
159 : :
160 [ + + ]: 3191 : if (BN_is_zero(z1))
161 : : {
162 : 77 : BN_zero(x2);
163 : 77 : BN_zero(z2);
164 : 77 : return 1;
165 : : }
166 : :
167 [ - + ]: 3114 : if (BN_is_zero(z2))
168 : : {
169 [ # # ]: 0 : if (!BN_copy(x2, x)) return 0;
170 [ # # ]: 0 : if (!BN_GF2m_add(z2, x, y)) return 0;
171 : 0 : return 2;
172 : : }
173 : :
174 : : /* Since Mxy is static we can guarantee that ctx != NULL. */
175 : 3114 : BN_CTX_start(ctx);
176 : 3114 : t3 = BN_CTX_get(ctx);
177 : 3114 : t4 = BN_CTX_get(ctx);
178 : 3114 : t5 = BN_CTX_get(ctx);
179 [ + - ]: 3114 : if (t5 == NULL) goto err;
180 : :
181 [ + - ]: 3114 : if (!BN_one(t5)) goto err;
182 : :
183 [ + - ]: 3114 : if (!group->meth->field_mul(group, t3, z1, z2, ctx)) goto err;
184 : :
185 [ + - ]: 3114 : if (!group->meth->field_mul(group, z1, z1, x, ctx)) goto err;
186 [ + - ]: 3114 : if (!BN_GF2m_add(z1, z1, x1)) goto err;
187 [ + - ]: 3114 : if (!group->meth->field_mul(group, z2, z2, x, ctx)) goto err;
188 [ + - ]: 3114 : if (!group->meth->field_mul(group, x1, z2, x1, ctx)) goto err;
189 [ + - ]: 3114 : if (!BN_GF2m_add(z2, z2, x2)) goto err;
190 : :
191 [ + - ]: 3114 : if (!group->meth->field_mul(group, z2, z2, z1, ctx)) goto err;
192 [ + - ]: 3114 : if (!group->meth->field_sqr(group, t4, x, ctx)) goto err;
193 [ + - ]: 3114 : if (!BN_GF2m_add(t4, t4, y)) goto err;
194 [ + - ]: 3114 : if (!group->meth->field_mul(group, t4, t4, t3, ctx)) goto err;
195 [ + - ]: 3114 : if (!BN_GF2m_add(t4, t4, z2)) goto err;
196 : :
197 [ + - ]: 3114 : if (!group->meth->field_mul(group, t3, t3, x, ctx)) goto err;
198 [ + - ]: 3114 : if (!group->meth->field_div(group, t3, t5, t3, ctx)) goto err;
199 [ + - ]: 3114 : if (!group->meth->field_mul(group, t4, t3, t4, ctx)) goto err;
200 [ + - ]: 3114 : if (!group->meth->field_mul(group, x2, x1, t3, ctx)) goto err;
201 [ + - ]: 3114 : if (!BN_GF2m_add(z2, x2, x)) goto err;
202 : :
203 [ + - ]: 3114 : if (!group->meth->field_mul(group, z2, z2, t4, ctx)) goto err;
204 [ + - ]: 3114 : if (!BN_GF2m_add(z2, z2, y)) goto err;
205 : :
206 : 3114 : ret = 2;
207 : :
208 : : err:
209 : 3114 : BN_CTX_end(ctx);
210 : 3114 : return ret;
211 : : }
212 : :
213 : :
214 : : /* Computes scalar*point and stores the result in r.
215 : : * point can not equal r.
216 : : * Uses a modified algorithm 2P of
217 : : * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over
218 : : * GF(2^m) without precomputation" (CHES '99, LNCS 1717).
219 : : *
220 : : * To protect against side-channel attack the function uses constant time swap,
221 : : * avoiding conditional branches.
222 : : */
223 : 3221 : static int ec_GF2m_montgomery_point_multiply(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
224 : : const EC_POINT *point, BN_CTX *ctx)
225 : : {
226 : : BIGNUM *x1, *x2, *z1, *z2;
227 : 3221 : int ret = 0, i;
228 : : BN_ULONG mask,word;
229 : :
230 [ - + ]: 3221 : if (r == point)
231 : : {
232 : 0 : ECerr(EC_F_EC_GF2M_MONTGOMERY_POINT_MULTIPLY, EC_R_INVALID_ARGUMENT);
233 : 0 : return 0;
234 : : }
235 : :
236 : : /* if result should be point at infinity */
237 [ + - ][ + - ]: 6442 : if ((scalar == NULL) || BN_is_zero(scalar) || (point == NULL) ||
[ + - + + ]
238 : 3221 : EC_POINT_is_at_infinity(group, point))
239 : : {
240 : 30 : return EC_POINT_set_to_infinity(group, r);
241 : : }
242 : :
243 : : /* only support affine coordinates */
244 [ + - ]: 3191 : if (!point->Z_is_one) return 0;
245 : :
246 : : /* Since point_multiply is static we can guarantee that ctx != NULL. */
247 : 3191 : BN_CTX_start(ctx);
248 : 3191 : x1 = BN_CTX_get(ctx);
249 : 3191 : z1 = BN_CTX_get(ctx);
250 [ + - ]: 3191 : if (z1 == NULL) goto err;
251 : :
252 : 3191 : x2 = &r->X;
253 : 3191 : z2 = &r->Y;
254 : :
255 [ + + ]: 3191 : bn_wexpand(x1, group->field.top);
256 [ + + ]: 3191 : bn_wexpand(z1, group->field.top);
257 [ + + ]: 3191 : bn_wexpand(x2, group->field.top);
258 [ + + ]: 3191 : bn_wexpand(z2, group->field.top);
259 : :
260 [ + - ]: 3191 : if (!BN_GF2m_mod_arr(x1, &point->X, group->poly)) goto err; /* x1 = x */
261 [ + - ]: 3191 : if (!BN_one(z1)) goto err; /* z1 = 1 */
262 [ + - ]: 3191 : if (!group->meth->field_sqr(group, z2, x1, ctx)) goto err; /* z2 = x1^2 = x^2 */
263 [ + - ]: 3191 : if (!group->meth->field_sqr(group, x2, z2, ctx)) goto err;
264 [ + - ]: 3191 : if (!BN_GF2m_add(x2, x2, &group->b)) goto err; /* x2 = x^4 + b */
265 : :
266 : : /* find top most bit and go one past it */
267 : 3191 : i = scalar->top - 1;
268 : 3191 : mask = BN_TBIT;
269 : 3191 : word = scalar->d[i];
270 [ + + ]: 98029 : while (!(word & mask)) mask >>= 1;
271 : 3191 : mask >>= 1;
272 : : /* if top most bit was at word break, go to next word */
273 [ + + ]: 3191 : if (!mask)
274 : : {
275 : 8 : i--;
276 : 3191 : mask = BN_TBIT;
277 : : }
278 : :
279 [ + + ]: 13618 : for (; i >= 0; i--)
280 : : {
281 : 10427 : word = scalar->d[i];
282 [ + + ]: 580238 : while (mask)
283 : : {
284 : 569811 : BN_consttime_swap(word & mask, x1, x2, group->field.top);
285 : 569811 : BN_consttime_swap(word & mask, z1, z2, group->field.top);
286 [ + - ]: 569811 : if (!gf2m_Madd(group, &point->X, x2, z2, x1, z1, ctx)) goto err;
287 [ + - ]: 569811 : if (!gf2m_Mdouble(group, x1, z1, ctx)) goto err;
288 : 569811 : BN_consttime_swap(word & mask, x1, x2, group->field.top);
289 : 569811 : BN_consttime_swap(word & mask, z1, z2, group->field.top);
290 : 569811 : mask >>= 1;
291 : : }
292 : 10427 : mask = BN_TBIT;
293 : : }
294 : :
295 : : /* convert out of "projective" coordinates */
296 : 3191 : i = gf2m_Mxy(group, &point->X, &point->Y, x1, z1, x2, z2, ctx);
297 [ + - ]: 3191 : if (i == 0) goto err;
298 [ + + ]: 3191 : else if (i == 1)
299 : : {
300 [ + - ]: 77 : if (!EC_POINT_set_to_infinity(group, r)) goto err;
301 : : }
302 : : else
303 : : {
304 [ + - ]: 3114 : if (!BN_one(&r->Z)) goto err;
305 : 3114 : r->Z_is_one = 1;
306 : : }
307 : :
308 : : /* GF(2^m) field elements should always have BIGNUM::neg = 0 */
309 : 3191 : BN_set_negative(&r->X, 0);
310 : 3191 : BN_set_negative(&r->Y, 0);
311 : :
312 : 3191 : ret = 1;
313 : :
314 : : err:
315 : 3191 : BN_CTX_end(ctx);
316 : 3191 : return ret;
317 : : }
318 : :
319 : :
320 : : /* Computes the sum
321 : : * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
322 : : * gracefully ignoring NULL scalar values.
323 : : */
324 : 3070 : int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
325 : : size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
326 : : {
327 : 3070 : BN_CTX *new_ctx = NULL;
328 : 3070 : int ret = 0;
329 : : size_t i;
330 : 3070 : EC_POINT *p=NULL;
331 : 3070 : EC_POINT *acc = NULL;
332 : :
333 [ - + ]: 3070 : if (ctx == NULL)
334 : : {
335 : 0 : ctx = new_ctx = BN_CTX_new();
336 [ # # ]: 0 : if (ctx == NULL)
337 : : return 0;
338 : : }
339 : :
340 : : /* This implementation is more efficient than the wNAF implementation for 2
341 : : * or fewer points. Use the ec_wNAF_mul implementation for 3 or more points,
342 : : * or if we can perform a fast multiplication based on precomputation.
343 : : */
344 [ + + ][ + + ]: 3070 : if ((scalar && (num > 1)) || (num > 2) || (num == 0 && EC_GROUP_have_precompute_mult(group)))
[ + + ][ + + ]
345 : : {
346 : 21 : ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx);
347 : 21 : goto err;
348 : : }
349 : :
350 [ + - ]: 3049 : if ((p = EC_POINT_new(group)) == NULL) goto err;
351 [ + - ]: 3049 : if ((acc = EC_POINT_new(group)) == NULL) goto err;
352 : :
353 [ + - ]: 3049 : if (!EC_POINT_set_to_infinity(group, acc)) goto err;
354 : :
355 [ + + ]: 3049 : if (scalar)
356 : : {
357 [ + - ]: 2037 : if (!ec_GF2m_montgomery_point_multiply(group, p, scalar, group->generator, ctx)) goto err;
358 [ - + ]: 2037 : if (BN_is_negative(scalar))
359 [ # # ]: 0 : if (!group->meth->invert(group, p, ctx)) goto err;
360 [ + - ]: 3049 : if (!group->meth->add(group, acc, acc, p, ctx)) goto err;
361 : : }
362 : :
363 [ + + ]: 4233 : for (i = 0; i < num; i++)
364 : : {
365 [ + - ]: 1184 : if (!ec_GF2m_montgomery_point_multiply(group, p, scalars[i], points[i], ctx)) goto err;
366 [ + + ]: 1184 : if (BN_is_negative(scalars[i]))
367 [ + - ]: 21 : if (!group->meth->invert(group, p, ctx)) goto err;
368 [ + - ]: 1184 : if (!group->meth->add(group, acc, acc, p, ctx)) goto err;
369 : : }
370 : :
371 [ + - ]: 3049 : if (!EC_POINT_copy(r, acc)) goto err;
372 : :
373 : 3049 : ret = 1;
374 : :
375 : : err:
376 [ + + ]: 3070 : if (p) EC_POINT_free(p);
377 [ + + ]: 3070 : if (acc) EC_POINT_free(acc);
378 [ - + ]: 3070 : if (new_ctx != NULL)
379 : 0 : BN_CTX_free(new_ctx);
380 : 3070 : return ret;
381 : : }
382 : :
383 : :
384 : : /* Precomputation for point multiplication: fall back to wNAF methods
385 : : * because ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate */
386 : :
387 : 10 : int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
388 : : {
389 : 10 : return ec_wNAF_precompute_mult(group, ctx);
390 : : }
391 : :
392 : 1886 : int ec_GF2m_have_precompute_mult(const EC_GROUP *group)
393 : : {
394 : 1886 : return ec_wNAF_have_precompute_mult(group);
395 : : }
396 : :
397 : : #endif
|
