1 | /* |
2 | * Copyright 1995-2018 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 "bn_local.h" |
14 | #include <openssl/opensslconf.h> |
15 | #include "internal/constant_time.h" |
16 | |
17 | /* This stuff appears to be completely unused, so is deprecated */ |
18 | #ifndef OPENSSL_NO_DEPRECATED_0_9_8 |
19 | /*- |
20 | * For a 32 bit machine |
21 | * 2 - 4 == 128 |
22 | * 3 - 8 == 256 |
23 | * 4 - 16 == 512 |
24 | * 5 - 32 == 1024 |
25 | * 6 - 64 == 2048 |
26 | * 7 - 128 == 4096 |
27 | * 8 - 256 == 8192 |
28 | */ |
29 | static int bn_limit_bits = 0; |
30 | static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ |
31 | static int bn_limit_bits_low = 0; |
32 | static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ |
33 | static int bn_limit_bits_high = 0; |
34 | static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ |
35 | static int bn_limit_bits_mont = 0; |
36 | static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ |
37 | |
38 | void BN_set_params(int mult, int high, int low, int mont) |
39 | { |
40 | if (mult >= 0) { |
41 | if (mult > (int)(sizeof(int) * 8) - 1) |
42 | mult = sizeof(int) * 8 - 1; |
43 | bn_limit_bits = mult; |
44 | bn_limit_num = 1 << mult; |
45 | } |
46 | if (high >= 0) { |
47 | if (high > (int)(sizeof(int) * 8) - 1) |
48 | high = sizeof(int) * 8 - 1; |
49 | bn_limit_bits_high = high; |
50 | bn_limit_num_high = 1 << high; |
51 | } |
52 | if (low >= 0) { |
53 | if (low > (int)(sizeof(int) * 8) - 1) |
54 | low = sizeof(int) * 8 - 1; |
55 | bn_limit_bits_low = low; |
56 | bn_limit_num_low = 1 << low; |
57 | } |
58 | if (mont >= 0) { |
59 | if (mont > (int)(sizeof(int) * 8) - 1) |
60 | mont = sizeof(int) * 8 - 1; |
61 | bn_limit_bits_mont = mont; |
62 | bn_limit_num_mont = 1 << mont; |
63 | } |
64 | } |
65 | |
66 | int BN_get_params(int which) |
67 | { |
68 | if (which == 0) |
69 | return bn_limit_bits; |
70 | else if (which == 1) |
71 | return bn_limit_bits_high; |
72 | else if (which == 2) |
73 | return bn_limit_bits_low; |
74 | else if (which == 3) |
75 | return bn_limit_bits_mont; |
76 | else |
77 | return 0; |
78 | } |
79 | #endif |
80 | |
81 | const BIGNUM *BN_value_one(void) |
82 | { |
83 | static const BN_ULONG data_one = 1L; |
84 | static const BIGNUM const_one = |
85 | { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; |
86 | |
87 | return &const_one; |
88 | } |
89 | |
90 | int BN_num_bits_word(BN_ULONG l) |
91 | { |
92 | BN_ULONG x, mask; |
93 | int bits = (l != 0); |
94 | |
95 | #if BN_BITS2 > 32 |
96 | x = l >> 32; |
97 | mask = (0 - x) & BN_MASK2; |
98 | mask = (0 - (mask >> (BN_BITS2 - 1))); |
99 | bits += 32 & mask; |
100 | l ^= (x ^ l) & mask; |
101 | #endif |
102 | |
103 | x = l >> 16; |
104 | mask = (0 - x) & BN_MASK2; |
105 | mask = (0 - (mask >> (BN_BITS2 - 1))); |
106 | bits += 16 & mask; |
107 | l ^= (x ^ l) & mask; |
108 | |
109 | x = l >> 8; |
110 | mask = (0 - x) & BN_MASK2; |
111 | mask = (0 - (mask >> (BN_BITS2 - 1))); |
112 | bits += 8 & mask; |
113 | l ^= (x ^ l) & mask; |
114 | |
115 | x = l >> 4; |
116 | mask = (0 - x) & BN_MASK2; |
117 | mask = (0 - (mask >> (BN_BITS2 - 1))); |
118 | bits += 4 & mask; |
119 | l ^= (x ^ l) & mask; |
120 | |
121 | x = l >> 2; |
122 | mask = (0 - x) & BN_MASK2; |
123 | mask = (0 - (mask >> (BN_BITS2 - 1))); |
124 | bits += 2 & mask; |
125 | l ^= (x ^ l) & mask; |
126 | |
127 | x = l >> 1; |
128 | mask = (0 - x) & BN_MASK2; |
129 | mask = (0 - (mask >> (BN_BITS2 - 1))); |
130 | bits += 1 & mask; |
131 | |
132 | return bits; |
133 | } |
134 | |
135 | /* |
136 | * This function still leaks `a->dmax`: it's caller's responsibility to |
137 | * expand the input `a` in advance to a public length. |
138 | */ |
139 | static ossl_inline |
140 | int bn_num_bits_consttime(const BIGNUM *a) |
141 | { |
142 | int j, ret; |
143 | unsigned int mask, past_i; |
144 | int i = a->top - 1; |
145 | bn_check_top(a); |
146 | |
147 | for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) { |
148 | mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */ |
149 | |
150 | ret += BN_BITS2 & (~mask & ~past_i); |
151 | ret += BN_num_bits_word(a->d[j]) & mask; |
152 | |
153 | past_i |= mask; /* past_i will become 0xff..ff after i==j */ |
154 | } |
155 | |
156 | /* |
157 | * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the |
158 | * final result. |
159 | */ |
160 | mask = ~(constant_time_eq_int(i, ((int)-1))); |
161 | |
162 | return ret & mask; |
163 | } |
164 | |
165 | int BN_num_bits(const BIGNUM *a) |
166 | { |
167 | int i = a->top - 1; |
168 | bn_check_top(a); |
169 | |
170 | if (a->flags & BN_FLG_CONSTTIME) { |
171 | /* |
172 | * We assume that BIGNUMs flagged as CONSTTIME have also been expanded |
173 | * so that a->dmax is not leaking secret information. |
174 | * |
175 | * In other words, it's the caller's responsibility to ensure `a` has |
176 | * been preallocated in advance to a public length if we hit this |
177 | * branch. |
178 | * |
179 | */ |
180 | return bn_num_bits_consttime(a); |
181 | } |
182 | |
183 | if (BN_is_zero(a)) |
184 | return 0; |
185 | |
186 | return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); |
187 | } |
188 | |
189 | static void bn_free_d(BIGNUM *a, int clear) |
190 | { |
191 | if (BN_get_flags(a, BN_FLG_SECURE)) |
192 | OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0])); |
193 | else if (clear != 0) |
194 | OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0])); |
195 | else |
196 | OPENSSL_free(a->d); |
197 | } |
198 | |
199 | |
200 | void BN_clear_free(BIGNUM *a) |
201 | { |
202 | if (a == NULL) |
203 | return; |
204 | if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) |
205 | bn_free_d(a, 1); |
206 | if (BN_get_flags(a, BN_FLG_MALLOCED)) { |
207 | OPENSSL_cleanse(a, sizeof(*a)); |
208 | OPENSSL_free(a); |
209 | } |
210 | } |
211 | |
212 | void BN_free(BIGNUM *a) |
213 | { |
214 | if (a == NULL) |
215 | return; |
216 | if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) |
217 | bn_free_d(a, 0); |
218 | if (a->flags & BN_FLG_MALLOCED) |
219 | OPENSSL_free(a); |
220 | } |
221 | |
222 | void bn_init(BIGNUM *a) |
223 | { |
224 | static BIGNUM nilbn; |
225 | |
226 | *a = nilbn; |
227 | bn_check_top(a); |
228 | } |
229 | |
230 | BIGNUM *BN_new(void) |
231 | { |
232 | BIGNUM *ret; |
233 | |
234 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { |
235 | BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); |
236 | return NULL; |
237 | } |
238 | ret->flags = BN_FLG_MALLOCED; |
239 | bn_check_top(ret); |
240 | return ret; |
241 | } |
242 | |
243 | BIGNUM *BN_secure_new(void) |
244 | { |
245 | BIGNUM *ret = BN_new(); |
246 | if (ret != NULL) |
247 | ret->flags |= BN_FLG_SECURE; |
248 | return ret; |
249 | } |
250 | |
251 | /* This is used by bn_expand2() */ |
252 | /* The caller MUST check that words > b->dmax before calling this */ |
253 | static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) |
254 | { |
255 | BN_ULONG *a = NULL; |
256 | |
257 | if (words > (INT_MAX / (4 * BN_BITS2))) { |
258 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); |
259 | return NULL; |
260 | } |
261 | if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { |
262 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); |
263 | return NULL; |
264 | } |
265 | if (BN_get_flags(b, BN_FLG_SECURE)) |
266 | a = OPENSSL_secure_zalloc(words * sizeof(*a)); |
267 | else |
268 | a = OPENSSL_zalloc(words * sizeof(*a)); |
269 | if (a == NULL) { |
270 | BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); |
271 | return NULL; |
272 | } |
273 | |
274 | assert(b->top <= words); |
275 | if (b->top > 0) |
276 | memcpy(a, b->d, sizeof(*a) * b->top); |
277 | |
278 | return a; |
279 | } |
280 | |
281 | /* |
282 | * This is an internal function that should not be used in applications. It |
283 | * ensures that 'b' has enough room for a 'words' word number and initialises |
284 | * any unused part of b->d with leading zeros. It is mostly used by the |
285 | * various BIGNUM routines. If there is an error, NULL is returned. If not, |
286 | * 'b' is returned. |
287 | */ |
288 | |
289 | BIGNUM *bn_expand2(BIGNUM *b, int words) |
290 | { |
291 | if (words > b->dmax) { |
292 | BN_ULONG *a = bn_expand_internal(b, words); |
293 | if (!a) |
294 | return NULL; |
295 | if (b->d != NULL) |
296 | bn_free_d(b, 1); |
297 | b->d = a; |
298 | b->dmax = words; |
299 | } |
300 | |
301 | return b; |
302 | } |
303 | |
304 | BIGNUM *BN_dup(const BIGNUM *a) |
305 | { |
306 | BIGNUM *t; |
307 | |
308 | if (a == NULL) |
309 | return NULL; |
310 | bn_check_top(a); |
311 | |
312 | t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new(); |
313 | if (t == NULL) |
314 | return NULL; |
315 | if (!BN_copy(t, a)) { |
316 | BN_free(t); |
317 | return NULL; |
318 | } |
319 | bn_check_top(t); |
320 | return t; |
321 | } |
322 | |
323 | BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) |
324 | { |
325 | bn_check_top(b); |
326 | |
327 | if (a == b) |
328 | return a; |
329 | if (bn_wexpand(a, b->top) == NULL) |
330 | return NULL; |
331 | |
332 | if (b->top > 0) |
333 | memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); |
334 | |
335 | a->neg = b->neg; |
336 | a->top = b->top; |
337 | a->flags |= b->flags & BN_FLG_FIXED_TOP; |
338 | bn_check_top(a); |
339 | return a; |
340 | } |
341 | |
342 | #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ |
343 | | BN_FLG_CONSTTIME \ |
344 | | BN_FLG_SECURE \ |
345 | | BN_FLG_FIXED_TOP)) |
346 | #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) |
347 | |
348 | void BN_swap(BIGNUM *a, BIGNUM *b) |
349 | { |
350 | int flags_old_a, flags_old_b; |
351 | BN_ULONG *tmp_d; |
352 | int tmp_top, tmp_dmax, tmp_neg; |
353 | |
354 | bn_check_top(a); |
355 | bn_check_top(b); |
356 | |
357 | flags_old_a = a->flags; |
358 | flags_old_b = b->flags; |
359 | |
360 | tmp_d = a->d; |
361 | tmp_top = a->top; |
362 | tmp_dmax = a->dmax; |
363 | tmp_neg = a->neg; |
364 | |
365 | a->d = b->d; |
366 | a->top = b->top; |
367 | a->dmax = b->dmax; |
368 | a->neg = b->neg; |
369 | |
370 | b->d = tmp_d; |
371 | b->top = tmp_top; |
372 | b->dmax = tmp_dmax; |
373 | b->neg = tmp_neg; |
374 | |
375 | a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); |
376 | b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); |
377 | bn_check_top(a); |
378 | bn_check_top(b); |
379 | } |
380 | |
381 | void BN_clear(BIGNUM *a) |
382 | { |
383 | if (a == NULL) |
384 | return; |
385 | bn_check_top(a); |
386 | if (a->d != NULL) |
387 | OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax); |
388 | a->neg = 0; |
389 | a->top = 0; |
390 | a->flags &= ~BN_FLG_FIXED_TOP; |
391 | } |
392 | |
393 | BN_ULONG BN_get_word(const BIGNUM *a) |
394 | { |
395 | if (a->top > 1) |
396 | return BN_MASK2; |
397 | else if (a->top == 1) |
398 | return a->d[0]; |
399 | /* a->top == 0 */ |
400 | return 0; |
401 | } |
402 | |
403 | int BN_set_word(BIGNUM *a, BN_ULONG w) |
404 | { |
405 | bn_check_top(a); |
406 | if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) |
407 | return 0; |
408 | a->neg = 0; |
409 | a->d[0] = w; |
410 | a->top = (w ? 1 : 0); |
411 | a->flags &= ~BN_FLG_FIXED_TOP; |
412 | bn_check_top(a); |
413 | return 1; |
414 | } |
415 | |
416 | BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
417 | { |
418 | unsigned int i, m; |
419 | unsigned int n; |
420 | BN_ULONG l; |
421 | BIGNUM *bn = NULL; |
422 | |
423 | if (ret == NULL) |
424 | ret = bn = BN_new(); |
425 | if (ret == NULL) |
426 | return NULL; |
427 | bn_check_top(ret); |
428 | /* Skip leading zero's. */ |
429 | for ( ; len > 0 && *s == 0; s++, len--) |
430 | continue; |
431 | n = len; |
432 | if (n == 0) { |
433 | ret->top = 0; |
434 | return ret; |
435 | } |
436 | i = ((n - 1) / BN_BYTES) + 1; |
437 | m = ((n - 1) % (BN_BYTES)); |
438 | if (bn_wexpand(ret, (int)i) == NULL) { |
439 | BN_free(bn); |
440 | return NULL; |
441 | } |
442 | ret->top = i; |
443 | ret->neg = 0; |
444 | l = 0; |
445 | while (n--) { |
446 | l = (l << 8L) | *(s++); |
447 | if (m-- == 0) { |
448 | ret->d[--i] = l; |
449 | l = 0; |
450 | m = BN_BYTES - 1; |
451 | } |
452 | } |
453 | /* |
454 | * need to call this due to clear byte at top if avoiding having the top |
455 | * bit set (-ve number) |
456 | */ |
457 | bn_correct_top(ret); |
458 | return ret; |
459 | } |
460 | |
461 | typedef enum {big, little} endianess_t; |
462 | |
463 | /* ignore negative */ |
464 | static |
465 | int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess) |
466 | { |
467 | int n; |
468 | size_t i, lasti, j, atop, mask; |
469 | BN_ULONG l; |
470 | |
471 | /* |
472 | * In case |a| is fixed-top, BN_num_bytes can return bogus length, |
473 | * but it's assumed that fixed-top inputs ought to be "nominated" |
474 | * even for padded output, so it works out... |
475 | */ |
476 | n = BN_num_bytes(a); |
477 | if (tolen == -1) { |
478 | tolen = n; |
479 | } else if (tolen < n) { /* uncommon/unlike case */ |
480 | BIGNUM temp = *a; |
481 | |
482 | bn_correct_top(&temp); |
483 | n = BN_num_bytes(&temp); |
484 | if (tolen < n) |
485 | return -1; |
486 | } |
487 | |
488 | /* Swipe through whole available data and don't give away padded zero. */ |
489 | atop = a->dmax * BN_BYTES; |
490 | if (atop == 0) { |
491 | OPENSSL_cleanse(to, tolen); |
492 | return tolen; |
493 | } |
494 | |
495 | lasti = atop - 1; |
496 | atop = a->top * BN_BYTES; |
497 | if (endianess == big) |
498 | to += tolen; /* start from the end of the buffer */ |
499 | for (i = 0, j = 0; j < (size_t)tolen; j++) { |
500 | unsigned char val; |
501 | l = a->d[i / BN_BYTES]; |
502 | mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); |
503 | val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); |
504 | if (endianess == big) |
505 | *--to = val; |
506 | else |
507 | *to++ = val; |
508 | i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ |
509 | } |
510 | |
511 | return tolen; |
512 | } |
513 | |
514 | int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) |
515 | { |
516 | if (tolen < 0) |
517 | return -1; |
518 | return bn2binpad(a, to, tolen, big); |
519 | } |
520 | |
521 | int BN_bn2bin(const BIGNUM *a, unsigned char *to) |
522 | { |
523 | return bn2binpad(a, to, -1, big); |
524 | } |
525 | |
526 | BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) |
527 | { |
528 | unsigned int i, m; |
529 | unsigned int n; |
530 | BN_ULONG l; |
531 | BIGNUM *bn = NULL; |
532 | |
533 | if (ret == NULL) |
534 | ret = bn = BN_new(); |
535 | if (ret == NULL) |
536 | return NULL; |
537 | bn_check_top(ret); |
538 | s += len; |
539 | /* Skip trailing zeroes. */ |
540 | for ( ; len > 0 && s[-1] == 0; s--, len--) |
541 | continue; |
542 | n = len; |
543 | if (n == 0) { |
544 | ret->top = 0; |
545 | return ret; |
546 | } |
547 | i = ((n - 1) / BN_BYTES) + 1; |
548 | m = ((n - 1) % (BN_BYTES)); |
549 | if (bn_wexpand(ret, (int)i) == NULL) { |
550 | BN_free(bn); |
551 | return NULL; |
552 | } |
553 | ret->top = i; |
554 | ret->neg = 0; |
555 | l = 0; |
556 | while (n--) { |
557 | s--; |
558 | l = (l << 8L) | *s; |
559 | if (m-- == 0) { |
560 | ret->d[--i] = l; |
561 | l = 0; |
562 | m = BN_BYTES - 1; |
563 | } |
564 | } |
565 | /* |
566 | * need to call this due to clear byte at top if avoiding having the top |
567 | * bit set (-ve number) |
568 | */ |
569 | bn_correct_top(ret); |
570 | return ret; |
571 | } |
572 | |
573 | int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) |
574 | { |
575 | if (tolen < 0) |
576 | return -1; |
577 | return bn2binpad(a, to, tolen, little); |
578 | } |
579 | |
580 | BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret) |
581 | { |
582 | #ifdef B_ENDIAN |
583 | return BN_bin2bn(s, len, ret); |
584 | #else |
585 | return BN_lebin2bn(s, len, ret); |
586 | #endif |
587 | } |
588 | |
589 | int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen) |
590 | { |
591 | #ifdef B_ENDIAN |
592 | return BN_bn2binpad(a, to, tolen); |
593 | #else |
594 | return BN_bn2lebinpad(a, to, tolen); |
595 | #endif |
596 | } |
597 | |
598 | int BN_ucmp(const BIGNUM *a, const BIGNUM *b) |
599 | { |
600 | int i; |
601 | BN_ULONG t1, t2, *ap, *bp; |
602 | |
603 | bn_check_top(a); |
604 | bn_check_top(b); |
605 | |
606 | i = a->top - b->top; |
607 | if (i != 0) |
608 | return i; |
609 | ap = a->d; |
610 | bp = b->d; |
611 | for (i = a->top - 1; i >= 0; i--) { |
612 | t1 = ap[i]; |
613 | t2 = bp[i]; |
614 | if (t1 != t2) |
615 | return ((t1 > t2) ? 1 : -1); |
616 | } |
617 | return 0; |
618 | } |
619 | |
620 | int BN_cmp(const BIGNUM *a, const BIGNUM *b) |
621 | { |
622 | int i; |
623 | int gt, lt; |
624 | BN_ULONG t1, t2; |
625 | |
626 | if ((a == NULL) || (b == NULL)) { |
627 | if (a != NULL) |
628 | return -1; |
629 | else if (b != NULL) |
630 | return 1; |
631 | else |
632 | return 0; |
633 | } |
634 | |
635 | bn_check_top(a); |
636 | bn_check_top(b); |
637 | |
638 | if (a->neg != b->neg) { |
639 | if (a->neg) |
640 | return -1; |
641 | else |
642 | return 1; |
643 | } |
644 | if (a->neg == 0) { |
645 | gt = 1; |
646 | lt = -1; |
647 | } else { |
648 | gt = -1; |
649 | lt = 1; |
650 | } |
651 | |
652 | if (a->top > b->top) |
653 | return gt; |
654 | if (a->top < b->top) |
655 | return lt; |
656 | for (i = a->top - 1; i >= 0; i--) { |
657 | t1 = a->d[i]; |
658 | t2 = b->d[i]; |
659 | if (t1 > t2) |
660 | return gt; |
661 | if (t1 < t2) |
662 | return lt; |
663 | } |
664 | return 0; |
665 | } |
666 | |
667 | int BN_set_bit(BIGNUM *a, int n) |
668 | { |
669 | int i, j, k; |
670 | |
671 | if (n < 0) |
672 | return 0; |
673 | |
674 | i = n / BN_BITS2; |
675 | j = n % BN_BITS2; |
676 | if (a->top <= i) { |
677 | if (bn_wexpand(a, i + 1) == NULL) |
678 | return 0; |
679 | for (k = a->top; k < i + 1; k++) |
680 | a->d[k] = 0; |
681 | a->top = i + 1; |
682 | a->flags &= ~BN_FLG_FIXED_TOP; |
683 | } |
684 | |
685 | a->d[i] |= (((BN_ULONG)1) << j); |
686 | bn_check_top(a); |
687 | return 1; |
688 | } |
689 | |
690 | int BN_clear_bit(BIGNUM *a, int n) |
691 | { |
692 | int i, j; |
693 | |
694 | bn_check_top(a); |
695 | if (n < 0) |
696 | return 0; |
697 | |
698 | i = n / BN_BITS2; |
699 | j = n % BN_BITS2; |
700 | if (a->top <= i) |
701 | return 0; |
702 | |
703 | a->d[i] &= (~(((BN_ULONG)1) << j)); |
704 | bn_correct_top(a); |
705 | return 1; |
706 | } |
707 | |
708 | int BN_is_bit_set(const BIGNUM *a, int n) |
709 | { |
710 | int i, j; |
711 | |
712 | bn_check_top(a); |
713 | if (n < 0) |
714 | return 0; |
715 | i = n / BN_BITS2; |
716 | j = n % BN_BITS2; |
717 | if (a->top <= i) |
718 | return 0; |
719 | return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); |
720 | } |
721 | |
722 | int BN_mask_bits(BIGNUM *a, int n) |
723 | { |
724 | int b, w; |
725 | |
726 | bn_check_top(a); |
727 | if (n < 0) |
728 | return 0; |
729 | |
730 | w = n / BN_BITS2; |
731 | b = n % BN_BITS2; |
732 | if (w >= a->top) |
733 | return 0; |
734 | if (b == 0) |
735 | a->top = w; |
736 | else { |
737 | a->top = w + 1; |
738 | a->d[w] &= ~(BN_MASK2 << b); |
739 | } |
740 | bn_correct_top(a); |
741 | return 1; |
742 | } |
743 | |
744 | void BN_set_negative(BIGNUM *a, int b) |
745 | { |
746 | if (b && !BN_is_zero(a)) |
747 | a->neg = 1; |
748 | else |
749 | a->neg = 0; |
750 | } |
751 | |
752 | int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) |
753 | { |
754 | int i; |
755 | BN_ULONG aa, bb; |
756 | |
757 | if (n == 0) |
758 | return 0; |
759 | |
760 | aa = a[n - 1]; |
761 | bb = b[n - 1]; |
762 | if (aa != bb) |
763 | return ((aa > bb) ? 1 : -1); |
764 | for (i = n - 2; i >= 0; i--) { |
765 | aa = a[i]; |
766 | bb = b[i]; |
767 | if (aa != bb) |
768 | return ((aa > bb) ? 1 : -1); |
769 | } |
770 | return 0; |
771 | } |
772 | |
773 | /* |
774 | * Here follows a specialised variants of bn_cmp_words(). It has the |
775 | * capability of performing the operation on arrays of different sizes. The |
776 | * sizes of those arrays is expressed through cl, which is the common length |
777 | * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the |
778 | * two lengths, calculated as len(a)-len(b). All lengths are the number of |
779 | * BN_ULONGs... |
780 | */ |
781 | |
782 | int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) |
783 | { |
784 | int n, i; |
785 | n = cl - 1; |
786 | |
787 | if (dl < 0) { |
788 | for (i = dl; i < 0; i++) { |
789 | if (b[n - i] != 0) |
790 | return -1; /* a < b */ |
791 | } |
792 | } |
793 | if (dl > 0) { |
794 | for (i = dl; i > 0; i--) { |
795 | if (a[n + i] != 0) |
796 | return 1; /* a > b */ |
797 | } |
798 | } |
799 | return bn_cmp_words(a, b, cl); |
800 | } |
801 | |
802 | /*- |
803 | * Constant-time conditional swap of a and b. |
804 | * a and b are swapped if condition is not 0. |
805 | * nwords is the number of words to swap. |
806 | * Assumes that at least nwords are allocated in both a and b. |
807 | * Assumes that no more than nwords are used by either a or b. |
808 | */ |
809 | void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) |
810 | { |
811 | BN_ULONG t; |
812 | int i; |
813 | |
814 | if (a == b) |
815 | return; |
816 | |
817 | bn_wcheck_size(a, nwords); |
818 | bn_wcheck_size(b, nwords); |
819 | |
820 | condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1; |
821 | |
822 | t = (a->top ^ b->top) & condition; |
823 | a->top ^= t; |
824 | b->top ^= t; |
825 | |
826 | t = (a->neg ^ b->neg) & condition; |
827 | a->neg ^= t; |
828 | b->neg ^= t; |
829 | |
830 | /*- |
831 | * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention |
832 | * is actually to treat it as it's read-only data, and some (if not most) |
833 | * of it does reside in read-only segment. In other words observation of |
834 | * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal |
835 | * condition. It would either cause SEGV or effectively cause data |
836 | * corruption. |
837 | * |
838 | * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be |
839 | * preserved. |
840 | * |
841 | * BN_FLG_SECURE: must be preserved, because it determines how x->d was |
842 | * allocated and hence how to free it. |
843 | * |
844 | * BN_FLG_CONSTTIME: sufficient to mask and swap |
845 | * |
846 | * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on |
847 | * the data, so the d array may be padded with additional 0 values (i.e. |
848 | * top could be greater than the minimal value that it could be). We should |
849 | * be swapping it |
850 | */ |
851 | |
852 | #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) |
853 | |
854 | t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; |
855 | a->flags ^= t; |
856 | b->flags ^= t; |
857 | |
858 | /* conditionally swap the data */ |
859 | for (i = 0; i < nwords; i++) { |
860 | t = (a->d[i] ^ b->d[i]) & condition; |
861 | a->d[i] ^= t; |
862 | b->d[i] ^= t; |
863 | } |
864 | } |
865 | |
866 | #undef BN_CONSTTIME_SWAP_FLAGS |
867 | |
868 | /* Bits of security, see SP800-57 */ |
869 | |
870 | int BN_security_bits(int L, int N) |
871 | { |
872 | int secbits, bits; |
873 | if (L >= 15360) |
874 | secbits = 256; |
875 | else if (L >= 7680) |
876 | secbits = 192; |
877 | else if (L >= 3072) |
878 | secbits = 128; |
879 | else if (L >= 2048) |
880 | secbits = 112; |
881 | else if (L >= 1024) |
882 | secbits = 80; |
883 | else |
884 | return 0; |
885 | if (N == -1) |
886 | return secbits; |
887 | bits = N / 2; |
888 | if (bits < 80) |
889 | return 0; |
890 | return bits >= secbits ? secbits : bits; |
891 | } |
892 | |
893 | void BN_zero_ex(BIGNUM *a) |
894 | { |
895 | a->neg = 0; |
896 | a->top = 0; |
897 | a->flags &= ~BN_FLG_FIXED_TOP; |
898 | } |
899 | |
900 | int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) |
901 | { |
902 | return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); |
903 | } |
904 | |
905 | int BN_is_zero(const BIGNUM *a) |
906 | { |
907 | return a->top == 0; |
908 | } |
909 | |
910 | int BN_is_one(const BIGNUM *a) |
911 | { |
912 | return BN_abs_is_word(a, 1) && !a->neg; |
913 | } |
914 | |
915 | int BN_is_word(const BIGNUM *a, const BN_ULONG w) |
916 | { |
917 | return BN_abs_is_word(a, w) && (!w || !a->neg); |
918 | } |
919 | |
920 | int BN_is_odd(const BIGNUM *a) |
921 | { |
922 | return (a->top > 0) && (a->d[0] & 1); |
923 | } |
924 | |
925 | int BN_is_negative(const BIGNUM *a) |
926 | { |
927 | return (a->neg != 0); |
928 | } |
929 | |
930 | int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, |
931 | BN_CTX *ctx) |
932 | { |
933 | return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx); |
934 | } |
935 | |
936 | void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) |
937 | { |
938 | dest->d = b->d; |
939 | dest->top = b->top; |
940 | dest->dmax = b->dmax; |
941 | dest->neg = b->neg; |
942 | dest->flags = ((dest->flags & BN_FLG_MALLOCED) |
943 | | (b->flags & ~BN_FLG_MALLOCED) |
944 | | BN_FLG_STATIC_DATA | flags); |
945 | } |
946 | |
947 | BN_GENCB *BN_GENCB_new(void) |
948 | { |
949 | BN_GENCB *ret; |
950 | |
951 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) { |
952 | BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE); |
953 | return NULL; |
954 | } |
955 | |
956 | return ret; |
957 | } |
958 | |
959 | void BN_GENCB_free(BN_GENCB *cb) |
960 | { |
961 | if (cb == NULL) |
962 | return; |
963 | OPENSSL_free(cb); |
964 | } |
965 | |
966 | void BN_set_flags(BIGNUM *b, int n) |
967 | { |
968 | b->flags |= n; |
969 | } |
970 | |
971 | int BN_get_flags(const BIGNUM *b, int n) |
972 | { |
973 | return b->flags & n; |
974 | } |
975 | |
976 | /* Populate a BN_GENCB structure with an "old"-style callback */ |
977 | void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *), |
978 | void *cb_arg) |
979 | { |
980 | BN_GENCB *tmp_gencb = gencb; |
981 | tmp_gencb->ver = 1; |
982 | tmp_gencb->arg = cb_arg; |
983 | tmp_gencb->cb.cb_1 = callback; |
984 | } |
985 | |
986 | /* Populate a BN_GENCB structure with a "new"-style callback */ |
987 | void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *), |
988 | void *cb_arg) |
989 | { |
990 | BN_GENCB *tmp_gencb = gencb; |
991 | tmp_gencb->ver = 2; |
992 | tmp_gencb->arg = cb_arg; |
993 | tmp_gencb->cb.cb_2 = callback; |
994 | } |
995 | |
996 | void *BN_GENCB_get_arg(BN_GENCB *cb) |
997 | { |
998 | return cb->arg; |
999 | } |
1000 | |
1001 | BIGNUM *bn_wexpand(BIGNUM *a, int words) |
1002 | { |
1003 | return (words <= a->dmax) ? a : bn_expand2(a, words); |
1004 | } |
1005 | |
1006 | void bn_correct_top(BIGNUM *a) |
1007 | { |
1008 | BN_ULONG *ftl; |
1009 | int tmp_top = a->top; |
1010 | |
1011 | if (tmp_top > 0) { |
1012 | for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) { |
1013 | ftl--; |
1014 | if (*ftl != 0) |
1015 | break; |
1016 | } |
1017 | a->top = tmp_top; |
1018 | } |
1019 | if (a->top == 0) |
1020 | a->neg = 0; |
1021 | a->flags &= ~BN_FLG_FIXED_TOP; |
1022 | bn_pollute(a); |
1023 | } |
1024 | |