/src/openssl/crypto/bn/bn_lib.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Copyright 1995-2024 The OpenSSL Project Authors. All Rights Reserved. |
3 | | * |
4 | | * Licensed under the Apache License 2.0 (the "License"). You may not use |
5 | | * this file except in compliance with the License. You can obtain a copy |
6 | | * in the file LICENSE in the source distribution or at |
7 | | * https://www.openssl.org/source/license.html |
8 | | */ |
9 | | |
10 | | #include <assert.h> |
11 | | #include <limits.h> |
12 | | #include "internal/cryptlib.h" |
13 | | #include "internal/endian.h" |
14 | | #include "bn_local.h" |
15 | | #include <openssl/opensslconf.h> |
16 | | #include "internal/constant_time.h" |
17 | | |
18 | | /* This stuff appears to be completely unused, so is deprecated */ |
19 | | #ifndef OPENSSL_NO_DEPRECATED_0_9_8 |
20 | | /*- |
21 | | * For a 32 bit machine |
22 | | * 2 - 4 == 128 |
23 | | * 3 - 8 == 256 |
24 | | * 4 - 16 == 512 |
25 | | * 5 - 32 == 1024 |
26 | | * 6 - 64 == 2048 |
27 | | * 7 - 128 == 4096 |
28 | | * 8 - 256 == 8192 |
29 | | */ |
30 | | static int bn_limit_bits = 0; |
31 | | static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ |
32 | | static int bn_limit_bits_low = 0; |
33 | | static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ |
34 | | static int bn_limit_bits_high = 0; |
35 | | static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ |
36 | | static int bn_limit_bits_mont = 0; |
37 | | static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ |
38 | | |
39 | | void BN_set_params(int mult, int high, int low, int mont) |
40 | 0 | { |
41 | 0 | if (mult >= 0) { |
42 | 0 | if (mult > (int)(sizeof(int) * 8) - 1) |
43 | 0 | mult = sizeof(int) * 8 - 1; |
44 | 0 | bn_limit_bits = mult; |
45 | 0 | bn_limit_num = 1 << mult; |
46 | 0 | } |
47 | 0 | if (high >= 0) { |
48 | 0 | if (high > (int)(sizeof(int) * 8) - 1) |
49 | 0 | high = sizeof(int) * 8 - 1; |
50 | 0 | bn_limit_bits_high = high; |
51 | 0 | bn_limit_num_high = 1 << high; |
52 | 0 | } |
53 | 0 | if (low >= 0) { |
54 | 0 | if (low > (int)(sizeof(int) * 8) - 1) |
55 | 0 | low = sizeof(int) * 8 - 1; |
56 | 0 | bn_limit_bits_low = low; |
57 | 0 | bn_limit_num_low = 1 << low; |
58 | 0 | } |
59 | 0 | if (mont >= 0) { |
60 | 0 | if (mont > (int)(sizeof(int) * 8) - 1) |
61 | 0 | mont = sizeof(int) * 8 - 1; |
62 | 0 | bn_limit_bits_mont = mont; |
63 | 0 | bn_limit_num_mont = 1 << mont; |
64 | 0 | } |
65 | 0 | } |
66 | | |
67 | | int BN_get_params(int which) |
68 | 0 | { |
69 | 0 | if (which == 0) |
70 | 0 | return bn_limit_bits; |
71 | 0 | else if (which == 1) |
72 | 0 | return bn_limit_bits_high; |
73 | 0 | else if (which == 2) |
74 | 0 | return bn_limit_bits_low; |
75 | 0 | else if (which == 3) |
76 | 0 | return bn_limit_bits_mont; |
77 | 0 | else |
78 | 0 | return 0; |
79 | 0 | } |
80 | | #endif |
81 | | |
82 | | const BIGNUM *BN_value_one(void) |
83 | 338k | { |
84 | 338k | static const BN_ULONG data_one = 1L; |
85 | 338k | static const BIGNUM const_one = { |
86 | 338k | (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA |
87 | 338k | }; |
88 | | |
89 | 338k | return &const_one; |
90 | 338k | } |
91 | | |
92 | | /* |
93 | | * Old Visual Studio ARM compiler miscompiles BN_num_bits_word() |
94 | | * https://mta.openssl.org/pipermail/openssl-users/2018-August/008465.html |
95 | | */ |
96 | | #if defined(_MSC_VER) && defined(_ARM_) && defined(_WIN32_WCE) \ |
97 | | && _MSC_VER>=1400 && _MSC_VER<1501 |
98 | | # define MS_BROKEN_BN_num_bits_word |
99 | | # pragma optimize("", off) |
100 | | #endif |
101 | | int BN_num_bits_word(BN_ULONG l) |
102 | 56.0M | { |
103 | 56.0M | BN_ULONG x, mask; |
104 | 56.0M | int bits = (l != 0); |
105 | | |
106 | 56.0M | #if BN_BITS2 > 32 |
107 | 56.0M | x = l >> 32; |
108 | 56.0M | mask = (0 - x) & BN_MASK2; |
109 | 56.0M | mask = (0 - (mask >> (BN_BITS2 - 1))); |
110 | 56.0M | bits += 32 & mask; |
111 | 56.0M | l ^= (x ^ l) & mask; |
112 | 56.0M | #endif |
113 | | |
114 | 56.0M | x = l >> 16; |
115 | 56.0M | mask = (0 - x) & BN_MASK2; |
116 | 56.0M | mask = (0 - (mask >> (BN_BITS2 - 1))); |
117 | 56.0M | bits += 16 & mask; |
118 | 56.0M | l ^= (x ^ l) & mask; |
119 | | |
120 | 56.0M | x = l >> 8; |
121 | 56.0M | mask = (0 - x) & BN_MASK2; |
122 | 56.0M | mask = (0 - (mask >> (BN_BITS2 - 1))); |
123 | 56.0M | bits += 8 & mask; |
124 | 56.0M | l ^= (x ^ l) & mask; |
125 | | |
126 | 56.0M | x = l >> 4; |
127 | 56.0M | mask = (0 - x) & BN_MASK2; |
128 | 56.0M | mask = (0 - (mask >> (BN_BITS2 - 1))); |
129 | 56.0M | bits += 4 & mask; |
130 | 56.0M | l ^= (x ^ l) & mask; |
131 | | |
132 | 56.0M | x = l >> 2; |
133 | 56.0M | mask = (0 - x) & BN_MASK2; |
134 | 56.0M | mask = (0 - (mask >> (BN_BITS2 - 1))); |
135 | 56.0M | bits += 2 & mask; |
136 | 56.0M | l ^= (x ^ l) & mask; |
137 | | |
138 | 56.0M | x = l >> 1; |
139 | 56.0M | mask = (0 - x) & BN_MASK2; |
140 | 56.0M | mask = (0 - (mask >> (BN_BITS2 - 1))); |
141 | 56.0M | bits += 1 & mask; |
142 | | |
143 | 56.0M | return bits; |
144 | 56.0M | } |
145 | | #ifdef MS_BROKEN_BN_num_bits_word |
146 | | # pragma optimize("", on) |
147 | | #endif |
148 | | |
149 | | /* |
150 | | * This function still leaks `a->dmax`: it's caller's responsibility to |
151 | | * expand the input `a` in advance to a public length. |
152 | | */ |
153 | | static ossl_inline |
154 | | int bn_num_bits_consttime(const BIGNUM *a) |
155 | 8.68k | { |
156 | 8.68k | int j, ret; |
157 | 8.68k | unsigned int mask, past_i; |
158 | 8.68k | int i = a->top - 1; |
159 | 8.68k | bn_check_top(a); |
160 | | |
161 | 95.2k | for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) { |
162 | 86.5k | mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */ |
163 | | |
164 | 86.5k | ret += BN_BITS2 & (~mask & ~past_i); |
165 | 86.5k | ret += BN_num_bits_word(a->d[j]) & mask; |
166 | | |
167 | 86.5k | past_i |= mask; /* past_i will become 0xff..ff after i==j */ |
168 | 86.5k | } |
169 | | |
170 | | /* |
171 | | * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the |
172 | | * final result. |
173 | | */ |
174 | 8.68k | mask = ~(constant_time_eq_int(i, ((int)-1))); |
175 | | |
176 | 8.68k | return ret & mask; |
177 | 8.68k | } |
178 | | |
179 | | int BN_num_bits(const BIGNUM *a) |
180 | 3.45M | { |
181 | 3.45M | int i = a->top - 1; |
182 | 3.45M | bn_check_top(a); |
183 | | |
184 | 3.45M | if (a->flags & BN_FLG_CONSTTIME) { |
185 | | /* |
186 | | * We assume that BIGNUMs flagged as CONSTTIME have also been expanded |
187 | | * so that a->dmax is not leaking secret information. |
188 | | * |
189 | | * In other words, it's the caller's responsibility to ensure `a` has |
190 | | * been preallocated in advance to a public length if we hit this |
191 | | * branch. |
192 | | * |
193 | | */ |
194 | 8.68k | return bn_num_bits_consttime(a); |
195 | 8.68k | } |
196 | | |
197 | 3.44M | if (BN_is_zero(a)) |
198 | 8.17k | return 0; |
199 | | |
200 | 3.44M | return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); |
201 | 3.44M | } |
202 | | |
203 | | static void bn_free_d(BIGNUM *a, int clear) |
204 | 659k | { |
205 | 659k | if (BN_get_flags(a, BN_FLG_SECURE)) |
206 | 29.1k | OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0])); |
207 | 629k | else if (clear != 0) |
208 | 401k | OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0])); |
209 | 228k | else |
210 | 228k | OPENSSL_free(a->d); |
211 | 659k | } |
212 | | |
213 | | |
214 | | void BN_clear_free(BIGNUM *a) |
215 | 304k | { |
216 | 304k | if (a == NULL) |
217 | 8.56k | return; |
218 | 295k | if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) |
219 | 256k | bn_free_d(a, 1); |
220 | 295k | if (BN_get_flags(a, BN_FLG_MALLOCED)) { |
221 | 32.3k | OPENSSL_cleanse(a, sizeof(*a)); |
222 | 32.3k | OPENSSL_free(a); |
223 | 32.3k | } |
224 | 295k | } |
225 | | |
226 | | void BN_free(BIGNUM *a) |
227 | 361k | { |
228 | 361k | if (a == NULL) |
229 | 132k | return; |
230 | 229k | if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) |
231 | 229k | bn_free_d(a, 0); |
232 | 229k | if (a->flags & BN_FLG_MALLOCED) |
233 | 228k | OPENSSL_free(a); |
234 | 229k | } |
235 | | |
236 | | void bn_init(BIGNUM *a) |
237 | 616k | { |
238 | 616k | static BIGNUM nilbn; |
239 | | |
240 | 616k | *a = nilbn; |
241 | 616k | bn_check_top(a); |
242 | 616k | } |
243 | | |
244 | | BIGNUM *BN_new(void) |
245 | 302k | { |
246 | 302k | BIGNUM *ret; |
247 | | |
248 | 302k | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) |
249 | 0 | return NULL; |
250 | 302k | ret->flags = BN_FLG_MALLOCED; |
251 | 302k | bn_check_top(ret); |
252 | 302k | return ret; |
253 | 302k | } |
254 | | |
255 | | BIGNUM *BN_secure_new(void) |
256 | 938 | { |
257 | 938 | BIGNUM *ret = BN_new(); |
258 | 938 | if (ret != NULL) |
259 | 938 | ret->flags |= BN_FLG_SECURE; |
260 | 938 | return ret; |
261 | 938 | } |
262 | | |
263 | | /* This is used by bn_expand2() */ |
264 | | /* The caller MUST check that words > b->dmax before calling this */ |
265 | | static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) |
266 | 642k | { |
267 | 642k | BN_ULONG *a = NULL; |
268 | | |
269 | 642k | if (words > (INT_MAX / (4 * BN_BITS2))) { |
270 | 0 | ERR_raise(ERR_LIB_BN, BN_R_BIGNUM_TOO_LONG); |
271 | 0 | return NULL; |
272 | 0 | } |
273 | 642k | if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { |
274 | 0 | ERR_raise(ERR_LIB_BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); |
275 | 0 | return NULL; |
276 | 0 | } |
277 | 642k | if (BN_get_flags(b, BN_FLG_SECURE)) |
278 | 29.1k | a = OPENSSL_secure_zalloc(words * sizeof(*a)); |
279 | 613k | else |
280 | 613k | a = OPENSSL_zalloc(words * sizeof(*a)); |
281 | 642k | if (a == NULL) |
282 | 0 | return NULL; |
283 | | |
284 | 642k | assert(b->top <= words); |
285 | 642k | if (b->top > 0) |
286 | 74.7k | memcpy(a, b->d, sizeof(*a) * b->top); |
287 | | |
288 | 642k | return a; |
289 | 642k | } |
290 | | |
291 | | /* |
292 | | * This is an internal function that should not be used in applications. It |
293 | | * ensures that 'b' has enough room for a 'words' word number and initialises |
294 | | * any unused part of b->d with leading zeros. It is mostly used by the |
295 | | * various BIGNUM routines. If there is an error, NULL is returned. If not, |
296 | | * 'b' is returned. |
297 | | */ |
298 | | |
299 | | BIGNUM *bn_expand2(BIGNUM *b, int words) |
300 | 642k | { |
301 | 642k | if (words > b->dmax) { |
302 | 642k | BN_ULONG *a = bn_expand_internal(b, words); |
303 | 642k | if (!a) |
304 | 0 | return NULL; |
305 | 642k | if (b->d != NULL) |
306 | 173k | bn_free_d(b, 1); |
307 | 642k | b->d = a; |
308 | 642k | b->dmax = words; |
309 | 642k | } |
310 | | |
311 | 642k | return b; |
312 | 642k | } |
313 | | |
314 | | BIGNUM *BN_dup(const BIGNUM *a) |
315 | 14.8k | { |
316 | 14.8k | BIGNUM *t; |
317 | | |
318 | 14.8k | if (a == NULL) |
319 | 0 | return NULL; |
320 | 14.8k | bn_check_top(a); |
321 | | |
322 | 14.8k | t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new(); |
323 | 14.8k | if (t == NULL) |
324 | 0 | return NULL; |
325 | 14.8k | if (!BN_copy(t, a)) { |
326 | 0 | BN_free(t); |
327 | 0 | return NULL; |
328 | 0 | } |
329 | 14.8k | bn_check_top(t); |
330 | 14.8k | return t; |
331 | 14.8k | } |
332 | | |
333 | | BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) |
334 | 3.12M | { |
335 | 3.12M | int bn_words; |
336 | | |
337 | 3.12M | bn_check_top(b); |
338 | | |
339 | 3.12M | bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top; |
340 | | |
341 | 3.12M | if (a == b) |
342 | 46 | return a; |
343 | 3.12M | if (bn_wexpand(a, bn_words) == NULL) |
344 | 0 | return NULL; |
345 | | |
346 | 3.12M | if (b->top > 0) |
347 | 3.10M | memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words); |
348 | | |
349 | 3.12M | a->neg = b->neg; |
350 | 3.12M | a->top = b->top; |
351 | 3.12M | a->flags |= b->flags & BN_FLG_FIXED_TOP; |
352 | 3.12M | bn_check_top(a); |
353 | 3.12M | return a; |
354 | 3.12M | } |
355 | | |
356 | 0 | #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ |
357 | 0 | | BN_FLG_CONSTTIME \ |
358 | 0 | | BN_FLG_SECURE \ |
359 | 0 | | BN_FLG_FIXED_TOP)) |
360 | 0 | #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) |
361 | | |
362 | | void BN_swap(BIGNUM *a, BIGNUM *b) |
363 | 0 | { |
364 | 0 | int flags_old_a, flags_old_b; |
365 | 0 | BN_ULONG *tmp_d; |
366 | 0 | int tmp_top, tmp_dmax, tmp_neg; |
367 | |
|
368 | 0 | bn_check_top(a); |
369 | 0 | bn_check_top(b); |
370 | |
|
371 | 0 | flags_old_a = a->flags; |
372 | 0 | flags_old_b = b->flags; |
373 | |
|
374 | 0 | tmp_d = a->d; |
375 | 0 | tmp_top = a->top; |
376 | 0 | tmp_dmax = a->dmax; |
377 | 0 | tmp_neg = a->neg; |
378 | |
|
379 | 0 | a->d = b->d; |
380 | 0 | a->top = b->top; |
381 | 0 | a->dmax = b->dmax; |
382 | 0 | a->neg = b->neg; |
383 | |
|
384 | 0 | b->d = tmp_d; |
385 | 0 | b->top = tmp_top; |
386 | 0 | b->dmax = tmp_dmax; |
387 | 0 | b->neg = tmp_neg; |
388 | |
|
389 | 0 | a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); |
390 | 0 | b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); |
391 | 0 | bn_check_top(a); |
392 | 0 | bn_check_top(b); |
393 | 0 | } |
394 | | |
395 | | void BN_clear(BIGNUM *a) |
396 | 191k | { |
397 | 191k | if (a == NULL) |
398 | 46 | return; |
399 | 191k | bn_check_top(a); |
400 | 191k | if (a->d != NULL) |
401 | 185k | OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax); |
402 | 191k | a->neg = 0; |
403 | 191k | a->top = 0; |
404 | 191k | a->flags &= ~BN_FLG_FIXED_TOP; |
405 | 191k | } |
406 | | |
407 | | BN_ULONG BN_get_word(const BIGNUM *a) |
408 | 0 | { |
409 | 0 | if (a->top > 1) |
410 | 0 | return BN_MASK2; |
411 | 0 | else if (a->top == 1) |
412 | 0 | return a->d[0]; |
413 | | /* a->top == 0 */ |
414 | 0 | return 0; |
415 | 0 | } |
416 | | |
417 | | int BN_set_word(BIGNUM *a, BN_ULONG w) |
418 | 233k | { |
419 | 233k | bn_check_top(a); |
420 | 233k | if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) |
421 | 0 | return 0; |
422 | 233k | a->neg = 0; |
423 | 233k | a->d[0] = w; |
424 | 233k | a->top = (w ? 1 : 0); |
425 | 233k | a->flags &= ~BN_FLG_FIXED_TOP; |
426 | 233k | bn_check_top(a); |
427 | 233k | return 1; |
428 | 233k | } |
429 | | |
430 | | typedef enum {BIG, LITTLE} endianness_t; |
431 | | typedef enum {SIGNED, UNSIGNED} signedness_t; |
432 | | |
433 | | static BIGNUM *bin2bn(const unsigned char *s, int len, BIGNUM *ret, |
434 | | endianness_t endianness, signedness_t signedness) |
435 | 1.10M | { |
436 | 1.10M | int inc; |
437 | 1.10M | const unsigned char *s2; |
438 | 1.10M | int inc2; |
439 | 1.10M | int neg = 0, xor = 0, carry = 0; |
440 | 1.10M | unsigned int i; |
441 | 1.10M | unsigned int n; |
442 | 1.10M | BIGNUM *bn = NULL; |
443 | | |
444 | | /* Negative length is not acceptable */ |
445 | 1.10M | if (len < 0) |
446 | 0 | return NULL; |
447 | | |
448 | 1.10M | if (ret == NULL) |
449 | 25.2k | ret = bn = BN_new(); |
450 | 1.10M | if (ret == NULL) |
451 | 0 | return NULL; |
452 | 1.10M | bn_check_top(ret); |
453 | | |
454 | | /* |
455 | | * If the input has no bits, the number is considered zero. |
456 | | * This makes calls with s==NULL and len==0 safe. |
457 | | */ |
458 | 1.10M | if (len == 0) { |
459 | 1.27k | BN_clear(ret); |
460 | 1.27k | return ret; |
461 | 1.27k | } |
462 | | |
463 | | /* |
464 | | * The loop that does the work iterates from least to most |
465 | | * significant BIGNUM chunk, so we adapt parameters to transfer |
466 | | * input bytes accordingly. |
467 | | */ |
468 | 1.10M | if (endianness == LITTLE) { |
469 | 0 | s2 = s + len - 1; |
470 | 0 | inc2 = -1; |
471 | 0 | inc = 1; |
472 | 1.10M | } else { |
473 | 1.10M | s2 = s; |
474 | 1.10M | inc2 = 1; |
475 | 1.10M | inc = -1; |
476 | 1.10M | s += len - 1; |
477 | 1.10M | } |
478 | | |
479 | | /* Take note of the signedness of the input bytes*/ |
480 | 1.10M | if (signedness == SIGNED) { |
481 | 0 | neg = !!(*s2 & 0x80); |
482 | 0 | xor = neg ? 0xff : 0x00; |
483 | 0 | carry = neg; |
484 | 0 | } |
485 | | |
486 | | /* |
487 | | * Skip leading sign extensions (the value of |xor|). |
488 | | * This is the only spot where |s2| and |inc2| are used. |
489 | | */ |
490 | 1.15M | for ( ; len > 0 && *s2 == xor; s2 += inc2, len--) |
491 | 52.4k | continue; |
492 | | |
493 | | /* |
494 | | * If there was a set of 0xff, we backtrack one byte unless the next |
495 | | * one has a sign bit, as the last 0xff is then part of the actual |
496 | | * number, rather then a mere sign extension. |
497 | | */ |
498 | 1.10M | if (xor == 0xff) { |
499 | 0 | if (len == 0 || !(*s2 & 0x80)) |
500 | 0 | len++; |
501 | 0 | } |
502 | | /* If it was all zeros, we're done */ |
503 | 1.10M | if (len == 0) { |
504 | 3.32k | ret->top = 0; |
505 | 3.32k | return ret; |
506 | 3.32k | } |
507 | 1.09M | n = ((len - 1) / BN_BYTES) + 1; /* Number of resulting bignum chunks */ |
508 | 1.09M | if (bn_wexpand(ret, (int)n) == NULL) { |
509 | 0 | BN_free(bn); |
510 | 0 | return NULL; |
511 | 0 | } |
512 | 1.09M | ret->top = n; |
513 | 1.09M | ret->neg = neg; |
514 | 5.52M | for (i = 0; n-- > 0; i++) { |
515 | 4.42M | BN_ULONG l = 0; /* Accumulator */ |
516 | 4.42M | unsigned int m = 0; /* Offset in a bignum chunk, in bits */ |
517 | | |
518 | 35.6M | for (; len > 0 && m < BN_BYTES * 8; len--, s += inc, m += 8) { |
519 | 31.2M | BN_ULONG byte_xored = *s ^ xor; |
520 | 31.2M | BN_ULONG byte = (byte_xored + carry) & 0xff; |
521 | | |
522 | 31.2M | carry = byte_xored > byte; /* Implicit 1 or 0 */ |
523 | 31.2M | l |= (byte << m); |
524 | 31.2M | } |
525 | 4.42M | ret->d[i] = l; |
526 | 4.42M | } |
527 | | /* |
528 | | * need to call this due to clear byte at top if avoiding having the top |
529 | | * bit set (-ve number) |
530 | | */ |
531 | 1.09M | bn_correct_top(ret); |
532 | 1.09M | return ret; |
533 | 1.09M | } |
534 | | |
535 | | BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
536 | 1.10M | { |
537 | 1.10M | return bin2bn(s, len, ret, BIG, UNSIGNED); |
538 | 1.10M | } |
539 | | |
540 | | BIGNUM *BN_signed_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
541 | 0 | { |
542 | 0 | return bin2bn(s, len, ret, BIG, SIGNED); |
543 | 0 | } |
544 | | |
545 | | static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, |
546 | | endianness_t endianness, signedness_t signedness) |
547 | 17.2k | { |
548 | 17.2k | int inc; |
549 | 17.2k | int n, n8; |
550 | 17.2k | int xor = 0, carry = 0, ext = 0; |
551 | 17.2k | size_t i, lasti, j, atop, mask; |
552 | 17.2k | BN_ULONG l; |
553 | | |
554 | | /* |
555 | | * In case |a| is fixed-top, BN_num_bits can return bogus length, |
556 | | * but it's assumed that fixed-top inputs ought to be "nominated" |
557 | | * even for padded output, so it works out... |
558 | | */ |
559 | 17.2k | n8 = BN_num_bits(a); |
560 | 17.2k | n = (n8 + 7) / 8; /* This is what BN_num_bytes() does */ |
561 | | |
562 | | /* Take note of the signedness of the bignum */ |
563 | 17.2k | if (signedness == SIGNED) { |
564 | 0 | xor = a->neg ? 0xff : 0x00; |
565 | 0 | carry = a->neg; |
566 | | |
567 | | /* |
568 | | * if |n * 8 == n|, then the MSbit is set, otherwise unset. |
569 | | * We must compensate with one extra byte if that doesn't |
570 | | * correspond to the signedness of the bignum with regards |
571 | | * to 2's complement. |
572 | | */ |
573 | 0 | ext = (n * 8 == n8) |
574 | 0 | ? !a->neg /* MSbit set on nonnegative bignum */ |
575 | 0 | : a->neg; /* MSbit unset on negative bignum */ |
576 | 0 | } |
577 | | |
578 | 17.2k | if (tolen == -1) { |
579 | 16.0k | tolen = n + ext; |
580 | 16.0k | } else if (tolen < n + ext) { /* uncommon/unlike case */ |
581 | 16 | BIGNUM temp = *a; |
582 | | |
583 | 16 | bn_correct_top(&temp); |
584 | 16 | n8 = BN_num_bits(&temp); |
585 | 16 | n = (n8 + 7) / 8; /* This is what BN_num_bytes() does */ |
586 | 16 | if (tolen < n + ext) |
587 | 16 | return -1; |
588 | 16 | } |
589 | | |
590 | | /* Swipe through whole available data and don't give away padded zero. */ |
591 | 17.2k | atop = a->dmax * BN_BYTES; |
592 | 17.2k | if (atop == 0) { |
593 | 2.16k | if (tolen != 0) |
594 | 61 | memset(to, '\0', tolen); |
595 | 2.16k | return tolen; |
596 | 2.16k | } |
597 | | |
598 | | /* |
599 | | * The loop that does the work iterates from least significant |
600 | | * to most significant BIGNUM limb, so we adapt parameters to |
601 | | * transfer output bytes accordingly. |
602 | | */ |
603 | 15.0k | if (endianness == LITTLE) { |
604 | 0 | inc = 1; |
605 | 15.0k | } else { |
606 | 15.0k | inc = -1; |
607 | 15.0k | to += tolen - 1; /* Move to the last byte, not beyond */ |
608 | 15.0k | } |
609 | | |
610 | 15.0k | lasti = atop - 1; |
611 | 15.0k | atop = a->top * BN_BYTES; |
612 | 2.26M | for (i = 0, j = 0; j < (size_t)tolen; j++) { |
613 | 2.24M | unsigned char byte, byte_xored; |
614 | | |
615 | 2.24M | l = a->d[i / BN_BYTES]; |
616 | 2.24M | mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); |
617 | 2.24M | byte = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); |
618 | 2.24M | byte_xored = byte ^ xor; |
619 | 2.24M | *to = (unsigned char)(byte_xored + carry); |
620 | 2.24M | carry = byte_xored > *to; /* Implicit 1 or 0 */ |
621 | 2.24M | to += inc; |
622 | 2.24M | i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ |
623 | 2.24M | } |
624 | | |
625 | 15.0k | return tolen; |
626 | 17.2k | } |
627 | | |
628 | | int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) |
629 | 1.21k | { |
630 | 1.21k | if (tolen < 0) |
631 | 0 | return -1; |
632 | 1.21k | return bn2binpad(a, to, tolen, BIG, UNSIGNED); |
633 | 1.21k | } |
634 | | |
635 | | int BN_signed_bn2bin(const BIGNUM *a, unsigned char *to, int tolen) |
636 | 0 | { |
637 | 0 | if (tolen < 0) |
638 | 0 | return -1; |
639 | 0 | return bn2binpad(a, to, tolen, BIG, SIGNED); |
640 | 0 | } |
641 | | |
642 | | int BN_bn2bin(const BIGNUM *a, unsigned char *to) |
643 | 21.0k | { |
644 | 21.0k | return bn2binpad(a, to, -1, BIG, UNSIGNED); |
645 | 21.0k | } |
646 | | |
647 | | BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) |
648 | 0 | { |
649 | 0 | return bin2bn(s, len, ret, LITTLE, UNSIGNED); |
650 | 0 | } |
651 | | |
652 | | BIGNUM *BN_signed_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) |
653 | 0 | { |
654 | 0 | return bin2bn(s, len, ret, LITTLE, SIGNED); |
655 | 0 | } |
656 | | |
657 | | int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) |
658 | 0 | { |
659 | 0 | if (tolen < 0) |
660 | 0 | return -1; |
661 | 0 | return bn2binpad(a, to, tolen, LITTLE, UNSIGNED); |
662 | 0 | } |
663 | | |
664 | | int BN_signed_bn2lebin(const BIGNUM *a, unsigned char *to, int tolen) |
665 | 0 | { |
666 | 0 | if (tolen < 0) |
667 | 0 | return -1; |
668 | 0 | return bn2binpad(a, to, tolen, LITTLE, SIGNED); |
669 | 0 | } |
670 | | |
671 | | BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret) |
672 | 0 | { |
673 | 0 | DECLARE_IS_ENDIAN; |
674 | |
|
675 | 0 | if (IS_LITTLE_ENDIAN) |
676 | 0 | return BN_lebin2bn(s, len, ret); |
677 | 0 | return BN_bin2bn(s, len, ret); |
678 | 0 | } |
679 | | |
680 | | BIGNUM *BN_signed_native2bn(const unsigned char *s, int len, BIGNUM *ret) |
681 | 0 | { |
682 | 0 | DECLARE_IS_ENDIAN; |
683 | |
|
684 | 0 | if (IS_LITTLE_ENDIAN) |
685 | 0 | return BN_signed_lebin2bn(s, len, ret); |
686 | 0 | return BN_signed_bin2bn(s, len, ret); |
687 | 0 | } |
688 | | |
689 | | int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen) |
690 | 0 | { |
691 | 0 | DECLARE_IS_ENDIAN; |
692 | |
|
693 | 0 | if (IS_LITTLE_ENDIAN) |
694 | 0 | return BN_bn2lebinpad(a, to, tolen); |
695 | 0 | return BN_bn2binpad(a, to, tolen); |
696 | 0 | } |
697 | | |
698 | | int BN_signed_bn2native(const BIGNUM *a, unsigned char *to, int tolen) |
699 | 0 | { |
700 | 0 | DECLARE_IS_ENDIAN; |
701 | |
|
702 | 0 | if (IS_LITTLE_ENDIAN) |
703 | 0 | return BN_signed_bn2lebin(a, to, tolen); |
704 | 0 | return BN_signed_bn2bin(a, to, tolen); |
705 | 0 | } |
706 | | |
707 | | int BN_ucmp(const BIGNUM *a, const BIGNUM *b) |
708 | 12.5M | { |
709 | 12.5M | int i; |
710 | 12.5M | BN_ULONG t1, t2, *ap, *bp; |
711 | | |
712 | 12.5M | ap = a->d; |
713 | 12.5M | bp = b->d; |
714 | | |
715 | 12.5M | if (BN_get_flags(a, BN_FLG_CONSTTIME) |
716 | 12.5M | && a->top == b->top) { |
717 | 448k | int res = 0; |
718 | | |
719 | 4.16M | for (i = 0; i < b->top; i++) { |
720 | 3.71M | res = constant_time_select_int(constant_time_lt_bn(ap[i], bp[i]), |
721 | 3.71M | -1, res); |
722 | 3.71M | res = constant_time_select_int(constant_time_lt_bn(bp[i], ap[i]), |
723 | 3.71M | 1, res); |
724 | 3.71M | } |
725 | 448k | return res; |
726 | 448k | } |
727 | | |
728 | 12.1M | bn_check_top(a); |
729 | 12.1M | bn_check_top(b); |
730 | | |
731 | 12.1M | i = a->top - b->top; |
732 | 12.1M | if (i != 0) |
733 | 3.60M | return i; |
734 | | |
735 | 8.63M | for (i = a->top - 1; i >= 0; i--) { |
736 | 8.60M | t1 = ap[i]; |
737 | 8.60M | t2 = bp[i]; |
738 | 8.60M | if (t1 != t2) |
739 | 8.48M | return ((t1 > t2) ? 1 : -1); |
740 | 8.60M | } |
741 | 39.1k | return 0; |
742 | 8.52M | } |
743 | | |
744 | | int BN_cmp(const BIGNUM *a, const BIGNUM *b) |
745 | 2.20M | { |
746 | 2.20M | int i; |
747 | 2.20M | int gt, lt; |
748 | 2.20M | BN_ULONG t1, t2; |
749 | | |
750 | 2.20M | if ((a == NULL) || (b == NULL)) { |
751 | 0 | if (a != NULL) |
752 | 0 | return -1; |
753 | 0 | else if (b != NULL) |
754 | 0 | return 1; |
755 | 0 | else |
756 | 0 | return 0; |
757 | 0 | } |
758 | | |
759 | 2.20M | bn_check_top(a); |
760 | 2.20M | bn_check_top(b); |
761 | | |
762 | 2.20M | if (a->neg != b->neg) { |
763 | 0 | if (a->neg) |
764 | 0 | return -1; |
765 | 0 | else |
766 | 0 | return 1; |
767 | 0 | } |
768 | 2.20M | if (a->neg == 0) { |
769 | 2.20M | gt = 1; |
770 | 2.20M | lt = -1; |
771 | 2.20M | } else { |
772 | 0 | gt = -1; |
773 | 0 | lt = 1; |
774 | 0 | } |
775 | | |
776 | 2.20M | if (a->top > b->top) |
777 | 794k | return gt; |
778 | 1.40M | if (a->top < b->top) |
779 | 38.7k | return lt; |
780 | 1.71M | for (i = a->top - 1; i >= 0; i--) { |
781 | 1.68M | t1 = a->d[i]; |
782 | 1.68M | t2 = b->d[i]; |
783 | 1.68M | if (t1 > t2) |
784 | 407k | return gt; |
785 | 1.27M | if (t1 < t2) |
786 | 922k | return lt; |
787 | 1.27M | } |
788 | 37.0k | return 0; |
789 | 1.36M | } |
790 | | |
791 | | int BN_set_bit(BIGNUM *a, int n) |
792 | 66.6k | { |
793 | 66.6k | int i, j, k; |
794 | | |
795 | 66.6k | if (n < 0) |
796 | 0 | return 0; |
797 | | |
798 | 66.6k | i = n / BN_BITS2; |
799 | 66.6k | j = n % BN_BITS2; |
800 | 66.6k | if (a->top <= i) { |
801 | 66.6k | if (bn_wexpand(a, i + 1) == NULL) |
802 | 0 | return 0; |
803 | 1.05M | for (k = a->top; k < i + 1; k++) |
804 | 991k | a->d[k] = 0; |
805 | 66.6k | a->top = i + 1; |
806 | 66.6k | a->flags &= ~BN_FLG_FIXED_TOP; |
807 | 66.6k | } |
808 | | |
809 | 66.6k | a->d[i] |= (((BN_ULONG)1) << j); |
810 | 66.6k | bn_check_top(a); |
811 | 66.6k | return 1; |
812 | 66.6k | } |
813 | | |
814 | | int BN_clear_bit(BIGNUM *a, int n) |
815 | 106 | { |
816 | 106 | int i, j; |
817 | | |
818 | 106 | bn_check_top(a); |
819 | 106 | if (n < 0) |
820 | 0 | return 0; |
821 | | |
822 | 106 | i = n / BN_BITS2; |
823 | 106 | j = n % BN_BITS2; |
824 | 106 | if (a->top <= i) |
825 | 0 | return 0; |
826 | | |
827 | 106 | a->d[i] &= (~(((BN_ULONG)1) << j)); |
828 | 106 | bn_correct_top(a); |
829 | 106 | return 1; |
830 | 106 | } |
831 | | |
832 | | int BN_is_bit_set(const BIGNUM *a, int n) |
833 | 71.3M | { |
834 | 71.3M | int i, j; |
835 | | |
836 | 71.3M | bn_check_top(a); |
837 | 71.3M | if (n < 0) |
838 | 182 | return 0; |
839 | 71.3M | i = n / BN_BITS2; |
840 | 71.3M | j = n % BN_BITS2; |
841 | 71.3M | if (a->top <= i) |
842 | 171k | return 0; |
843 | 71.2M | return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); |
844 | 71.3M | } |
845 | | |
846 | | int ossl_bn_mask_bits_fixed_top(BIGNUM *a, int n) |
847 | 134k | { |
848 | 134k | int b, w; |
849 | | |
850 | 134k | if (n < 0) |
851 | 0 | return 0; |
852 | | |
853 | 134k | w = n / BN_BITS2; |
854 | 134k | b = n % BN_BITS2; |
855 | 134k | if (w >= a->top) |
856 | 0 | return 0; |
857 | 134k | if (b == 0) |
858 | 245 | a->top = w; |
859 | 134k | else { |
860 | 134k | a->top = w + 1; |
861 | 134k | a->d[w] &= ~(BN_MASK2 << b); |
862 | 134k | } |
863 | 134k | a->flags |= BN_FLG_FIXED_TOP; |
864 | 134k | return 1; |
865 | 134k | } |
866 | | |
867 | | int BN_mask_bits(BIGNUM *a, int n) |
868 | 134k | { |
869 | 134k | int ret; |
870 | | |
871 | 134k | bn_check_top(a); |
872 | 134k | ret = ossl_bn_mask_bits_fixed_top(a, n); |
873 | 134k | if (ret) |
874 | 134k | bn_correct_top(a); |
875 | 134k | return ret; |
876 | 134k | } |
877 | | |
878 | | void BN_set_negative(BIGNUM *a, int b) |
879 | 4.27k | { |
880 | 4.27k | if (b && !BN_is_zero(a)) |
881 | 132 | a->neg = 1; |
882 | 4.13k | else |
883 | 4.13k | a->neg = 0; |
884 | 4.27k | } |
885 | | |
886 | | int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) |
887 | 91.8M | { |
888 | 91.8M | int i; |
889 | 91.8M | BN_ULONG aa, bb; |
890 | | |
891 | 91.8M | if (n == 0) |
892 | 0 | return 0; |
893 | | |
894 | 91.8M | aa = a[n - 1]; |
895 | 91.8M | bb = b[n - 1]; |
896 | 91.8M | if (aa != bb) |
897 | 91.1M | return ((aa > bb) ? 1 : -1); |
898 | 6.57M | for (i = n - 2; i >= 0; i--) { |
899 | 6.19M | aa = a[i]; |
900 | 6.19M | bb = b[i]; |
901 | 6.19M | if (aa != bb) |
902 | 333k | return ((aa > bb) ? 1 : -1); |
903 | 6.19M | } |
904 | 379k | return 0; |
905 | 712k | } |
906 | | |
907 | | /* |
908 | | * Here follows a specialised variants of bn_cmp_words(). It has the |
909 | | * capability of performing the operation on arrays of different sizes. The |
910 | | * sizes of those arrays is expressed through cl, which is the common length |
911 | | * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the |
912 | | * two lengths, calculated as len(a)-len(b). All lengths are the number of |
913 | | * BN_ULONGs... |
914 | | */ |
915 | | |
916 | | int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) |
917 | 35.4M | { |
918 | 35.4M | int n, i; |
919 | 35.4M | n = cl - 1; |
920 | | |
921 | 35.4M | if (dl < 0) { |
922 | 1.11M | for (i = dl; i < 0; i++) { |
923 | 1.10M | if (b[n - i] != 0) |
924 | 975k | return -1; /* a < b */ |
925 | 1.10M | } |
926 | 987k | } |
927 | 34.4M | if (dl > 0) { |
928 | 1.12M | for (i = dl; i > 0; i--) { |
929 | 1.10M | if (a[n + i] != 0) |
930 | 976k | return 1; /* a > b */ |
931 | 1.10M | } |
932 | 988k | } |
933 | 33.4M | return bn_cmp_words(a, b, cl); |
934 | 34.4M | } |
935 | | |
936 | | /*- |
937 | | * Constant-time conditional swap of a and b. |
938 | | * a and b are swapped if condition is not 0. |
939 | | * nwords is the number of words to swap. |
940 | | * Assumes that at least nwords are allocated in both a and b. |
941 | | * Assumes that no more than nwords are used by either a or b. |
942 | | */ |
943 | | void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) |
944 | 2.23M | { |
945 | 2.23M | BN_ULONG t; |
946 | 2.23M | int i; |
947 | | |
948 | 2.23M | bn_wcheck_size(a, nwords); |
949 | 2.23M | bn_wcheck_size(b, nwords); |
950 | | |
951 | 2.23M | condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1; |
952 | | |
953 | 2.23M | t = (a->top ^ b->top) & condition; |
954 | 2.23M | a->top ^= t; |
955 | 2.23M | b->top ^= t; |
956 | | |
957 | 2.23M | t = (a->neg ^ b->neg) & condition; |
958 | 2.23M | a->neg ^= t; |
959 | 2.23M | b->neg ^= t; |
960 | | |
961 | | /*- |
962 | | * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention |
963 | | * is actually to treat it as it's read-only data, and some (if not most) |
964 | | * of it does reside in read-only segment. In other words observation of |
965 | | * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal |
966 | | * condition. It would either cause SEGV or effectively cause data |
967 | | * corruption. |
968 | | * |
969 | | * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be |
970 | | * preserved. |
971 | | * |
972 | | * BN_FLG_SECURE: must be preserved, because it determines how x->d was |
973 | | * allocated and hence how to free it. |
974 | | * |
975 | | * BN_FLG_CONSTTIME: sufficient to mask and swap |
976 | | * |
977 | | * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on |
978 | | * the data, so the d array may be padded with additional 0 values (i.e. |
979 | | * top could be greater than the minimal value that it could be). We should |
980 | | * be swapping it |
981 | | */ |
982 | | |
983 | 2.23M | #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) |
984 | | |
985 | 2.23M | t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; |
986 | 2.23M | a->flags ^= t; |
987 | 2.23M | b->flags ^= t; |
988 | | |
989 | | /* conditionally swap the data */ |
990 | 70.4M | for (i = 0; i < nwords; i++) { |
991 | 68.2M | t = (a->d[i] ^ b->d[i]) & condition; |
992 | 68.2M | a->d[i] ^= t; |
993 | 68.2M | b->d[i] ^= t; |
994 | 68.2M | } |
995 | 2.23M | } |
996 | | |
997 | | #undef BN_CONSTTIME_SWAP_FLAGS |
998 | | |
999 | | /* Bits of security, see SP800-57 */ |
1000 | | |
1001 | | int BN_security_bits(int L, int N) |
1002 | 0 | { |
1003 | 0 | int secbits, bits; |
1004 | 0 | if (L >= 15360) |
1005 | 0 | secbits = 256; |
1006 | 0 | else if (L >= 7680) |
1007 | 0 | secbits = 192; |
1008 | 0 | else if (L >= 3072) |
1009 | 0 | secbits = 128; |
1010 | 0 | else if (L >= 2048) |
1011 | 0 | secbits = 112; |
1012 | 0 | else if (L >= 1024) |
1013 | 0 | secbits = 80; |
1014 | 0 | else |
1015 | 0 | return 0; |
1016 | 0 | if (N == -1) |
1017 | 0 | return secbits; |
1018 | 0 | bits = N / 2; |
1019 | 0 | if (bits < 80) |
1020 | 0 | return 0; |
1021 | 0 | return bits >= secbits ? secbits : bits; |
1022 | 0 | } |
1023 | | |
1024 | | void BN_zero_ex(BIGNUM *a) |
1025 | 107M | { |
1026 | 107M | a->neg = 0; |
1027 | 107M | a->top = 0; |
1028 | 107M | a->flags &= ~BN_FLG_FIXED_TOP; |
1029 | 107M | } |
1030 | | |
1031 | | int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) |
1032 | 1.10M | { |
1033 | 1.10M | return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); |
1034 | 1.10M | } |
1035 | | |
1036 | | int BN_is_zero(const BIGNUM *a) |
1037 | 11.9M | { |
1038 | 11.9M | return a->top == 0; |
1039 | 11.9M | } |
1040 | | |
1041 | | int BN_is_one(const BIGNUM *a) |
1042 | 498k | { |
1043 | 498k | return BN_abs_is_word(a, 1) && !a->neg; |
1044 | 498k | } |
1045 | | |
1046 | | int BN_is_word(const BIGNUM *a, const BN_ULONG w) |
1047 | 567k | { |
1048 | 567k | return BN_abs_is_word(a, w) && (!w || !a->neg); |
1049 | 567k | } |
1050 | | |
1051 | | int ossl_bn_is_word_fixed_top(const BIGNUM *a, const BN_ULONG w) |
1052 | 462 | { |
1053 | 462 | int res, i; |
1054 | 462 | const BN_ULONG *ap = a->d; |
1055 | | |
1056 | 462 | if (a->neg || a->top == 0) |
1057 | 0 | return 0; |
1058 | | |
1059 | 462 | res = constant_time_select_int(constant_time_eq_bn(ap[0], w), 1, 0); |
1060 | | |
1061 | 6.42k | for (i = 1; i < a->top; i++) |
1062 | 5.96k | res = constant_time_select_int(constant_time_is_zero_bn(ap[i]), |
1063 | 5.96k | res, 0); |
1064 | 462 | return res; |
1065 | 462 | } |
1066 | | |
1067 | | int BN_is_odd(const BIGNUM *a) |
1068 | 2.66M | { |
1069 | 2.66M | return (a->top > 0) && (a->d[0] & 1); |
1070 | 2.66M | } |
1071 | | |
1072 | | int BN_is_negative(const BIGNUM *a) |
1073 | 2.17M | { |
1074 | 2.17M | return (a->neg != 0); |
1075 | 2.17M | } |
1076 | | |
1077 | | int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, |
1078 | | BN_CTX *ctx) |
1079 | 22.7k | { |
1080 | 22.7k | return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx); |
1081 | 22.7k | } |
1082 | | |
1083 | | void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) |
1084 | 176k | { |
1085 | 176k | dest->d = b->d; |
1086 | 176k | dest->top = b->top; |
1087 | 176k | dest->dmax = b->dmax; |
1088 | 176k | dest->neg = b->neg; |
1089 | 176k | dest->flags = ((dest->flags & BN_FLG_MALLOCED) |
1090 | 176k | | (b->flags & ~BN_FLG_MALLOCED) |
1091 | 176k | | BN_FLG_STATIC_DATA | flags); |
1092 | 176k | } |
1093 | | |
1094 | | BN_GENCB *BN_GENCB_new(void) |
1095 | 0 | { |
1096 | 0 | BN_GENCB *ret; |
1097 | |
|
1098 | 0 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) |
1099 | 0 | return NULL; |
1100 | | |
1101 | 0 | return ret; |
1102 | 0 | } |
1103 | | |
1104 | | void BN_GENCB_free(BN_GENCB *cb) |
1105 | 0 | { |
1106 | 0 | if (cb == NULL) |
1107 | 0 | return; |
1108 | 0 | OPENSSL_free(cb); |
1109 | 0 | } |
1110 | | |
1111 | | void BN_set_flags(BIGNUM *b, int n) |
1112 | 53.6k | { |
1113 | 53.6k | b->flags |= n; |
1114 | 53.6k | } |
1115 | | |
1116 | | int BN_get_flags(const BIGNUM *b, int n) |
1117 | 18.8M | { |
1118 | 18.8M | return b->flags & n; |
1119 | 18.8M | } |
1120 | | |
1121 | | /* Populate a BN_GENCB structure with an "old"-style callback */ |
1122 | | void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *), |
1123 | | void *cb_arg) |
1124 | 0 | { |
1125 | 0 | BN_GENCB *tmp_gencb = gencb; |
1126 | 0 | tmp_gencb->ver = 1; |
1127 | 0 | tmp_gencb->arg = cb_arg; |
1128 | 0 | tmp_gencb->cb.cb_1 = callback; |
1129 | 0 | } |
1130 | | |
1131 | | /* Populate a BN_GENCB structure with a "new"-style callback */ |
1132 | | void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *), |
1133 | | void *cb_arg) |
1134 | 0 | { |
1135 | 0 | BN_GENCB *tmp_gencb = gencb; |
1136 | 0 | tmp_gencb->ver = 2; |
1137 | 0 | tmp_gencb->arg = cb_arg; |
1138 | 0 | tmp_gencb->cb.cb_2 = callback; |
1139 | 0 | } |
1140 | | |
1141 | | void *BN_GENCB_get_arg(BN_GENCB *cb) |
1142 | 0 | { |
1143 | 0 | return cb->arg; |
1144 | 0 | } |
1145 | | |
1146 | | BIGNUM *bn_wexpand(BIGNUM *a, int words) |
1147 | 241M | { |
1148 | 241M | return (words <= a->dmax) ? a : bn_expand2(a, words); |
1149 | 241M | } |
1150 | | |
1151 | | void bn_correct_top_consttime(BIGNUM *a) |
1152 | 0 | { |
1153 | 0 | int j, atop; |
1154 | 0 | BN_ULONG limb; |
1155 | 0 | unsigned int mask; |
1156 | |
|
1157 | 0 | for (j = 0, atop = 0; j < a->dmax; j++) { |
1158 | 0 | limb = a->d[j]; |
1159 | 0 | limb |= 0 - limb; |
1160 | 0 | limb >>= BN_BITS2 - 1; |
1161 | 0 | limb = 0 - limb; |
1162 | 0 | mask = (unsigned int)limb; |
1163 | 0 | mask &= constant_time_msb(j - a->top); |
1164 | 0 | atop = constant_time_select_int(mask, j + 1, atop); |
1165 | 0 | } |
1166 | |
|
1167 | 0 | mask = constant_time_eq_int(atop, 0); |
1168 | 0 | a->top = atop; |
1169 | 0 | a->neg = constant_time_select_int(mask, 0, a->neg); |
1170 | 0 | a->flags &= ~BN_FLG_FIXED_TOP; |
1171 | 0 | } |
1172 | | |
1173 | | void bn_correct_top(BIGNUM *a) |
1174 | 21.6M | { |
1175 | 21.6M | BN_ULONG *ftl; |
1176 | 21.6M | int tmp_top = a->top; |
1177 | | |
1178 | 21.6M | if (tmp_top > 0) { |
1179 | 29.1M | for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) { |
1180 | 29.0M | ftl--; |
1181 | 29.0M | if (*ftl != 0) |
1182 | 21.5M | break; |
1183 | 29.0M | } |
1184 | 21.6M | a->top = tmp_top; |
1185 | 21.6M | } |
1186 | 21.6M | if (a->top == 0) |
1187 | 107k | a->neg = 0; |
1188 | 21.6M | a->flags &= ~BN_FLG_FIXED_TOP; |
1189 | 21.6M | bn_pollute(a); |
1190 | 21.6M | } |