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