4 //FIXME Not checked on threadsafety yet; after checking please remove this line
5 /* crypto/bn/bn_lib.c */
6 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
9 * This package is an SSL implementation written
10 * by Eric Young (eay@cryptsoft.com).
11 * The implementation was written so as to conform with Netscapes SSL.
13 * This library is free for commercial and non-commercial use as long as
14 * the following conditions are aheared to. The following conditions
15 * apply to all code found in this distribution, be it the RC4, RSA,
16 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
17 * included with this distribution is covered by the same copyright terms
18 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
20 * Copyright remains Eric Young's, and as such any Copyright notices in
21 * the code are not to be removed.
22 * If this package is used in a product, Eric Young should be given attribution
23 * as the author of the parts of the library used.
24 * This can be in the form of a textual message at program startup or
25 * in documentation (online or textual) provided with the package.
27 * Redistribution and use in source and binary forms, with or without
28 * modification, are permitted provided that the following conditions
30 * 1. Redistributions of source code must retain the copyright
31 * notice, this list of conditions and the following disclaimer.
32 * 2. Redistributions in binary form must reproduce the above copyright
33 * notice, this list of conditions and the following disclaimer in the
34 * documentation and/or other materials provided with the distribution.
35 * 3. All advertising materials mentioning features or use of this software
36 * must display the following acknowledgement:
37 * "This product includes cryptographic software written by
38 * Eric Young (eay@cryptsoft.com)"
39 * The word 'cryptographic' can be left out if the rouines from the library
40 * being used are not cryptographic related :-).
41 * 4. If you include any Windows specific code (or a derivative thereof) from
42 * the apps directory (application code) you must include an acknowledgement:
43 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
45 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
46 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
47 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
48 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
49 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
51 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
52 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
53 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
54 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
57 * The license and distribution terms for any publically available version or
58 * derivative of this code cannot be changed. i.e. this code cannot simply be
59 * copied and put under another distribution license
60 * [including the GNU Public License.]
64 # undef NDEBUG /* avoid conflicting definitions */
73 #include "openssl_mods.h"
75 //const char *BN_version="Big Number 42";
77 /* For a 32 bit machine
86 static int bn_limit_bits
= 0;
87 static int bn_limit_num
= 8; /* (1<<bn_limit_bits) */
88 static int bn_limit_bits_low
= 0;
89 static int bn_limit_num_low
= 8; /* (1<<bn_limit_bits_low) */
90 static int bn_limit_bits_high
= 0;
91 static int bn_limit_num_high
= 8; /* (1<<bn_limit_bits_high) */
92 static int bn_limit_bits_mont
= 0;
93 static int bn_limit_num_mont
= 8; /* (1<<bn_limit_bits_mont) */
95 void BN_set_params(int mult
, int high
, int low
, int mont
)
99 if(mult
> (int)(sizeof(int) * 8) - 1)
100 { mult
= sizeof(int) * 8 - 1; }
101 bn_limit_bits
= mult
;
102 bn_limit_num
= 1 << mult
;
106 if(high
> (int)(sizeof(int) * 8) - 1)
107 { high
= sizeof(int) * 8 - 1; }
108 bn_limit_bits_high
= high
;
109 bn_limit_num_high
= 1 << high
;
113 if(low
> (int)(sizeof(int) * 8) - 1)
114 { low
= sizeof(int) * 8 - 1; }
115 bn_limit_bits_low
= low
;
116 bn_limit_num_low
= 1 << low
;
120 if(mont
> (int)(sizeof(int) * 8) - 1)
121 { mont
= sizeof(int) * 8 - 1; }
122 bn_limit_bits_mont
= mont
;
123 bn_limit_num_mont
= 1 << mont
;
127 int BN_get_params(int which
)
129 if(which
== 0) { return (bn_limit_bits
); }
130 else if(which
== 1) { return (bn_limit_bits_high
); }
131 else if(which
== 2) { return (bn_limit_bits_low
); }
132 else if(which
== 3) { return (bn_limit_bits_mont
); }
136 const BIGNUM
*BN_value_one(void)
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
};
144 char *BN_options(void)
147 static char data
[16];
153 snprintf(data
, sizeof(data
), "bn(%d,%d)", (int)sizeof(BN_ULLONG
) * 8,
154 (int)sizeof(BN_ULONG
) * 8);
156 snprintf(data
, sizeof(data
), "bn(%d,%d)", (int)sizeof(BN_ULONG
) * 8,
157 (int)sizeof(BN_ULONG
) * 8);
163 int BN_num_bits_word(BN_ULONG l
)
165 static const char bits
[256] =
167 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
168 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
169 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
170 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
171 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
172 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
173 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
174 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
175 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
176 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
177 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
178 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
179 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
180 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
181 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
182 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
185 #if defined(SIXTY_FOUR_BIT_LONG)
186 if(l
& 0xffffffff00000000L
)
188 if(l
& 0xffff000000000000L
)
190 if(l
& 0xff00000000000000L
)
192 return (bits
[(int)(l
>> 56)] + 56);
194 else { return (bits
[(int)(l
>> 48)] + 48); }
198 if(l
& 0x0000ff0000000000L
)
200 return (bits
[(int)(l
>> 40)] + 40);
202 else { return (bits
[(int)(l
>> 32)] + 32); }
207 #ifdef SIXTY_FOUR_BIT
208 if(l
& 0xffffffff00000000LL
)
210 if(l
& 0xffff000000000000LL
)
212 if(l
& 0xff00000000000000LL
)
214 return (bits
[(int)(l
>> 56)] + 56);
216 else { return (bits
[(int)(l
>> 48)] + 48); }
220 if(l
& 0x0000ff0000000000LL
)
222 return (bits
[(int)(l
>> 40)] + 40);
224 else { return (bits
[(int)(l
>> 32)] + 32); }
231 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
235 { return (bits
[(int)(l
>> 24L)] + 24); }
236 else { return (bits
[(int)(l
>> 16L)] + 16); }
241 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
243 { return (bits
[(int)(l
>> 8)] + 8); }
246 return (bits
[(int)(l
)]);
251 int BN_num_bits(const BIGNUM
*a
)
258 if(a
->top
== 0) { return (0); }
259 l
= a
->d
[a
->top
- 1];
261 i
= (a
->top
- 1) * BN_BITS2
;
262 return (i
+ BN_num_bits_word(l
));
265 void BN_clear_free(BIGNUM
*a
)
269 if(a
== NULL
) { return; }
272 memset(a
->d
, 0, a
->dmax
* sizeof(a
->d
[0]));
273 if(!(BN_get_flags(a
, BN_FLG_STATIC_DATA
)))
274 { OPENSSL_free(a
->d
); }
276 i
= BN_get_flags(a
, BN_FLG_MALLOCED
);
277 memset(a
, 0, sizeof(BIGNUM
));
282 void BN_free(BIGNUM
*a
)
284 if(a
== NULL
) { return; }
285 if((a
->d
!= NULL
) && !(BN_get_flags(a
, BN_FLG_STATIC_DATA
)))
286 { OPENSSL_free(a
->d
); }
287 a
->flags
|= BN_FLG_FREE
; /* REMOVE? */
288 if(a
->flags
& BN_FLG_MALLOCED
)
292 void BN_init(BIGNUM
*a
)
294 memset(a
, 0, sizeof(BIGNUM
));
301 if((ret
= (BIGNUM
*)OPENSSL_malloc(sizeof(BIGNUM
))) == NULL
)
305 ret
->flags
= BN_FLG_MALLOCED
;
313 /* This is an internal function that should not be used in applications.
314 * It ensures that 'b' has enough room for a 'words' word number number.
315 * It is mostly used by the various BIGNUM routines. If there is an error,
316 * NULL is returned. If not, 'b' is returned. */
318 BIGNUM
*bn_expand2(BIGNUM
*b
, int words
)
328 if(words
> (INT_MAX
/ (4 * BN_BITS2
)))
334 if(BN_get_flags(b
, BN_FLG_STATIC_DATA
))
338 a
= A
= (BN_ULONG
*)OPENSSL_malloc(sizeof(BN_ULONG
) * (words
+ 1));
345 /* Check if the previous number needs to be copied */
349 /* This lot is an unrolled loop to copy b->top
350 * BN_ULONGs from B to A
353 * I have nothing against unrolling but it's usually done for
354 * several reasons, namely:
355 * - minimize percentage of decision making code, i.e. branches;
356 * - avoid cache trashing;
357 * - make it possible to schedule loads earlier;
358 * Now let's examine the code below. The cornerstone of C is
359 * "programmer is always right" and that's what we love it for:-)
360 * For this very reason C compilers have to be paranoid when it
361 * comes to data aliasing and assume the worst. Yeah, but what
362 * does it mean in real life? This means that loop body below will
363 * be compiled to sequence of loads immediately followed by stores
364 * as compiler assumes the worst, something in A==B+1 style. As a
365 * result CPU pipeline is going to starve for incoming data. Secondly
366 * if A and B happen to share same cache line such code is going to
367 * cause severe cache trashing. Both factors have severe impact on
368 * performance of modern CPUs and this is the reason why this
369 * particular piece of code is #ifdefed away and replaced by more
370 * "friendly" version found in #else section below. This comment
371 * also applies to BN_copy function.
373 * <appro@fy.chalmers.se>
375 for(i
= b
->top
& (~7); i
> 0; i
-= 8)
405 /* I need the 'case 0' entry for utrix cc.
406 * If the optimizer is turned on, it does the
407 * switch table by doing
410 * goto jump_table[a];
411 * If top is 0, this makes us jump to 0xffffffc
412 * which is rather bad :-(.
418 for(i
= b
->top
>> 2; i
> 0; i
--, A
+= 4, B
+= 4)
421 * The fact that the loop is unrolled
422 * 4-wise is a tribute to Intel. It's
423 * the one that doesn't have enough
424 * registers to accomodate more data.
425 * I'd unroll it 8-wise otherwise:-)
427 * <appro@fy.chalmers.se>
429 BN_ULONG a0
, a1
, a2
, a3
;
442 A
[2] = B
[2]; /* fallthrough */
444 A
[1] = B
[1]; /* fallthrough */
446 A
[0] = B
[0]; /* fallthrough */
447 case 0: ; /* ultrix cc workaround, see above */
456 /* Now need to zero any data between b->top and b->max */
459 for(i
= (b
->dmax
- b
->top
) >> 3; i
> 0; i
--, A
+= 8)
470 for(i
= (b
->dmax
- b
->top
) & 7; i
> 0; i
--, A
++)
473 memset(A
, 0, sizeof(BN_ULONG
) * (words
+ 1));
474 memcpy(A
, b
->d
, sizeof(b
->d
[0])*b
->top
);
479 /* memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */
480 /* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */
486 BIGNUM
*BN_dup(const BIGNUM
*a
)
490 if(a
== NULL
) { return NULL
; }
495 if(r
== NULL
) { return (NULL
); }
496 return ((BIGNUM
*)BN_copy(r
, a
));
499 BIGNUM
*BN_copy(BIGNUM
*a
, const BIGNUM
*b
)
507 if(a
== b
) { return (a
); }
508 if(bn_wexpand(a
, b
->top
) == NULL
) { return (NULL
); }
513 for(i
= b
->top
>> 2; i
> 0; i
--, A
+= 4, B
+= 4)
515 BN_ULONG a0
, a1
, a2
, a3
;
528 A
[2] = B
[2]; /* fallthrough */
530 A
[1] = B
[1]; /* fallthrough */
532 A
[0] = B
[0]; /* fallthrough */
533 case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */
536 memcpy(a
->d
, b
->d
, sizeof(b
->d
[0])*b
->top
);
539 /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
541 if((a
->top
== 0) && (a
->d
!= NULL
))
547 void BN_clear(BIGNUM
*a
)
550 { memset(a
->d
, 0, a
->dmax
* sizeof(a
->d
[0])); }
555 BN_ULONG
BN_get_word(const BIGNUM
*a
)
565 int BN_set_word(BIGNUM
*a
, BN_ULONG w
)
568 if(bn_expand(a
, (int)sizeof(BN_ULONG
) * 8) == NULL
) { return (0); }
571 a
->top
= (w
? 1 : 0);
576 /* ignore negative */
577 BIGNUM
*BN_bin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
583 if(ret
== NULL
) { ret
= BN_new(); }
584 if(ret
== NULL
) { return (NULL
); }
592 if(bn_expand(ret
, (int)(n
+ 2) * 8) == NULL
)
594 i
= ((n
- 1) / BN_BYTES
) + 1;
595 m
= ((n
- 1) % (BN_BYTES
));
599 l
= (l
<< 8L) | *(s
++);
607 /* need to call this due to clear byte at top if avoiding
608 * having the top bit set (-ve number) */
613 /* ignore negative */
614 int BN_bn2bin(const BIGNUM
*a
, unsigned char *to
)
619 n
= i
= BN_num_bytes(a
);
622 l
= a
->d
[i
/ BN_BYTES
];
623 *(to
++) = (unsigned char)(l
>> (8 * (i
% BN_BYTES
))) & 0xff;
628 int BN_ucmp(const BIGNUM
*a
, const BIGNUM
*b
)
631 BN_ULONG t1
, t2
, *ap
, *bp
;
637 if(i
!= 0) { return (i
); }
640 for(i
= a
->top
- 1; i
>= 0; i
--)
645 { return (t1
> t2
? 1 : -1); }
650 int BN_cmp(const BIGNUM
*a
, const BIGNUM
*b
)
656 if((a
== NULL
) || (b
== NULL
))
686 if(a
->top
> b
->top
) { return (gt
); }
687 if(a
->top
< b
->top
) { return (lt
); }
688 for(i
= a
->top
- 1; i
>= 0; i
--)
692 if(t1
> t2
) { return (gt
); }
693 if(t1
< t2
) { return (lt
); }
698 int BN_set_bit(BIGNUM
*a
, int n
)
706 if(bn_wexpand(a
, i
+ 1) == NULL
) { return (0); }
707 for(k
= a
->top
; k
< i
+ 1; k
++)
712 a
->d
[i
] |= (((BN_ULONG
)1) << j
);
716 int BN_clear_bit(BIGNUM
*a
, int n
)
722 if(a
->top
<= i
) { return (0); }
724 a
->d
[i
] &= (~(((BN_ULONG
)1) << j
));
729 int BN_is_bit_set(const BIGNUM
*a
, int n
)
733 if(n
< 0) { return (0); }
736 if(a
->top
<= i
) { return (0); }
737 return ((a
->d
[i
] & (((BN_ULONG
)1) << j
)) ? 1 : 0);
740 int BN_mask_bits(BIGNUM
*a
, int n
)
746 if(w
>= a
->top
) { return (0); }
752 a
->d
[w
] &= ~(BN_MASK2
<< b
);
758 int bn_cmp_words(BN_ULONG
*a
, BN_ULONG
*b
, int n
)
765 if(aa
!= bb
) { return ((aa
> bb
) ? 1 : -1); }
766 for(i
= n
- 2; i
>= 0; i
--)
770 if(aa
!= bb
) { return ((aa
> bb
) ? 1 : -1); }