[BN] harden `BN_copy()` against leaks from memory accesses
[openssl.git] / crypto / bn / bn_lib.c
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     int bn_words;
326
327     bn_check_top(b);
328
329     bn_words = BN_get_flags(b, BN_FLG_CONSTTIME) ? b->dmax : b->top;
330
331     if (a == b)
332         return a;
333     if (bn_wexpand(a, bn_words) == NULL)
334         return NULL;
335
336     if (b->top > 0)
337         memcpy(a->d, b->d, sizeof(b->d[0]) * bn_words);
338
339     a->neg = b->neg;
340     a->top = b->top;
341     a->flags |= b->flags & BN_FLG_FIXED_TOP;
342     bn_check_top(a);
343     return a;
344 }
345
346 #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
347                                     | BN_FLG_CONSTTIME   \
348                                     | BN_FLG_SECURE      \
349                                     | BN_FLG_FIXED_TOP))
350 #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
351
352 void BN_swap(BIGNUM *a, BIGNUM *b)
353 {
354     int flags_old_a, flags_old_b;
355     BN_ULONG *tmp_d;
356     int tmp_top, tmp_dmax, tmp_neg;
357
358     bn_check_top(a);
359     bn_check_top(b);
360
361     flags_old_a = a->flags;
362     flags_old_b = b->flags;
363
364     tmp_d = a->d;
365     tmp_top = a->top;
366     tmp_dmax = a->dmax;
367     tmp_neg = a->neg;
368
369     a->d = b->d;
370     a->top = b->top;
371     a->dmax = b->dmax;
372     a->neg = b->neg;
373
374     b->d = tmp_d;
375     b->top = tmp_top;
376     b->dmax = tmp_dmax;
377     b->neg = tmp_neg;
378
379     a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b);
380     b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a);
381     bn_check_top(a);
382     bn_check_top(b);
383 }
384
385 void BN_clear(BIGNUM *a)
386 {
387     if (a == NULL)
388         return;
389     bn_check_top(a);
390     if (a->d != NULL)
391         OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
392     a->neg = 0;
393     a->top = 0;
394     a->flags &= ~BN_FLG_FIXED_TOP;
395 }
396
397 BN_ULONG BN_get_word(const BIGNUM *a)
398 {
399     if (a->top > 1)
400         return BN_MASK2;
401     else if (a->top == 1)
402         return a->d[0];
403     /* a->top == 0 */
404     return 0;
405 }
406
407 int BN_set_word(BIGNUM *a, BN_ULONG w)
408 {
409     bn_check_top(a);
410     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
411         return 0;
412     a->neg = 0;
413     a->d[0] = w;
414     a->top = (w ? 1 : 0);
415     a->flags &= ~BN_FLG_FIXED_TOP;
416     bn_check_top(a);
417     return 1;
418 }
419
420 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
421 {
422     unsigned int i, m;
423     unsigned int n;
424     BN_ULONG l;
425     BIGNUM *bn = NULL;
426
427     if (ret == NULL)
428         ret = bn = BN_new();
429     if (ret == NULL)
430         return NULL;
431     bn_check_top(ret);
432     /* Skip leading zero's. */
433     for ( ; len > 0 && *s == 0; s++, len--)
434         continue;
435     n = len;
436     if (n == 0) {
437         ret->top = 0;
438         return ret;
439     }
440     i = ((n - 1) / BN_BYTES) + 1;
441     m = ((n - 1) % (BN_BYTES));
442     if (bn_wexpand(ret, (int)i) == NULL) {
443         BN_free(bn);
444         return NULL;
445     }
446     ret->top = i;
447     ret->neg = 0;
448     l = 0;
449     while (n--) {
450         l = (l << 8L) | *(s++);
451         if (m-- == 0) {
452             ret->d[--i] = l;
453             l = 0;
454             m = BN_BYTES - 1;
455         }
456     }
457     /*
458      * need to call this due to clear byte at top if avoiding having the top
459      * bit set (-ve number)
460      */
461     bn_correct_top(ret);
462     return ret;
463 }
464
465 typedef enum {big, little} endianess_t;
466
467 /* ignore negative */
468 static
469 int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess)
470 {
471     int n;
472     size_t i, lasti, j, atop, mask;
473     BN_ULONG l;
474
475     /*
476      * In case |a| is fixed-top, BN_num_bytes can return bogus length,
477      * but it's assumed that fixed-top inputs ought to be "nominated"
478      * even for padded output, so it works out...
479      */
480     n = BN_num_bytes(a);
481     if (tolen == -1) {
482         tolen = n;
483     } else if (tolen < n) {     /* uncommon/unlike case */
484         BIGNUM temp = *a;
485
486         bn_correct_top(&temp);
487         n = BN_num_bytes(&temp);
488         if (tolen < n)
489             return -1;
490     }
491
492     /* Swipe through whole available data and don't give away padded zero. */
493     atop = a->dmax * BN_BYTES;
494     if (atop == 0) {
495         OPENSSL_cleanse(to, tolen);
496         return tolen;
497     }
498
499     lasti = atop - 1;
500     atop = a->top * BN_BYTES;
501     if (endianess == big)
502         to += tolen; /* start from the end of the buffer */
503     for (i = 0, j = 0; j < (size_t)tolen; j++) {
504         unsigned char val;
505         l = a->d[i / BN_BYTES];
506         mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
507         val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
508         if (endianess == big)
509             *--to = val;
510         else
511             *to++ = val;
512         i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
513     }
514
515     return tolen;
516 }
517
518 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
519 {
520     if (tolen < 0)
521         return -1;
522     return bn2binpad(a, to, tolen, big);
523 }
524
525 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
526 {
527     return bn2binpad(a, to, -1, big);
528 }
529
530 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
531 {
532     unsigned int i, m;
533     unsigned int n;
534     BN_ULONG l;
535     BIGNUM *bn = NULL;
536
537     if (ret == NULL)
538         ret = bn = BN_new();
539     if (ret == NULL)
540         return NULL;
541     bn_check_top(ret);
542     s += len;
543     /* Skip trailing zeroes. */
544     for ( ; len > 0 && s[-1] == 0; s--, len--)
545         continue;
546     n = len;
547     if (n == 0) {
548         ret->top = 0;
549         return ret;
550     }
551     i = ((n - 1) / BN_BYTES) + 1;
552     m = ((n - 1) % (BN_BYTES));
553     if (bn_wexpand(ret, (int)i) == NULL) {
554         BN_free(bn);
555         return NULL;
556     }
557     ret->top = i;
558     ret->neg = 0;
559     l = 0;
560     while (n--) {
561         s--;
562         l = (l << 8L) | *s;
563         if (m-- == 0) {
564             ret->d[--i] = l;
565             l = 0;
566             m = BN_BYTES - 1;
567         }
568     }
569     /*
570      * need to call this due to clear byte at top if avoiding having the top
571      * bit set (-ve number)
572      */
573     bn_correct_top(ret);
574     return ret;
575 }
576
577 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
578 {
579     if (tolen < 0)
580         return -1;
581     return bn2binpad(a, to, tolen, little);
582 }
583
584 BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret)
585 {
586 #ifdef B_ENDIAN
587     return BN_bin2bn(s, len, ret);
588 #else
589     return BN_lebin2bn(s, len, ret);
590 #endif
591 }
592
593 int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen)
594 {
595 #ifdef B_ENDIAN
596     return BN_bn2binpad(a, to, tolen);
597 #else
598     return BN_bn2lebinpad(a, to, tolen);
599 #endif
600 }
601
602 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
603 {
604     int i;
605     BN_ULONG t1, t2, *ap, *bp;
606
607     bn_check_top(a);
608     bn_check_top(b);
609
610     i = a->top - b->top;
611     if (i != 0)
612         return i;
613     ap = a->d;
614     bp = b->d;
615     for (i = a->top - 1; i >= 0; i--) {
616         t1 = ap[i];
617         t2 = bp[i];
618         if (t1 != t2)
619             return ((t1 > t2) ? 1 : -1);
620     }
621     return 0;
622 }
623
624 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
625 {
626     int i;
627     int gt, lt;
628     BN_ULONG t1, t2;
629
630     if ((a == NULL) || (b == NULL)) {
631         if (a != NULL)
632             return -1;
633         else if (b != NULL)
634             return 1;
635         else
636             return 0;
637     }
638
639     bn_check_top(a);
640     bn_check_top(b);
641
642     if (a->neg != b->neg) {
643         if (a->neg)
644             return -1;
645         else
646             return 1;
647     }
648     if (a->neg == 0) {
649         gt = 1;
650         lt = -1;
651     } else {
652         gt = -1;
653         lt = 1;
654     }
655
656     if (a->top > b->top)
657         return gt;
658     if (a->top < b->top)
659         return lt;
660     for (i = a->top - 1; i >= 0; i--) {
661         t1 = a->d[i];
662         t2 = b->d[i];
663         if (t1 > t2)
664             return gt;
665         if (t1 < t2)
666             return lt;
667     }
668     return 0;
669 }
670
671 int BN_set_bit(BIGNUM *a, int n)
672 {
673     int i, j, k;
674
675     if (n < 0)
676         return 0;
677
678     i = n / BN_BITS2;
679     j = n % BN_BITS2;
680     if (a->top <= i) {
681         if (bn_wexpand(a, i + 1) == NULL)
682             return 0;
683         for (k = a->top; k < i + 1; k++)
684             a->d[k] = 0;
685         a->top = i + 1;
686         a->flags &= ~BN_FLG_FIXED_TOP;
687     }
688
689     a->d[i] |= (((BN_ULONG)1) << j);
690     bn_check_top(a);
691     return 1;
692 }
693
694 int BN_clear_bit(BIGNUM *a, int n)
695 {
696     int i, j;
697
698     bn_check_top(a);
699     if (n < 0)
700         return 0;
701
702     i = n / BN_BITS2;
703     j = n % BN_BITS2;
704     if (a->top <= i)
705         return 0;
706
707     a->d[i] &= (~(((BN_ULONG)1) << j));
708     bn_correct_top(a);
709     return 1;
710 }
711
712 int BN_is_bit_set(const BIGNUM *a, int n)
713 {
714     int i, j;
715
716     bn_check_top(a);
717     if (n < 0)
718         return 0;
719     i = n / BN_BITS2;
720     j = n % BN_BITS2;
721     if (a->top <= i)
722         return 0;
723     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
724 }
725
726 int BN_mask_bits(BIGNUM *a, int n)
727 {
728     int b, w;
729
730     bn_check_top(a);
731     if (n < 0)
732         return 0;
733
734     w = n / BN_BITS2;
735     b = n % BN_BITS2;
736     if (w >= a->top)
737         return 0;
738     if (b == 0)
739         a->top = w;
740     else {
741         a->top = w + 1;
742         a->d[w] &= ~(BN_MASK2 << b);
743     }
744     bn_correct_top(a);
745     return 1;
746 }
747
748 void BN_set_negative(BIGNUM *a, int b)
749 {
750     if (b && !BN_is_zero(a))
751         a->neg = 1;
752     else
753         a->neg = 0;
754 }
755
756 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
757 {
758     int i;
759     BN_ULONG aa, bb;
760
761     if (n == 0)
762         return 0;
763
764     aa = a[n - 1];
765     bb = b[n - 1];
766     if (aa != bb)
767         return ((aa > bb) ? 1 : -1);
768     for (i = n - 2; i >= 0; i--) {
769         aa = a[i];
770         bb = b[i];
771         if (aa != bb)
772             return ((aa > bb) ? 1 : -1);
773     }
774     return 0;
775 }
776
777 /*
778  * Here follows a specialised variants of bn_cmp_words().  It has the
779  * capability of performing the operation on arrays of different sizes. The
780  * sizes of those arrays is expressed through cl, which is the common length
781  * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
782  * two lengths, calculated as len(a)-len(b). All lengths are the number of
783  * BN_ULONGs...
784  */
785
786 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
787 {
788     int n, i;
789     n = cl - 1;
790
791     if (dl < 0) {
792         for (i = dl; i < 0; i++) {
793             if (b[n - i] != 0)
794                 return -1;      /* a < b */
795         }
796     }
797     if (dl > 0) {
798         for (i = dl; i > 0; i--) {
799             if (a[n + i] != 0)
800                 return 1;       /* a > b */
801         }
802     }
803     return bn_cmp_words(a, b, cl);
804 }
805
806 /*-
807  * Constant-time conditional swap of a and b.
808  * a and b are swapped if condition is not 0.
809  * nwords is the number of words to swap.
810  * Assumes that at least nwords are allocated in both a and b.
811  * Assumes that no more than nwords are used by either a or b.
812  */
813 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
814 {
815     BN_ULONG t;
816     int i;
817
818     if (a == b)
819         return;
820
821     bn_wcheck_size(a, nwords);
822     bn_wcheck_size(b, nwords);
823
824     condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1;
825
826     t = (a->top ^ b->top) & condition;
827     a->top ^= t;
828     b->top ^= t;
829
830     t = (a->neg ^ b->neg) & condition;
831     a->neg ^= t;
832     b->neg ^= t;
833
834     /*-
835      * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention
836      * is actually to treat it as it's read-only data, and some (if not most)
837      * of it does reside in read-only segment. In other words observation of
838      * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal
839      * condition. It would either cause SEGV or effectively cause data
840      * corruption.
841      *
842      * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be
843      * preserved.
844      *
845      * BN_FLG_SECURE: must be preserved, because it determines how x->d was
846      * allocated and hence how to free it.
847      *
848      * BN_FLG_CONSTTIME: sufficient to mask and swap
849      *
850      * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on
851      * the data, so the d array may be padded with additional 0 values (i.e.
852      * top could be greater than the minimal value that it could be). We should
853      * be swapping it
854      */
855
856 #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP)
857
858     t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition;
859     a->flags ^= t;
860     b->flags ^= t;
861
862     /* conditionally swap the data */
863     for (i = 0; i < nwords; i++) {
864         t = (a->d[i] ^ b->d[i]) & condition;
865         a->d[i] ^= t;
866         b->d[i] ^= t;
867     }
868 }
869
870 #undef BN_CONSTTIME_SWAP_FLAGS
871
872 /* Bits of security, see SP800-57 */
873
874 int BN_security_bits(int L, int N)
875 {
876     int secbits, bits;
877     if (L >= 15360)
878         secbits = 256;
879     else if (L >= 7680)
880         secbits = 192;
881     else if (L >= 3072)
882         secbits = 128;
883     else if (L >= 2048)
884         secbits = 112;
885     else if (L >= 1024)
886         secbits = 80;
887     else
888         return 0;
889     if (N == -1)
890         return secbits;
891     bits = N / 2;
892     if (bits < 80)
893         return 0;
894     return bits >= secbits ? secbits : bits;
895 }
896
897 void BN_zero_ex(BIGNUM *a)
898 {
899     a->neg = 0;
900     a->top = 0;
901     a->flags &= ~BN_FLG_FIXED_TOP;
902 }
903
904 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
905 {
906     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
907 }
908
909 int BN_is_zero(const BIGNUM *a)
910 {
911     return a->top == 0;
912 }
913
914 int BN_is_one(const BIGNUM *a)
915 {
916     return BN_abs_is_word(a, 1) && !a->neg;
917 }
918
919 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
920 {
921     return BN_abs_is_word(a, w) && (!w || !a->neg);
922 }
923
924 int BN_is_odd(const BIGNUM *a)
925 {
926     return (a->top > 0) && (a->d[0] & 1);
927 }
928
929 int BN_is_negative(const BIGNUM *a)
930 {
931     return (a->neg != 0);
932 }
933
934 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
935                      BN_CTX *ctx)
936 {
937     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
938 }
939
940 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
941 {
942     dest->d = b->d;
943     dest->top = b->top;
944     dest->dmax = b->dmax;
945     dest->neg = b->neg;
946     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
947                    | (b->flags & ~BN_FLG_MALLOCED)
948                    | BN_FLG_STATIC_DATA | flags);
949 }
950
951 BN_GENCB *BN_GENCB_new(void)
952 {
953     BN_GENCB *ret;
954
955     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
956         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
957         return NULL;
958     }
959
960     return ret;
961 }
962
963 void BN_GENCB_free(BN_GENCB *cb)
964 {
965     if (cb == NULL)
966         return;
967     OPENSSL_free(cb);
968 }
969
970 void BN_set_flags(BIGNUM *b, int n)
971 {
972     b->flags |= n;
973 }
974
975 int BN_get_flags(const BIGNUM *b, int n)
976 {
977     return b->flags & n;
978 }
979
980 /* Populate a BN_GENCB structure with an "old"-style callback */
981 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
982                       void *cb_arg)
983 {
984     BN_GENCB *tmp_gencb = gencb;
985     tmp_gencb->ver = 1;
986     tmp_gencb->arg = cb_arg;
987     tmp_gencb->cb.cb_1 = callback;
988 }
989
990 /* Populate a BN_GENCB structure with a "new"-style callback */
991 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
992                   void *cb_arg)
993 {
994     BN_GENCB *tmp_gencb = gencb;
995     tmp_gencb->ver = 2;
996     tmp_gencb->arg = cb_arg;
997     tmp_gencb->cb.cb_2 = callback;
998 }
999
1000 void *BN_GENCB_get_arg(BN_GENCB *cb)
1001 {
1002     return cb->arg;
1003 }
1004
1005 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1006 {
1007     return (words <= a->dmax) ? a : bn_expand2(a, words);
1008 }
1009
1010 void bn_correct_top(BIGNUM *a)
1011 {
1012     BN_ULONG *ftl;
1013     int tmp_top = a->top;
1014
1015     if (tmp_top > 0) {
1016         for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
1017             ftl--;
1018             if (*ftl != 0)
1019                 break;
1020         }
1021         a->top = tmp_top;
1022     }
1023     if (a->top == 0)
1024         a->neg = 0;
1025     a->flags &= ~BN_FLG_FIXED_TOP;
1026     bn_pollute(a);
1027 }