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