]>
git.ipfire.org Git - thirdparty/openssl.git/blob - crypto/bn/bn_lib.c
1 /* crypto/bn/bn_lib.c */
2 /* Copyright (C) 1995-1997 Eric Young (eay@cryptsoft.com)
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.
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).
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.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
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)"
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
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.]
63 char *BN_version
="Big Number part of SSLeay 0.8.1b 29-Jun-1998";
65 BIGNUM
*BN_value_one()
67 static BN_ULONG data_one
=1L;
68 static BIGNUM const_one
={&data_one
,1,1,0};
82 sprintf(data
,"bn(%d,%d)",(int)sizeof(BN_ULLONG
)*8,
83 (int)sizeof(BN_ULONG
)*8);
85 sprintf(data
,"bn(%d,%d)",(int)sizeof(BN_ULONG
)*8,
86 (int)sizeof(BN_ULONG
)*8);
92 int BN_num_bits_word(l
)
95 static char bits
[256]={
96 0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,
97 5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
98 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
99 6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
100 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
101 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
102 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
103 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
104 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
105 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
106 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
107 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
108 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
109 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
110 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
111 8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
114 #ifdef SIXTY_FOUR_BIT_LONG
115 if (l
& 0xffffffff00000000L
)
117 if (l
& 0xffff000000000000L
)
119 if (l
& 0xff00000000000000L
)
121 return(bits
[l
>>56]+56);
123 else return(bits
[l
>>48]+48);
127 if (l
& 0x0000ff0000000000L
)
129 return(bits
[l
>>40]+40);
131 else return(bits
[l
>>32]+32);
136 #ifdef SIXTY_FOUR_BIT
137 if (l
& 0xffffffff00000000LL
)
139 if (l
& 0xffff000000000000LL
)
141 if (l
& 0xff00000000000000LL
)
143 return(bits
[l
>>56]+56);
145 else return(bits
[l
>>48]+48);
149 if (l
& 0x0000ff0000000000LL
)
151 return(bits
[l
>>40]+40);
153 else return(bits
[l
>>32]+32);
160 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
164 return(bits
[l
>>24L]+24);
165 else return(bits
[l
>>16L]+16);
170 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
172 return(bits
[l
>>8]+8);
186 if (a
->top
== 0) return(0);
188 i
=(a
->top
-1)*BN_BITS2
;
192 fprintf(stderr
,"BAD TOP VALUE\n");
196 return(i
+BN_num_bits_word(l
));
199 void BN_clear_free(a
)
202 if (a
== NULL
) return;
205 memset(a
->d
,0,a
->max
*sizeof(a
->d
[0]));
208 memset(a
,0,sizeof(BIGNUM
));
215 if (a
== NULL
) return;
216 if (a
->d
!= NULL
) Free(a
->d
);
225 ret
=(BIGNUM
*)Malloc(sizeof(BIGNUM
));
226 if (ret
== NULL
) goto err
;
229 ret
->max
=(BN_DEFAULT_BITS
/BN_BITS2
);
230 p
=(BN_ULONG
*)Malloc(sizeof(BN_ULONG
)*(ret
->max
+1));
231 if (p
== NULL
) goto err
;
234 memset(p
,0,(ret
->max
+1)*sizeof(p
[0]));
237 BNerr(BN_F_BN_NEW
,ERR_R_MALLOC_FAILURE
);
247 ret
=(BN_CTX
*)Malloc(sizeof(BN_CTX
));
248 if (ret
== NULL
) goto err2
;
250 for (i
=0; i
<BN_CTX_NUM
; i
++)
253 if (n
== NULL
) goto err
;
257 /* There is actually an extra one, this is for debugging my
259 ret
->bn
[BN_CTX_NUM
]=NULL
;
268 BNerr(BN_F_BN_CTX_NEW
,ERR_R_MALLOC_FAILURE
);
277 for (i
=0; i
<BN_CTX_NUM
; i
++)
278 BN_clear_free(c
->bn
[i
]);
282 BIGNUM
*bn_expand2(b
, bits
)
289 while (bits
> b
->max
*BN_BITS2
)
291 n
=((bits
+BN_BITS2
-1)/BN_BITS2
)*2;
292 p
=b
->d
=(BN_ULONG
*)Realloc(b
->d
,sizeof(BN_ULONG
)*(n
+1));
295 BNerr(BN_F_BN_EXPAND2
,ERR_R_MALLOC_FAILURE
);
298 memset(&(p
[b
->max
]),0,((n
+1)-b
->max
)*sizeof(BN_ULONG
));
310 if (r
== NULL
) return(NULL
);
311 return((BIGNUM
*)BN_copy(r
,a
));
314 BIGNUM
*BN_copy(a
, b
)
318 if (bn_expand(a
,b
->top
*BN_BITS2
) == NULL
) return(NULL
);
319 memcpy(a
->d
,b
->d
,sizeof(b
->d
[0])*b
->top
);
320 /* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/
329 memset(a
->d
,0,a
->max
*sizeof(a
->d
[0]));
334 unsigned long BN_get_word(a
)
341 if (n
> sizeof(unsigned long))
342 #ifdef SIXTY_FOUR_BIT_LONG
347 for (i
=a
->top
-1; i
>=0; i
--)
349 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
350 ret
<<=BN_BITS4
; /* stops the compiler complaining */
363 if (bn_expand(a
,sizeof(unsigned long)*8) == NULL
) return(0);
365 n
=sizeof(unsigned long)/BN_BYTES
;
368 a
->d
[0]=(BN_ULONG
)w
&BN_MASK2
;
369 if (a
->d
[0] != 0) a
->top
=1;
372 /* the following is done instead of
373 * w>>=BN_BITS2 so compilers don't complain
374 * on builds where sizeof(long) == BN_TYPES */
375 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
379 a
->d
[i
]=(BN_ULONG
)w
&BN_MASK2
;
380 if (a
->d
[i
] != 0) a
->top
=i
+1;
385 /* ignore negative */
386 BIGNUM
*BN_bin2bn(s
, len
, ret
)
395 if (ret
== NULL
) ret
=BN_new();
396 if (ret
== NULL
) return(NULL
);
404 if (bn_expand(ret
,(int)(n
+2)*8) == NULL
)
406 i
=((n
-1)/BN_BYTES
)+1;
407 m
=((n
-1)%(BN_BYTES
));
419 /* need to call this due to clear byte at top if avoiding
420 * having the top bit set (-ve number) */
425 /* ignore negative */
437 *(to
++)=(unsigned char)(l
>>(8*(i
%BN_BYTES
)))&0xff;
447 BN_ULONG t1
,t2
,*ap
,*bp
;
450 if (i
!= 0) return(i
);
453 for (i
=a
->top
-1; i
>=0; i
--)
458 return(t1
> t2
?1:-1);
471 if ((a
== NULL
) || (b
== NULL
))
480 if (a
->neg
!= b
->neg
)
488 else { gt
= -1; lt
=1; }
490 if (a
->top
> b
->top
) return(gt
);
491 if (a
->top
< b
->top
) return(lt
);
492 for (i
=a
->top
-1; i
>=0; i
--)
496 if (t1
> t2
) return(gt
);
497 if (t1
< t2
) return(lt
);
510 if (a
->top
<= i
) return(0);
516 int BN_clear_bit(a
, n
)
524 if (a
->top
<= i
) return(0);
530 int BN_is_bit_set(a
, n
)
536 if (n
< 0) return(0);
539 if (a
->top
<= i
) return(0);
540 return((a
->d
[i
]&(((BN_ULONG
)1)<<j
))?1:0);
543 int BN_mask_bits(a
,n
)
551 if (w
>= a
->top
) return(0);
557 a
->d
[w
]&= ~(BN_MASK2
<<b
);
558 while ((w
>= 0) && (a
->d
[w
] == 0))