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