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