d253eba51b5a16d34a1e68a4e669951a219b3abf
[openssl.git] / crypto / ec / ec2_mult.c
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;
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;
319
320  err:
321     BN_CTX_end(ctx);
322     return ret;
323 }
324
325 /*-
326  * Computes the sum
327  *     scalar*group->generator + scalars[0]*points[0] + ... + scalars[num-1]*points[num-1]
328  * gracefully ignoring NULL scalar values.
329  */
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:
395     EC_POINT_free(p);
396     EC_POINT_free(acc);
397     BN_CTX_free(new_ctx);
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  */
405
406 int ec_GF2m_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
407 {
408     return ec_wNAF_precompute_mult(group, ctx);
409 }
410
411 int ec_GF2m_have_precompute_mult(const EC_GROUP *group)
412 {
413     return ec_wNAF_have_precompute_mult(group);
414 }
415
416 #endif