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