651de977c9e347cc4a968efb14a9d57100ba1468
[openssl.git] / crypto / ec / ec_mult.c
1 /* crypto/ec/ec_mult.c */
2 /* ====================================================================
3  * Copyright (c) 1998-2001 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 #include <openssl/err.h>
57
58 #include "ec_lcl.h"
59
60
61 /* TODO: width-m NAFs */
62
63 /* TODO: optional precomputation of multiples of the generator */
64
65
66 #define EC_window_bits_for_scalar_size(b) \
67                 ((b) >= 2000 ? 6 : \
68                  (b) >=  800 ? 5 : \
69                  (b) >=  300 ? 4 : \
70                  (b) >=   70 ? 3 : \
71                  (b) >=   20 ? 2 : \
72                   1)
73 /* For window size 'w' (w >= 2), we compute the odd multiples
74  *      1*P .. (2^w-1)*P.
75  * This accounts for  2^(w-1)  point additions (neglecting constants),
76  * each of which requires 16 field multiplications (4 squarings
77  * and 12 general multiplications) in the case of curves defined
78  * over GF(p), which are the only curves we have so far.
79  *
80  * Converting these precomputed points into affine form takes
81  * three field multiplications for inverting Z and one squaring
82  * and three multiplications for adjusting X and Y, i.e.
83  * 7 multiplications in total (1 squaring and 6 general multiplications),
84  * again except for constants.
85  *
86  * The average number of windows for a 'b' bit scalar is roughly
87  *          b/(w+1).
88  * Each of these windows (except possibly for the first one, but
89  * we are ignoring constants anyway) requires one point addition.
90  * As the precomputed table stores points in affine form, these
91  * additions take only 11 field multiplications each (3 squarings
92  * and 8 general multiplications).
93  *
94  * So the total workload, except for constants, is
95  *
96  *        2^(w-1)*[5 squarings + 18 multiplications]
97  *      + (b/(w+1))*[3 squarings + 8 multiplications]
98  *
99  * If we assume that 10 squarings are as costly as 9 multiplications,
100  * our task is to find the 'w' that, given 'b', minimizes
101  *
102  *        2^(w-1)*(5*9 + 18*10) + (b/(w+1))*(3*9 + 8*10)
103  *      = 2^(w-1)*225 +           (b/(w+1))*107.
104  *
105  * Thus optimal window sizes should be roughly as follows:
106  *
107  *    w >= 6  if         b >= 1414
108  *     w = 5  if 1413 >= b >=  505
109  *     w = 4  if  504 >= b >=  169
110  *     w = 3  if  168 >= b >=   51
111  *     w = 2  if   50 >= b >=   13
112  *     w = 1  if   12 >= b
113  *
114  * If we assume instead that squarings are exactly as costly as
115  * multiplications, we have to minimize
116  *      2^(w-1)*23 + (b/(w+1))*11.
117  *
118  * This gives us the following (nearly unchanged) table of optimal
119  * windows sizes:
120  *
121  *    w >= 6  if         b >= 1406
122  *     w = 5  if 1405 >= b >=  502
123  *     w = 4  if  501 >= b >=  168
124  *     w = 3  if  167 >= b >=   51
125  *     w = 2  if   50 >= b >=   13
126  *     w = 1  if   12 >= b
127  *
128  * Note that neither table tries to take into account memory usage
129  * (allocation overhead, code locality etc.).  Actual timings with
130  * NIST curves P-192, P-224, and P-256 with scalars of 192, 224,
131  * and 256 bits, respectively, show that  w = 3  (instead of 4) is
132  * preferrable; timings with NIST curve P-384 and 384-bit scalars
133  * confirm that  w = 4  is optimal for this case; and timings with
134  * NIST curve P-521 and 521-bit scalars show that  w = 4  (instead
135  * of 5) is preferrable.  So we generously round up all the
136  * boundaries and use the following table:
137  *
138  *    w >= 6  if         b >= 2000
139  *     w = 5  if 1999 >= b >=  800
140  *     w = 4  if  799 >= b >=  300
141  *     w = 3  if  299 >= b >=   70
142  *     w = 2  if   69 >= b >=   20
143  *     w = 1  if   19 >= b
144  */
145
146
147
148 /* Compute
149  *      \sum scalars[i]*points[i]
150  * where
151  *      scalar*generator
152  * is included in the addition if scalar != NULL
153  */
154 int EC_POINTs_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *scalar,
155         size_t num, const EC_POINT *points[], const BIGNUM *scalars[], BN_CTX *ctx)
156         {
157         BN_CTX *new_ctx = NULL;
158         EC_POINT *generator = NULL;
159         EC_POINT *tmp = NULL;
160         size_t totalnum;
161         size_t i, j;
162         int k, t;
163         int r_is_at_infinity = 1;
164         size_t max_bits = 0;
165         size_t *wsize = NULL; /* individual window sizes */
166         unsigned long *wbits = NULL; /* individual window contents */
167         int *wpos = NULL; /* position of bottom bit of current individual windows
168                            * (wpos[i] is valid if wbits[i] != 0) */
169         size_t num_val;
170         EC_POINT **val = NULL; /* precomputation */
171         EC_POINT **v;
172         EC_POINT ***val_sub = NULL; /* pointers to sub-arrays of 'val' */
173         int ret = 0;
174         
175         if (scalar != NULL)
176                 {
177                 generator = EC_GROUP_get0_generator(group);
178                 if (generator == NULL)
179                         {
180                         ECerr(EC_F_EC_POINTS_MUL, EC_R_UNDEFINED_GENERATOR);
181                         return 0;
182                         }
183                 }
184         
185         for (i = 0; i < num; i++)
186                 {
187                 if (group->meth != points[i]->meth)
188                         {
189                         ECerr(EC_F_EC_POINTS_MUL, EC_R_INCOMPATIBLE_OBJECTS);
190                         return 0;
191                         }
192                 }
193
194         totalnum = num + (scalar != NULL);
195
196         wsize = OPENSSL_malloc(totalnum * sizeof wsize[0]);
197         wbits = OPENSSL_malloc(totalnum * sizeof wbits[0]);
198         wpos = OPENSSL_malloc(totalnum * sizeof wpos[0]);
199         if (wsize == NULL || wbits == NULL || wpos == NULL) goto err;
200
201         /* num_val := total number of points to precompute */
202         num_val = 0;
203         for (i = 0; i < totalnum; i++)
204                 {
205                 size_t bits;
206
207                 bits = i < num ? BN_num_bits(scalars[i]) : BN_num_bits(scalar);
208                 wsize[i] = EC_window_bits_for_scalar_size(bits);
209                 num_val += 1u << (wsize[i] - 1);
210                 if (bits > max_bits)
211                         max_bits = bits;
212                 wbits[i] = 0;
213                 wpos[i] = 0;
214                 }
215
216         /* all precomputed points go into a single array 'val',
217          * 'val_sub[i]' is a pointer to the subarray for the i-th point */
218         val = OPENSSL_malloc((num_val + 1) * sizeof val[0]);
219         if (val == NULL) goto err;
220         val[num_val] = NULL; /* pivot element */
221
222         val_sub = OPENSSL_malloc(totalnum * sizeof val_sub[0]);
223         if (val_sub == NULL) goto err;
224
225         /* allocate points for precomputation */
226         v = val;
227         for (i = 0; i < totalnum; i++)
228                 {
229                 val_sub[i] = v;
230                 for (j = 0; j < (1u << (wsize[i] - 1)); j++)
231                         {
232                         *v = EC_POINT_new(group);
233                         if (*v == NULL) goto err;
234                         v++;
235                         }
236                 }
237         if (!(v == val + num_val))
238                 {
239                 ECerr(EC_F_EC_POINTS_MUL, ERR_R_INTERNAL_ERROR);
240                 goto err;
241                 }
242
243         if (ctx == NULL)
244                 {
245                 ctx = new_ctx = BN_CTX_new();
246                 if (ctx == NULL)
247                         goto err;
248                 }
249         
250         tmp = EC_POINT_new(group);
251         if (tmp == NULL) goto err;
252
253         /* prepare precomputed values:
254          *    val_sub[i][0] :=     points[i]
255          *    val_sub[i][1] := 3 * points[i]
256          *    val_sub[i][2] := 5 * points[i]
257          *    ...
258          */
259         for (i = 0; i < totalnum; i++)
260                 {
261                 if (i < num)
262                         {
263                         if (!EC_POINT_copy(val_sub[i][0], points[i])) goto err;
264                         if (scalars[i]->neg)
265                                 {
266                                 if (!EC_POINT_invert(group, val_sub[i][0], ctx)) goto err;
267                                 }
268                         }
269                 else
270                         {
271                         if (!EC_POINT_copy(val_sub[i][0], generator)) goto err;
272                         if (scalar->neg)
273                                 {
274                                 if (!EC_POINT_invert(group, val_sub[i][0], ctx)) goto err;
275                                 }
276                         }
277
278                 if (wsize[i] > 1)
279                         {
280                         if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err;
281                         for (j = 1; j < (1u << (wsize[i] - 1)); j++)
282                                 {
283                                 if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err;
284                                 }
285                         }
286                 }
287
288 #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */
289         if (!EC_POINTs_make_affine(group, num_val, val, ctx)) goto err;
290 #endif
291
292         r_is_at_infinity = 1;
293
294         for (k = max_bits - 1; k >= 0; k--)
295                 {
296                 if (!r_is_at_infinity)
297                         {
298                         if (!EC_POINT_dbl(group, r, r, ctx)) goto err;
299                         }
300                 
301                 for (i = 0; i < totalnum; i++)
302                         {
303                         if (wbits[i] == 0)
304                                 {
305                                 const BIGNUM *s;
306
307                                 s = i < num ? scalars[i] : scalar;
308
309                                 if (BN_is_bit_set(s, k))
310                                         {
311                                         /* look at bits  k - wsize[i] + 1 .. k  for this window */
312                                         t = k - wsize[i] + 1;
313                                         while (!BN_is_bit_set(s, t)) /* BN_is_bit_set is false for t < 0 */
314                                                 t++;
315                                         wpos[i] = t;
316                                         wbits[i] = 1;
317                                         for (t = k - 1; t >= wpos[i]; t--)
318                                                 {
319                                                 wbits[i] <<= 1;
320                                                 if (BN_is_bit_set(s, t))
321                                                         wbits[i]++;
322                                                 }
323                                         /* now wbits[i] is the odd bit pattern at bits wpos[i] .. k */
324                                         }
325                                 }
326                         
327                         if ((wbits[i] != 0) && (wpos[i] == k))
328                                 {
329                                 if (r_is_at_infinity)
330                                         {
331                                         if (!EC_POINT_copy(r, val_sub[i][wbits[i] >> 1])) goto err;
332                                         r_is_at_infinity = 0;
333                                         }
334                                 else
335                                         {
336                                         if (!EC_POINT_add(group, r, r, val_sub[i][wbits[i] >> 1], ctx)) goto err;
337                                         }
338                                 wbits[i] = 0;
339                                 }
340                         }
341                 }
342
343         if (r_is_at_infinity)
344                 if (!EC_POINT_set_to_infinity(group, r)) goto err;
345         
346         ret = 1;
347
348  err:
349         if (new_ctx != NULL)
350                 BN_CTX_free(new_ctx);
351         if (tmp != NULL)
352                 EC_POINT_free(tmp);
353         if (wsize != NULL)
354                 OPENSSL_free(wsize);
355         if (wbits != NULL)
356                 OPENSSL_free(wbits);
357         if (wpos != NULL)
358                 OPENSSL_free(wpos);
359         if (val != NULL)
360                 {
361                 for (v = val; *v != NULL; v++)
362                         EC_POINT_clear_free(*v);
363
364                 OPENSSL_free(val);
365                 }
366         if (val_sub != NULL)
367                 {
368                 OPENSSL_free(val_sub);
369                 }
370         return ret;
371         }
372
373
374 int EC_POINT_mul(const EC_GROUP *group, EC_POINT *r, const BIGNUM *g_scalar, const EC_POINT *point, const BIGNUM *p_scalar, BN_CTX *ctx)
375         {
376         const EC_POINT *points[1];
377         const BIGNUM *scalars[1];
378
379         points[0] = point;
380         scalars[0] = p_scalar;
381
382         return EC_POINTs_mul(group, r, g_scalar, (point != NULL && p_scalar != NULL), points, scalars, ctx);
383         }
384
385
386 int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx)
387         {
388         const EC_POINT *generator;
389         BN_CTX *new_ctx = NULL;
390         BIGNUM *order;
391         int ret = 0;
392
393         generator = EC_GROUP_get0_generator(group);
394         if (generator == NULL)
395                 {
396                 ECerr(EC_F_EC_GROUP_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR);
397                 return 0;
398                 }
399
400         if (ctx == NULL)
401                 {
402                 ctx = new_ctx = BN_CTX_new();
403                 if (ctx == NULL)
404                         return 0;
405                 }
406         
407         BN_CTX_start(ctx);
408         order = BN_CTX_get(ctx);
409         if (order == NULL) goto err;
410         
411         if (!EC_GROUP_get_order(group, order, ctx)) return 0;
412         if (BN_is_zero(order))
413                 {
414                 ECerr(EC_F_EC_GROUP_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER);
415                 goto err;
416                 }
417
418         /* TODO */
419
420         ret = 1;
421         
422  err:
423         BN_CTX_end(ctx);
424         if (new_ctx != NULL)
425                 BN_CTX_free(new_ctx);
426         return ret;
427         }