/src/boringssl/crypto/fipsmodule/bn/mul.c.inc
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
2 | | * All rights reserved. |
3 | | * |
4 | | * This package is an SSL implementation written |
5 | | * by Eric Young (eay@cryptsoft.com). |
6 | | * The implementation was written so as to conform with Netscapes SSL. |
7 | | * |
8 | | * This library is free for commercial and non-commercial use as long as |
9 | | * the following conditions are aheared to. The following conditions |
10 | | * apply to all code found in this distribution, be it the RC4, RSA, |
11 | | * lhash, DES, etc., code; not just the SSL code. The SSL documentation |
12 | | * included with this distribution is covered by the same copyright terms |
13 | | * except that the holder is Tim Hudson (tjh@cryptsoft.com). |
14 | | * |
15 | | * Copyright remains Eric Young's, and as such any Copyright notices in |
16 | | * the code are not to be removed. |
17 | | * If this package is used in a product, Eric Young should be given attribution |
18 | | * as the author of the parts of the library used. |
19 | | * This can be in the form of a textual message at program startup or |
20 | | * in documentation (online or textual) provided with the package. |
21 | | * |
22 | | * Redistribution and use in source and binary forms, with or without |
23 | | * modification, are permitted provided that the following conditions |
24 | | * are met: |
25 | | * 1. Redistributions of source code must retain the copyright |
26 | | * notice, this list of conditions and the following disclaimer. |
27 | | * 2. Redistributions in binary form must reproduce the above copyright |
28 | | * notice, this list of conditions and the following disclaimer in the |
29 | | * documentation and/or other materials provided with the distribution. |
30 | | * 3. All advertising materials mentioning features or use of this software |
31 | | * must display the following acknowledgement: |
32 | | * "This product includes cryptographic software written by |
33 | | * Eric Young (eay@cryptsoft.com)" |
34 | | * The word 'cryptographic' can be left out if the rouines from the library |
35 | | * being used are not cryptographic related :-). |
36 | | * 4. If you include any Windows specific code (or a derivative thereof) from |
37 | | * the apps directory (application code) you must include an acknowledgement: |
38 | | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" |
39 | | * |
40 | | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
41 | | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
42 | | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
43 | | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE |
44 | | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
45 | | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
46 | | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
47 | | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
48 | | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
49 | | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
50 | | * SUCH DAMAGE. |
51 | | * |
52 | | * The licence and distribution terms for any publically available version or |
53 | | * derivative of this code cannot be changed. i.e. this code cannot simply be |
54 | | * copied and put under another distribution licence |
55 | | * [including the GNU Public Licence.] */ |
56 | | |
57 | | #include <openssl/bn.h> |
58 | | |
59 | | #include <assert.h> |
60 | | #include <stdlib.h> |
61 | | #include <string.h> |
62 | | |
63 | | #include <openssl/err.h> |
64 | | #include <openssl/mem.h> |
65 | | |
66 | | #include "internal.h" |
67 | | #include "../../internal.h" |
68 | | |
69 | | |
70 | 14.5M | #define BN_MUL_RECURSIVE_SIZE_NORMAL 16 |
71 | 3.27M | #define BN_SQR_RECURSIVE_SIZE_NORMAL BN_MUL_RECURSIVE_SIZE_NORMAL |
72 | | |
73 | | |
74 | | static void bn_abs_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, |
75 | 1.07M | size_t num, BN_ULONG *tmp) { |
76 | 1.07M | BN_ULONG borrow = bn_sub_words(tmp, a, b, num); |
77 | 1.07M | bn_sub_words(r, b, a, num); |
78 | 1.07M | bn_select_words(r, 0 - borrow, r /* tmp < 0 */, tmp /* tmp >= 0 */, num); |
79 | 1.07M | } |
80 | | |
81 | | static void bn_mul_normal(BN_ULONG *r, const BN_ULONG *a, size_t na, |
82 | 957k | const BN_ULONG *b, size_t nb) { |
83 | 957k | if (na < nb) { |
84 | 217k | size_t itmp = na; |
85 | 217k | na = nb; |
86 | 217k | nb = itmp; |
87 | 217k | const BN_ULONG *ltmp = a; |
88 | 217k | a = b; |
89 | 217k | b = ltmp; |
90 | 217k | } |
91 | 957k | BN_ULONG *rr = &(r[na]); |
92 | 957k | if (nb == 0) { |
93 | 374k | OPENSSL_memset(r, 0, na * sizeof(BN_ULONG)); |
94 | 374k | return; |
95 | 374k | } |
96 | 583k | rr[0] = bn_mul_words(r, a, na, b[0]); |
97 | | |
98 | 1.15M | for (;;) { |
99 | 1.15M | if (--nb == 0) { |
100 | 308k | return; |
101 | 308k | } |
102 | 844k | rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]); |
103 | 844k | if (--nb == 0) { |
104 | 100k | return; |
105 | 100k | } |
106 | 743k | rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]); |
107 | 743k | if (--nb == 0) { |
108 | 147k | return; |
109 | 147k | } |
110 | 595k | rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]); |
111 | 595k | if (--nb == 0) { |
112 | 25.5k | return; |
113 | 25.5k | } |
114 | 570k | rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]); |
115 | 570k | rr += 4; |
116 | 570k | r += 4; |
117 | 570k | b += 4; |
118 | 570k | } |
119 | 583k | } |
120 | | |
121 | | // bn_sub_part_words sets |r| to |a| - |b|. It returns the borrow bit, which is |
122 | | // one if the operation underflowed and zero otherwise. |cl| is the common |
123 | | // length, that is, the shorter of len(a) or len(b). |dl| is the delta length, |
124 | | // that is, len(a) - len(b). |r|'s length matches the larger of |a| and |b|, or |
125 | | // cl + abs(dl). |
126 | | // |
127 | | // TODO(davidben): Make this take |size_t|. The |cl| + |dl| calling convention |
128 | | // is confusing. |
129 | | static BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, |
130 | 37.4M | const BN_ULONG *b, int cl, int dl) { |
131 | 37.4M | assert(cl >= 0); |
132 | 37.4M | BN_ULONG borrow = bn_sub_words(r, a, b, cl); |
133 | 37.4M | if (dl == 0) { |
134 | 32.3M | return borrow; |
135 | 32.3M | } |
136 | | |
137 | 5.11M | r += cl; |
138 | 5.11M | a += cl; |
139 | 5.11M | b += cl; |
140 | | |
141 | 5.11M | if (dl < 0) { |
142 | | // |a| is shorter than |b|. Complete the subtraction as if the excess words |
143 | | // in |a| were zeros. |
144 | 2.55M | dl = -dl; |
145 | 44.8M | for (int i = 0; i < dl; i++) { |
146 | 42.2M | r[i] = CRYPTO_subc_w(0, b[i], borrow, &borrow); |
147 | 42.2M | } |
148 | 2.55M | } else { |
149 | | // |b| is shorter than |a|. Complete the subtraction as if the excess words |
150 | | // in |b| were zeros. |
151 | 44.8M | for (int i = 0; i < dl; i++) { |
152 | 42.2M | r[i] = CRYPTO_subc_w(a[i], 0, borrow, &borrow); |
153 | 42.2M | } |
154 | 2.55M | } |
155 | | |
156 | 5.11M | return borrow; |
157 | 37.4M | } |
158 | | |
159 | | // bn_abs_sub_part_words computes |r| = |a| - |b|, storing the absolute value |
160 | | // and returning a mask of all ones if the result was negative and all zeros if |
161 | | // the result was positive. |cl| and |dl| follow the |bn_sub_part_words| calling |
162 | | // convention. |
163 | | // |
164 | | // TODO(davidben): Make this take |size_t|. The |cl| + |dl| calling convention |
165 | | // is confusing. |
166 | | static BN_ULONG bn_abs_sub_part_words(BN_ULONG *r, const BN_ULONG *a, |
167 | | const BN_ULONG *b, int cl, int dl, |
168 | 18.7M | BN_ULONG *tmp) { |
169 | 18.7M | BN_ULONG borrow = bn_sub_part_words(tmp, a, b, cl, dl); |
170 | 18.7M | bn_sub_part_words(r, b, a, cl, -dl); |
171 | 18.7M | int r_len = cl + (dl < 0 ? -dl : dl); |
172 | 18.7M | borrow = 0 - borrow; |
173 | 18.7M | bn_select_words(r, borrow, r /* tmp < 0 */, tmp /* tmp >= 0 */, r_len); |
174 | 18.7M | return borrow; |
175 | 18.7M | } |
176 | | |
177 | | int bn_abs_sub_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
178 | 12 | BN_CTX *ctx) { |
179 | 12 | int cl = a->width < b->width ? a->width : b->width; |
180 | 12 | int dl = a->width - b->width; |
181 | 12 | int r_len = a->width < b->width ? b->width : a->width; |
182 | 12 | BN_CTX_start(ctx); |
183 | 12 | BIGNUM *tmp = BN_CTX_get(ctx); |
184 | 12 | int ok = tmp != NULL && |
185 | 12 | bn_wexpand(r, r_len) && |
186 | 12 | bn_wexpand(tmp, r_len); |
187 | 12 | if (ok) { |
188 | 12 | bn_abs_sub_part_words(r->d, a->d, b->d, cl, dl, tmp->d); |
189 | 12 | r->width = r_len; |
190 | 12 | } |
191 | 12 | BN_CTX_end(ctx); |
192 | 12 | return ok; |
193 | 12 | } |
194 | | |
195 | | // Karatsuba recursive multiplication algorithm |
196 | | // (cf. Knuth, The Art of Computer Programming, Vol. 2) |
197 | | |
198 | | // bn_mul_recursive sets |r| to |a| * |b|, using |t| as scratch space. |r| has |
199 | | // length 2*|n2|, |a| has length |n2| + |dna|, |b| has length |n2| + |dnb|, and |
200 | | // |t| has length 4*|n2|. |n2| must be a power of two. Finally, we must have |
201 | | // -|BN_MUL_RECURSIVE_SIZE_NORMAL|/2 <= |dna| <= 0 and |
202 | | // -|BN_MUL_RECURSIVE_SIZE_NORMAL|/2 <= |dnb| <= 0. |
203 | | // |
204 | | // TODO(davidben): Simplify and |size_t| the calling convention around lengths |
205 | | // here. |
206 | | static void bn_mul_recursive(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, |
207 | 8.10M | int n2, int dna, int dnb, BN_ULONG *t) { |
208 | | // |n2| is a power of two. |
209 | 8.10M | assert(n2 != 0 && (n2 & (n2 - 1)) == 0); |
210 | | // Check |dna| and |dnb| are in range. |
211 | 8.10M | assert(-BN_MUL_RECURSIVE_SIZE_NORMAL/2 <= dna && dna <= 0); |
212 | 8.10M | assert(-BN_MUL_RECURSIVE_SIZE_NORMAL/2 <= dnb && dnb <= 0); |
213 | | |
214 | | // Only call bn_mul_comba 8 if n2 == 8 and the |
215 | | // two arrays are complete [steve] |
216 | 8.10M | if (n2 == 8 && dna == 0 && dnb == 0) { |
217 | 5.66k | bn_mul_comba8(r, a, b); |
218 | 5.66k | return; |
219 | 5.66k | } |
220 | | |
221 | | // Else do normal multiply |
222 | 8.09M | if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) { |
223 | 2.83k | bn_mul_normal(r, a, n2 + dna, b, n2 + dnb); |
224 | 2.83k | if (dna + dnb < 0) { |
225 | 2.83k | OPENSSL_memset(&r[2 * n2 + dna + dnb], 0, |
226 | 2.83k | sizeof(BN_ULONG) * -(dna + dnb)); |
227 | 2.83k | } |
228 | 2.83k | return; |
229 | 2.83k | } |
230 | | |
231 | | // Split |a| and |b| into a0,a1 and b0,b1, where a0 and b0 have size |n|. |
232 | | // Split |t| into t0,t1,t2,t3, each of size |n|, with the remaining 4*|n| used |
233 | | // for recursive calls. |
234 | | // Split |r| into r0,r1,r2,r3. We must contribute a0*b0 to r0,r1, a0*a1+b0*b1 |
235 | | // to r1,r2, and a1*b1 to r2,r3. The middle term we will compute as: |
236 | | // |
237 | | // a0*a1 + b0*b1 = (a0 - a1)*(b1 - b0) + a1*b1 + a0*b0 |
238 | | // |
239 | | // Note that we know |n| >= |BN_MUL_RECURSIVE_SIZE_NORMAL|/2 above, so |
240 | | // |tna| and |tnb| are non-negative. |
241 | 8.09M | int n = n2 / 2, tna = n + dna, tnb = n + dnb; |
242 | | |
243 | | // t0 = a0 - a1 and t1 = b1 - b0. The result will be multiplied, so we XOR |
244 | | // their sign masks, giving the sign of (a0 - a1)*(b1 - b0). t0 and t1 |
245 | | // themselves store the absolute value. |
246 | 8.09M | BN_ULONG neg = bn_abs_sub_part_words(t, a, &a[n], tna, n - tna, &t[n2]); |
247 | 8.09M | neg ^= bn_abs_sub_part_words(&t[n], &b[n], b, tnb, tnb - n, &t[n2]); |
248 | | |
249 | | // Compute: |
250 | | // t2,t3 = t0 * t1 = |(a0 - a1)*(b1 - b0)| |
251 | | // r0,r1 = a0 * b0 |
252 | | // r2,r3 = a1 * b1 |
253 | 8.09M | if (n == 4 && dna == 0 && dnb == 0) { |
254 | 0 | bn_mul_comba4(&t[n2], t, &t[n]); |
255 | |
|
256 | 0 | bn_mul_comba4(r, a, b); |
257 | 0 | bn_mul_comba4(&r[n2], &a[n], &b[n]); |
258 | 8.09M | } else if (n == 8 && dna == 0 && dnb == 0) { |
259 | 6.30M | bn_mul_comba8(&t[n2], t, &t[n]); |
260 | | |
261 | 6.30M | bn_mul_comba8(r, a, b); |
262 | 6.30M | bn_mul_comba8(&r[n2], &a[n], &b[n]); |
263 | 6.30M | } else { |
264 | 1.78M | BN_ULONG *p = &t[n2 * 2]; |
265 | 1.78M | bn_mul_recursive(&t[n2], t, &t[n], n, 0, 0, p); |
266 | 1.78M | bn_mul_recursive(r, a, b, n, 0, 0, p); |
267 | 1.78M | bn_mul_recursive(&r[n2], &a[n], &b[n], n, dna, dnb, p); |
268 | 1.78M | } |
269 | | |
270 | | // t0,t1,c = r0,r1 + r2,r3 = a0*b0 + a1*b1 |
271 | 8.09M | BN_ULONG c = bn_add_words(t, r, &r[n2], n2); |
272 | | |
273 | | // t2,t3,c = t0,t1,c + neg*t2,t3 = (a0 - a1)*(b1 - b0) + a1*b1 + a0*b0. |
274 | | // The second term is stored as the absolute value, so we do this with a |
275 | | // constant-time select. |
276 | 8.09M | BN_ULONG c_neg = c - bn_sub_words(&t[n2 * 2], t, &t[n2], n2); |
277 | 8.09M | BN_ULONG c_pos = c + bn_add_words(&t[n2], t, &t[n2], n2); |
278 | 8.09M | bn_select_words(&t[n2], neg, &t[n2 * 2], &t[n2], n2); |
279 | 8.09M | static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), |
280 | 8.09M | "crypto_word_t is too small"); |
281 | 8.09M | c = constant_time_select_w(neg, c_neg, c_pos); |
282 | | |
283 | | // We now have our three components. Add them together. |
284 | | // r1,r2,c = r1,r2 + t2,t3,c |
285 | 8.09M | c += bn_add_words(&r[n], &r[n], &t[n2], n2); |
286 | | |
287 | | // Propagate the carry bit to the end. |
288 | 89.1M | for (int i = n + n2; i < n2 + n2; i++) { |
289 | 81.0M | BN_ULONG old = r[i]; |
290 | 81.0M | r[i] = old + c; |
291 | 81.0M | c = r[i] < old; |
292 | 81.0M | } |
293 | | |
294 | | // The product should fit without carries. |
295 | 8.09M | declassify_assert(c == 0); |
296 | 8.09M | } |
297 | | |
298 | | // bn_mul_part_recursive sets |r| to |a| * |b|, using |t| as scratch space. |r| |
299 | | // has length 4*|n|, |a| has length |n| + |tna|, |b| has length |n| + |tnb|, and |
300 | | // |t| has length 8*|n|. |n| must be a power of two. Additionally, we must have |
301 | | // 0 <= tna < n and 0 <= tnb < n, and |tna| and |tnb| must differ by at most |
302 | | // one. |
303 | | // |
304 | | // TODO(davidben): Make this take |size_t| and perhaps the actual lengths of |a| |
305 | | // and |b|. |
306 | | static void bn_mul_part_recursive(BN_ULONG *r, const BN_ULONG *a, |
307 | | const BN_ULONG *b, int n, int tna, int tnb, |
308 | 1.27M | BN_ULONG *t) { |
309 | | // |n| is a power of two. |
310 | 1.27M | assert(n != 0 && (n & (n - 1)) == 0); |
311 | | // Check |tna| and |tnb| are in range. |
312 | 1.27M | assert(0 <= tna && tna < n); |
313 | 1.27M | assert(0 <= tnb && tnb < n); |
314 | 1.27M | assert(-1 <= tna - tnb && tna - tnb <= 1); |
315 | | |
316 | 1.27M | int n2 = n * 2; |
317 | 1.27M | if (n < 8) { |
318 | 0 | bn_mul_normal(r, a, n + tna, b, n + tnb); |
319 | 0 | OPENSSL_memset(r + n2 + tna + tnb, 0, n2 - tna - tnb); |
320 | 0 | return; |
321 | 0 | } |
322 | | |
323 | | // Split |a| and |b| into a0,a1 and b0,b1, where a0 and b0 have size |n|. |a1| |
324 | | // and |b1| have size |tna| and |tnb|, respectively. |
325 | | // Split |t| into t0,t1,t2,t3, each of size |n|, with the remaining 4*|n| used |
326 | | // for recursive calls. |
327 | | // Split |r| into r0,r1,r2,r3. We must contribute a0*b0 to r0,r1, a0*a1+b0*b1 |
328 | | // to r1,r2, and a1*b1 to r2,r3. The middle term we will compute as: |
329 | | // |
330 | | // a0*a1 + b0*b1 = (a0 - a1)*(b1 - b0) + a1*b1 + a0*b0 |
331 | | |
332 | | // t0 = a0 - a1 and t1 = b1 - b0. The result will be multiplied, so we XOR |
333 | | // their sign masks, giving the sign of (a0 - a1)*(b1 - b0). t0 and t1 |
334 | | // themselves store the absolute value. |
335 | 1.27M | BN_ULONG neg = bn_abs_sub_part_words(t, a, &a[n], tna, n - tna, &t[n2]); |
336 | 1.27M | neg ^= bn_abs_sub_part_words(&t[n], &b[n], b, tnb, tnb - n, &t[n2]); |
337 | | |
338 | | // Compute: |
339 | | // t2,t3 = t0 * t1 = |(a0 - a1)*(b1 - b0)| |
340 | | // r0,r1 = a0 * b0 |
341 | | // r2,r3 = a1 * b1 |
342 | 1.27M | if (n == 8) { |
343 | 0 | bn_mul_comba8(&t[n2], t, &t[n]); |
344 | 0 | bn_mul_comba8(r, a, b); |
345 | |
|
346 | 0 | bn_mul_normal(&r[n2], &a[n], tna, &b[n], tnb); |
347 | | // |bn_mul_normal| only writes |tna| + |tna| words. Zero the rest. |
348 | 0 | OPENSSL_memset(&r[n2 + tna + tnb], 0, sizeof(BN_ULONG) * (n2 - tna - tnb)); |
349 | 1.27M | } else { |
350 | 1.27M | BN_ULONG *p = &t[n2 * 2]; |
351 | 1.27M | bn_mul_recursive(&t[n2], t, &t[n], n, 0, 0, p); |
352 | 1.27M | bn_mul_recursive(r, a, b, n, 0, 0, p); |
353 | | |
354 | 1.27M | OPENSSL_memset(&r[n2], 0, sizeof(BN_ULONG) * n2); |
355 | 1.27M | if (tna < BN_MUL_RECURSIVE_SIZE_NORMAL && |
356 | 1.27M | tnb < BN_MUL_RECURSIVE_SIZE_NORMAL) { |
357 | 651k | bn_mul_normal(&r[n2], &a[n], tna, &b[n], tnb); |
358 | 651k | } else { |
359 | 625k | int i = n; |
360 | 628k | for (;;) { |
361 | 628k | i /= 2; |
362 | 628k | if (i < tna || i < tnb) { |
363 | | // E.g., n == 16, i == 8 and tna == 11. |tna| and |tnb| are within one |
364 | | // of each other, so if |tna| is larger and tna > i, then we know |
365 | | // tnb >= i, and this call is valid. |
366 | 581k | bn_mul_part_recursive(&r[n2], &a[n], &b[n], i, tna - i, tnb - i, p); |
367 | 581k | break; |
368 | 581k | } |
369 | 46.9k | if (i == tna || i == tnb) { |
370 | | // If there is only a bottom half to the number, just do it. We know |
371 | | // the larger of |tna - i| and |tnb - i| is zero. The other is zero or |
372 | | // -1 by because of |tna| and |tnb| differ by at most one. |
373 | 43.4k | bn_mul_recursive(&r[n2], &a[n], &b[n], i, tna - i, tnb - i, p); |
374 | 43.4k | break; |
375 | 43.4k | } |
376 | | |
377 | | // This loop will eventually terminate when |i| falls below |
378 | | // |BN_MUL_RECURSIVE_SIZE_NORMAL| because we know one of |tna| and |tnb| |
379 | | // exceeds that. |
380 | 46.9k | } |
381 | 625k | } |
382 | 1.27M | } |
383 | | |
384 | | // t0,t1,c = r0,r1 + r2,r3 = a0*b0 + a1*b1 |
385 | 1.27M | BN_ULONG c = bn_add_words(t, r, &r[n2], n2); |
386 | | |
387 | | // t2,t3,c = t0,t1,c + neg*t2,t3 = (a0 - a1)*(b1 - b0) + a1*b1 + a0*b0. |
388 | | // The second term is stored as the absolute value, so we do this with a |
389 | | // constant-time select. |
390 | 1.27M | BN_ULONG c_neg = c - bn_sub_words(&t[n2 * 2], t, &t[n2], n2); |
391 | 1.27M | BN_ULONG c_pos = c + bn_add_words(&t[n2], t, &t[n2], n2); |
392 | 1.27M | bn_select_words(&t[n2], neg, &t[n2 * 2], &t[n2], n2); |
393 | 1.27M | static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), |
394 | 1.27M | "crypto_word_t is too small"); |
395 | 1.27M | c = constant_time_select_w(neg, c_neg, c_pos); |
396 | | |
397 | | // We now have our three components. Add them together. |
398 | | // r1,r2,c = r1,r2 + t2,t3,c |
399 | 1.27M | c += bn_add_words(&r[n], &r[n], &t[n2], n2); |
400 | | |
401 | | // Propagate the carry bit to the end. |
402 | 34.8M | for (int i = n + n2; i < n2 + n2; i++) { |
403 | 33.5M | BN_ULONG old = r[i]; |
404 | 33.5M | r[i] = old + c; |
405 | 33.5M | c = r[i] < old; |
406 | 33.5M | } |
407 | | |
408 | | // The product should fit without carries. |
409 | 1.27M | declassify_assert(c == 0); |
410 | 1.27M | } |
411 | | |
412 | | // bn_mul_impl implements |BN_mul| and |bn_mul_consttime|. Note this function |
413 | | // breaks |BIGNUM| invariants and may return a negative zero. This is handled by |
414 | | // the callers. |
415 | | static int bn_mul_impl(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
416 | 1.05M | BN_CTX *ctx) { |
417 | 1.05M | int al = a->width; |
418 | 1.05M | int bl = b->width; |
419 | 1.05M | if (al == 0 || bl == 0) { |
420 | 2 | BN_zero(r); |
421 | 2 | return 1; |
422 | 2 | } |
423 | | |
424 | 1.05M | int ret = 0; |
425 | 1.05M | BIGNUM *rr; |
426 | 1.05M | BN_CTX_start(ctx); |
427 | 1.05M | if (r == a || r == b) { |
428 | 3 | rr = BN_CTX_get(ctx); |
429 | 3 | if (rr == NULL) { |
430 | 0 | goto err; |
431 | 0 | } |
432 | 1.05M | } else { |
433 | 1.05M | rr = r; |
434 | 1.05M | } |
435 | 1.05M | rr->neg = a->neg ^ b->neg; |
436 | | |
437 | 1.05M | int i = al - bl; |
438 | 1.05M | if (i == 0) { |
439 | 622k | if (al == 8) { |
440 | 2.79k | if (!bn_wexpand(rr, 16)) { |
441 | 0 | goto err; |
442 | 0 | } |
443 | 2.79k | rr->width = 16; |
444 | 2.79k | bn_mul_comba8(rr->d, a->d, b->d); |
445 | 2.79k | goto end; |
446 | 2.79k | } |
447 | 622k | } |
448 | | |
449 | 1.05M | int top = al + bl; |
450 | 1.05M | static const int kMulNormalSize = 16; |
451 | 1.05M | if (al >= kMulNormalSize && bl >= kMulNormalSize) { |
452 | 880k | if (-1 <= i && i <= 1) { |
453 | | // Find the largest power of two less than or equal to the larger length. |
454 | 848k | int j; |
455 | 848k | if (i >= 0) { |
456 | 650k | j = BN_num_bits_word((BN_ULONG)al); |
457 | 650k | } else { |
458 | 197k | j = BN_num_bits_word((BN_ULONG)bl); |
459 | 197k | } |
460 | 848k | j = 1 << (j - 1); |
461 | 848k | assert(j <= al || j <= bl); |
462 | 848k | BIGNUM *t = BN_CTX_get(ctx); |
463 | 848k | if (t == NULL) { |
464 | 0 | goto err; |
465 | 0 | } |
466 | 848k | if (al > j || bl > j) { |
467 | | // We know |al| and |bl| are at most one from each other, so if al > j, |
468 | | // bl >= j, and vice versa. Thus we can use |bn_mul_part_recursive|. |
469 | | // |
470 | | // TODO(davidben): This codepath is almost unused in standard |
471 | | // algorithms. Is this optimization necessary? See notes in |
472 | | // https://boringssl-review.googlesource.com/q/I0bd604e2cd6a75c266f64476c23a730ca1721ea6 |
473 | 694k | assert(al >= j && bl >= j); |
474 | 694k | if (!bn_wexpand(t, j * 8) || |
475 | 694k | !bn_wexpand(rr, j * 4)) { |
476 | 0 | goto err; |
477 | 0 | } |
478 | 694k | bn_mul_part_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); |
479 | 694k | } else { |
480 | | // al <= j && bl <= j. Additionally, we know j <= al or j <= bl, so one |
481 | | // of al - j or bl - j is zero. The other, by the bound on |i| above, is |
482 | | // zero or -1. Thus, we can use |bn_mul_recursive|. |
483 | 153k | if (!bn_wexpand(t, j * 4) || |
484 | 153k | !bn_wexpand(rr, j * 2)) { |
485 | 0 | goto err; |
486 | 0 | } |
487 | 153k | bn_mul_recursive(rr->d, a->d, b->d, j, al - j, bl - j, t->d); |
488 | 153k | } |
489 | 848k | rr->width = top; |
490 | 848k | goto end; |
491 | 848k | } |
492 | 880k | } |
493 | | |
494 | 209k | if (!bn_wexpand(rr, top)) { |
495 | 0 | goto err; |
496 | 0 | } |
497 | 209k | rr->width = top; |
498 | 209k | bn_mul_normal(rr->d, a->d, al, b->d, bl); |
499 | | |
500 | 1.05M | end: |
501 | 1.05M | if (r != rr && !BN_copy(r, rr)) { |
502 | 0 | goto err; |
503 | 0 | } |
504 | 1.05M | ret = 1; |
505 | | |
506 | 1.05M | err: |
507 | 1.05M | BN_CTX_end(ctx); |
508 | 1.05M | return ret; |
509 | 1.05M | } |
510 | | |
511 | 734k | int BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { |
512 | 734k | if (!bn_mul_impl(r, a, b, ctx)) { |
513 | 0 | return 0; |
514 | 0 | } |
515 | | |
516 | | // This additionally fixes any negative zeros created by |bn_mul_impl|. |
517 | 734k | bn_set_minimal_width(r); |
518 | 734k | return 1; |
519 | 734k | } |
520 | | |
521 | 325k | int bn_mul_consttime(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) { |
522 | | // Prevent negative zeros. |
523 | 325k | if (a->neg || b->neg) { |
524 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
525 | 0 | return 0; |
526 | 0 | } |
527 | | |
528 | 325k | return bn_mul_impl(r, a, b, ctx); |
529 | 325k | } |
530 | | |
531 | | void bn_mul_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a, size_t num_a, |
532 | 94.0k | const BN_ULONG *b, size_t num_b) { |
533 | 94.0k | if (num_r != num_a + num_b) { |
534 | 0 | abort(); |
535 | 0 | } |
536 | | // TODO(davidben): Should this call |bn_mul_comba4| too? |BN_mul| does not |
537 | | // hit that code. |
538 | 94.0k | if (num_a == 8 && num_b == 8) { |
539 | 0 | bn_mul_comba8(r, a, b); |
540 | 94.0k | } else { |
541 | 94.0k | bn_mul_normal(r, a, num_a, b, num_b); |
542 | 94.0k | } |
543 | 94.0k | } |
544 | | |
545 | | // tmp must have 2*n words |
546 | | static void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, size_t n, |
547 | 1.31M | BN_ULONG *tmp) { |
548 | 1.31M | if (n == 0) { |
549 | 0 | return; |
550 | 0 | } |
551 | | |
552 | 1.31M | size_t max = n * 2; |
553 | 1.31M | const BN_ULONG *ap = a; |
554 | 1.31M | BN_ULONG *rp = r; |
555 | 1.31M | rp[0] = rp[max - 1] = 0; |
556 | 1.31M | rp++; |
557 | | |
558 | | // Compute the contribution of a[i] * a[j] for all i < j. |
559 | 1.31M | if (n > 1) { |
560 | 1.28M | ap++; |
561 | 1.28M | rp[n - 1] = bn_mul_words(rp, ap, n - 1, ap[-1]); |
562 | 1.28M | rp += 2; |
563 | 1.28M | } |
564 | 1.31M | if (n > 2) { |
565 | 26.2M | for (size_t i = n - 2; i > 0; i--) { |
566 | 25.0M | ap++; |
567 | 25.0M | rp[i] = bn_mul_add_words(rp, ap, i, ap[-1]); |
568 | 25.0M | rp += 2; |
569 | 25.0M | } |
570 | 1.22M | } |
571 | | |
572 | | // The final result fits in |max| words, so none of the following operations |
573 | | // will overflow. |
574 | | |
575 | | // Double |r|, giving the contribution of a[i] * a[j] for all i != j. |
576 | 1.31M | bn_add_words(r, r, r, max); |
577 | | |
578 | | // Add in the contribution of a[i] * a[i] for all i. |
579 | 1.31M | bn_sqr_words(tmp, a, n); |
580 | 1.31M | bn_add_words(r, r, tmp, max); |
581 | 1.31M | } |
582 | | |
583 | | // bn_sqr_recursive sets |r| to |a|^2, using |t| as scratch space. |r| has |
584 | | // length 2*|n2|, |a| has length |n2|, and |t| has length 4*|n2|. |n2| must be |
585 | | // a power of two. |
586 | | static void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, size_t n2, |
587 | 4.22M | BN_ULONG *t) { |
588 | | // |n2| is a power of two. |
589 | 4.22M | assert(n2 != 0 && (n2 & (n2 - 1)) == 0); |
590 | | |
591 | 4.22M | if (n2 == 4) { |
592 | 0 | bn_sqr_comba4(r, a); |
593 | 0 | return; |
594 | 0 | } |
595 | 4.22M | if (n2 == 8) { |
596 | 3.15M | bn_sqr_comba8(r, a); |
597 | 3.15M | return; |
598 | 3.15M | } |
599 | 1.07M | if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) { |
600 | 0 | bn_sqr_normal(r, a, n2, t); |
601 | 0 | return; |
602 | 0 | } |
603 | | |
604 | | // Split |a| into a0,a1, each of size |n|. |
605 | | // Split |t| into t0,t1,t2,t3, each of size |n|, with the remaining 4*|n| used |
606 | | // for recursive calls. |
607 | | // Split |r| into r0,r1,r2,r3. We must contribute a0^2 to r0,r1, 2*a0*a1 to |
608 | | // r1,r2, and a1^2 to r2,r3. |
609 | 1.07M | size_t n = n2 / 2; |
610 | 1.07M | BN_ULONG *t_recursive = &t[n2 * 2]; |
611 | | |
612 | | // t0 = |a0 - a1|. |
613 | 1.07M | bn_abs_sub_words(t, a, &a[n], n, &t[n]); |
614 | | // t2,t3 = t0^2 = |a0 - a1|^2 = a0^2 - 2*a0*a1 + a1^2 |
615 | 1.07M | bn_sqr_recursive(&t[n2], t, n, t_recursive); |
616 | | |
617 | | // r0,r1 = a0^2 |
618 | 1.07M | bn_sqr_recursive(r, a, n, t_recursive); |
619 | | |
620 | | // r2,r3 = a1^2 |
621 | 1.07M | bn_sqr_recursive(&r[n2], &a[n], n, t_recursive); |
622 | | |
623 | | // t0,t1,c = r0,r1 + r2,r3 = a0^2 + a1^2 |
624 | 1.07M | BN_ULONG c = bn_add_words(t, r, &r[n2], n2); |
625 | | // t2,t3,c = t0,t1,c - t2,t3 = 2*a0*a1 |
626 | 1.07M | c -= bn_sub_words(&t[n2], t, &t[n2], n2); |
627 | | |
628 | | // We now have our three components. Add them together. |
629 | | // r1,r2,c = r1,r2 + t2,t3,c |
630 | 1.07M | c += bn_add_words(&r[n], &r[n], &t[n2], n2); |
631 | | |
632 | | // Propagate the carry bit to the end. |
633 | 9.83M | for (size_t i = n + n2; i < n2 + n2; i++) { |
634 | 8.76M | BN_ULONG old = r[i]; |
635 | 8.76M | r[i] = old + c; |
636 | 8.76M | c = r[i] < old; |
637 | 8.76M | } |
638 | | |
639 | | // The square should fit without carries. |
640 | 1.07M | assert(c == 0); |
641 | 1.07M | } |
642 | | |
643 | 201k | int BN_mul_word(BIGNUM *bn, BN_ULONG w) { |
644 | 201k | if (!bn->width) { |
645 | 13.2k | return 1; |
646 | 13.2k | } |
647 | | |
648 | 187k | if (w == 0) { |
649 | 0 | BN_zero(bn); |
650 | 0 | return 1; |
651 | 0 | } |
652 | | |
653 | 187k | BN_ULONG ll = bn_mul_words(bn->d, bn->d, bn->width, w); |
654 | 187k | if (ll) { |
655 | 183k | if (!bn_wexpand(bn, bn->width + 1)) { |
656 | 0 | return 0; |
657 | 0 | } |
658 | 183k | bn->d[bn->width++] = ll; |
659 | 183k | } |
660 | | |
661 | 187k | return 1; |
662 | 187k | } |
663 | | |
664 | 2.23M | int bn_sqr_consttime(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { |
665 | 2.23M | int al = a->width; |
666 | 2.23M | if (al <= 0) { |
667 | 1 | r->width = 0; |
668 | 1 | r->neg = 0; |
669 | 1 | return 1; |
670 | 1 | } |
671 | | |
672 | 2.23M | int ret = 0; |
673 | 2.23M | BN_CTX_start(ctx); |
674 | 2.23M | BIGNUM *rr = (a != r) ? r : BN_CTX_get(ctx); |
675 | 2.23M | BIGNUM *tmp = BN_CTX_get(ctx); |
676 | 2.23M | if (!rr || !tmp) { |
677 | 0 | goto err; |
678 | 0 | } |
679 | | |
680 | 2.23M | int max = 2 * al; // Non-zero (from above) |
681 | 2.23M | if (!bn_wexpand(rr, max)) { |
682 | 0 | goto err; |
683 | 0 | } |
684 | | |
685 | 2.23M | if (al == 4) { |
686 | 13.9k | bn_sqr_comba4(rr->d, a->d); |
687 | 2.21M | } else if (al == 8) { |
688 | 10.9k | bn_sqr_comba8(rr->d, a->d); |
689 | 2.20M | } else { |
690 | 2.20M | if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) { |
691 | 784k | BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL * 2]; |
692 | 784k | bn_sqr_normal(rr->d, a->d, al, t); |
693 | 1.42M | } else { |
694 | | // If |al| is a power of two, we can use |bn_sqr_recursive|. |
695 | 1.42M | if (al != 0 && (al & (al - 1)) == 0) { |
696 | 1.00M | if (!bn_wexpand(tmp, al * 4)) { |
697 | 0 | goto err; |
698 | 0 | } |
699 | 1.00M | bn_sqr_recursive(rr->d, a->d, al, tmp->d); |
700 | 1.00M | } else { |
701 | 414k | if (!bn_wexpand(tmp, max)) { |
702 | 0 | goto err; |
703 | 0 | } |
704 | 414k | bn_sqr_normal(rr->d, a->d, al, tmp->d); |
705 | 414k | } |
706 | 1.42M | } |
707 | 2.20M | } |
708 | | |
709 | 2.23M | rr->neg = 0; |
710 | 2.23M | rr->width = max; |
711 | | |
712 | 2.23M | if (rr != r && !BN_copy(r, rr)) { |
713 | 0 | goto err; |
714 | 0 | } |
715 | 2.23M | ret = 1; |
716 | | |
717 | 2.23M | err: |
718 | 2.23M | BN_CTX_end(ctx); |
719 | 2.23M | return ret; |
720 | 2.23M | } |
721 | | |
722 | 302k | int BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx) { |
723 | 302k | if (!bn_sqr_consttime(r, a, ctx)) { |
724 | 0 | return 0; |
725 | 0 | } |
726 | | |
727 | 302k | bn_set_minimal_width(r); |
728 | 302k | return 1; |
729 | 302k | } |
730 | | |
731 | 115k | void bn_sqr_small(BN_ULONG *r, size_t num_r, const BN_ULONG *a, size_t num_a) { |
732 | 115k | if (num_r != 2 * num_a || num_a > BN_SMALL_MAX_WORDS) { |
733 | 0 | abort(); |
734 | 0 | } |
735 | 115k | if (num_a == 4) { |
736 | 198 | bn_sqr_comba4(r, a); |
737 | 115k | } else if (num_a == 8) { |
738 | 0 | bn_sqr_comba8(r, a); |
739 | 115k | } else { |
740 | 115k | BN_ULONG tmp[2 * BN_SMALL_MAX_WORDS]; |
741 | 115k | bn_sqr_normal(r, a, num_a, tmp); |
742 | 115k | OPENSSL_cleanse(tmp, 2 * num_a * sizeof(BN_ULONG)); |
743 | 115k | } |
744 | 115k | } |