]>
Commit | Line | Data |
---|---|---|
aa6bb135 RS |
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 | ||
7793f30e BM |
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 | * | |
7793f30e BM |
20 | * The software is originally written by Sheueling Chang Shantz and |
21 | * Douglas Stebila of Sun Microsystems Laboratories. | |
22 | * | |
23 | */ | |
7793f30e BM |
24 | |
25 | #include <openssl/err.h> | |
26 | ||
5784a521 | 27 | #include "internal/bn_int.h" |
7793f30e BM |
28 | #include "ec_lcl.h" |
29 | ||
b3310161 DSH |
30 | #ifndef OPENSSL_NO_EC2M |
31 | ||
3a83462d | 32 | /*- |
0f113f3e | 33 | * Compute the x-coordinate x/z for the point 2*(x/z) in Montgomery projective |
7793f30e | 34 | * coordinates. |
0f113f3e MC |
35 | * Uses algorithm Mdouble in appendix of |
36 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over | |
2238e8e4 | 37 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717). |
7793f30e BM |
38 | * modified to not require precomputation of c=b^{2^{m-1}}. |
39 | */ | |
0f113f3e MC |
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; | |
7793f30e BM |
68 | |
69 | err: | |
0f113f3e MC |
70 | BN_CTX_end(ctx); |
71 | return ret; | |
72 | } | |
7793f30e | 73 | |
3a83462d | 74 | /*- |
0f113f3e | 75 | * Compute the x-coordinate x1/z1 for the point (x1/z1)+(x2/x2) in Montgomery |
7793f30e | 76 | * projective coordinates. |
0f113f3e MC |
77 | * Uses algorithm Madd in appendix of |
78 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over | |
2238e8e4 | 79 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717). |
7793f30e | 80 | */ |
0f113f3e MC |
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; | |
7793f30e BM |
113 | |
114 | err: | |
0f113f3e MC |
115 | BN_CTX_end(ctx); |
116 | return ret; | |
117 | } | |
7793f30e | 118 | |
1d97c843 | 119 | /*- |
0f113f3e MC |
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 | |
2238e8e4 | 123 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717). |
7793f30e BM |
124 | * Returns: |
125 | * 0 on error | |
126 | * 1 if return value should be the point at infinity | |
127 | * 2 otherwise | |
128 | */ | |
0f113f3e MC |
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; | |
7793f30e BM |
203 | |
204 | err: | |
0f113f3e MC |
205 | BN_CTX_end(ctx); |
206 | return ret; | |
207 | } | |
f9b6c0ba | 208 | |
1d97c843 TH |
209 | /*- |
210 | * Computes scalar*point and stores the result in r. | |
7793f30e | 211 | * point can not equal r. |
f9b6c0ba | 212 | * Uses a modified algorithm 2P of |
0f113f3e | 213 | * Lopez, J. and Dahab, R. "Fast multiplication on elliptic curves over |
2238e8e4 | 214 | * GF(2^m) without precomputation" (CHES '99, LNCS 1717). |
f9b6c0ba DSH |
215 | * |
216 | * To protect against side-channel attack the function uses constant time swap, | |
217 | * avoiding conditional branches. | |
7793f30e | 218 | */ |
0f113f3e MC |
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; | |
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 | bn_wexpand(x1, bn_get_top(group->field)); | |
257 | bn_wexpand(z1, bn_get_top(group->field)); | |
258 | bn_wexpand(x2, bn_get_top(group->field)); | |
259 | bn_wexpand(z2, bn_get_top(group->field)); | |
260 | ||
261 | if (!BN_GF2m_mod_arr(x1, point->X, group->poly)) | |
262 | goto err; /* x1 = x */ | |
263 | if (!BN_one(z1)) | |
264 | goto err; /* z1 = 1 */ | |
265 | if (!group->meth->field_sqr(group, z2, x1, ctx)) | |
266 | goto err; /* z2 = x1^2 = x^2 */ | |
267 | if (!group->meth->field_sqr(group, x2, z2, ctx)) | |
268 | goto err; | |
269 | if (!BN_GF2m_add(x2, x2, group->b)) | |
270 | goto err; /* x2 = x^4 + b */ | |
271 | ||
272 | /* find top most bit and go one past it */ | |
273 | i = bn_get_top(scalar) - 1; | |
274 | mask = BN_TBIT; | |
275 | word = bn_get_words(scalar)[i]; | |
276 | while (!(word & mask)) | |
277 | mask >>= 1; | |
278 | mask >>= 1; | |
279 | /* if top most bit was at word break, go to next word */ | |
280 | if (!mask) { | |
281 | i--; | |
282 | mask = BN_TBIT; | |
283 | } | |
284 | ||
285 | for (; i >= 0; i--) { | |
286 | word = bn_get_words(scalar)[i]; | |
287 | while (mask) { | |
288 | BN_consttime_swap(word & mask, x1, x2, bn_get_top(group->field)); | |
289 | BN_consttime_swap(word & mask, z1, z2, bn_get_top(group->field)); | |
290 | if (!gf2m_Madd(group, point->X, x2, z2, x1, z1, ctx)) | |
291 | goto err; | |
292 | if (!gf2m_Mdouble(group, x1, z1, ctx)) | |
293 | goto err; | |
294 | BN_consttime_swap(word & mask, x1, x2, bn_get_top(group->field)); | |
295 | BN_consttime_swap(word & mask, z1, z2, bn_get_top(group->field)); | |
296 | mask >>= 1; | |
297 | } | |
298 | mask = BN_TBIT; | |
299 | } | |
300 | ||
301 | /* convert out of "projective" coordinates */ | |
302 | i = gf2m_Mxy(group, point->X, point->Y, x1, z1, x2, z2, ctx); | |
303 | if (i == 0) | |
304 | goto err; | |
305 | else if (i == 1) { | |
306 | if (!EC_POINT_set_to_infinity(group, r)) | |
307 | goto err; | |
308 | } else { | |
309 | if (!BN_one(r->Z)) | |
310 | goto err; | |
311 | r->Z_is_one = 1; | |
312 | } | |
313 | ||
314 | /* GF(2^m) field elements should always have BIGNUM::neg = 0 */ | |
315 | BN_set_negative(r->X, 0); | |
316 | BN_set_negative(r->Y, 0); | |
317 | ||
318 | ret = 1; | |
7793f30e BM |
319 | |
320 | err: | |
0f113f3e MC |
321 | BN_CTX_end(ctx); |
322 | return ret; | |
323 | } | |
7793f30e | 324 | |
1d97c843 TH |
325 | /*- |
326 | * Computes the sum | |
7793f30e BM |
327 | * scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1] |
328 | * gracefully ignoring NULL scalar values. | |
329 | */ | |
0f113f3e MC |
330 | int ec_GF2m_simple_mul(const EC_GROUP *group, EC_POINT *r, |
331 | const BIGNUM *scalar, size_t num, | |
332 | const EC_POINT *points[], const BIGNUM *scalars[], | |
333 | BN_CTX *ctx) | |
334 | { | |
335 | BN_CTX *new_ctx = NULL; | |
336 | int ret = 0; | |
337 | size_t i; | |
338 | EC_POINT *p = NULL; | |
339 | EC_POINT *acc = NULL; | |
340 | ||
341 | if (ctx == NULL) { | |
342 | ctx = new_ctx = BN_CTX_new(); | |
343 | if (ctx == NULL) | |
344 | return 0; | |
345 | } | |
346 | ||
347 | /* | |
348 | * This implementation is more efficient than the wNAF implementation for | |
349 | * 2 or fewer points. Use the ec_wNAF_mul implementation for 3 or more | |
350 | * points, or if we can perform a fast multiplication based on | |
351 | * precomputation. | |
352 | */ | |
353 | if ((scalar && (num > 1)) || (num > 2) | |
354 | || (num == 0 && EC_GROUP_have_precompute_mult(group))) { | |
355 | ret = ec_wNAF_mul(group, r, scalar, num, points, scalars, ctx); | |
356 | goto err; | |
357 | } | |
358 | ||
359 | if ((p = EC_POINT_new(group)) == NULL) | |
360 | goto err; | |
361 | if ((acc = EC_POINT_new(group)) == NULL) | |
362 | goto err; | |
363 | ||
364 | if (!EC_POINT_set_to_infinity(group, acc)) | |
365 | goto err; | |
366 | ||
367 | if (scalar) { | |
368 | if (!ec_GF2m_montgomery_point_multiply | |
369 | (group, p, scalar, group->generator, ctx)) | |
370 | goto err; | |
371 | if (BN_is_negative(scalar)) | |
372 | if (!group->meth->invert(group, p, ctx)) | |
373 | goto err; | |
374 | if (!group->meth->add(group, acc, acc, p, ctx)) | |
375 | goto err; | |
376 | } | |
377 | ||
378 | for (i = 0; i < num; i++) { | |
379 | if (!ec_GF2m_montgomery_point_multiply | |
380 | (group, p, scalars[i], points[i], ctx)) | |
381 | goto err; | |
382 | if (BN_is_negative(scalars[i])) | |
383 | if (!group->meth->invert(group, p, ctx)) | |
384 | goto err; | |
385 | if (!group->meth->add(group, acc, acc, p, ctx)) | |
386 | goto err; | |
387 | } | |
388 | ||
389 | if (!EC_POINT_copy(r, acc)) | |
390 | goto err; | |
391 | ||
392 | ret = 1; | |
393 | ||
394 | err: | |
8fdc3734 RS |
395 | EC_POINT_free(p); |
396 | EC_POINT_free(acc); | |
23a1d5e9 | 397 | BN_CTX_free(new_ctx); |
0f113f3e MC |
398 | return ret; |
399 | } | |
400 | ||
401 | /* | |
402 | * Precomputation for point multiplication: fall back to wNAF methods because | |
403 | * ec_GF2m_simple_mul() uses ec_wNAF_mul() if appropriate | |
404 | */ | |
37c660ff | 405 | |
15994b03 | 406 | int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx) |
0f113f3e MC |
407 | { |
408 | return ec_wNAF_precompute_mult(group, ctx); | |
409 | } | |
37c660ff BM |
410 | |
411 | int ec_GF2m_have_precompute_mult(const EC_GROUP *group) | |
0f113f3e MC |
412 | { |
413 | return ec_wNAF_have_precompute_mult(group); | |
414 | } | |
b3310161 DSH |
415 | |
416 | #endif |