]>
Commit | Line | Data |
---|---|---|
65e81670 BM |
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 | ||
48fe4d62 BM |
56 | #include <openssl/err.h> |
57 | ||
65e81670 | 58 | #include "ec_lcl.h" |
48fe4d62 BM |
59 | |
60 | ||
61 | /* TODO: width-m NAFs */ | |
62 | ||
e3a4f8b8 | 63 | /* TODO: optional precomputation of multiples of the generator */ |
48fe4d62 BM |
64 | |
65 | ||
48fe4d62 | 66 | #define EC_window_bits_for_scalar_size(b) \ |
26fbabf3 BM |
67 | ((b) >= 2000 ? 6 : \ |
68 | (b) >= 800 ? 5 : \ | |
69 | (b) >= 300 ? 4 : \ | |
70 | (b) >= 70 ? 3 : \ | |
37cdcb4d BM |
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 | |
26fbabf3 BM |
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 | |
37cdcb4d BM |
136 | * boundaries and use the following table: |
137 | * | |
26fbabf3 BM |
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 | |
37cdcb4d BM |
143 | * w = 1 if 19 >= b |
144 | */ | |
145 | ||
146 | ||
48fe4d62 BM |
147 | |
148 | /* Compute | |
56a10611 BM |
149 | * \sum scalars[i]*points[i], |
150 | * also including | |
48fe4d62 | 151 | * scalar*generator |
56a10611 | 152 | * in the addition if scalar != NULL |
48fe4d62 | 153 | */ |
38374911 BM |
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) | |
48fe4d62 BM |
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 | { | |
6f8f4431 | 180 | ECerr(EC_F_EC_POINTS_MUL, EC_R_UNDEFINED_GENERATOR); |
48fe4d62 BM |
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); | |
413a4a04 | 209 | num_val += 1u << (wsize[i] - 1); |
48fe4d62 BM |
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; | |
413a4a04 | 230 | for (j = 0; j < (1u << (wsize[i] - 1)); j++) |
48fe4d62 BM |
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; | |
86a921af BM |
264 | if (scalars[i]->neg) |
265 | { | |
266 | if (!EC_POINT_invert(group, val_sub[i][0], ctx)) goto err; | |
267 | } | |
48fe4d62 BM |
268 | } |
269 | else | |
270 | { | |
271 | if (!EC_POINT_copy(val_sub[i][0], generator)) goto err; | |
86a921af BM |
272 | if (scalar->neg) |
273 | { | |
274 | if (!EC_POINT_invert(group, val_sub[i][0], ctx)) goto err; | |
275 | } | |
48fe4d62 BM |
276 | } |
277 | ||
278 | if (wsize[i] > 1) | |
279 | { | |
280 | if (!EC_POINT_dbl(group, tmp, val_sub[i][0], ctx)) goto err; | |
413a4a04 | 281 | for (j = 1; j < (1u << (wsize[i] - 1)); j++) |
48fe4d62 BM |
282 | { |
283 | if (!EC_POINT_add(group, val_sub[i][j], val_sub[i][j - 1], tmp, ctx)) goto err; | |
284 | } | |
285 | } | |
286 | } | |
287 | ||
26fbabf3 | 288 | #if 1 /* optional; EC_window_bits_for_scalar_size assumes we do this step */ |
48fe4d62 BM |
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 | { | |
38374911 | 305 | const BIGNUM *s; |
48fe4d62 BM |
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 | } | |
38374911 BM |
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 | ||
194dd046 | 386 | int EC_GROUP_precompute_mult(EC_GROUP *group, BN_CTX *ctx) |
38374911 BM |
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 | { | |
194dd046 | 396 | ECerr(EC_F_EC_GROUP_PRECOMPUTE_MULT, EC_R_UNDEFINED_GENERATOR); |
38374911 BM |
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 | { | |
194dd046 | 414 | ECerr(EC_F_EC_GROUP_PRECOMPUTE_MULT, EC_R_UNKNOWN_ORDER); |
38374911 BM |
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 | } |