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