1 /* Originally written by Bodo Moeller for the OpenSSL project.
2  * ====================================================================
3  * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer.
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in
14  *    the documentation and/or other materials provided with the
15  *    distribution.
16  *
17  * 3. All advertising materials mentioning features or use of this
18  *    software must display the following acknowledgment:
19  *    "This product includes software developed by the OpenSSL Project
20  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21  *
22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23  *    endorse or promote products derived from this software without
24  *    prior written permission. For written permission, please contact
25  *    openssl-core@openssl.org.
26  *
27  * 5. Products derived from this software may not be called "OpenSSL"
28  *    nor may "OpenSSL" appear in their names without prior written
29  *    permission of the OpenSSL Project.
30  *
31  * 6. Redistributions of any form whatsoever must retain the following
32  *    acknowledgment:
33  *    "This product includes software developed by the OpenSSL Project
34  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35  *
36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47  * OF THE POSSIBILITY OF SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This product includes cryptographic software written by Eric Young
51  * (eay@cryptsoft.com).  This product includes software written by Tim
52  * Hudson (tjh@cryptsoft.com).
53  *
54  */
55 /* ====================================================================
56  * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57  *
58  * Portions of the attached software ("Contribution") are developed by
59  * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60  *
61  * The Contribution is licensed pursuant to the OpenSSL open source
62  * license provided above.
63  *
64  * The elliptic curve binary polynomial software is originally written by
65  * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66  * Laboratories. */
67 
68 #include <openssl/ec.h>
69 
70 #include <string.h>
71 
72 #include <openssl/bn.h>
73 #include <openssl/err.h>
74 #include <openssl/mem.h>
75 #include <openssl/thread.h>
76 
77 #include "internal.h"
78 #include "../internal.h"
79 
80 
81 /* This file implements the wNAF-based interleaving multi-exponentation method
82  * (<URL:http://www.informatik.tu-darmstadt.de/TI/Mitarbeiter/moeller.html#multiexp>);
83  * */
84 
85 /* Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
86  * This is an array  r[]  of values that are either zero or odd with an
87  * absolute value less than  2^w  satisfying
88  *     scalar = \sum_j r[j]*2^j
89  * where at most one of any  w+1  consecutive digits is non-zero
90  * with the exception that the most significant digit may be only
91  * w-1 zeros away from that next non-zero digit.
92  */
compute_wNAF(const BIGNUM * scalar,int w,size_t * ret_len)93 static signed char *compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len) {
94   int window_val;
95   int ok = 0;
96   signed char *r = NULL;
97   int sign = 1;
98   int bit, next_bit, mask;
99   size_t len = 0, j;
100 
101   if (BN_is_zero(scalar)) {
102     r = OPENSSL_malloc(1);
103     if (!r) {
104       OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
105       goto err;
106     }
107     r[0] = 0;
108     *ret_len = 1;
109     return r;
110   }
111 
112   if (w <= 0 || w > 7) /* 'signed char' can represent integers with absolute
113                           values less than 2^7 */
114   {
115     OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
116     goto err;
117   }
118   bit = 1 << w;        /* at most 128 */
119   next_bit = bit << 1; /* at most 256 */
120   mask = next_bit - 1; /* at most 255 */
121 
122   if (BN_is_negative(scalar)) {
123     sign = -1;
124   }
125 
126   if (scalar->d == NULL || scalar->top == 0) {
127     OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
128     goto err;
129   }
130 
131   len = BN_num_bits(scalar);
132   r = OPENSSL_malloc(
133       len +
134       1); /* modified wNAF may be one digit longer than binary representation
135            * (*ret_len will be set to the actual length, i.e. at most
136            * BN_num_bits(scalar) + 1) */
137   if (r == NULL) {
138     OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
139     goto err;
140   }
141   window_val = scalar->d[0] & mask;
142   j = 0;
143   while ((window_val != 0) ||
144          (j + w + 1 < len)) /* if j+w+1 >= len, window_val will not increase */
145   {
146     int digit = 0;
147 
148     /* 0 <= window_val <= 2^(w+1) */
149 
150     if (window_val & 1) {
151       /* 0 < window_val < 2^(w+1) */
152 
153       if (window_val & bit) {
154         digit = window_val - next_bit; /* -2^w < digit < 0 */
155 
156 #if 1 /* modified wNAF */
157         if (j + w + 1 >= len) {
158           /* special case for generating modified wNAFs:
159            * no new bits will be added into window_val,
160            * so using a positive digit here will decrease
161            * the total length of the representation */
162 
163           digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
164         }
165 #endif
166       } else {
167         digit = window_val; /* 0 < digit < 2^w */
168       }
169 
170       if (digit <= -bit || digit >= bit || !(digit & 1)) {
171         OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
172         goto err;
173       }
174 
175       window_val -= digit;
176 
177       /* now window_val is 0 or 2^(w+1) in standard wNAF generation;
178        * for modified window NAFs, it may also be 2^w
179        */
180       if (window_val != 0 && window_val != next_bit && window_val != bit) {
181         OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
182         goto err;
183       }
184     }
185 
186     r[j++] = sign * digit;
187 
188     window_val >>= 1;
189     window_val += bit * BN_is_bit_set(scalar, j + w);
190 
191     if (window_val > next_bit) {
192       OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
193       goto err;
194     }
195   }
196 
197   if (j > len + 1) {
198     OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
199     goto err;
200   }
201   len = j;
202   ok = 1;
203 
204 err:
205   if (!ok) {
206     OPENSSL_free(r);
207     r = NULL;
208   }
209   if (ok) {
210     *ret_len = len;
211   }
212   return r;
213 }
214 
215 
216 /* TODO: table should be optimised for the wNAF-based implementation,
217  *       sometimes smaller windows will give better performance
218  *       (thus the boundaries should be increased)
219  */
220 #define EC_window_bits_for_scalar_size(b)                                      \
221   ((size_t)((b) >= 2000 ? 6 : (b) >= 800 ? 5 : (b) >= 300                      \
222                                                    ? 4                         \
223                                                    : (b) >= 70 ? 3 : (b) >= 20 \
224                                                                          ? 2   \
225                                                                          : 1))
226 
ec_wNAF_mul(const EC_GROUP * group,EC_POINT * r,const BIGNUM * g_scalar,const EC_POINT * p,const BIGNUM * p_scalar,BN_CTX * ctx)227 int ec_wNAF_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar,
228                 const EC_POINT *p, const BIGNUM *p_scalar, BN_CTX *ctx) {
229   BN_CTX *new_ctx = NULL;
230   const EC_POINT *generator = NULL;
231   EC_POINT *tmp = NULL;
232   size_t total_num;
233   size_t i, j;
234   int k;
235   int r_is_inverted = 0;
236   int r_is_at_infinity = 1;
237   size_t *wsize = NULL;      /* individual window sizes */
238   signed char **wNAF = NULL; /* individual wNAFs */
239   size_t *wNAF_len = NULL;
240   size_t max_len = 0;
241   size_t num_val;
242   EC_POINT **val = NULL; /* precomputation */
243   EC_POINT **v;
244   EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' */
245   int ret = 0;
246 
247   if (ctx == NULL) {
248     ctx = new_ctx = BN_CTX_new();
249     if (ctx == NULL) {
250       goto err;
251     }
252   }
253 
254   /* TODO: This function used to take |points| and |scalars| as arrays of
255    * |num| elements. The code below should be simplified to work in terms of |p|
256    * and |p_scalar|. */
257   size_t num = p != NULL ? 1 : 0;
258   const EC_POINT **points = p != NULL ? &p : NULL;
259   const BIGNUM **scalars = p != NULL ? &p_scalar : NULL;
260 
261   total_num = num;
262 
263   if (g_scalar != NULL) {
264     generator = EC_GROUP_get0_generator(group);
265     if (generator == NULL) {
266       OPENSSL_PUT_ERROR(EC, EC_R_UNDEFINED_GENERATOR);
267       goto err;
268     }
269 
270     ++total_num; /* treat 'g_scalar' like 'num'-th element of 'scalars' */
271   }
272 
273 
274   wsize = OPENSSL_malloc(total_num * sizeof wsize[0]);
275   wNAF_len = OPENSSL_malloc(total_num * sizeof wNAF_len[0]);
276   wNAF = OPENSSL_malloc((total_num + 1) *
277                         sizeof wNAF[0]); /* includes space for pivot */
278   val_sub = OPENSSL_malloc(total_num * sizeof val_sub[0]);
279 
280   /* Ensure wNAF is initialised in case we end up going to err. */
281   if (wNAF) {
282     wNAF[0] = NULL; /* preliminary pivot */
283   }
284 
285   if (!wsize || !wNAF_len || !wNAF || !val_sub) {
286     OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
287     goto err;
288   }
289 
290   /* num_val will be the total number of temporarily precomputed points */
291   num_val = 0;
292 
293   for (i = 0; i < total_num; i++) {
294     size_t bits;
295 
296     bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(g_scalar);
297     wsize[i] = EC_window_bits_for_scalar_size(bits);
298     num_val += (size_t)1 << (wsize[i] - 1);
299     wNAF[i + 1] = NULL; /* make sure we always have a pivot */
300     wNAF[i] =
301         compute_wNAF((i < num ? scalars[i] : g_scalar), wsize[i], &wNAF_len[i]);
302     if (wNAF[i] == NULL) {
303       goto err;
304     }
305     if (wNAF_len[i] > max_len) {
306       max_len = wNAF_len[i];
307     }
308   }
309 
310   /* All points we precompute now go into a single array 'val'. 'val_sub[i]' is
311    * a pointer to the subarray for the i-th point. */
312   val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
313   if (val == NULL) {
314     OPENSSL_PUT_ERROR(EC, ERR_R_MALLOC_FAILURE);
315     goto err;
316   }
317   val[num_val] = NULL; /* pivot element */
318 
319   /* allocate points for precomputation */
320   v = val;
321   for (i = 0; i < total_num; i++) {
322     val_sub[i] = v;
323     for (j = 0; j < ((size_t)1 << (wsize[i] - 1)); j++) {
324       *v = EC_POINT_new(group);
325       if (*v == NULL) {
326         goto err;
327       }
328       v++;
329     }
330   }
331   if (!(v == val + num_val)) {
332     OPENSSL_PUT_ERROR(EC, ERR_R_INTERNAL_ERROR);
333     goto err;
334   }
335 
336   if (!(tmp = EC_POINT_new(group))) {
337     goto err;
338   }
339 
340   /* prepare precomputed values:
341    *    val_sub[i][0] :=     points[i]
342    *    val_sub[i][1] := 3 * points[i]
343    *    val_sub[i][2] := 5 * points[i]
344    *    ...
345    */
346   for (i = 0; i < total_num; i++) {
347     if (i < num) {
348       if (!EC_POINT_copy(val_sub[i][0], points[i])) {
349         goto err;
350       }
351     } else if (!EC_POINT_copy(val_sub[i][0], generator)) {
352       goto err;
353     }
354 
355     if (wsize[i] > 1) {
356       if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) {
357         goto err;
358       }
359       for (j = 1; j < ((size_t)1 << (wsize[i] - 1)); j++) {
360         if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) {
361           goto err;
362         }
363       }
364     }
365   }
366 
367 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */
368   if (!EC_POINTs_make_affine(group, num_val, val, ctx)) {
369     goto err;
370   }
371 #endif
372 
373   r_is_at_infinity = 1;
374 
375   for (k = max_len - 1; k >= 0; k--) {
376     if (!r_is_at_infinity && !EC_POINT_dbl(group, r, r, ctx)) {
377       goto err;
378     }
379 
380     for (i = 0; i < total_num; i++) {
381       if (wNAF_len[i] > (size_t)k) {
382         int digit = wNAF[i][k];
383         int is_neg;
384 
385         if (digit) {
386           is_neg = digit < 0;
387 
388           if (is_neg) {
389             digit = -digit;
390           }
391 
392           if (is_neg != r_is_inverted) {
393             if (!r_is_at_infinity && !EC_POINT_invert(group, r, ctx)) {
394               goto err;
395             }
396             r_is_inverted = !r_is_inverted;
397           }
398 
399           /* digit > 0 */
400 
401           if (r_is_at_infinity) {
402             if (!EC_POINT_copy(r, val_sub[i][digit >> 1])) {
403               goto err;
404             }
405             r_is_at_infinity = 0;
406           } else {
407             if (!EC_POINT_add(group, r, r, val_sub[i][digit >> 1], ctx)) {
408               goto err;
409             }
410           }
411         }
412       }
413     }
414   }
415 
416   if (r_is_at_infinity) {
417     if (!EC_POINT_set_to_infinity(group, r)) {
418       goto err;
419     }
420   } else if (r_is_inverted && !EC_POINT_invert(group, r, ctx)) {
421     goto err;
422   }
423 
424   ret = 1;
425 
426 err:
427   BN_CTX_free(new_ctx);
428   EC_POINT_free(tmp);
429   OPENSSL_free(wsize);
430   OPENSSL_free(wNAF_len);
431   if (wNAF != NULL) {
432     signed char **w;
433 
434     for (w = wNAF; *w != NULL; w++) {
435       OPENSSL_free(*w);
436     }
437 
438     OPENSSL_free(wNAF);
439   }
440   if (val != NULL) {
441     for (v = val; *v != NULL; v++) {
442       EC_POINT_clear_free(*v);
443     }
444 
445     OPENSSL_free(val);
446   }
447   OPENSSL_free(val_sub);
448   return ret;
449 }
450