/src/boringssl/crypto/fipsmodule/ec/wnaf.c.inc
Line | Count | Source (jump to first uncovered line) |
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 <assert.h> |
71 | | #include <string.h> |
72 | | |
73 | | #include <openssl/bn.h> |
74 | | #include <openssl/err.h> |
75 | | #include <openssl/mem.h> |
76 | | #include <openssl/thread.h> |
77 | | |
78 | | #include "internal.h" |
79 | | #include "../bn/internal.h" |
80 | | #include "../../internal.h" |
81 | | |
82 | | |
83 | | // This file implements the wNAF-based interleaving multi-exponentiation method |
84 | | // at: |
85 | | // http://link.springer.com/chapter/10.1007%2F3-540-45537-X_13 |
86 | | // http://www.bmoeller.de/pdf/TI-01-08.multiexp.pdf |
87 | | |
88 | | void ec_compute_wNAF(const EC_GROUP *group, int8_t *out, |
89 | 8 | const EC_SCALAR *scalar, size_t bits, int w) { |
90 | | // 'int8_t' can represent integers with absolute values less than 2^7. |
91 | 8 | assert(0 < w && w <= 7); |
92 | 8 | assert(bits != 0); |
93 | 8 | int bit = 1 << w; // 2^w, at most 128 |
94 | 8 | int next_bit = bit << 1; // 2^(w+1), at most 256 |
95 | 8 | int mask = next_bit - 1; // at most 255 |
96 | | |
97 | 8 | int window_val = scalar->words[0] & mask; |
98 | 3.63k | for (size_t j = 0; j < bits + 1; j++) { |
99 | 3.62k | assert(0 <= window_val && window_val <= next_bit); |
100 | 3.62k | int digit = 0; |
101 | 3.62k | if (window_val & 1) { |
102 | 622 | assert(0 < window_val && window_val < next_bit); |
103 | 622 | if (window_val & bit) { |
104 | 302 | digit = window_val - next_bit; |
105 | | // We know -next_bit < digit < 0 and window_val - digit = next_bit. |
106 | | |
107 | | // modified wNAF |
108 | 302 | if (j + w + 1 >= bits) { |
109 | | // special case for generating modified wNAFs: |
110 | | // no new bits will be added into window_val, |
111 | | // so using a positive digit here will decrease |
112 | | // the total length of the representation |
113 | | |
114 | 1 | digit = window_val & (mask >> 1); |
115 | | // We know 0 < digit < bit and window_val - digit = bit. |
116 | 1 | } |
117 | 320 | } else { |
118 | 320 | digit = window_val; |
119 | | // We know 0 < digit < bit and window_val - digit = 0. |
120 | 320 | } |
121 | | |
122 | 622 | window_val -= digit; |
123 | | |
124 | | // Now window_val is 0 or 2^(w+1) in standard wNAF generation. |
125 | | // For modified window NAFs, it may also be 2^w. |
126 | | // |
127 | | // See the comments above for the derivation of each of these bounds. |
128 | 622 | assert(window_val == 0 || window_val == next_bit || window_val == bit); |
129 | 622 | assert(-bit < digit && digit < bit); |
130 | | |
131 | | // window_val was odd, so digit is also odd. |
132 | 622 | assert(digit & 1); |
133 | 622 | } |
134 | | |
135 | 3.62k | out[j] = digit; |
136 | | |
137 | | // Incorporate the next bit. Previously, |window_val| <= |next_bit|, so if |
138 | | // we shift and add at most one copy of |bit|, this will continue to hold |
139 | | // afterwards. |
140 | 3.62k | window_val >>= 1; |
141 | 3.62k | window_val += bit * bn_is_bit_set_words(scalar->words, group->order.N.width, |
142 | 3.62k | j + w + 1); |
143 | 3.62k | assert(window_val <= next_bit); |
144 | 3.62k | } |
145 | | |
146 | | // bits + 1 entries should be sufficient to consume all bits. |
147 | 8 | assert(window_val == 0); |
148 | 8 | } |
149 | | |
150 | | // compute_precomp sets |out[i]| to (2*i+1)*p, for i from 0 to |len|. |
151 | | static void compute_precomp(const EC_GROUP *group, EC_JACOBIAN *out, |
152 | 8 | const EC_JACOBIAN *p, size_t len) { |
153 | 8 | ec_GFp_simple_point_copy(&out[0], p); |
154 | 8 | EC_JACOBIAN two_p; |
155 | 8 | ec_GFp_mont_dbl(group, &two_p, p); |
156 | 64 | for (size_t i = 1; i < len; i++) { |
157 | 56 | ec_GFp_mont_add(group, &out[i], &out[i - 1], &two_p); |
158 | 56 | } |
159 | 8 | } |
160 | | |
161 | | static void lookup_precomp(const EC_GROUP *group, EC_JACOBIAN *out, |
162 | 622 | const EC_JACOBIAN *precomp, int digit) { |
163 | 622 | if (digit < 0) { |
164 | 301 | digit = -digit; |
165 | 301 | ec_GFp_simple_point_copy(out, &precomp[digit >> 1]); |
166 | 301 | ec_GFp_simple_invert(group, out); |
167 | 321 | } else { |
168 | 321 | ec_GFp_simple_point_copy(out, &precomp[digit >> 1]); |
169 | 321 | } |
170 | 622 | } |
171 | | |
172 | | // EC_WNAF_WINDOW_BITS is the window size to use for |ec_GFp_mont_mul_public|. |
173 | 16 | #define EC_WNAF_WINDOW_BITS 4 |
174 | | |
175 | | // EC_WNAF_TABLE_SIZE is the table size to use for |ec_GFp_mont_mul_public|. |
176 | 8 | #define EC_WNAF_TABLE_SIZE (1 << (EC_WNAF_WINDOW_BITS - 1)) |
177 | | |
178 | | // EC_WNAF_STACK is the number of points worth of data to stack-allocate and |
179 | | // avoid a malloc. |
180 | 4 | #define EC_WNAF_STACK 3 |
181 | | |
182 | | int ec_GFp_mont_mul_public_batch(const EC_GROUP *group, EC_JACOBIAN *r, |
183 | | const EC_SCALAR *g_scalar, |
184 | | const EC_JACOBIAN *points, |
185 | 4 | const EC_SCALAR *scalars, size_t num) { |
186 | 4 | size_t bits = EC_GROUP_order_bits(group); |
187 | 4 | size_t wNAF_len = bits + 1; |
188 | | |
189 | 4 | int ret = 0; |
190 | 4 | int8_t wNAF_stack[EC_WNAF_STACK][EC_MAX_BYTES * 8 + 1]; |
191 | 4 | int8_t (*wNAF_alloc)[EC_MAX_BYTES * 8 + 1] = NULL; |
192 | 4 | int8_t (*wNAF)[EC_MAX_BYTES * 8 + 1]; |
193 | 4 | EC_JACOBIAN precomp_stack[EC_WNAF_STACK][EC_WNAF_TABLE_SIZE]; |
194 | 4 | EC_JACOBIAN (*precomp_alloc)[EC_WNAF_TABLE_SIZE] = NULL; |
195 | 4 | EC_JACOBIAN (*precomp)[EC_WNAF_TABLE_SIZE]; |
196 | 4 | if (num <= EC_WNAF_STACK) { |
197 | 4 | wNAF = wNAF_stack; |
198 | 4 | precomp = precomp_stack; |
199 | 4 | } else { |
200 | 0 | wNAF_alloc = OPENSSL_calloc(num, sizeof(wNAF_alloc[0])); |
201 | 0 | precomp_alloc = OPENSSL_calloc(num, sizeof(precomp_alloc[0])); |
202 | 0 | if (wNAF_alloc == NULL || precomp_alloc == NULL) { |
203 | 0 | goto err; |
204 | 0 | } |
205 | 0 | wNAF = wNAF_alloc; |
206 | 0 | precomp = precomp_alloc; |
207 | 0 | } |
208 | | |
209 | 4 | int8_t g_wNAF[EC_MAX_BYTES * 8 + 1]; |
210 | 4 | EC_JACOBIAN g_precomp[EC_WNAF_TABLE_SIZE]; |
211 | 4 | assert(wNAF_len <= OPENSSL_ARRAY_SIZE(g_wNAF)); |
212 | 4 | const EC_JACOBIAN *g = &group->generator.raw; |
213 | 4 | if (g_scalar != NULL) { |
214 | 4 | ec_compute_wNAF(group, g_wNAF, g_scalar, bits, EC_WNAF_WINDOW_BITS); |
215 | 4 | compute_precomp(group, g_precomp, g, EC_WNAF_TABLE_SIZE); |
216 | 4 | } |
217 | | |
218 | 8 | for (size_t i = 0; i < num; i++) { |
219 | 4 | assert(wNAF_len <= OPENSSL_ARRAY_SIZE(wNAF[i])); |
220 | 4 | ec_compute_wNAF(group, wNAF[i], &scalars[i], bits, EC_WNAF_WINDOW_BITS); |
221 | 4 | compute_precomp(group, precomp[i], &points[i], EC_WNAF_TABLE_SIZE); |
222 | 4 | } |
223 | | |
224 | 4 | EC_JACOBIAN tmp; |
225 | 4 | int r_is_at_infinity = 1; |
226 | 1.81k | for (size_t k = wNAF_len - 1; k < wNAF_len; k--) { |
227 | 1.81k | if (!r_is_at_infinity) { |
228 | 1.80k | ec_GFp_mont_dbl(group, r, r); |
229 | 1.80k | } |
230 | | |
231 | 1.81k | if (g_scalar != NULL && g_wNAF[k] != 0) { |
232 | 314 | lookup_precomp(group, &tmp, g_precomp, g_wNAF[k]); |
233 | 314 | if (r_is_at_infinity) { |
234 | 2 | ec_GFp_simple_point_copy(r, &tmp); |
235 | 2 | r_is_at_infinity = 0; |
236 | 312 | } else { |
237 | 312 | ec_GFp_mont_add(group, r, r, &tmp); |
238 | 312 | } |
239 | 314 | } |
240 | | |
241 | 3.62k | for (size_t i = 0; i < num; i++) { |
242 | 1.81k | if (wNAF[i][k] != 0) { |
243 | 308 | lookup_precomp(group, &tmp, precomp[i], wNAF[i][k]); |
244 | 308 | if (r_is_at_infinity) { |
245 | 2 | ec_GFp_simple_point_copy(r, &tmp); |
246 | 2 | r_is_at_infinity = 0; |
247 | 306 | } else { |
248 | 306 | ec_GFp_mont_add(group, r, r, &tmp); |
249 | 306 | } |
250 | 308 | } |
251 | 1.81k | } |
252 | 1.81k | } |
253 | | |
254 | 4 | if (r_is_at_infinity) { |
255 | 0 | ec_GFp_simple_point_set_to_infinity(group, r); |
256 | 0 | } |
257 | | |
258 | 4 | ret = 1; |
259 | | |
260 | 4 | err: |
261 | 4 | OPENSSL_free(wNAF_alloc); |
262 | 4 | OPENSSL_free(precomp_alloc); |
263 | 4 | return ret; |
264 | 4 | } |