/src/boringssl/crypto/fipsmodule/bn/shift.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 <string.h> |
61 | | |
62 | | #include <openssl/err.h> |
63 | | |
64 | | #include "internal.h" |
65 | | |
66 | | |
67 | 137k | int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) { |
68 | 137k | int i, nw, lb, rb; |
69 | 137k | BN_ULONG *t, *f; |
70 | 137k | BN_ULONG l; |
71 | | |
72 | 137k | if (n < 0) { |
73 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
74 | 0 | return 0; |
75 | 0 | } |
76 | | |
77 | 137k | r->neg = a->neg; |
78 | 137k | nw = n / BN_BITS2; |
79 | 137k | if (!bn_wexpand(r, a->width + nw + 1)) { |
80 | 0 | return 0; |
81 | 0 | } |
82 | 137k | lb = n % BN_BITS2; |
83 | 137k | rb = BN_BITS2 - lb; |
84 | 137k | f = a->d; |
85 | 137k | t = r->d; |
86 | 137k | t[a->width + nw] = 0; |
87 | 137k | if (lb == 0) { |
88 | 526k | for (i = a->width - 1; i >= 0; i--) { |
89 | 506k | t[nw + i] = f[i]; |
90 | 506k | } |
91 | 116k | } else { |
92 | 4.98M | for (i = a->width - 1; i >= 0; i--) { |
93 | 4.86M | l = f[i]; |
94 | 4.86M | t[nw + i + 1] |= l >> rb; |
95 | 4.86M | t[nw + i] = l << lb; |
96 | 4.86M | } |
97 | 116k | } |
98 | 137k | OPENSSL_memset(t, 0, nw * sizeof(t[0])); |
99 | 137k | r->width = a->width + nw + 1; |
100 | 137k | bn_set_minimal_width(r); |
101 | | |
102 | 137k | return 1; |
103 | 137k | } |
104 | | |
105 | 2.28k | int BN_lshift1(BIGNUM *r, const BIGNUM *a) { |
106 | 2.28k | BN_ULONG *ap, *rp, t, c; |
107 | 2.28k | int i; |
108 | | |
109 | 2.28k | if (r != a) { |
110 | 2.28k | r->neg = a->neg; |
111 | 2.28k | if (!bn_wexpand(r, a->width + 1)) { |
112 | 0 | return 0; |
113 | 0 | } |
114 | 2.28k | r->width = a->width; |
115 | 2.28k | } else { |
116 | 0 | if (!bn_wexpand(r, a->width + 1)) { |
117 | 0 | return 0; |
118 | 0 | } |
119 | 0 | } |
120 | 2.28k | ap = a->d; |
121 | 2.28k | rp = r->d; |
122 | 2.28k | c = 0; |
123 | 9.61k | for (i = 0; i < a->width; i++) { |
124 | 7.33k | t = *(ap++); |
125 | 7.33k | *(rp++) = (t << 1) | c; |
126 | 7.33k | c = t >> (BN_BITS2 - 1); |
127 | 7.33k | } |
128 | 2.28k | if (c) { |
129 | 4 | *rp = 1; |
130 | 4 | r->width++; |
131 | 4 | } |
132 | | |
133 | 2.28k | return 1; |
134 | 2.28k | } |
135 | | |
136 | | void bn_rshift_words(BN_ULONG *r, const BN_ULONG *a, unsigned shift, |
137 | 848k | size_t num) { |
138 | 848k | unsigned shift_bits = shift % BN_BITS2; |
139 | 848k | size_t shift_words = shift / BN_BITS2; |
140 | 848k | if (shift_words >= num) { |
141 | 510 | OPENSSL_memset(r, 0, num * sizeof(BN_ULONG)); |
142 | 510 | return; |
143 | 510 | } |
144 | 847k | if (shift_bits == 0) { |
145 | 24.5k | OPENSSL_memmove(r, a + shift_words, (num - shift_words) * sizeof(BN_ULONG)); |
146 | 822k | } else { |
147 | 38.1M | for (size_t i = shift_words; i < num - 1; i++) { |
148 | 37.3M | r[i - shift_words] = |
149 | 37.3M | (a[i] >> shift_bits) | (a[i + 1] << (BN_BITS2 - shift_bits)); |
150 | 37.3M | } |
151 | 822k | r[num - 1 - shift_words] = a[num - 1] >> shift_bits; |
152 | 822k | } |
153 | 847k | OPENSSL_memset(r + num - shift_words, 0, shift_words * sizeof(BN_ULONG)); |
154 | 847k | } |
155 | | |
156 | 842k | int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) { |
157 | 842k | if (n < 0) { |
158 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); |
159 | 0 | return 0; |
160 | 0 | } |
161 | | |
162 | 842k | if (!bn_wexpand(r, a->width)) { |
163 | 0 | return 0; |
164 | 0 | } |
165 | 842k | bn_rshift_words(r->d, a->d, n, a->width); |
166 | 842k | r->neg = a->neg; |
167 | 842k | r->width = a->width; |
168 | 842k | bn_set_minimal_width(r); |
169 | 842k | return 1; |
170 | 842k | } |
171 | | |
172 | | int bn_rshift_secret_shift(BIGNUM *r, const BIGNUM *a, unsigned n, |
173 | 574 | BN_CTX *ctx) { |
174 | 574 | int ret = 0; |
175 | 574 | BN_CTX_start(ctx); |
176 | 574 | BIGNUM *tmp = BN_CTX_get(ctx); |
177 | 574 | if (tmp == NULL || |
178 | 574 | !BN_copy(r, a) || |
179 | 574 | !bn_wexpand(tmp, r->width)) { |
180 | 0 | goto err; |
181 | 0 | } |
182 | | |
183 | | // Shift conditionally by powers of two. |
184 | 574 | unsigned max_bits = BN_BITS2 * r->width; |
185 | 6.38k | for (unsigned i = 0; (max_bits >> i) != 0; i++) { |
186 | 5.81k | BN_ULONG mask = (n >> i) & 1; |
187 | 5.81k | mask = 0 - mask; |
188 | 5.81k | bn_rshift_words(tmp->d, r->d, 1u << i, r->width); |
189 | 5.81k | bn_select_words(r->d, mask, tmp->d /* apply shift */, |
190 | 5.81k | r->d /* ignore shift */, r->width); |
191 | 5.81k | } |
192 | | |
193 | 574 | ret = 1; |
194 | | |
195 | 574 | err: |
196 | 574 | BN_CTX_end(ctx); |
197 | 574 | return ret; |
198 | 574 | } |
199 | | |
200 | 2.53M | void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num) { |
201 | 2.53M | if (num == 0) { |
202 | 0 | return; |
203 | 0 | } |
204 | 162M | for (size_t i = 0; i < num - 1; i++) { |
205 | 160M | r[i] = (a[i] >> 1) | (a[i + 1] << (BN_BITS2 - 1)); |
206 | 160M | } |
207 | 2.53M | r[num - 1] = a[num - 1] >> 1; |
208 | 2.53M | } |
209 | | |
210 | 107k | int BN_rshift1(BIGNUM *r, const BIGNUM *a) { |
211 | 107k | if (!bn_wexpand(r, a->width)) { |
212 | 0 | return 0; |
213 | 0 | } |
214 | 107k | bn_rshift1_words(r->d, a->d, a->width); |
215 | 107k | r->width = a->width; |
216 | 107k | r->neg = a->neg; |
217 | 107k | bn_set_minimal_width(r); |
218 | 107k | return 1; |
219 | 107k | } |
220 | | |
221 | 1.06k | int BN_set_bit(BIGNUM *a, int n) { |
222 | 1.06k | if (n < 0) { |
223 | 0 | return 0; |
224 | 0 | } |
225 | | |
226 | 1.06k | int i = n / BN_BITS2; |
227 | 1.06k | int j = n % BN_BITS2; |
228 | 1.06k | if (a->width <= i) { |
229 | 1.06k | if (!bn_wexpand(a, i + 1)) { |
230 | 0 | return 0; |
231 | 0 | } |
232 | 38.8k | for (int k = a->width; k < i + 1; k++) { |
233 | 37.8k | a->d[k] = 0; |
234 | 37.8k | } |
235 | 1.06k | a->width = i + 1; |
236 | 1.06k | } |
237 | | |
238 | 1.06k | a->d[i] |= (((BN_ULONG)1) << j); |
239 | | |
240 | 1.06k | return 1; |
241 | 1.06k | } |
242 | | |
243 | 106 | int BN_clear_bit(BIGNUM *a, int n) { |
244 | 106 | int i, j; |
245 | | |
246 | 106 | if (n < 0) { |
247 | 0 | return 0; |
248 | 0 | } |
249 | | |
250 | 106 | i = n / BN_BITS2; |
251 | 106 | j = n % BN_BITS2; |
252 | 106 | if (a->width <= i) { |
253 | 0 | return 0; |
254 | 0 | } |
255 | | |
256 | 106 | a->d[i] &= (~(((BN_ULONG)1) << j)); |
257 | 106 | bn_set_minimal_width(a); |
258 | 106 | return 1; |
259 | 106 | } |
260 | | |
261 | 2.30M | int bn_is_bit_set_words(const BN_ULONG *a, size_t num, size_t bit) { |
262 | 2.30M | size_t i = bit / BN_BITS2; |
263 | 2.30M | size_t j = bit % BN_BITS2; |
264 | 2.30M | if (i >= num) { |
265 | 44 | return 0; |
266 | 44 | } |
267 | 2.30M | return (a[i] >> j) & 1; |
268 | 2.30M | } |
269 | | |
270 | 2.26M | int BN_is_bit_set(const BIGNUM *a, int n) { |
271 | 2.26M | if (n < 0) { |
272 | 0 | return 0; |
273 | 0 | } |
274 | 2.26M | return bn_is_bit_set_words(a->d, a->width, n); |
275 | 2.26M | } |
276 | | |
277 | 2.27k | int BN_mask_bits(BIGNUM *a, int n) { |
278 | 2.27k | if (n < 0) { |
279 | 0 | return 0; |
280 | 0 | } |
281 | | |
282 | 2.27k | int w = n / BN_BITS2; |
283 | 2.27k | int b = n % BN_BITS2; |
284 | 2.27k | if (w >= a->width) { |
285 | 0 | return 1; |
286 | 0 | } |
287 | 2.27k | if (b == 0) { |
288 | 0 | a->width = w; |
289 | 2.27k | } else { |
290 | 2.27k | a->width = w + 1; |
291 | 2.27k | a->d[w] &= ~(BN_MASK2 << b); |
292 | 2.27k | } |
293 | | |
294 | 2.27k | bn_set_minimal_width(a); |
295 | 2.27k | return 1; |
296 | 2.27k | } |
297 | | |
298 | 6.37k | static int bn_count_low_zero_bits_word(BN_ULONG l) { |
299 | 6.37k | static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), |
300 | 6.37k | "crypto_word_t is too small"); |
301 | 6.37k | static_assert(sizeof(int) <= sizeof(crypto_word_t), |
302 | 6.37k | "crypto_word_t is too small"); |
303 | 6.37k | static_assert(BN_BITS2 == sizeof(BN_ULONG) * 8, "BN_ULONG has padding bits"); |
304 | | // C has very bizarre rules for types smaller than an int. |
305 | 6.37k | static_assert(sizeof(BN_ULONG) >= sizeof(int), |
306 | 6.37k | "BN_ULONG gets promoted to int"); |
307 | | |
308 | 6.37k | crypto_word_t mask; |
309 | 6.37k | int bits = 0; |
310 | | |
311 | 6.37k | #if BN_BITS2 > 32 |
312 | | // Check if the lower half of |x| are all zero. |
313 | 6.37k | mask = constant_time_is_zero_w(l << (BN_BITS2 - 32)); |
314 | | // If the lower half is all zeros, it is included in the bit count and we |
315 | | // count the upper half. Otherwise, we count the lower half. |
316 | 6.37k | bits += 32 & mask; |
317 | 6.37k | l = constant_time_select_w(mask, l >> 32, l); |
318 | 6.37k | #endif |
319 | | |
320 | | // The remaining blocks are analogous iterations at lower powers of two. |
321 | 6.37k | mask = constant_time_is_zero_w(l << (BN_BITS2 - 16)); |
322 | 6.37k | bits += 16 & mask; |
323 | 6.37k | l = constant_time_select_w(mask, l >> 16, l); |
324 | | |
325 | 6.37k | mask = constant_time_is_zero_w(l << (BN_BITS2 - 8)); |
326 | 6.37k | bits += 8 & mask; |
327 | 6.37k | l = constant_time_select_w(mask, l >> 8, l); |
328 | | |
329 | 6.37k | mask = constant_time_is_zero_w(l << (BN_BITS2 - 4)); |
330 | 6.37k | bits += 4 & mask; |
331 | 6.37k | l = constant_time_select_w(mask, l >> 4, l); |
332 | | |
333 | 6.37k | mask = constant_time_is_zero_w(l << (BN_BITS2 - 2)); |
334 | 6.37k | bits += 2 & mask; |
335 | 6.37k | l = constant_time_select_w(mask, l >> 2, l); |
336 | | |
337 | 6.37k | mask = constant_time_is_zero_w(l << (BN_BITS2 - 1)); |
338 | 6.37k | bits += 1 & mask; |
339 | | |
340 | 6.37k | return bits; |
341 | 6.37k | } |
342 | | |
343 | 548 | int BN_count_low_zero_bits(const BIGNUM *bn) { |
344 | 548 | static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), |
345 | 548 | "crypto_word_t is too small"); |
346 | 548 | static_assert(sizeof(int) <= sizeof(crypto_word_t), |
347 | 548 | "crypto_word_t is too small"); |
348 | | |
349 | 548 | int ret = 0; |
350 | 548 | crypto_word_t saw_nonzero = 0; |
351 | 6.91k | for (int i = 0; i < bn->width; i++) { |
352 | 6.37k | crypto_word_t nonzero = ~constant_time_is_zero_w(bn->d[i]); |
353 | 6.37k | crypto_word_t first_nonzero = ~saw_nonzero & nonzero; |
354 | 6.37k | saw_nonzero |= nonzero; |
355 | | |
356 | 6.37k | int bits = bn_count_low_zero_bits_word(bn->d[i]); |
357 | 6.37k | ret |= first_nonzero & (i * BN_BITS2 + bits); |
358 | 6.37k | } |
359 | | |
360 | | // If got to the end of |bn| and saw no non-zero words, |bn| is zero. |ret| |
361 | | // will then remain zero. |
362 | 548 | return ret; |
363 | 548 | } |