RT4320/GH705: Fix PEM parsing bug.
[openssl.git] / crypto / bn / bn_lib.c
1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2  * All rights reserved.
3  *
4  * This package is an SSL implementation written
5  * by Eric Young (eay@cryptsoft.com).
6  * The implementation was written so as to conform with Netscapes SSL.
7  *
8  * This library is free for commercial and non-commercial use as long as
9  * the following conditions are aheared to.  The following conditions
10  * apply to all code found in this distribution, be it the RC4, RSA,
11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
12  * included with this distribution is covered by the same copyright terms
13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14  *
15  * Copyright remains Eric Young's, and as such any Copyright notices in
16  * the code are not to be removed.
17  * If this package is used in a product, Eric Young should be given attribution
18  * as the author of the parts of the library used.
19  * This can be in the form of a textual message at program startup or
20  * in documentation (online or textual) provided with the package.
21  *
22  * Redistribution and use in source and binary forms, with or without
23  * modification, are permitted provided that the following conditions
24  * are met:
25  * 1. Redistributions of source code must retain the copyright
26  *    notice, this list of conditions and the following disclaimer.
27  * 2. Redistributions in binary form must reproduce the above copyright
28  *    notice, this list of conditions and the following disclaimer in the
29  *    documentation and/or other materials provided with the distribution.
30  * 3. All advertising materials mentioning features or use of this software
31  *    must display the following acknowledgement:
32  *    "This product includes cryptographic software written by
33  *     Eric Young (eay@cryptsoft.com)"
34  *    The word 'cryptographic' can be left out if the rouines from the library
35  *    being used are not cryptographic related :-).
36  * 4. If you include any Windows specific code (or a derivative thereof) from
37  *    the apps directory (application code) you must include an acknowledgement:
38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39  *
40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50  * SUCH DAMAGE.
51  *
52  * The licence and distribution terms for any publically available version or
53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
54  * copied and put under another distribution licence
55  * [including the GNU Public Licence.]
56  */
57
58 #ifndef BN_DEBUG
59 # undef NDEBUG                  /* avoid conflicting definitions */
60 # define NDEBUG
61 #endif
62
63 #include <assert.h>
64 #include <limits.h>
65 #include "internal/cryptlib.h"
66 #include "bn_lcl.h"
67 #include <openssl/opensslconf.h>
68
69 /* This stuff appears to be completely unused, so is deprecated */
70 #if OPENSSL_API_COMPAT < 0x00908000L
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 #if OPENSSL_API_COMPAT < 0x00908000L
262         a->flags |= BN_FLG_FREE;
263 #endif
264         a->d = NULL;
265     }
266 }
267
268 void bn_init(BIGNUM *a)
269 {
270     static BIGNUM nilbn;
271
272     *a = nilbn;
273     bn_check_top(a);
274 }
275
276 BIGNUM *BN_new(void)
277 {
278     BIGNUM *ret;
279
280     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
281         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
282         return (NULL);
283     }
284     ret->flags = BN_FLG_MALLOCED;
285     bn_check_top(ret);
286     return (ret);
287 }
288
289  BIGNUM *BN_secure_new(void)
290  {
291      BIGNUM *ret = BN_new();
292      if (ret != NULL)
293          ret->flags |= BN_FLG_SECURE;
294      return (ret);
295  }
296
297 /* This is used by bn_expand2() */
298 /* The caller MUST check that words > b->dmax before calling this */
299 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
300 {
301     BN_ULONG *A, *a = NULL;
302     const BN_ULONG *B;
303     int i;
304
305     bn_check_top(b);
306
307     if (words > (INT_MAX / (4 * BN_BITS2))) {
308         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
309         return NULL;
310     }
311     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
312         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
313         return (NULL);
314     }
315     if (BN_get_flags(b,BN_FLG_SECURE))
316         a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
317     else
318         a = A = OPENSSL_zalloc(words * sizeof(*a));
319     if (A == NULL) {
320         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
321         return (NULL);
322     }
323
324 #if 1
325     B = b->d;
326     /* Check if the previous number needs to be copied */
327     if (B != NULL) {
328         for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
329             /*
330              * The fact that the loop is unrolled
331              * 4-wise is a tribute to Intel. It's
332              * the one that doesn't have enough
333              * registers to accommodate more data.
334              * I'd unroll it 8-wise otherwise:-)
335              *
336              *              <appro@fy.chalmers.se>
337              */
338             BN_ULONG a0, a1, a2, a3;
339             a0 = B[0];
340             a1 = B[1];
341             a2 = B[2];
342             a3 = B[3];
343             A[0] = a0;
344             A[1] = a1;
345             A[2] = a2;
346             A[3] = a3;
347         }
348         /*
349          * workaround for ultrix cc: without 'case 0', the optimizer does
350          * the switch table by doing a=top&3; a--; goto jump_table[a];
351          * which fails for top== 0
352          */
353         switch (b->top & 3) {
354         case 3:
355             A[2] = B[2];
356         case 2:
357             A[1] = B[1];
358         case 1:
359             A[0] = B[0];
360         case 0:
361             ;
362         }
363     }
364 #else
365     memset(A, 0, sizeof(*A) * words);
366     memcpy(A, b->d, sizeof(b->d[0]) * b->top);
367 #endif
368
369     return (a);
370 }
371
372 /*
373  * This is an internal function that should not be used in applications. It
374  * ensures that 'b' has enough room for a 'words' word number and initialises
375  * any unused part of b->d with leading zeros. It is mostly used by the
376  * various BIGNUM routines. If there is an error, NULL is returned. If not,
377  * 'b' is returned.
378  */
379
380 BIGNUM *bn_expand2(BIGNUM *b, int words)
381 {
382     bn_check_top(b);
383
384     if (words > b->dmax) {
385         BN_ULONG *a = bn_expand_internal(b, words);
386         if (!a)
387             return NULL;
388         if (b->d) {
389             OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
390             bn_free_d(b);
391         }
392         b->d = a;
393         b->dmax = words;
394     }
395
396     bn_check_top(b);
397     return b;
398 }
399
400 BIGNUM *BN_dup(const BIGNUM *a)
401 {
402     BIGNUM *t;
403
404     if (a == NULL)
405         return NULL;
406     bn_check_top(a);
407
408     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
409     if (t == NULL)
410         return NULL;
411     if (!BN_copy(t, a)) {
412         BN_free(t);
413         return NULL;
414     }
415     bn_check_top(t);
416     return t;
417 }
418
419 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
420 {
421     int i;
422     BN_ULONG *A;
423     const BN_ULONG *B;
424
425     bn_check_top(b);
426
427     if (a == b)
428         return (a);
429     if (bn_wexpand(a, b->top) == NULL)
430         return (NULL);
431
432 #if 1
433     A = a->d;
434     B = b->d;
435     for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
436         BN_ULONG a0, a1, a2, a3;
437         a0 = B[0];
438         a1 = B[1];
439         a2 = B[2];
440         a3 = B[3];
441         A[0] = a0;
442         A[1] = a1;
443         A[2] = a2;
444         A[3] = a3;
445     }
446     /* ultrix cc workaround, see comments in bn_expand_internal */
447     switch (b->top & 3) {
448     case 3:
449         A[2] = B[2];
450     case 2:
451         A[1] = B[1];
452     case 1:
453         A[0] = B[0];
454     case 0:;
455     }
456 #else
457     memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
458 #endif
459
460     a->top = b->top;
461     a->neg = b->neg;
462     bn_check_top(a);
463     return (a);
464 }
465
466 void BN_swap(BIGNUM *a, BIGNUM *b)
467 {
468     int flags_old_a, flags_old_b;
469     BN_ULONG *tmp_d;
470     int tmp_top, tmp_dmax, tmp_neg;
471
472     bn_check_top(a);
473     bn_check_top(b);
474
475     flags_old_a = a->flags;
476     flags_old_b = b->flags;
477
478     tmp_d = a->d;
479     tmp_top = a->top;
480     tmp_dmax = a->dmax;
481     tmp_neg = a->neg;
482
483     a->d = b->d;
484     a->top = b->top;
485     a->dmax = b->dmax;
486     a->neg = b->neg;
487
488     b->d = tmp_d;
489     b->top = tmp_top;
490     b->dmax = tmp_dmax;
491     b->neg = tmp_neg;
492
493     a->flags =
494         (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
495     b->flags =
496         (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
497     bn_check_top(a);
498     bn_check_top(b);
499 }
500
501 void BN_clear(BIGNUM *a)
502 {
503     bn_check_top(a);
504     if (a->d != NULL)
505         memset(a->d, 0, sizeof(*a->d) * a->dmax);
506     a->top = 0;
507     a->neg = 0;
508 }
509
510 BN_ULONG BN_get_word(const BIGNUM *a)
511 {
512     if (a->top > 1)
513         return BN_MASK2;
514     else if (a->top == 1)
515         return a->d[0];
516     /* a->top == 0 */
517     return 0;
518 }
519
520 int BN_set_word(BIGNUM *a, BN_ULONG w)
521 {
522     bn_check_top(a);
523     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
524         return (0);
525     a->neg = 0;
526     a->d[0] = w;
527     a->top = (w ? 1 : 0);
528     bn_check_top(a);
529     return (1);
530 }
531
532 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
533 {
534     unsigned int i, m;
535     unsigned int n;
536     BN_ULONG l;
537     BIGNUM *bn = NULL;
538
539     if (ret == NULL)
540         ret = bn = BN_new();
541     if (ret == NULL)
542         return (NULL);
543     bn_check_top(ret);
544     /* Skip leading zero's. */
545     for ( ; len > 0 && *s == 0; s++, len--)
546         continue;
547     n = len;
548     if (n == 0) {
549         ret->top = 0;
550         return (ret);
551     }
552     i = ((n - 1) / BN_BYTES) + 1;
553     m = ((n - 1) % (BN_BYTES));
554     if (bn_wexpand(ret, (int)i) == NULL) {
555         BN_free(bn);
556         return NULL;
557     }
558     ret->top = i;
559     ret->neg = 0;
560     l = 0;
561     while (n--) {
562         l = (l << 8L) | *(s++);
563         if (m-- == 0) {
564             ret->d[--i] = l;
565             l = 0;
566             m = BN_BYTES - 1;
567         }
568     }
569     /*
570      * need to call this due to clear byte at top if avoiding having the top
571      * bit set (-ve number)
572      */
573     bn_correct_top(ret);
574     return (ret);
575 }
576
577 /* ignore negative */
578 static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
579 {
580     int i;
581     BN_ULONG l;
582
583     bn_check_top(a);
584     i = BN_num_bytes(a);
585     if (tolen == -1)
586         tolen = i;
587     else if (tolen < i)
588         return -1;
589     /* Add leading zeroes if necessary */
590     if (tolen > i) {
591         memset(to, 0, tolen - i);
592         to += tolen - i;
593     }
594     while (i--) {
595         l = a->d[i / BN_BYTES];
596         *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
597     }
598     return tolen;
599 }
600
601 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
602 {
603     if (tolen < 0)
604         return -1;
605     return bn2binpad(a, to, tolen);
606 }
607
608 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
609 {
610     return bn2binpad(a, to, -1);
611 }
612
613 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
614 {
615     unsigned int i, m;
616     unsigned int n;
617     BN_ULONG l;
618     BIGNUM *bn = NULL;
619
620     if (ret == NULL)
621         ret = bn = BN_new();
622     if (ret == NULL)
623         return (NULL);
624     bn_check_top(ret);
625     s += len - 1;
626     /* Skip trailing zeroes. */
627     for ( ; len > 0 && *s == 0; s--, len--)
628         continue;
629     n = len;
630     if (n == 0) {
631         ret->top = 0;
632         return ret;
633     }
634     i = ((n - 1) / BN_BYTES) + 1;
635     m = ((n - 1) % (BN_BYTES));
636     if (bn_wexpand(ret, (int)i) == NULL) {
637         BN_free(bn);
638         return NULL;
639     }
640     ret->top = i;
641     ret->neg = 0;
642     l = 0;
643     while (n--) {
644         l = (l << 8L) | *(s--);
645         if (m-- == 0) {
646             ret->d[--i] = l;
647             l = 0;
648             m = BN_BYTES - 1;
649         }
650     }
651     /*
652      * need to call this due to clear byte at top if avoiding having the top
653      * bit set (-ve number)
654      */
655     bn_correct_top(ret);
656     return ret;
657 }
658
659 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
660 {
661     int i;
662     BN_ULONG l;
663     bn_check_top(a);
664     i = BN_num_bytes(a);
665     if (tolen < i)
666         return -1;
667     /* Add trailing zeroes if necessary */
668     if (tolen > i)
669         memset(to + i, 0, tolen - i);
670     to += i - 1;
671     while (i--) {
672         l = a->d[i / BN_BYTES];
673         *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
674     }
675     return tolen;
676 }
677
678 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
679 {
680     int i;
681     BN_ULONG t1, t2, *ap, *bp;
682
683     bn_check_top(a);
684     bn_check_top(b);
685
686     i = a->top - b->top;
687     if (i != 0)
688         return (i);
689     ap = a->d;
690     bp = b->d;
691     for (i = a->top - 1; i >= 0; i--) {
692         t1 = ap[i];
693         t2 = bp[i];
694         if (t1 != t2)
695             return ((t1 > t2) ? 1 : -1);
696     }
697     return (0);
698 }
699
700 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
701 {
702     int i;
703     int gt, lt;
704     BN_ULONG t1, t2;
705
706     if ((a == NULL) || (b == NULL)) {
707         if (a != NULL)
708             return (-1);
709         else if (b != NULL)
710             return (1);
711         else
712             return (0);
713     }
714
715     bn_check_top(a);
716     bn_check_top(b);
717
718     if (a->neg != b->neg) {
719         if (a->neg)
720             return (-1);
721         else
722             return (1);
723     }
724     if (a->neg == 0) {
725         gt = 1;
726         lt = -1;
727     } else {
728         gt = -1;
729         lt = 1;
730     }
731
732     if (a->top > b->top)
733         return (gt);
734     if (a->top < b->top)
735         return (lt);
736     for (i = a->top - 1; i >= 0; i--) {
737         t1 = a->d[i];
738         t2 = b->d[i];
739         if (t1 > t2)
740             return (gt);
741         if (t1 < t2)
742             return (lt);
743     }
744     return (0);
745 }
746
747 int BN_set_bit(BIGNUM *a, int n)
748 {
749     int i, j, k;
750
751     if (n < 0)
752         return 0;
753
754     i = n / BN_BITS2;
755     j = n % BN_BITS2;
756     if (a->top <= i) {
757         if (bn_wexpand(a, i + 1) == NULL)
758             return (0);
759         for (k = a->top; k < i + 1; k++)
760             a->d[k] = 0;
761         a->top = i + 1;
762     }
763
764     a->d[i] |= (((BN_ULONG)1) << j);
765     bn_check_top(a);
766     return (1);
767 }
768
769 int BN_clear_bit(BIGNUM *a, int n)
770 {
771     int i, j;
772
773     bn_check_top(a);
774     if (n < 0)
775         return 0;
776
777     i = n / BN_BITS2;
778     j = n % BN_BITS2;
779     if (a->top <= i)
780         return (0);
781
782     a->d[i] &= (~(((BN_ULONG)1) << j));
783     bn_correct_top(a);
784     return (1);
785 }
786
787 int BN_is_bit_set(const BIGNUM *a, int n)
788 {
789     int i, j;
790
791     bn_check_top(a);
792     if (n < 0)
793         return 0;
794     i = n / BN_BITS2;
795     j = n % BN_BITS2;
796     if (a->top <= i)
797         return 0;
798     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
799 }
800
801 int BN_mask_bits(BIGNUM *a, int n)
802 {
803     int b, w;
804
805     bn_check_top(a);
806     if (n < 0)
807         return 0;
808
809     w = n / BN_BITS2;
810     b = n % BN_BITS2;
811     if (w >= a->top)
812         return 0;
813     if (b == 0)
814         a->top = w;
815     else {
816         a->top = w + 1;
817         a->d[w] &= ~(BN_MASK2 << b);
818     }
819     bn_correct_top(a);
820     return (1);
821 }
822
823 void BN_set_negative(BIGNUM *a, int b)
824 {
825     if (b && !BN_is_zero(a))
826         a->neg = 1;
827     else
828         a->neg = 0;
829 }
830
831 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
832 {
833     int i;
834     BN_ULONG aa, bb;
835
836     aa = a[n - 1];
837     bb = b[n - 1];
838     if (aa != bb)
839         return ((aa > bb) ? 1 : -1);
840     for (i = n - 2; i >= 0; i--) {
841         aa = a[i];
842         bb = b[i];
843         if (aa != bb)
844             return ((aa > bb) ? 1 : -1);
845     }
846     return (0);
847 }
848
849 /*
850  * Here follows a specialised variants of bn_cmp_words().  It has the
851  * property of performing the operation on arrays of different sizes. The
852  * sizes of those arrays is expressed through cl, which is the common length
853  * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the
854  * two lengths, calculated as len(a)-len(b). All lengths are the number of
855  * BN_ULONGs...
856  */
857
858 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
859 {
860     int n, i;
861     n = cl - 1;
862
863     if (dl < 0) {
864         for (i = dl; i < 0; i++) {
865             if (b[n - i] != 0)
866                 return -1;      /* a < b */
867         }
868     }
869     if (dl > 0) {
870         for (i = dl; i > 0; i--) {
871             if (a[n + i] != 0)
872                 return 1;       /* a > b */
873         }
874     }
875     return bn_cmp_words(a, b, cl);
876 }
877
878 /*
879  * Constant-time conditional swap of a and b.
880  * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
881  * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
882  * and that no more than nwords are used by either a or b.
883  * a and b cannot be the same number
884  */
885 void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
886 {
887     BN_ULONG t;
888     int i;
889
890     bn_wcheck_size(a, nwords);
891     bn_wcheck_size(b, nwords);
892
893     assert(a != b);
894     assert((condition & (condition - 1)) == 0);
895     assert(sizeof(BN_ULONG) >= sizeof(int));
896
897     condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
898
899     t = (a->top ^ b->top) & condition;
900     a->top ^= t;
901     b->top ^= t;
902
903 #define BN_CONSTTIME_SWAP(ind) \
904         do { \
905                 t = (a->d[ind] ^ b->d[ind]) & condition; \
906                 a->d[ind] ^= t; \
907                 b->d[ind] ^= t; \
908         } while (0)
909
910     switch (nwords) {
911     default:
912         for (i = 10; i < nwords; i++)
913             BN_CONSTTIME_SWAP(i);
914         /* Fallthrough */
915     case 10:
916         BN_CONSTTIME_SWAP(9);   /* Fallthrough */
917     case 9:
918         BN_CONSTTIME_SWAP(8);   /* Fallthrough */
919     case 8:
920         BN_CONSTTIME_SWAP(7);   /* Fallthrough */
921     case 7:
922         BN_CONSTTIME_SWAP(6);   /* Fallthrough */
923     case 6:
924         BN_CONSTTIME_SWAP(5);   /* Fallthrough */
925     case 5:
926         BN_CONSTTIME_SWAP(4);   /* Fallthrough */
927     case 4:
928         BN_CONSTTIME_SWAP(3);   /* Fallthrough */
929     case 3:
930         BN_CONSTTIME_SWAP(2);   /* Fallthrough */
931     case 2:
932         BN_CONSTTIME_SWAP(1);   /* Fallthrough */
933     case 1:
934         BN_CONSTTIME_SWAP(0);
935     }
936 #undef BN_CONSTTIME_SWAP
937 }
938
939 /* Bits of security, see SP800-57 */
940
941 int BN_security_bits(int L, int N)
942 {
943     int secbits, bits;
944     if (L >= 15360)
945         secbits = 256;
946     else if (L >= 7690)
947         secbits = 192;
948     else if (L >= 3072)
949         secbits = 128;
950     else if (L >= 2048)
951         secbits = 112;
952     else if (L >= 1024)
953         secbits = 80;
954     else
955         return 0;
956     if (N == -1)
957         return secbits;
958     bits = N / 2;
959     if (bits < 80)
960         return 0;
961     return bits >= secbits ? secbits : bits;
962 }
963
964 void BN_zero_ex(BIGNUM *a)
965 {
966     a->top = 0;
967     a->neg = 0;
968 }
969
970 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
971 {
972     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
973 }
974
975 int BN_is_zero(const BIGNUM *a)
976 {
977     return a->top == 0;
978 }
979
980 int BN_is_one(const BIGNUM *a)
981 {
982     return BN_abs_is_word(a, 1) && !a->neg;
983 }
984
985 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
986 {
987     return BN_abs_is_word(a, w) && (!w || !a->neg);
988 }
989
990 int BN_is_odd(const BIGNUM *a)
991 {
992     return (a->top > 0) && (a->d[0] & 1);
993 }
994
995 int BN_is_negative(const BIGNUM *a)
996 {
997     return (a->neg != 0);
998 }
999
1000 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
1001                      BN_CTX *ctx)
1002 {
1003     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
1004 }
1005
1006 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
1007 {
1008     dest->d = b->d;
1009     dest->top = b->top;
1010     dest->dmax = b->dmax;
1011     dest->neg = b->neg;
1012     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
1013                    | (b->flags & ~BN_FLG_MALLOCED)
1014                    | BN_FLG_STATIC_DATA | flags);
1015 }
1016
1017 BN_GENCB *BN_GENCB_new(void)
1018 {
1019     BN_GENCB *ret;
1020
1021     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
1022         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
1023         return (NULL);
1024     }
1025
1026     return ret;
1027 }
1028
1029 void BN_GENCB_free(BN_GENCB *cb)
1030 {
1031     if (cb == NULL)
1032         return;
1033     OPENSSL_free(cb);
1034 }
1035
1036 void BN_set_flags(BIGNUM *b, int n)
1037 {
1038     b->flags |= n;
1039 }
1040
1041 int BN_get_flags(const BIGNUM *b, int n)
1042 {
1043     return b->flags & n;
1044 }
1045
1046 /* Populate a BN_GENCB structure with an "old"-style callback */
1047 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
1048                       void *cb_arg)
1049 {
1050     BN_GENCB *tmp_gencb = gencb;
1051     tmp_gencb->ver = 1;
1052     tmp_gencb->arg = cb_arg;
1053     tmp_gencb->cb.cb_1 = callback;
1054 }
1055
1056 /* Populate a BN_GENCB structure with a "new"-style callback */
1057 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
1058                   void *cb_arg)
1059 {
1060     BN_GENCB *tmp_gencb = gencb;
1061     tmp_gencb->ver = 2;
1062     tmp_gencb->arg = cb_arg;
1063     tmp_gencb->cb.cb_2 = callback;
1064 }
1065
1066 void *BN_GENCB_get_arg(BN_GENCB *cb)
1067 {
1068     return cb->arg;
1069 }
1070
1071 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1072 {
1073     return (words <= a->dmax) ? a : bn_expand2(a, words);
1074 }
1075
1076 void bn_correct_top(BIGNUM *a)
1077 {
1078     BN_ULONG *ftl;
1079     int tmp_top = a->top;
1080
1081     if (tmp_top > 0) {
1082         for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--)
1083             if (*(ftl--))
1084                 break;
1085         a->top = tmp_top;
1086     }
1087     bn_pollute(a);
1088 }