1 |
matty |
32 |
/* 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 |
|
|
#include <assert.h> |
65 |
|
|
#include <limits.h> |
66 |
|
|
#include <stdio.h> |
67 |
|
|
#include "bn_lcl.h" |
68 |
|
|
|
69 |
|
|
#if 0 |
70 |
|
|
BIGNUM *BN_value_one(void) |
71 |
|
|
{ |
72 |
|
|
static BN_ULONG data_one=1L; |
73 |
|
|
static BIGNUM const_one={&data_one,1,1,0}; |
74 |
|
|
|
75 |
|
|
return(&const_one); |
76 |
|
|
} |
77 |
|
|
#endif |
78 |
|
|
|
79 |
|
|
int BN_num_bits_word(BN_ULONG l) |
80 |
|
|
{ |
81 |
|
|
static const char bits[256]={ |
82 |
|
|
0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4, |
83 |
|
|
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5, |
84 |
|
|
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, |
85 |
|
|
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6, |
86 |
|
|
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, |
87 |
|
|
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, |
88 |
|
|
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, |
89 |
|
|
7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7, |
90 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
91 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
92 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
93 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
94 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
95 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
96 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
97 |
|
|
8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8, |
98 |
|
|
}; |
99 |
|
|
|
100 |
|
|
#if defined(SIXTY_FOUR_BIT_LONG) |
101 |
|
|
if (l & 0xffffffff00000000L) |
102 |
|
|
{ |
103 |
|
|
if (l & 0xffff000000000000L) |
104 |
|
|
{ |
105 |
|
|
if (l & 0xff00000000000000L) |
106 |
|
|
{ |
107 |
|
|
return(bits[(int)(l>>56)]+56); |
108 |
|
|
} |
109 |
|
|
else return(bits[(int)(l>>48)]+48); |
110 |
|
|
} |
111 |
|
|
else |
112 |
|
|
{ |
113 |
|
|
if (l & 0x0000ff0000000000L) |
114 |
|
|
{ |
115 |
|
|
return(bits[(int)(l>>40)]+40); |
116 |
|
|
} |
117 |
|
|
else return(bits[(int)(l>>32)]+32); |
118 |
|
|
} |
119 |
|
|
} |
120 |
|
|
else |
121 |
|
|
#else |
122 |
|
|
#ifdef SIXTY_FOUR_BIT |
123 |
|
|
if (l & 0xffffffff00000000LL) |
124 |
|
|
{ |
125 |
|
|
if (l & 0xffff000000000000LL) |
126 |
|
|
{ |
127 |
|
|
if (l & 0xff00000000000000LL) |
128 |
|
|
{ |
129 |
|
|
return(bits[(int)(l>>56)]+56); |
130 |
|
|
} |
131 |
|
|
else return(bits[(int)(l>>48)]+48); |
132 |
|
|
} |
133 |
|
|
else |
134 |
|
|
{ |
135 |
|
|
if (l & 0x0000ff0000000000LL) |
136 |
|
|
{ |
137 |
|
|
return(bits[(int)(l>>40)]+40); |
138 |
|
|
} |
139 |
|
|
else return(bits[(int)(l>>32)]+32); |
140 |
|
|
} |
141 |
|
|
} |
142 |
|
|
else |
143 |
|
|
#endif |
144 |
|
|
#endif |
145 |
|
|
{ |
146 |
|
|
#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) |
147 |
|
|
if (l & 0xffff0000L) |
148 |
|
|
{ |
149 |
|
|
if (l & 0xff000000L) |
150 |
|
|
return(bits[(int)(l>>24L)]+24); |
151 |
|
|
else return(bits[(int)(l>>16L)]+16); |
152 |
|
|
} |
153 |
|
|
else |
154 |
|
|
#endif |
155 |
|
|
{ |
156 |
|
|
#if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) |
157 |
|
|
if (l & 0xff00L) |
158 |
|
|
return(bits[(int)(l>>8)]+8); |
159 |
|
|
else |
160 |
|
|
#endif |
161 |
|
|
return(bits[(int)(l )] ); |
162 |
|
|
} |
163 |
|
|
} |
164 |
|
|
} |
165 |
|
|
|
166 |
|
|
int BN_num_bits(const BIGNUM *a) |
167 |
|
|
{ |
168 |
|
|
BN_ULONG l; |
169 |
|
|
int i; |
170 |
|
|
|
171 |
|
|
bn_check_top(a); |
172 |
|
|
|
173 |
|
|
if (a->top == 0) return(0); |
174 |
|
|
l=a->d[a->top-1]; |
175 |
|
|
assert(l != 0); |
176 |
|
|
i=(a->top-1)*BN_BITS2; |
177 |
|
|
return(i+BN_num_bits_word(l)); |
178 |
|
|
} |
179 |
|
|
|
180 |
|
|
void BN_clear_free(BIGNUM *a) |
181 |
|
|
{ |
182 |
|
|
int i; |
183 |
|
|
|
184 |
|
|
if (a == NULL) return; |
185 |
|
|
if (a->d != NULL) |
186 |
|
|
{ |
187 |
|
|
memset(a->d,0,a->dmax*sizeof(a->d[0])); |
188 |
|
|
if (!(BN_get_flags(a,BN_FLG_STATIC_DATA))) |
189 |
|
|
OPENSSL_free(a->d); |
190 |
|
|
} |
191 |
|
|
i=BN_get_flags(a,BN_FLG_MALLOCED); |
192 |
|
|
memset(a,0,sizeof(BIGNUM)); |
193 |
|
|
if (i) |
194 |
|
|
OPENSSL_free(a); |
195 |
|
|
} |
196 |
|
|
|
197 |
|
|
void BN_free(BIGNUM *a) |
198 |
|
|
{ |
199 |
|
|
if (a == NULL) return; |
200 |
|
|
if ((a->d != NULL) && !(BN_get_flags(a,BN_FLG_STATIC_DATA))) |
201 |
|
|
OPENSSL_free(a->d); |
202 |
|
|
a->flags|=BN_FLG_FREE; /* REMOVE? */ |
203 |
|
|
if (a->flags & BN_FLG_MALLOCED) |
204 |
|
|
OPENSSL_free(a); |
205 |
|
|
} |
206 |
|
|
|
207 |
|
|
void BN_init(BIGNUM *a) |
208 |
|
|
{ |
209 |
|
|
memset(a,0,sizeof(BIGNUM)); |
210 |
|
|
} |
211 |
|
|
|
212 |
|
|
#if 0 |
213 |
|
|
BIGNUM *BN_new(void) |
214 |
|
|
{ |
215 |
|
|
BIGNUM *ret; |
216 |
|
|
|
217 |
|
|
if ((ret=(BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) |
218 |
|
|
{ |
219 |
|
|
BNerr(BN_F_BN_NEW,ERR_R_MALLOC_FAILURE); |
220 |
|
|
return(NULL); |
221 |
|
|
} |
222 |
|
|
ret->flags=BN_FLG_MALLOCED; |
223 |
|
|
ret->top=0; |
224 |
|
|
ret->neg=0; |
225 |
|
|
ret->dmax=0; |
226 |
|
|
ret->d=NULL; |
227 |
|
|
return(ret); |
228 |
|
|
} |
229 |
|
|
#endif |
230 |
|
|
|
231 |
|
|
/* This is an internal function that should not be used in applications. |
232 |
|
|
* It ensures that 'b' has enough room for a 'words' word number number. |
233 |
|
|
* It is mostly used by the various BIGNUM routines. If there is an error, |
234 |
|
|
* NULL is returned. If not, 'b' is returned. */ |
235 |
|
|
|
236 |
|
|
BIGNUM *bn_expand2(BIGNUM *b, int words) |
237 |
|
|
{ |
238 |
|
|
BN_ULONG *A,*a; |
239 |
|
|
const BN_ULONG *B; |
240 |
|
|
int i; |
241 |
|
|
|
242 |
|
|
bn_check_top(b); |
243 |
|
|
|
244 |
|
|
if (words > b->dmax) |
245 |
|
|
{ |
246 |
|
|
if (words > (INT_MAX/(4*BN_BITS2))) |
247 |
|
|
{ |
248 |
|
|
BNerr(BN_F_BN_EXPAND2,BN_R_BIGNUM_TOO_LONG); |
249 |
|
|
return NULL; |
250 |
|
|
} |
251 |
|
|
|
252 |
|
|
bn_check_top(b); |
253 |
|
|
if (BN_get_flags(b,BN_FLG_STATIC_DATA)) |
254 |
|
|
{ |
255 |
|
|
BNerr(BN_F_BN_EXPAND2,BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); |
256 |
|
|
return(NULL); |
257 |
|
|
} |
258 |
|
|
a=A=(BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1)); |
259 |
|
|
if (A == NULL) |
260 |
|
|
{ |
261 |
|
|
BNerr(BN_F_BN_EXPAND2,ERR_R_MALLOC_FAILURE); |
262 |
|
|
return(NULL); |
263 |
|
|
} |
264 |
|
|
#if 1 |
265 |
|
|
B=b->d; |
266 |
|
|
/* Check if the previous number needs to be copied */ |
267 |
|
|
if (B != NULL) |
268 |
|
|
{ |
269 |
|
|
#if 0 |
270 |
|
|
/* This lot is an unrolled loop to copy b->top |
271 |
|
|
* BN_ULONGs from B to A |
272 |
|
|
*/ |
273 |
|
|
/* |
274 |
|
|
* I have nothing against unrolling but it's usually done for |
275 |
|
|
* several reasons, namely: |
276 |
|
|
* - minimize percentage of decision making code, i.e. branches; |
277 |
|
|
* - avoid cache trashing; |
278 |
|
|
* - make it possible to schedule loads earlier; |
279 |
|
|
* Now let's examine the code below. The cornerstone of C is |
280 |
|
|
* "programmer is always right" and that's what we love it for:-) |
281 |
|
|
* For this very reason C compilers have to be paranoid when it |
282 |
|
|
* comes to data aliasing and assume the worst. Yeah, but what |
283 |
|
|
* does it mean in real life? This means that loop body below will |
284 |
|
|
* be compiled to sequence of loads immediately followed by stores |
285 |
|
|
* as compiler assumes the worst, something in A==B+1 style. As a |
286 |
|
|
* result CPU pipeline is going to starve for incoming data. Secondly |
287 |
|
|
* if A and B happen to share same cache line such code is going to |
288 |
|
|
* cause severe cache trashing. Both factors have severe impact on |
289 |
|
|
* performance of modern CPUs and this is the reason why this |
290 |
|
|
* particular piece of code is #ifdefed away and replaced by more |
291 |
|
|
* "friendly" version found in #else section below. This comment |
292 |
|
|
* also applies to BN_copy function. |
293 |
|
|
* |
294 |
|
|
* <appro@fy.chalmers.se> |
295 |
|
|
*/ |
296 |
|
|
for (i=b->top&(~7); i>0; i-=8) |
297 |
|
|
{ |
298 |
|
|
A[0]=B[0]; A[1]=B[1]; A[2]=B[2]; A[3]=B[3]; |
299 |
|
|
A[4]=B[4]; A[5]=B[5]; A[6]=B[6]; A[7]=B[7]; |
300 |
|
|
A+=8; |
301 |
|
|
B+=8; |
302 |
|
|
} |
303 |
|
|
switch (b->top&7) |
304 |
|
|
{ |
305 |
|
|
case 7: |
306 |
|
|
A[6]=B[6]; |
307 |
|
|
case 6: |
308 |
|
|
A[5]=B[5]; |
309 |
|
|
case 5: |
310 |
|
|
A[4]=B[4]; |
311 |
|
|
case 4: |
312 |
|
|
A[3]=B[3]; |
313 |
|
|
case 3: |
314 |
|
|
A[2]=B[2]; |
315 |
|
|
case 2: |
316 |
|
|
A[1]=B[1]; |
317 |
|
|
case 1: |
318 |
|
|
A[0]=B[0]; |
319 |
|
|
case 0: |
320 |
|
|
/* I need the 'case 0' entry for utrix cc. |
321 |
|
|
* If the optimizer is turned on, it does the |
322 |
|
|
* switch table by doing |
323 |
|
|
* a=top&7 |
324 |
|
|
* a--; |
325 |
|
|
* goto jump_table[a]; |
326 |
|
|
* If top is 0, this makes us jump to 0xffffffc |
327 |
|
|
* which is rather bad :-(. |
328 |
|
|
* eric 23-Apr-1998 |
329 |
|
|
*/ |
330 |
|
|
; |
331 |
|
|
} |
332 |
|
|
#else |
333 |
|
|
for (i=b->top>>2; i>0; i--,A+=4,B+=4) |
334 |
|
|
{ |
335 |
|
|
/* |
336 |
|
|
* The fact that the loop is unrolled |
337 |
|
|
* 4-wise is a tribute to Intel. It's |
338 |
|
|
* the one that doesn't have enough |
339 |
|
|
* registers to accomodate more data. |
340 |
|
|
* I'd unroll it 8-wise otherwise:-) |
341 |
|
|
* |
342 |
|
|
* <appro@fy.chalmers.se> |
343 |
|
|
*/ |
344 |
|
|
BN_ULONG a0,a1,a2,a3; |
345 |
|
|
a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; |
346 |
|
|
A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; |
347 |
|
|
} |
348 |
|
|
switch (b->top&3) |
349 |
|
|
{ |
350 |
|
|
case 3: A[2]=B[2]; |
351 |
|
|
case 2: A[1]=B[1]; |
352 |
|
|
case 1: A[0]=B[0]; |
353 |
|
|
case 0: ; /* ultrix cc workaround, see above */ |
354 |
|
|
} |
355 |
|
|
#endif |
356 |
|
|
OPENSSL_free(b->d); |
357 |
|
|
} |
358 |
|
|
|
359 |
|
|
b->d=a; |
360 |
|
|
b->dmax=words; |
361 |
|
|
|
362 |
|
|
/* Now need to zero any data between b->top and b->max */ |
363 |
|
|
|
364 |
|
|
A= &(b->d[b->top]); |
365 |
|
|
for (i=(b->dmax - b->top)>>3; i>0; i--,A+=8) |
366 |
|
|
{ |
367 |
|
|
A[0]=0; A[1]=0; A[2]=0; A[3]=0; |
368 |
|
|
A[4]=0; A[5]=0; A[6]=0; A[7]=0; |
369 |
|
|
} |
370 |
|
|
for (i=(b->dmax - b->top)&7; i>0; i--,A++) |
371 |
|
|
A[0]=0; |
372 |
|
|
#else |
373 |
|
|
memset(A,0,sizeof(BN_ULONG)*(words+1)); |
374 |
|
|
memcpy(A,b->d,sizeof(b->d[0])*b->top); |
375 |
|
|
b->d=a; |
376 |
|
|
b->max=words; |
377 |
|
|
#endif |
378 |
|
|
|
379 |
|
|
/* memset(&(p[b->max]),0,((words+1)-b->max)*sizeof(BN_ULONG)); */ |
380 |
|
|
/* { int i; for (i=b->max; i<words+1; i++) p[i]=i;} */ |
381 |
|
|
|
382 |
|
|
} |
383 |
|
|
return(b); |
384 |
|
|
} |
385 |
|
|
|
386 |
|
|
#if 0 |
387 |
|
|
BIGNUM *BN_dup(const BIGNUM *a) |
388 |
|
|
{ |
389 |
|
|
BIGNUM *r; |
390 |
|
|
|
391 |
|
|
if (a == NULL) return NULL; |
392 |
|
|
|
393 |
|
|
bn_check_top(a); |
394 |
|
|
|
395 |
|
|
r=BN_new(); |
396 |
|
|
if (r == NULL) return(NULL); |
397 |
|
|
return((BIGNUM *)BN_copy(r,a)); |
398 |
|
|
} |
399 |
|
|
#endif |
400 |
|
|
|
401 |
|
|
BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) |
402 |
|
|
{ |
403 |
|
|
int i; |
404 |
|
|
BN_ULONG *A; |
405 |
|
|
const BN_ULONG *B; |
406 |
|
|
|
407 |
|
|
bn_check_top(b); |
408 |
|
|
|
409 |
|
|
if (a == b) return(a); |
410 |
|
|
if (bn_wexpand(a,b->top) == NULL) return(NULL); |
411 |
|
|
|
412 |
|
|
#if 1 |
413 |
|
|
A=a->d; |
414 |
|
|
B=b->d; |
415 |
|
|
for (i=b->top>>2; i>0; i--,A+=4,B+=4) |
416 |
|
|
{ |
417 |
|
|
BN_ULONG a0,a1,a2,a3; |
418 |
|
|
a0=B[0]; a1=B[1]; a2=B[2]; a3=B[3]; |
419 |
|
|
A[0]=a0; A[1]=a1; A[2]=a2; A[3]=a3; |
420 |
|
|
} |
421 |
|
|
switch (b->top&3) |
422 |
|
|
{ |
423 |
|
|
case 3: A[2]=B[2]; |
424 |
|
|
case 2: A[1]=B[1]; |
425 |
|
|
case 1: A[0]=B[0]; |
426 |
|
|
case 0: ; /* ultrix cc workaround, see comments in bn_expand2 */ |
427 |
|
|
} |
428 |
|
|
#else |
429 |
|
|
memcpy(a->d,b->d,sizeof(b->d[0])*b->top); |
430 |
|
|
#endif |
431 |
|
|
|
432 |
|
|
/* memset(&(a->d[b->top]),0,sizeof(a->d[0])*(a->max-b->top));*/ |
433 |
|
|
a->top=b->top; |
434 |
|
|
if ((a->top == 0) && (a->d != NULL)) |
435 |
|
|
a->d[0]=0; |
436 |
|
|
a->neg=b->neg; |
437 |
|
|
return(a); |
438 |
|
|
} |
439 |
|
|
|
440 |
|
|
#if 0 |
441 |
|
|
void BN_clear(BIGNUM *a) |
442 |
|
|
{ |
443 |
|
|
if (a->d != NULL) |
444 |
|
|
memset(a->d,0,a->dmax*sizeof(a->d[0])); |
445 |
|
|
a->top=0; |
446 |
|
|
a->neg=0; |
447 |
|
|
} |
448 |
|
|
|
449 |
|
|
BN_ULONG BN_get_word(BIGNUM *a) |
450 |
|
|
{ |
451 |
|
|
int i,n; |
452 |
|
|
BN_ULONG ret=0; |
453 |
|
|
|
454 |
|
|
n=BN_num_bytes(a); |
455 |
|
|
if (n > sizeof(BN_ULONG)) |
456 |
|
|
return(BN_MASK2); |
457 |
|
|
for (i=a->top-1; i>=0; i--) |
458 |
|
|
{ |
459 |
|
|
#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ |
460 |
|
|
ret<<=BN_BITS4; /* stops the compiler complaining */ |
461 |
|
|
ret<<=BN_BITS4; |
462 |
|
|
#else |
463 |
|
|
ret=0; |
464 |
|
|
#endif |
465 |
|
|
ret|=a->d[i]; |
466 |
|
|
} |
467 |
|
|
return(ret); |
468 |
|
|
} |
469 |
|
|
#endif |
470 |
|
|
|
471 |
|
|
int BN_set_word(BIGNUM *a, BN_ULONG w) |
472 |
|
|
{ |
473 |
|
|
int i,n; |
474 |
|
|
if (bn_expand(a,sizeof(BN_ULONG)*8) == NULL) return(0); |
475 |
|
|
|
476 |
|
|
n=sizeof(BN_ULONG)/BN_BYTES; |
477 |
|
|
a->neg=0; |
478 |
|
|
a->top=0; |
479 |
|
|
a->d[0]=(BN_ULONG)w&BN_MASK2; |
480 |
|
|
if (a->d[0] != 0) a->top=1; |
481 |
|
|
for (i=1; i<n; i++) |
482 |
|
|
{ |
483 |
|
|
/* the following is done instead of |
484 |
|
|
* w>>=BN_BITS2 so compilers don't complain |
485 |
|
|
* on builds where sizeof(long) == BN_TYPES */ |
486 |
|
|
#ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */ |
487 |
|
|
w>>=BN_BITS4; |
488 |
|
|
w>>=BN_BITS4; |
489 |
|
|
#else |
490 |
|
|
w=0; |
491 |
|
|
#endif |
492 |
|
|
a->d[i]=(BN_ULONG)w&BN_MASK2; |
493 |
|
|
if (a->d[i] != 0) a->top=i+1; |
494 |
|
|
} |
495 |
|
|
return(1); |
496 |
|
|
} |
497 |
|
|
|
498 |
|
|
/* ignore negative */ |
499 |
|
|
BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
500 |
|
|
{ |
501 |
|
|
unsigned int i,m; |
502 |
|
|
unsigned int n; |
503 |
|
|
BN_ULONG l; |
504 |
|
|
|
505 |
|
|
#if 0 |
506 |
|
|
if (ret == NULL) ret=BN_new(); |
507 |
|
|
#endif |
508 |
|
|
if (ret == NULL) return(NULL); |
509 |
|
|
l=0; |
510 |
|
|
n=len; |
511 |
|
|
if (n == 0) |
512 |
|
|
{ |
513 |
|
|
ret->top=0; |
514 |
|
|
return(ret); |
515 |
|
|
} |
516 |
|
|
if (bn_expand(ret,(int)(n+2)*8) == NULL) |
517 |
|
|
return(NULL); |
518 |
|
|
i=((n-1)/BN_BYTES)+1; |
519 |
|
|
m=((n-1)%(BN_BYTES)); |
520 |
|
|
ret->top=i; |
521 |
|
|
while (n-- > 0) |
522 |
|
|
{ |
523 |
|
|
l=(l<<8L)| *(s++); |
524 |
|
|
if (m-- == 0) |
525 |
|
|
{ |
526 |
|
|
ret->d[--i]=l; |
527 |
|
|
l=0; |
528 |
|
|
m=BN_BYTES-1; |
529 |
|
|
} |
530 |
|
|
} |
531 |
|
|
/* need to call this due to clear byte at top if avoiding |
532 |
|
|
* having the top bit set (-ve number) */ |
533 |
|
|
bn_fix_top(ret); |
534 |
|
|
return(ret); |
535 |
|
|
} |
536 |
|
|
|
537 |
|
|
/* ignore negative */ |
538 |
|
|
int BN_bn2bin(const BIGNUM *a, unsigned char *to) |
539 |
|
|
{ |
540 |
|
|
int n,i; |
541 |
|
|
BN_ULONG l; |
542 |
|
|
|
543 |
|
|
n=i=BN_num_bytes(a); |
544 |
|
|
while (i-- > 0) |
545 |
|
|
{ |
546 |
|
|
l=a->d[i/BN_BYTES]; |
547 |
|
|
*(to++)=(unsigned char)(l>>(8*(i%BN_BYTES)))&0xff; |
548 |
|
|
} |
549 |
|
|
return(n); |
550 |
|
|
} |
551 |
|
|
|
552 |
|
|
int BN_ucmp(const BIGNUM *a, const BIGNUM *b) |
553 |
|
|
{ |
554 |
|
|
int i; |
555 |
|
|
BN_ULONG t1,t2,*ap,*bp; |
556 |
|
|
|
557 |
|
|
bn_check_top(a); |
558 |
|
|
bn_check_top(b); |
559 |
|
|
|
560 |
|
|
i=a->top-b->top; |
561 |
|
|
if (i != 0) return(i); |
562 |
|
|
ap=a->d; |
563 |
|
|
bp=b->d; |
564 |
|
|
for (i=a->top-1; i>=0; i--) |
565 |
|
|
{ |
566 |
|
|
t1= ap[i]; |
567 |
|
|
t2= bp[i]; |
568 |
|
|
if (t1 != t2) |
569 |
|
|
return(t1 > t2?1:-1); |
570 |
|
|
} |
571 |
|
|
return(0); |
572 |
|
|
} |
573 |
|
|
|
574 |
|
|
#if 0 |
575 |
|
|
int BN_cmp(const BIGNUM *a, const BIGNUM *b) |
576 |
|
|
{ |
577 |
|
|
int i; |
578 |
|
|
int gt,lt; |
579 |
|
|
BN_ULONG t1,t2; |
580 |
|
|
|
581 |
|
|
if ((a == NULL) || (b == NULL)) |
582 |
|
|
{ |
583 |
|
|
if (a != NULL) |
584 |
|
|
return(-1); |
585 |
|
|
else if (b != NULL) |
586 |
|
|
return(1); |
587 |
|
|
else |
588 |
|
|
return(0); |
589 |
|
|
} |
590 |
|
|
|
591 |
|
|
bn_check_top(a); |
592 |
|
|
bn_check_top(b); |
593 |
|
|
|
594 |
|
|
if (a->neg != b->neg) |
595 |
|
|
{ |
596 |
|
|
if (a->neg) |
597 |
|
|
return(-1); |
598 |
|
|
else return(1); |
599 |
|
|
} |
600 |
|
|
if (a->neg == 0) |
601 |
|
|
{ gt=1; lt= -1; } |
602 |
|
|
else { gt= -1; lt=1; } |
603 |
|
|
|
604 |
|
|
if (a->top > b->top) return(gt); |
605 |
|
|
if (a->top < b->top) return(lt); |
606 |
|
|
for (i=a->top-1; i>=0; i--) |
607 |
|
|
{ |
608 |
|
|
t1=a->d[i]; |
609 |
|
|
t2=b->d[i]; |
610 |
|
|
if (t1 > t2) return(gt); |
611 |
|
|
if (t1 < t2) return(lt); |
612 |
|
|
} |
613 |
|
|
return(0); |
614 |
|
|
} |
615 |
|
|
|
616 |
|
|
int BN_set_bit(BIGNUM *a, int n) |
617 |
|
|
{ |
618 |
|
|
int i,j,k; |
619 |
|
|
|
620 |
|
|
i=n/BN_BITS2; |
621 |
|
|
j=n%BN_BITS2; |
622 |
|
|
if (a->top <= i) |
623 |
|
|
{ |
624 |
|
|
if (bn_wexpand(a,i+1) == NULL) return(0); |
625 |
|
|
for(k=a->top; k<i+1; k++) |
626 |
|
|
a->d[k]=0; |
627 |
|
|
a->top=i+1; |
628 |
|
|
} |
629 |
|
|
|
630 |
|
|
a->d[i]|=(((BN_ULONG)1)<<j); |
631 |
|
|
return(1); |
632 |
|
|
} |
633 |
|
|
|
634 |
|
|
int BN_clear_bit(BIGNUM *a, int n) |
635 |
|
|
{ |
636 |
|
|
int i,j; |
637 |
|
|
|
638 |
|
|
i=n/BN_BITS2; |
639 |
|
|
j=n%BN_BITS2; |
640 |
|
|
if (a->top <= i) return(0); |
641 |
|
|
|
642 |
|
|
a->d[i]&=(~(((BN_ULONG)1)<<j)); |
643 |
|
|
bn_fix_top(a); |
644 |
|
|
return(1); |
645 |
|
|
} |
646 |
|
|
#endif |
647 |
|
|
|
648 |
|
|
int BN_is_bit_set(const BIGNUM *a, int n) |
649 |
|
|
{ |
650 |
|
|
int i,j; |
651 |
|
|
|
652 |
|
|
if (n < 0) return(0); |
653 |
|
|
i=n/BN_BITS2; |
654 |
|
|
j=n%BN_BITS2; |
655 |
|
|
if (a->top <= i) return(0); |
656 |
|
|
return((a->d[i]&(((BN_ULONG)1)<<j))?1:0); |
657 |
|
|
} |
658 |
|
|
|
659 |
|
|
#if 0 |
660 |
|
|
int BN_mask_bits(BIGNUM *a, int n) |
661 |
|
|
{ |
662 |
|
|
int b,w; |
663 |
|
|
|
664 |
|
|
w=n/BN_BITS2; |
665 |
|
|
b=n%BN_BITS2; |
666 |
|
|
if (w >= a->top) return(0); |
667 |
|
|
if (b == 0) |
668 |
|
|
a->top=w; |
669 |
|
|
else |
670 |
|
|
{ |
671 |
|
|
a->top=w+1; |
672 |
|
|
a->d[w]&= ~(BN_MASK2<<b); |
673 |
|
|
} |
674 |
|
|
bn_fix_top(a); |
675 |
|
|
return(1); |
676 |
|
|
} |
677 |
|
|
|
678 |
|
|
int bn_cmp_words(BN_ULONG *a, BN_ULONG *b, int n) |
679 |
|
|
{ |
680 |
|
|
int i; |
681 |
|
|
BN_ULONG aa,bb; |
682 |
|
|
|
683 |
|
|
aa=a[n-1]; |
684 |
|
|
bb=b[n-1]; |
685 |
|
|
if (aa != bb) return((aa > bb)?1:-1); |
686 |
|
|
for (i=n-2; i>=0; i--) |
687 |
|
|
{ |
688 |
|
|
aa=a[i]; |
689 |
|
|
bb=b[i]; |
690 |
|
|
if (aa != bb) return((aa > bb)?1:-1); |
691 |
|
|
} |
692 |
|
|
return(0); |
693 |
|
|
} |
694 |
|
|
#endif |