Documentation updates due to naming tweaks
[openssl.git] / crypto / bn / bn_lib.c
1 /*
2  * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9
10 #include <assert.h>
11 #include <limits.h>
12 #include "internal/cryptlib.h"
13 #include "bn_local.h"
14 #include <openssl/opensslconf.h>
15 #include "internal/constant_time.h"
16
17 /* This stuff appears to be completely unused, so is deprecated */
18 #ifndef OPENSSL_NO_DEPRECATED_0_9_8
19 /*-
20  * For a 32 bit machine
21  * 2 -   4 ==  128
22  * 3 -   8 ==  256
23  * 4 -  16 ==  512
24  * 5 -  32 == 1024
25  * 6 -  64 == 2048
26  * 7 - 128 == 4096
27  * 8 - 256 == 8192
28  */
29 static int bn_limit_bits = 0;
30 static int bn_limit_num = 8;    /* (1<<bn_limit_bits) */
31 static int bn_limit_bits_low = 0;
32 static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */
33 static int bn_limit_bits_high = 0;
34 static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */
35 static int bn_limit_bits_mont = 0;
36 static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */
37
38 void BN_set_params(int mult, int high, int low, int mont)
39 {
40     if (mult >= 0) {
41         if (mult > (int)(sizeof(int) * 8) - 1)
42             mult = sizeof(int) * 8 - 1;
43         bn_limit_bits = mult;
44         bn_limit_num = 1 << mult;
45     }
46     if (high >= 0) {
47         if (high > (int)(sizeof(int) * 8) - 1)
48             high = sizeof(int) * 8 - 1;
49         bn_limit_bits_high = high;
50         bn_limit_num_high = 1 << high;
51     }
52     if (low >= 0) {
53         if (low > (int)(sizeof(int) * 8) - 1)
54             low = sizeof(int) * 8 - 1;
55         bn_limit_bits_low = low;
56         bn_limit_num_low = 1 << low;
57     }
58     if (mont >= 0) {
59         if (mont > (int)(sizeof(int) * 8) - 1)
60             mont = sizeof(int) * 8 - 1;
61         bn_limit_bits_mont = mont;
62         bn_limit_num_mont = 1 << mont;
63     }
64 }
65
66 int BN_get_params(int which)
67 {
68     if (which == 0)
69         return bn_limit_bits;
70     else if (which == 1)
71         return bn_limit_bits_high;
72     else if (which == 2)
73         return bn_limit_bits_low;
74     else if (which == 3)
75         return bn_limit_bits_mont;
76     else
77         return 0;
78 }
79 #endif
80
81 const BIGNUM *BN_value_one(void)
82 {
83     static const BN_ULONG data_one = 1L;
84     static const BIGNUM const_one =
85         { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA };
86
87     return &const_one;
88 }
89
90 int BN_num_bits_word(BN_ULONG l)
91 {
92     BN_ULONG x, mask;
93     int bits = (l != 0);
94
95 #if BN_BITS2 > 32
96     x = l >> 32;
97     mask = (0 - x) & BN_MASK2;
98     mask = (0 - (mask >> (BN_BITS2 - 1)));
99     bits += 32 & mask;
100     l ^= (x ^ l) & mask;
101 #endif
102
103     x = l >> 16;
104     mask = (0 - x) & BN_MASK2;
105     mask = (0 - (mask >> (BN_BITS2 - 1)));
106     bits += 16 & mask;
107     l ^= (x ^ l) & mask;
108
109     x = l >> 8;
110     mask = (0 - x) & BN_MASK2;
111     mask = (0 - (mask >> (BN_BITS2 - 1)));
112     bits += 8 & mask;
113     l ^= (x ^ l) & mask;
114
115     x = l >> 4;
116     mask = (0 - x) & BN_MASK2;
117     mask = (0 - (mask >> (BN_BITS2 - 1)));
118     bits += 4 & mask;
119     l ^= (x ^ l) & mask;
120
121     x = l >> 2;
122     mask = (0 - x) & BN_MASK2;
123     mask = (0 - (mask >> (BN_BITS2 - 1)));
124     bits += 2 & mask;
125     l ^= (x ^ l) & mask;
126
127     x = l >> 1;
128     mask = (0 - x) & BN_MASK2;
129     mask = (0 - (mask >> (BN_BITS2 - 1)));
130     bits += 1 & mask;
131
132     return bits;
133 }
134
135 /*
136  * This function still leaks `a->dmax`: it's caller's responsibility to
137  * expand the input `a` in advance to a public length.
138  */
139 static ossl_inline
140 int bn_num_bits_consttime(const BIGNUM *a)
141 {
142     int j, ret;
143     unsigned int mask, past_i;
144     int i = a->top - 1;
145     bn_check_top(a);
146
147     for (j = 0, past_i = 0, ret = 0; j < a->dmax; j++) {
148         mask = constant_time_eq_int(i, j); /* 0xff..ff if i==j, 0x0 otherwise */
149
150         ret += BN_BITS2 & (~mask & ~past_i);
151         ret += BN_num_bits_word(a->d[j]) & mask;
152
153         past_i |= mask; /* past_i will become 0xff..ff after i==j */
154     }
155
156     /*
157      * if BN_is_zero(a) => i is -1 and ret contains garbage, so we mask the
158      * final result.
159      */
160     mask = ~(constant_time_eq_int(i, ((int)-1)));
161
162     return ret & mask;
163 }
164
165 int BN_num_bits(const BIGNUM *a)
166 {
167     int i = a->top - 1;
168     bn_check_top(a);
169
170     if (a->flags & BN_FLG_CONSTTIME) {
171         /*
172          * We assume that BIGNUMs flagged as CONSTTIME have also been expanded
173          * so that a->dmax is not leaking secret information.
174          *
175          * In other words, it's the caller's responsibility to ensure `a` has
176          * been preallocated in advance to a public length if we hit this
177          * branch.
178          *
179          */
180         return bn_num_bits_consttime(a);
181     }
182
183     if (BN_is_zero(a))
184         return 0;
185
186     return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
187 }
188
189 static void bn_free_d(BIGNUM *a, int clear)
190 {
191     if (BN_get_flags(a, BN_FLG_SECURE))
192         OPENSSL_secure_clear_free(a->d, a->dmax * sizeof(a->d[0]));
193     else if (clear != 0)
194         OPENSSL_clear_free(a->d, a->dmax * sizeof(a->d[0]));
195     else
196         OPENSSL_free(a->d);
197 }
198
199
200 void BN_clear_free(BIGNUM *a)
201 {
202     if (a == NULL)
203         return;
204     if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA))
205         bn_free_d(a, 1);
206     if (BN_get_flags(a, BN_FLG_MALLOCED)) {
207         OPENSSL_cleanse(a, sizeof(*a));
208         OPENSSL_free(a);
209     }
210 }
211
212 void BN_free(BIGNUM *a)
213 {
214     if (a == NULL)
215         return;
216     if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
217         bn_free_d(a, 0);
218     if (a->flags & BN_FLG_MALLOCED)
219         OPENSSL_free(a);
220 }
221
222 void bn_init(BIGNUM *a)
223 {
224     static BIGNUM nilbn;
225
226     *a = nilbn;
227     bn_check_top(a);
228 }
229
230 BIGNUM *BN_new(void)
231 {
232     BIGNUM *ret;
233
234     if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
235         BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
236         return NULL;
237     }
238     ret->flags = BN_FLG_MALLOCED;
239     bn_check_top(ret);
240     return ret;
241 }
242
243  BIGNUM *BN_secure_new(void)
244  {
245      BIGNUM *ret = BN_new();
246      if (ret != NULL)
247          ret->flags |= BN_FLG_SECURE;
248      return ret;
249  }
250
251 /* This is used by bn_expand2() */
252 /* The caller MUST check that words > b->dmax before calling this */
253 static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
254 {
255     BN_ULONG *a = NULL;
256
257     if (words > (INT_MAX / (4 * BN_BITS2))) {
258         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
259         return NULL;
260     }
261     if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
262         BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
263         return NULL;
264     }
265     if (BN_get_flags(b, BN_FLG_SECURE))
266         a = OPENSSL_secure_zalloc(words * sizeof(*a));
267     else
268         a = OPENSSL_zalloc(words * sizeof(*a));
269     if (a == NULL) {
270         BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
271         return NULL;
272     }
273
274     assert(b->top <= words);
275     if (b->top > 0)
276         memcpy(a, b->d, sizeof(*a) * b->top);
277
278     return a;
279 }
280
281 /*
282  * This is an internal function that should not be used in applications. It
283  * ensures that 'b' has enough room for a 'words' word number and initialises
284  * any unused part of b->d with leading zeros. It is mostly used by the
285  * various BIGNUM routines. If there is an error, NULL is returned. If not,
286  * 'b' is returned.
287  */
288
289 BIGNUM *bn_expand2(BIGNUM *b, int words)
290 {
291     if (words > b->dmax) {
292         BN_ULONG *a = bn_expand_internal(b, words);
293         if (!a)
294             return NULL;
295         if (b->d != NULL)
296             bn_free_d(b, 1);
297         b->d = a;
298         b->dmax = words;
299     }
300
301     return b;
302 }
303
304 BIGNUM *BN_dup(const BIGNUM *a)
305 {
306     BIGNUM *t;
307
308     if (a == NULL)
309         return NULL;
310     bn_check_top(a);
311
312     t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
313     if (t == NULL)
314         return NULL;
315     if (!BN_copy(t, a)) {
316         BN_free(t);
317         return NULL;
318     }
319     bn_check_top(t);
320     return t;
321 }
322
323 BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
324 {
325     bn_check_top(b);
326
327     if (a == b)
328         return a;
329     if (bn_wexpand(a, b->top) == NULL)
330         return NULL;
331
332     if (b->top > 0)
333         memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
334
335     a->neg = b->neg;
336     a->top = b->top;
337     a->flags |= b->flags & BN_FLG_FIXED_TOP;
338     bn_check_top(a);
339     return a;
340 }
341
342 #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \
343                                     | BN_FLG_CONSTTIME   \
344                                     | BN_FLG_SECURE      \
345                                     | BN_FLG_FIXED_TOP))
346 #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED))
347
348 void BN_swap(BIGNUM *a, BIGNUM *b)
349 {
350     int flags_old_a, flags_old_b;
351     BN_ULONG *tmp_d;
352     int tmp_top, tmp_dmax, tmp_neg;
353
354     bn_check_top(a);
355     bn_check_top(b);
356
357     flags_old_a = a->flags;
358     flags_old_b = b->flags;
359
360     tmp_d = a->d;
361     tmp_top = a->top;
362     tmp_dmax = a->dmax;
363     tmp_neg = a->neg;
364
365     a->d = b->d;
366     a->top = b->top;
367     a->dmax = b->dmax;
368     a->neg = b->neg;
369
370     b->d = tmp_d;
371     b->top = tmp_top;
372     b->dmax = tmp_dmax;
373     b->neg = tmp_neg;
374
375     a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b);
376     b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a);
377     bn_check_top(a);
378     bn_check_top(b);
379 }
380
381 void BN_clear(BIGNUM *a)
382 {
383     if (a == NULL)
384         return;
385     bn_check_top(a);
386     if (a->d != NULL)
387         OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
388     a->neg = 0;
389     a->top = 0;
390     a->flags &= ~BN_FLG_FIXED_TOP;
391 }
392
393 BN_ULONG BN_get_word(const BIGNUM *a)
394 {
395     if (a->top > 1)
396         return BN_MASK2;
397     else if (a->top == 1)
398         return a->d[0];
399     /* a->top == 0 */
400     return 0;
401 }
402
403 int BN_set_word(BIGNUM *a, BN_ULONG w)
404 {
405     bn_check_top(a);
406     if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
407         return 0;
408     a->neg = 0;
409     a->d[0] = w;
410     a->top = (w ? 1 : 0);
411     a->flags &= ~BN_FLG_FIXED_TOP;
412     bn_check_top(a);
413     return 1;
414 }
415
416 BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
417 {
418     unsigned int i, m;
419     unsigned int n;
420     BN_ULONG l;
421     BIGNUM *bn = NULL;
422
423     if (ret == NULL)
424         ret = bn = BN_new();
425     if (ret == NULL)
426         return NULL;
427     bn_check_top(ret);
428     /* Skip leading zero's. */
429     for ( ; len > 0 && *s == 0; s++, len--)
430         continue;
431     n = len;
432     if (n == 0) {
433         ret->top = 0;
434         return ret;
435     }
436     i = ((n - 1) / BN_BYTES) + 1;
437     m = ((n - 1) % (BN_BYTES));
438     if (bn_wexpand(ret, (int)i) == NULL) {
439         BN_free(bn);
440         return NULL;
441     }
442     ret->top = i;
443     ret->neg = 0;
444     l = 0;
445     while (n--) {
446         l = (l << 8L) | *(s++);
447         if (m-- == 0) {
448             ret->d[--i] = l;
449             l = 0;
450             m = BN_BYTES - 1;
451         }
452     }
453     /*
454      * need to call this due to clear byte at top if avoiding having the top
455      * bit set (-ve number)
456      */
457     bn_correct_top(ret);
458     return ret;
459 }
460
461 typedef enum {big, little} endianess_t;
462
463 /* ignore negative */
464 static
465 int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianess_t endianess)
466 {
467     int n;
468     size_t i, lasti, j, atop, mask;
469     BN_ULONG l;
470
471     /*
472      * In case |a| is fixed-top, BN_num_bytes can return bogus length,
473      * but it's assumed that fixed-top inputs ought to be "nominated"
474      * even for padded output, so it works out...
475      */
476     n = BN_num_bytes(a);
477     if (tolen == -1) {
478         tolen = n;
479     } else if (tolen < n) {     /* uncommon/unlike case */
480         BIGNUM temp = *a;
481
482         bn_correct_top(&temp);
483         n = BN_num_bytes(&temp);
484         if (tolen < n)
485             return -1;
486     }
487
488     /* Swipe through whole available data and don't give away padded zero. */
489     atop = a->dmax * BN_BYTES;
490     if (atop == 0) {
491         OPENSSL_cleanse(to, tolen);
492         return tolen;
493     }
494
495     lasti = atop - 1;
496     atop = a->top * BN_BYTES;
497     if (endianess == big)
498         to += tolen; /* start from the end of the buffer */
499     for (i = 0, j = 0; j < (size_t)tolen; j++) {
500         unsigned char val;
501         l = a->d[i / BN_BYTES];
502         mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
503         val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
504         if (endianess == big)
505             *--to = val;
506         else
507             *to++ = val;
508         i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
509     }
510
511     return tolen;
512 }
513
514 int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
515 {
516     if (tolen < 0)
517         return -1;
518     return bn2binpad(a, to, tolen, big);
519 }
520
521 int BN_bn2bin(const BIGNUM *a, unsigned char *to)
522 {
523     return bn2binpad(a, to, -1, big);
524 }
525
526 BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret)
527 {
528     unsigned int i, m;
529     unsigned int n;
530     BN_ULONG l;
531     BIGNUM *bn = NULL;
532
533     if (ret == NULL)
534         ret = bn = BN_new();
535     if (ret == NULL)
536         return NULL;
537     bn_check_top(ret);
538     s += len;
539     /* Skip trailing zeroes. */
540     for ( ; len > 0 && s[-1] == 0; s--, len--)
541         continue;
542     n = len;
543     if (n == 0) {
544         ret->top = 0;
545         return ret;
546     }
547     i = ((n - 1) / BN_BYTES) + 1;
548     m = ((n - 1) % (BN_BYTES));
549     if (bn_wexpand(ret, (int)i) == NULL) {
550         BN_free(bn);
551         return NULL;
552     }
553     ret->top = i;
554     ret->neg = 0;
555     l = 0;
556     while (n--) {
557         s--;
558         l = (l << 8L) | *s;
559         if (m-- == 0) {
560             ret->d[--i] = l;
561             l = 0;
562             m = BN_BYTES - 1;
563         }
564     }
565     /*
566      * need to call this due to clear byte at top if avoiding having the top
567      * bit set (-ve number)
568      */
569     bn_correct_top(ret);
570     return ret;
571 }
572
573 int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
574 {
575     if (tolen < 0)
576         return -1;
577     return bn2binpad(a, to, tolen, little);
578 }
579
580 BIGNUM *BN_native2bn(const unsigned char *s, int len, BIGNUM *ret)
581 {
582 #ifdef B_ENDIAN
583     return BN_bin2bn(s, len, ret);
584 #else
585     return BN_lebin2bn(s, len, ret);
586 #endif
587 }
588
589 int BN_bn2nativepad(const BIGNUM *a, unsigned char *to, int tolen)
590 {
591 #ifdef B_ENDIAN
592     return BN_bn2binpad(a, to, tolen);
593 #else
594     return BN_bn2lebinpad(a, to, tolen);
595 #endif
596 }
597
598 int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
599 {
600     int i;
601     BN_ULONG t1, t2, *ap, *bp;
602
603     bn_check_top(a);
604     bn_check_top(b);
605
606     i = a->top - b->top;
607     if (i != 0)
608         return i;
609     ap = a->d;
610     bp = b->d;
611     for (i = a->top - 1; i >= 0; i--) {
612         t1 = ap[i];
613         t2 = bp[i];
614         if (t1 != t2)
615             return ((t1 > t2) ? 1 : -1);
616     }
617     return 0;
618 }
619
620 int BN_cmp(const BIGNUM *a, const BIGNUM *b)
621 {
622     int i;
623     int gt, lt;
624     BN_ULONG t1, t2;
625
626     if ((a == NULL) || (b == NULL)) {
627         if (a != NULL)
628             return -1;
629         else if (b != NULL)
630             return 1;
631         else
632             return 0;
633     }
634
635     bn_check_top(a);
636     bn_check_top(b);
637
638     if (a->neg != b->neg) {
639         if (a->neg)
640             return -1;
641         else
642             return 1;
643     }
644     if (a->neg == 0) {
645         gt = 1;
646         lt = -1;
647     } else {
648         gt = -1;
649         lt = 1;
650     }
651
652     if (a->top > b->top)
653         return gt;
654     if (a->top < b->top)
655         return lt;
656     for (i = a->top - 1; i >= 0; i--) {
657         t1 = a->d[i];
658         t2 = b->d[i];
659         if (t1 > t2)
660             return gt;
661         if (t1 < t2)
662             return lt;
663     }
664     return 0;
665 }
666
667 int BN_set_bit(BIGNUM *a, int n)
668 {
669     int i, j, k;
670
671     if (n < 0)
672         return 0;
673
674     i = n / BN_BITS2;
675     j = n % BN_BITS2;
676     if (a->top <= i) {
677         if (bn_wexpand(a, i + 1) == NULL)
678             return 0;
679         for (k = a->top; k < i + 1; k++)
680             a->d[k] = 0;
681         a->top = i + 1;
682         a->flags &= ~BN_FLG_FIXED_TOP;
683     }
684
685     a->d[i] |= (((BN_ULONG)1) << j);
686     bn_check_top(a);
687     return 1;
688 }
689
690 int BN_clear_bit(BIGNUM *a, int n)
691 {
692     int i, j;
693
694     bn_check_top(a);
695     if (n < 0)
696         return 0;
697
698     i = n / BN_BITS2;
699     j = n % BN_BITS2;
700     if (a->top <= i)
701         return 0;
702
703     a->d[i] &= (~(((BN_ULONG)1) << j));
704     bn_correct_top(a);
705     return 1;
706 }
707
708 int BN_is_bit_set(const BIGNUM *a, int n)
709 {
710     int i, j;
711
712     bn_check_top(a);
713     if (n < 0)
714         return 0;
715     i = n / BN_BITS2;
716     j = n % BN_BITS2;
717     if (a->top <= i)
718         return 0;
719     return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
720 }
721
722 int BN_mask_bits(BIGNUM *a, int n)
723 {
724     int b, w;
725
726     bn_check_top(a);
727     if (n < 0)
728         return 0;
729
730     w = n / BN_BITS2;
731     b = n % BN_BITS2;
732     if (w >= a->top)
733         return 0;
734     if (b == 0)
735         a->top = w;
736     else {
737         a->top = w + 1;
738         a->d[w] &= ~(BN_MASK2 << b);
739     }
740     bn_correct_top(a);
741     return 1;
742 }
743
744 void BN_set_negative(BIGNUM *a, int b)
745 {
746     if (b && !BN_is_zero(a))
747         a->neg = 1;
748     else
749         a->neg = 0;
750 }
751
752 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
753 {
754     int i;
755     BN_ULONG aa, bb;
756
757     if (n == 0)
758         return 0;
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  * capability 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  * ( basically, 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.
805  * nwords is the number of words to swap.
806  * Assumes that at least nwords are allocated in both a and b.
807  * Assumes that no more than nwords are used by either a or b.
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     if (a == b)
815         return;
816
817     bn_wcheck_size(a, nwords);
818     bn_wcheck_size(b, nwords);
819
820     condition = ((~condition & ((condition - 1))) >> (BN_BITS2 - 1)) - 1;
821
822     t = (a->top ^ b->top) & condition;
823     a->top ^= t;
824     b->top ^= t;
825
826     t = (a->neg ^ b->neg) & condition;
827     a->neg ^= t;
828     b->neg ^= t;
829
830     /*-
831      * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention
832      * is actually to treat it as it's read-only data, and some (if not most)
833      * of it does reside in read-only segment. In other words observation of
834      * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal
835      * condition. It would either cause SEGV or effectively cause data
836      * corruption.
837      *
838      * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be
839      * preserved.
840      *
841      * BN_FLG_SECURE: must be preserved, because it determines how x->d was
842      * allocated and hence how to free it.
843      *
844      * BN_FLG_CONSTTIME: sufficient to mask and swap
845      *
846      * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on
847      * the data, so the d array may be padded with additional 0 values (i.e.
848      * top could be greater than the minimal value that it could be). We should
849      * be swapping it
850      */
851
852 #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP)
853
854     t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition;
855     a->flags ^= t;
856     b->flags ^= t;
857
858     /* conditionally swap the data */
859     for (i = 0; i < nwords; i++) {
860         t = (a->d[i] ^ b->d[i]) & condition;
861         a->d[i] ^= t;
862         b->d[i] ^= t;
863     }
864 }
865
866 #undef BN_CONSTTIME_SWAP_FLAGS
867
868 /* Bits of security, see SP800-57 */
869
870 int BN_security_bits(int L, int N)
871 {
872     int secbits, bits;
873     if (L >= 15360)
874         secbits = 256;
875     else if (L >= 7680)
876         secbits = 192;
877     else if (L >= 3072)
878         secbits = 128;
879     else if (L >= 2048)
880         secbits = 112;
881     else if (L >= 1024)
882         secbits = 80;
883     else
884         return 0;
885     if (N == -1)
886         return secbits;
887     bits = N / 2;
888     if (bits < 80)
889         return 0;
890     return bits >= secbits ? secbits : bits;
891 }
892
893 void BN_zero_ex(BIGNUM *a)
894 {
895     a->neg = 0;
896     a->top = 0;
897     a->flags &= ~BN_FLG_FIXED_TOP;
898 }
899
900 int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
901 {
902     return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
903 }
904
905 int BN_is_zero(const BIGNUM *a)
906 {
907     return a->top == 0;
908 }
909
910 int BN_is_one(const BIGNUM *a)
911 {
912     return BN_abs_is_word(a, 1) && !a->neg;
913 }
914
915 int BN_is_word(const BIGNUM *a, const BN_ULONG w)
916 {
917     return BN_abs_is_word(a, w) && (!w || !a->neg);
918 }
919
920 int BN_is_odd(const BIGNUM *a)
921 {
922     return (a->top > 0) && (a->d[0] & 1);
923 }
924
925 int BN_is_negative(const BIGNUM *a)
926 {
927     return (a->neg != 0);
928 }
929
930 int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
931                      BN_CTX *ctx)
932 {
933     return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
934 }
935
936 void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
937 {
938     dest->d = b->d;
939     dest->top = b->top;
940     dest->dmax = b->dmax;
941     dest->neg = b->neg;
942     dest->flags = ((dest->flags & BN_FLG_MALLOCED)
943                    | (b->flags & ~BN_FLG_MALLOCED)
944                    | BN_FLG_STATIC_DATA | flags);
945 }
946
947 BN_GENCB *BN_GENCB_new(void)
948 {
949     BN_GENCB *ret;
950
951     if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
952         BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
953         return NULL;
954     }
955
956     return ret;
957 }
958
959 void BN_GENCB_free(BN_GENCB *cb)
960 {
961     if (cb == NULL)
962         return;
963     OPENSSL_free(cb);
964 }
965
966 void BN_set_flags(BIGNUM *b, int n)
967 {
968     b->flags |= n;
969 }
970
971 int BN_get_flags(const BIGNUM *b, int n)
972 {
973     return b->flags & n;
974 }
975
976 /* Populate a BN_GENCB structure with an "old"-style callback */
977 void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
978                       void *cb_arg)
979 {
980     BN_GENCB *tmp_gencb = gencb;
981     tmp_gencb->ver = 1;
982     tmp_gencb->arg = cb_arg;
983     tmp_gencb->cb.cb_1 = callback;
984 }
985
986 /* Populate a BN_GENCB structure with a "new"-style callback */
987 void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
988                   void *cb_arg)
989 {
990     BN_GENCB *tmp_gencb = gencb;
991     tmp_gencb->ver = 2;
992     tmp_gencb->arg = cb_arg;
993     tmp_gencb->cb.cb_2 = callback;
994 }
995
996 void *BN_GENCB_get_arg(BN_GENCB *cb)
997 {
998     return cb->arg;
999 }
1000
1001 BIGNUM *bn_wexpand(BIGNUM *a, int words)
1002 {
1003     return (words <= a->dmax) ? a : bn_expand2(a, words);
1004 }
1005
1006 void bn_correct_top(BIGNUM *a)
1007 {
1008     BN_ULONG *ftl;
1009     int tmp_top = a->top;
1010
1011     if (tmp_top > 0) {
1012         for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
1013             ftl--;
1014             if (*ftl != 0)
1015                 break;
1016         }
1017         a->top = tmp_top;
1018     }
1019     if (a->top == 0)
1020         a->neg = 0;
1021     a->flags &= ~BN_FLG_FIXED_TOP;
1022     bn_pollute(a);
1023 }