source: EcnlProtoTool/trunk/openssl-1.1.0e/crypto/ec/ec2_mult.c@ 331

Last change on this file since 331 was 331, checked in by coas-nagasima, 6 years ago

prototoolに関連するプロジェクトをnewlibからmuslを使うよう変更・更新
ntshellをnewlibの下位の実装から、muslのsyscallの実装に変更・更新
以下のOSSをアップデート
・mruby-1.3.0
・musl-1.1.18
・onigmo-6.1.3
・tcc-0.9.27
以下のOSSを追加
・openssl-1.1.0e
・curl-7.57.0
・zlib-1.2.11
以下のmrbgemsを追加
・iij/mruby-digest
・iij/mruby-env
・iij/mruby-errno
・iij/mruby-iijson
・iij/mruby-ipaddr
・iij/mruby-mock
・iij/mruby-require
・iij/mruby-tls-openssl
  • Property svn:eol-style set to native
  • Property svn:mime-type set to text/x-csrc
File size: 11.6 KB
Line 
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 */
40static 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 */
81static 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 */
129static 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 */
219static 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 */
332int 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
408int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
409{
410 return ec_wNAF_precompute_mult(group, ctx);
411}
412
413int ec_GF2m_have_precompute_mult(const EC_GROUP *group)
414{
415 return ec_wNAF_have_precompute_mult(group);
416}
417
418#endif
Note: See TracBrowser for help on using the repository browser.