2ca6beab364d801df75c2230572668644941d68f
[openssl.git] / crypto / bn / bn_lib.c
1 /* crypto/bn/bn_lib.c */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3  * All rights reserved.
4  *
5  * This package is an SSL implementation written
6  * by Eric Young (eay@cryptsoft.com).
7  * The implementation was written so as to conform with Netscapes SSL.
8  *
9  * This library is free for commercial and non-commercial use as long as
10  * the following conditions are aheared to.  The following conditions
11  * apply to all code found in this distribution, be it the RC4, RSA,
12  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13  * included with this distribution is covered by the same copyright terms
14  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15  *
16  * Copyright remains Eric Young's, and as such any Copyright notices in
17  * the code are not to be removed.
18  * If this package is used in a product, Eric Young should be given attribution
19  * as the author of the parts of the library used.
20  * This can be in the form of a textual message at program startup or
21  * in documentation (online or textual) provided with the package.
22  *
23  * Redistribution and use in source and binary forms, with or without
24  * modification, are permitted provided that the following conditions
25  * are met:
26  * 1. Redistributions of source code must retain the copyright
27  *    notice, this list of conditions and the following disclaimer.
28  * 2. Redistributions in binary form must reproduce the above copyright
29  *    notice, this list of conditions and the following disclaimer in the
30  *    documentation and/or other materials provided with the distribution.
31  * 3. All advertising materials mentioning features or use of this software
32  *    must display the following acknowledgement:
33  *    "This product includes cryptographic software written by
34  *     Eric Young (eay@cryptsoft.com)"
35  *    The word 'cryptographic' can be left out if the rouines from the library
36  *    being used are not cryptographic related :-).
37  * 4. If you include any Windows specific code (or a derivative thereof) from
38  *    the apps directory (application code) you must include an acknowledgement:
39  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40  *
41  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51  * SUCH DAMAGE.
52  *
53  * The licence and distribution terms for any publically available version or
54  * derivative of this code cannot be changed.  i.e. this code cannot simply be
55  * copied and put under another distribution licence
56  * [including the GNU Public Licence.]
57  */
58
59 #ifndef BN_DEBUG
60 # undef NDEBUG                  /* avoid conflicting definitions */
61 # define NDEBUG
62 #endif
63
64 #include <assert.h>
65 #include <limits.h>
66 #include "internal/cryptlib.h"
67 #include "bn_lcl.h"
68
69 /* This stuff appears to be completely unused, so is deprecated */
70 #ifndef OPENSSL_NO_DEPRECATED
71 /*-
72  * For a 32 bit machine
73  * 2 -   4 ==  128
74  * 3 -   8 ==  256
75  * 4 -  16 ==  512
76  * 5 -  32 == 1024
77  * 6 -  64 == 2048
78  * 7 - 128 == 4096
79  * 8 - 256 == 8192
80  */
81 static int bn_limit_bits = 0;
82 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
83 static int bn_limit_bits_low = 0;
84 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
85 static int bn_limit_bits_high = 0;
86 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
87 static int bn_limit_bits_mont = 0;
88 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
89
90 void BN_set_params(int mult, int high, int low, int mont)
91 {
92     if (mult >= 0) {
93         if (mult > (int)(sizeof(int) * 8) - 1)
94             mult = sizeof(int) * 8 - 1;
95         bn_limit_bits = mult;
96         bn_limit_num = 1 << mult;
97     }
98     if (high >= 0) {
99         if (high > (int)(sizeof(int) * 8) - 1)
100             high = sizeof(int) * 8 - 1;
101         bn_limit_bits_high = high;
102         bn_limit_num_high = 1 << high;
103     }
104     if (low >= 0) {
105         if (low > (int)(sizeof(int) * 8) - 1)
106             low = sizeof(int) * 8 - 1;
107         bn_limit_bits_low = low;
108         bn_limit_num_low = 1 << low;
109     }
110     if (mont >= 0) {
111         if (mont > (int)(sizeof(int) * 8) - 1)
112             mont = sizeof(int) * 8 - 1;
113         bn_limit_bits_mont = mont;
114         bn_limit_num_mont = 1 << mont;
115     }
116 }
117
118 int BN_get_params(int which)
119 {
120     if (which == 0)
121         return (bn_limit_bits);
122     else if (which == 1)
123         return (bn_limit_bits_high);
124     else if (which == 2)
125         return (bn_limit_bits_low);
126     else if (which == 3)
127         return (bn_limit_bits_mont);
128     else
129         return (0);
130 }
131 #endif
132
133 const BIGNUM *BN_value_one(void)
134 {
135     static const BN_ULONG data_one = 1L;
136     static const BIGNUM const_one =
137         { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
138
139     return (&const_one);
140 }
141
142 int BN_num_bits_word(BN_ULONG l)
143 {
144     static const unsigned char bits[256] = {
145         0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
146         5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
147         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
148         6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
149         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
150         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
151         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
152         7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
153         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
154         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
155         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
156         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
157         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
158         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
159         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
160         8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
161     };
162
163 #if defined(SIXTY_FOUR_BIT_LONG)
164     if (l & 0xffffffff00000000L) {
165         if (l & 0xffff000000000000L) {
166             if (l & 0xff00000000000000L) {
167                 return (bits[(int)(l >> 56)] + 56);
168             } else
169                 return (bits[(int)(l >> 48)] + 48);
170         } else {
171             if (l & 0x0000ff0000000000L) {
172                 return (bits[(int)(l >> 40)] + 40);
173             } else
174                 return (bits[(int)(l >> 32)] + 32);
175         }
176     } else
177 #else
178 # ifdef SIXTY_FOUR_BIT
179     if (l & 0xffffffff00000000LL) {
180         if (l & 0xffff000000000000LL) {
181             if (l & 0xff00000000000000LL) {
182                 return (bits[(int)(l >> 56)] + 56);
183             } else
184                 return (bits[(int)(l >> 48)] + 48);
185         } else {
186             if (l & 0x0000ff0000000000LL) {
187                 return (bits[(int)(l >> 40)] + 40);
188             } else
189                 return (bits[(int)(l >> 32)] + 32);
190         }
191     } else
192 # endif
193 #endif
194     {
195 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
196         if (l & 0xffff0000L) {
197             if (l & 0xff000000L)
198                 return (bits[(int)(l >> 24L)] + 24);
199             else
200                 return (bits[(int)(l >> 16L)] + 16);
201         } else
202 #endif
203         {
204 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
205             if (l & 0xff00L)
206                 return (bits[(int)(l >> 8)] + 8);
207             else
208 #endif
209                 return (bits[(int)(l)]);
210         }
211     }
212 }
213
214 int BN_num_bits(const BIGNUM *a)
215 {
216     int i = a->top - 1;
217     bn_check_top(a);
218
219     if (BN_is_zero(a))
220         return 0;
221     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
222 }
223
224 static void bn_free_d(BIGNUM *a)
225 {
226     if (BN_get_flags(a,BN_FLG_SECURE))
227         OPENSSL_secure_free(a->d);
228     else
229         OPENSSL_free(a->d);
230 }
231
232
233 void BN_clear_free(BIGNUM *a)
234 {
235     int i;
236
237     if (a == NULL)
238         return;
239     bn_check_top(a);
240     if (a->d != NULL) {
241         OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
242         if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
243             bn_free_d(a);
244     }
245     i = BN_get_flags(a, BN_FLG_MALLOCED);
246     OPENSSL_cleanse(a, sizeof(*a));
247     if (i)
248         OPENSSL_free(a);
249 }
250
251 void BN_free(BIGNUM *a)
252 {
253     if (a == NULL)
254         return;
255     bn_check_top(a);
256     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
257         bn_free_d(a);
258     if (a->flags & BN_FLG_MALLOCED)
259         OPENSSL_free(a);
260     else {
261 #ifndef OPENSSL_NO_DEPRECATED
262         a->flags |= BN_FLG_FREE;
263 #endif
264         a->d = NULL;
265     }
266 }
267
268 void BN_init(BIGNUM *a)
269 {
270     memset(a, 0, sizeof(*a));
271     bn_check_top(a);
272 }
273
274 BIGNUM *BN_new(void)
275 {
276     BIGNUM *ret;
277
278     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
279         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
280         return (NULL);
281     }
282     ret->flags = BN_FLG_MALLOCED;
283     ret->top = 0;
284     ret->neg = 0;
285     ret->dmax = 0;
286     ret->d = NULL;
287     bn_check_top(ret);
288     return (ret);
289 }
290
291  BIGNUM *BN_secure_new(void)
292  {
293      BIGNUM *ret = BN_new();
294      if (ret)
295          ret->flags |= BN_FLG_SECURE;
296      return (ret);
297  }
298
299 /* This is used both by bn_expand2() and bn_dup_expand() */
300 /* The caller MUST check that words > b->dmax before calling this */
301 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
302 {
303     BN_ULONG *A, *a = NULL;
304     const BN_ULONG *B;
305     int i;
306
307     bn_check_top(b);
308
309     if (words > (INT_MAX / (4 * BN_BITS2))) {
310         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
311         return NULL;
312     }
313     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
314         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
315         return (NULL);
316     }
317     if (BN_get_flags(b,BN_FLG_SECURE))
318         a = A = OPENSSL_secure_malloc(words * sizeof(*a));
319     else
320         a = A = OPENSSL_malloc(words * sizeof(*a));
321     if (A == NULL) {
322         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
323         return (NULL);
324     }
325 #ifdef PURIFY
326     /*
327      * Valgrind complains in BN_consttime_swap because we process the whole
328      * array even if it's not initialised yet. This doesn't matter in that
329      * function - what's important is constant time operation (we're not
330      * actually going to use the data)
331      */
332     memset(a, 0, sizeof(*a) * words);
333 #endif
334
335 #if 1
336     B = b->d;
337     /* Check if the previous number needs to be copied */
338     if (B != NULL) {
339         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
340             /*
341              * The fact that the loop is unrolled
342              * 4-wise is a tribute to Intel. It's
343              * the one that doesn't have enough
344              * registers to accomodate more data.
345              * I'd unroll it 8-wise otherwise:-)
346              *
347              *              <appro@fy.chalmers.se>
348              */
349             BN_ULONG a0, a1, a2, a3;
350             a0 = B[0];
351             a1 = B[1];
352             a2 = B[2];
353             a3 = B[3];
354             A[0] = a0;
355             A[1] = a1;
356             A[2] = a2;
357             A[3] = a3;
358         }
359         /*
360          * workaround for ultrix cc: without 'case 0', the optimizer does
361          * the switch table by doing a=top&3; a--; goto jump_table[a];
362          * which fails for top== 0
363          */
364         switch (b->top & 3) {
365         case 3:
366             A[2] = B[2];
367         case 2:
368             A[1] = B[1];
369         case 1:
370             A[0] = B[0];
371         case 0:
372             ;
373         }
374     }
375 #else
376     memset(A, 0, sizeof(*A) * words);
377     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
378 #endif
379
380     return (a);
381 }
382
383 /*
384  * This is an internal function that should not be used in applications. It
385  * ensures that 'b' has enough room for a 'words' word number and initialises
386  * any unused part of b->d with leading zeros. It is mostly used by the
387  * various BIGNUM routines. If there is an error, NULL is returned. If not,
388  * 'b' is returned.
389  */
390
391 BIGNUM *bn_expand2(BIGNUM *b, int words)
392 {
393     bn_check_top(b);
394
395     if (words > b->dmax) {
396         BN_ULONG *a = bn_expand_internal(b, words);
397         if (!a)
398             return NULL;
399         if (b->d) {
400             OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
401             bn_free_d(b);
402         }
403         b->d = a;
404         b->dmax = words;
405     }
406
407     bn_check_top(b);
408     return b;
409 }
410
411 BIGNUM *BN_dup(const BIGNUM *a)
412 {
413     BIGNUM *t;
414
415     if (a == NULL)
416         return NULL;
417     bn_check_top(a);
418
419     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
420     if (t == NULL)
421         return NULL;
422     if (!BN_copy(t, a)) {
423         BN_free(t);
424         return NULL;
425     }
426     bn_check_top(t);
427     return t;
428 }
429
430 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
431 {
432     int i;
433     BN_ULONG *A;
434     const BN_ULONG *B;
435
436     bn_check_top(b);
437
438     if (a == b)
439         return (a);
440     if (bn_wexpand(a, b->top) == NULL)
441         return (NULL);
442
443 #if 1
444     A = a->d;
445     B = b->d;
446     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
447         BN_ULONG a0, a1, a2, a3;
448         a0 = B[0];
449         a1 = B[1];
450         a2 = B[2];
451         a3 = B[3];
452         A[0] = a0;
453         A[1] = a1;
454         A[2] = a2;
455         A[3] = a3;
456     }
457     /* ultrix cc workaround, see comments in bn_expand_internal */
458     switch (b->top & 3) {
459     case 3:
460         A[2] = B[2];
461     case 2:
462         A[1] = B[1];
463     case 1:
464         A[0] = B[0];
465     case 0:;
466     }
467 #else
468     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
469 #endif
470
471     a->top = b->top;
472     a->neg = b->neg;
473     bn_check_top(a);
474     return (a);
475 }
476
477 void BN_swap(BIGNUM *a, BIGNUM *b)
478 {
479     int flags_old_a, flags_old_b;
480     BN_ULONG *tmp_d;
481     int tmp_top, tmp_dmax, tmp_neg;
482
483     bn_check_top(a);
484     bn_check_top(b);
485
486     flags_old_a = a->flags;
487     flags_old_b = b->flags;
488
489     tmp_d = a->d;
490     tmp_top = a->top;
491     tmp_dmax = a->dmax;
492     tmp_neg = a->neg;
493
494     a->d = b->d;
495     a->top = b->top;
496     a->dmax = b->dmax;
497     a->neg = b->neg;
498
499     b->d = tmp_d;
500     b->top = tmp_top;
501     b->dmax = tmp_dmax;
502     b->neg = tmp_neg;
503
504     a->flags =
505         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
506     b->flags =
507         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
508     bn_check_top(a);
509     bn_check_top(b);
510 }
511
512 void BN_clear(BIGNUM *a)
513 {
514     bn_check_top(a);
515     if (a->d != NULL)
516         memset(a->d, 0, sizeof(*a->d) * a->dmax);
517     a->top = 0;
518     a->neg = 0;
519 }
520
521 BN_ULONG BN_get_word(const BIGNUM *a)
522 {
523     if (a->top > 1)
524         return BN_MASK2;
525     else if (a->top == 1)
526         return a->d[0];
527     /* a->top == 0 */
528     return 0;
529 }
530
531 int BN_set_word(BIGNUM *a, BN_ULONG w)
532 {
533     bn_check_top(a);
534     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
535         return (0);
536     a->neg = 0;
537     a->d[0] = w;
538     a->top = (w ? 1 : 0);
539     bn_check_top(a);
540     return (1);
541 }
542
543 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
544 {
545     unsigned int i, m;
546     unsigned int n;
547     BN_ULONG l;
548     BIGNUM *bn = NULL;
549
550     if (ret == NULL)
551         ret = bn = BN_new();
552     if (ret == NULL)
553         return (NULL);
554     bn_check_top(ret);
555     /* Skip leading zero's. */
556     for ( ; len > 0 && *s == 0; s++, len--)
557         continue;
558     n = len;
559     if (n == 0) {
560         ret->top = 0;
561         return (ret);
562     }
563     i = ((n - 1) / BN_BYTES) + 1;
564     m = ((n - 1) % (BN_BYTES));
565     if (bn_wexpand(ret, (int)i) == NULL) {
566         BN_free(bn);
567         return NULL;
568     }
569     ret->top = i;
570     ret->neg = 0;
571     l = 0;
572     while (n--) {
573         l = (l << 8L) | *(s++);
574         if (m-- == 0) {
575             ret->d[--i] = l;
576             l = 0;
577             m = BN_BYTES - 1;
578         }
579     }
580     /*
581      * need to call this due to clear byte at top if avoiding having the top
582      * bit set (-ve number)
583      */
584     bn_correct_top(ret);
585     return (ret);
586 }
587
588 /* ignore negative */
589 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
590 {
591     int n, i;
592     BN_ULONG l;
593
594     bn_check_top(a);
595     n = i = BN_num_bytes(a);
596     while (i--) {
597         l = a->d[i / BN_BYTES];
598         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
599     }
600     return (n);
601 }
602
603 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
604 {
605     int i;
606     BN_ULONG t1, t2, *ap, *bp;
607
608     bn_check_top(a);
609     bn_check_top(b);
610
611     i = a->top - b->top;
612     if (i != 0)
613         return (i);
614     ap = a->d;
615     bp = b->d;
616     for (i = a->top - 1; i >= 0; i--) {
617         t1 = ap[i];
618         t2 = bp[i];
619         if (t1 != t2)
620             return ((t1 > t2) ? 1 : -1);
621     }
622     return (0);
623 }
624
625 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
626 {
627     int i;
628     int gt, lt;
629     BN_ULONG t1, t2;
630
631     if ((a == NULL) || (b == NULL)) {
632         if (a != NULL)
633             return (-1);
634         else if (b != NULL)
635             return (1);
636         else
637             return (0);
638     }
639
640     bn_check_top(a);
641     bn_check_top(b);
642
643     if (a->neg != b->neg) {
644         if (a->neg)
645             return (-1);
646         else
647             return (1);
648     }
649     if (a->neg == 0) {
650         gt = 1;
651         lt = -1;
652     } else {
653         gt = -1;
654         lt = 1;
655     }
656
657     if (a->top > b->top)
658         return (gt);
659     if (a->top < b->top)
660         return (lt);
661     for (i = a->top - 1; i >= 0; i--) {
662         t1 = a->d[i];
663         t2 = b->d[i];
664         if (t1 > t2)
665             return (gt);
666         if (t1 < t2)
667             return (lt);
668     }
669     return (0);
670 }
671
672 int BN_set_bit(BIGNUM *a, int n)
673 {
674     int i, j, k;
675
676     if (n < 0)
677         return 0;
678
679     i = n / BN_BITS2;
680     j = n % BN_BITS2;
681     if (a->top <= i) {
682         if (bn_wexpand(a, i + 1) == NULL)
683             return (0);
684         for (k = a->top; k < i + 1; k++)
685             a->d[k] = 0;
686         a->top = i + 1;
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     aa = a[n - 1];
762     bb = b[n - 1];
763     if (aa != bb)
764         return ((aa > bb) ? 1 : -1);
765     for (i = n - 2; i >= 0; i--) {
766         aa = a[i];
767         bb = b[i];
768         if (aa != bb)
769             return ((aa > bb) ? 1 : -1);
770     }
771     return (0);
772 }
773
774 /*
775  * Here follows a specialised variants of bn_cmp_words().  It has the
776  * property of performing the operation on arrays of different sizes. The
777  * sizes of those arrays is expressed through cl, which is the common length
778  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
779  * two lengths, calculated as len(a)-len(b). All lengths are the number of
780  * BN_ULONGs...
781  */
782
783 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
784 {
785     int n, i;
786     n = cl - 1;
787
788     if (dl < 0) {
789         for (i = dl; i < 0; i++) {
790             if (b[n - i] != 0)
791                 return -1;      /* a < b */
792         }
793     }
794     if (dl > 0) {
795         for (i = dl; i > 0; i--) {
796             if (a[n + i] != 0)
797                 return 1;       /* a > b */
798         }
799     }
800     return bn_cmp_words(a, b, cl);
801 }
802
803 /*
804  * Constant-time conditional swap of a and b.
805  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
806  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
807  * and that no more than nwords are used by either a or b.
808  * a and b cannot be the same number
809  */
810 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
811 {
812     BN_ULONG t;
813     int i;
814
815     bn_wcheck_size(a, nwords);
816     bn_wcheck_size(b, nwords);
817
818     assert(a != b);
819     assert((condition & (condition - 1)) == 0);
820     assert(sizeof(BN_ULONG) >= sizeof(int));
821
822     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
823
824     t = (a->top ^ b->top) & condition;
825     a->top ^= t;
826     b->top ^= t;
827
828 #define BN_CONSTTIME_SWAP(ind) \
829         do { \
830                 t = (a->d[ind] ^ b->d[ind]) & condition; \
831                 a->d[ind] ^= t; \
832                 b->d[ind] ^= t; \
833         } while (0)
834
835     switch (nwords) {
836     default:
837         for (i = 10; i < nwords; i++)
838             BN_CONSTTIME_SWAP(i);
839         /* Fallthrough */
840     case 10:
841         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
842     case 9:
843         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
844     case 8:
845         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
846     case 7:
847         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
848     case 6:
849         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
850     case 5:
851         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
852     case 4:
853         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
854     case 3:
855         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
856     case 2:
857         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
858     case 1:
859         BN_CONSTTIME_SWAP(0);
860     }
861 #undef BN_CONSTTIME_SWAP
862 }
863
864 /* Bits of security, see SP800-57 */
865
866 int BN_security_bits(int L, int N)
867 {
868     int secbits, bits;
869     if (L >= 15360)
870         secbits = 256;
871     else if (L >= 7690)
872         secbits = 192;
873     else if (L >= 3072)
874         secbits = 128;
875     else if (L >= 2048)
876         secbits = 112;
877     else if (L >= 1024)
878         secbits = 80;
879     else
880         return 0;
881     if (N == -1)
882         return secbits;
883     bits = N / 2;
884     if (bits < 80)
885         return 0;
886     return bits >= secbits ? secbits : bits;
887 }
888
889 void BN_zero_ex(BIGNUM *a)
890 {
891     a->top = 0;
892     a->neg = 0;
893 }
894
895 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
896 {
897     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
898 }
899
900 int BN_is_zero(const BIGNUM *a)
901 {
902     return a->top == 0;
903 }
904
905 int BN_is_one(const BIGNUM *a)
906 {
907     return BN_abs_is_word(a, 1) && !a->neg;
908 }
909
910 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
911 {
912     return BN_abs_is_word(a, w) && (!w || !a->neg);
913 }
914
915 int BN_is_odd(const BIGNUM *a)
916 {
917     return (a->top > 0) && (a->d[0] & 1);
918 }
919
920 int BN_is_negative(const BIGNUM *a)
921 {
922     return (a->neg != 0);
923 }
924
925 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
926                      BN_CTX *ctx)
927 {
928     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
929 }
930
931 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int n)
932 {
933     dest->d = b->d;
934     dest->top = b->top;
935     dest->dmax = b->dmax;
936     dest->neg = b->neg;
937     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
938                    | (b->flags & ~BN_FLG_MALLOCED)
939                    | BN_FLG_STATIC_DATA | n);
940 }
941
942 BN_GENCB *BN_GENCB_new(void)
943 {
944     BN_GENCB *ret;
945
946     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
947         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
948         return (NULL);
949     }
950
951     return ret;
952 }
953
954 void BN_GENCB_free(BN_GENCB *cb)
955 {
956     if (cb == NULL)
957         return;
958     OPENSSL_free(cb);
959 }
960
961 void BN_set_flags(BIGNUM *b, int n)
962 {
963     b->flags |= n;
964 }
965
966 int BN_get_flags(const BIGNUM *b, int n)
967 {
968     return b->flags & n;
969 }
970
971 /* Populate a BN_GENCB structure with an "old"-style callback */
972 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
973                       void *cb_arg)
974 {
975     BN_GENCB *tmp_gencb = gencb;
976     tmp_gencb->ver = 1;
977     tmp_gencb->arg = cb_arg;
978     tmp_gencb->cb.cb_1 = callback;
979 }
980
981 /* Populate a BN_GENCB structure with a "new"-style callback */
982 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
983                   void *cb_arg)
984 {
985     BN_GENCB *tmp_gencb = gencb;
986     tmp_gencb->ver = 2;
987     tmp_gencb->arg = cb_arg;
988     tmp_gencb->cb.cb_2 = callback;
989 }
990
991 void *BN_GENCB_get_arg(BN_GENCB *cb)
992 {
993     return cb->arg;
994 }
995
996 BIGNUM *bn_wexpand(BIGNUM *a, int words)
997 {
998     return (words <= a->dmax) ? a : bn_expand2(a, words);
999 }
1000
1001 void bn_correct_top(BIGNUM *a)
1002 {
1003     BN_ULONG *ftl;
1004     int tmp_top = a->top;
1005
1006     if (tmp_top > 0) {
1007         for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)
1008             if (*(ftl--))
1009                 break;
1010         a->top = tmp_top;
1011     }
1012     bn_pollute(a);
1013 }