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