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