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