1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young (eay@cryptsoft.com).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young (eay@cryptsoft.com)"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.]
56 */
57
58#include "../bn/bn.h"
59#include "../bn/crypto.h"
60#include "../bn/err.h"
61
62#include "stddef.h"
63#include "stdio.h"
64
65void BN_init(BIGNUM *a)
66{
67 memset(a, 0, sizeof(BIGNUM));
68 bn_check_top(a);
69}
70
71BIGNUM *BN_new(void)
72{
73 BIGNUM *ret;
74
75 if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) {
76 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
77 return (NULL);
78 }
79 ret->flags = BN_FLG_MALLOCED;
80 ret->top = 0;
81 ret->neg = 0;
82 ret->dmax = 0;
83 ret->d = NULL;
84 bn_check_top(ret);
85 return (ret);
86}
87
88BIGNUM *BN_dup(const BIGNUM *a)
89{
90 BIGNUM *t;
91
92 if (a == NULL)
93 return NULL;
94 bn_check_top(a);
95
96 t = BN_new();
97 if (t == NULL)
98 return NULL;
99 if (!BN_copy(t, a)) {
100 BN_free(t);
101 return NULL;
102 }
103 bn_check_top(t);
104 return t;
105}
106
107BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
108{
109 int i;
110 BN_ULONG *A;
111 const BN_ULONG *B;
112
113 bn_check_top(b);
114
115 if (a == b)
116 return (a);
117 if (bn_wexpand(a, b->top) == NULL)
118 return (NULL);
119
120#if 1
121 A = a->d;
122 B = b->d;
123 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
124 BN_ULONG a0, a1, a2, a3;
125 a0 = B[0];
126 a1 = B[1];
127 a2 = B[2];
128 a3 = B[3];
129 A[0] = a0;
130 A[1] = a1;
131 A[2] = a2;
132 A[3] = a3;
133 }
134 /* ultrix cc workaround, see comments in bn_expand_internal */
135 switch (b->top & 3) {
136 case 3:
137 A[2] = B[2];
138 case 2:
139 A[1] = B[1];
140 case 1:
141 A[0] = B[0];
142 case 0:;
143 }
144#else
145 memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
146#endif
147
148 a->top = b->top;
149 a->neg = b->neg;
150 bn_check_top(a);
151 return (a);
152}
153
154void BN_clear(BIGNUM *a)
155{
156 bn_check_top(a);
157 if (a->d != NULL)
158 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
159 a->top = 0;
160 a->neg = 0;
161}
162
163void BN_clear_free(BIGNUM *a)
164{
165 int i;
166
167 if (a == NULL)
168 return;
169 bn_check_top(a);
170 if (a->d != NULL) {
171 OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0]));
172 if (!(BN_get_flags(a, BN_FLG_STATIC_DATA)))
173 OPENSSL_free(a->d);
174 }
175 i = BN_get_flags(a, BN_FLG_MALLOCED);
176 OPENSSL_cleanse(a, sizeof(BIGNUM));
177 if (i)
178 OPENSSL_free(a);
179}
180
181void BN_free(BIGNUM *a)
182{
183 if (a == NULL)
184 return;
185 bn_check_top(a);
186 if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA)))
187 OPENSSL_free(a->d);
188 if (a->flags & BN_FLG_MALLOCED)
189 OPENSSL_free(a);
190 else {
191#ifndef OPENSSL_NO_DEPRECATED
192 a->flags |= BN_FLG_FREE;
193#endif
194 a->d = NULL;
195 }
196}
197
198void BN_set_negative(BIGNUM *a, int b)
199{
200 if (b && !BN_is_zero(a))
201 a->neg = 1;
202 else
203 a->neg = 0;
204}
205
206int BN_is_bit_set(const BIGNUM *a, int n)
207{
208 int i, j;
209
210 bn_check_top(a);
211 if (n < 0)
212 return 0;
213 i = n / BN_BITS2;
214 j = n % BN_BITS2;
215 if (a->top <= i)
216 return 0;
217 return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
218}
219
220int BN_num_bits_word(BN_ULONG l)
221{
222 static const unsigned char bits[256] = {
223 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
224 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
225 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
226 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
227 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
228 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
229 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
230 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
231 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
232 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
233 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
234 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
235 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
236 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
237 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
238 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
239 };
240
241#if defined(SIXTY_FOUR_BIT_LONG)
242 if (l & 0xffffffff00000000L) {
243 if (l & 0xffff000000000000L) {
244 if (l & 0xff00000000000000L) {
245 return (bits[(int)(l >> 56)] + 56);
246 } else
247 return (bits[(int)(l >> 48)] + 48);
248 } else {
249 if (l & 0x0000ff0000000000L) {
250 return (bits[(int)(l >> 40)] + 40);
251 } else
252 return (bits[(int)(l >> 32)] + 32);
253 }
254 } else
255#else
256# ifdef SIXTY_FOUR_BIT
257 if (l & 0xffffffff00000000LL) {
258 if (l & 0xffff000000000000LL) {
259 if (l & 0xff00000000000000LL) {
260 return (bits[(int)(l >> 56)] + 56);
261 } else
262 return (bits[(int)(l >> 48)] + 48);
263 } else {
264 if (l & 0x0000ff0000000000LL) {
265 return (bits[(int)(l >> 40)] + 40);
266 } else
267 return (bits[(int)(l >> 32)] + 32);
268 }
269 } else
270# endif
271#endif
272 {
273#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
274 if (l & 0xffff0000L) {
275 if (l & 0xff000000L)
276 return (bits[(int)(l >> 24L)] + 24);
277 else
278 return (bits[(int)(l >> 16L)] + 16);
279 } else
280#endif
281 {
282#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
283 if (l & 0xff00L)
284 return (bits[(int)(l >> 8)] + 8);
285 else
286#endif
287 return (bits[(int)(l)]);
288 }
289 }
290}
291
292int BN_num_bits(const BIGNUM *a)
293{
294 int i = a->top - 1;
295 bn_check_top(a);
296
297 if (BN_is_zero(a))
298 return 0;
299 return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
300}
301
302/* This is used both by bn_expand2() and bn_dup_expand() */
303/* The caller MUST check that words > b->dmax before calling this */
304static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
305{
306 BN_ULONG *A, *a = NULL;
307 const BN_ULONG *B;
308 int i;
309
310 bn_check_top(b);
311
312 if (words > (INT_MAX / (4 * BN_BITS2))) {
313 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
314 return NULL;
315 }
316 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
317 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
318 return (NULL);
319 }
320 a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words);
321 if (A == NULL) {
322 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
323 return (NULL);
324 }
325#ifdef PURIFY
326 /*
327 * Valgrind complains in BN_consttime_swap because we process the whole
328 * array even if it's not initialised yet. This doesn't matter in that
329 * function - what's important is constant time operation (we're not
330 * actually going to use the data)
331 */
332 memset(a, 0, sizeof(BN_ULONG) * words);
333#endif
334
335#if 1
336 B = b->d;
337 /* Check if the previous number needs to be copied */
338 if (B != NULL) {
339 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
340 /*
341 * The fact that the loop is unrolled
342 * 4-wise is a tribute to Intel. It's
343 * the one that doesn't have enough
344 * registers to accomodate more data.
345 * I'd unroll it 8-wise otherwise:-)
346 *
347 * <appro@fy.chalmers.se>
348 */
349 BN_ULONG a0, a1, a2, a3;
350 a0 = B[0];
351 a1 = B[1];
352 a2 = B[2];
353 a3 = B[3];
354 A[0] = a0;
355 A[1] = a1;
356 A[2] = a2;
357 A[3] = a3;
358 }
359 /*
360 * workaround for ultrix cc: without 'case 0', the optimizer does
361 * the switch table by doing a=top&3; a--; goto jump_table[a];
362 * which fails for top== 0
363 */
364 switch (b->top & 3) {
365 case 3:
366 A[2] = B[2];
367 case 2:
368 A[1] = B[1];
369 case 1:
370 A[0] = B[0];
371 case 0:
372 ;
373 }
374 }
375#else
376 memset(A, 0, sizeof(BN_ULONG) * words);
377 memcpy(A, b->d, sizeof(b->d[0]) * b->top);
378#endif
379
380 return (a);
381}
382
383BIGNUM *bn_expand2(BIGNUM *b, int words)
384{
385 bn_check_top(b);
386
387 if (words > b->dmax) {
388 BN_ULONG *a = bn_expand_internal(b, words);
389 if (!a)
390 return NULL;
391 if (b->d)
392 OPENSSL_free(b->d);
393 b->d = a;
394 b->dmax = words;
395 }
396
397/* None of this should be necessary because of what b->top means! */
398#if 0
399 /*
400 * NB: bn_wexpand() calls this only if the BIGNUM really has to grow
401 */
402 if (b->top < b->dmax) {
403 int i;
404 BN_ULONG *A = &(b->d[b->top]);
405 for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) {
406 A[0] = 0;
407 A[1] = 0;
408 A[2] = 0;
409 A[3] = 0;
410 A[4] = 0;
411 A[5] = 0;
412 A[6] = 0;
413 A[7] = 0;
414 }
415 for (i = (b->dmax - b->top) & 7; i > 0; i--, A++)
416 A[0] = 0;
417 assert(A == &(b->d[b->dmax]));
418 }
419#endif
420 bn_check_top(b);
421 return b;
422}
423
424int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
425{
426 int i;
427 BN_ULONG aa, bb;
428
429 aa = a[n - 1];
430 bb = b[n - 1];
431 if (aa != bb)
432 return ((aa > bb) ? 1 : -1);
433 for (i = n - 2; i >= 0; i--) {
434 aa = a[i];
435 bb = b[i];
436 if (aa != bb)
437 return ((aa > bb) ? 1 : -1);
438 }
439 return (0);
440}
441
442int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
443{
444 int n, i;
445 n = cl - 1;
446
447 if (dl < 0) {
448 for (i = dl; i < 0; i++) {
449 if (b[n - i] != 0)
450 return -1; /* a < b */
451 }
452 }
453 if (dl > 0) {
454 for (i = dl; i > 0; i--) {
455 if (a[n + i] != 0)
456 return 1; /* a > b */
457 }
458 }
459 return bn_cmp_words(a, b, cl);
460}
461
462BN_ULONG BN_get_word(const BIGNUM *a)
463{
464 if (a->top > 1)
465 return BN_MASK2;
466 else if (a->top == 1)
467 return a->d[0];
468 /* a->top == 0 */
469 return 0;
470}
471
472int BN_set_word(BIGNUM *a, BN_ULONG w)
473{
474 bn_check_top(a);
475 if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
476 return (0);
477 a->neg = 0;
478 a->d[0] = w;
479 a->top = (w ? 1 : 0);
480 bn_check_top(a);
481 return (1);
482}
483
484int BN_add_word(BIGNUM *a, BN_ULONG w)
485{
486 BN_ULONG l;
487 int i;
488
489 bn_check_top(a);
490 w &= BN_MASK2;
491
492 /* degenerate case: w is zero */
493 if (!w)
494 return 1;
495 /* degenerate case: a is zero */
496 if (BN_is_zero(a))
497 return BN_set_word(a, w);
498 /* handle 'a' when negative */
499 if (a->neg) {
500 a->neg = 0;
501 i = BN_sub_word(a, w);
502 if (!BN_is_zero(a))
503 a->neg = !(a->neg);
504 return (i);
505 }
506 for (i = 0; w != 0 && i < a->top; i++) {
507 a->d[i] = l = (a->d[i] + w) & BN_MASK2;
508 w = (w > l) ? 1 : 0;
509 }
510 if (w && i == a->top) {
511 if (bn_wexpand(a, a->top + 1) == NULL)
512 return 0;
513 a->top++;
514 a->d[i] = w;
515 }
516 bn_check_top(a);
517 return (1);
518}
519
520int BN_sub_word(BIGNUM *a, BN_ULONG w)
521{
522 int i;
523
524 bn_check_top(a);
525 w &= BN_MASK2;
526
527 /* degenerate case: w is zero */
528 if (!w)
529 return 1;
530 /* degenerate case: a is zero */
531 if (BN_is_zero(a)) {
532 i = BN_set_word(a, w);
533 if (i != 0)
534 BN_set_negative(a, 1);
535 return i;
536 }
537 /* handle 'a' when negative */
538 if (a->neg) {
539 a->neg = 0;
540 i = BN_add_word(a, w);
541 a->neg = 1;
542 return (i);
543 }
544
545 if ((a->top == 1) && (a->d[0] < w)) {
546 a->d[0] = w - a->d[0];
547 a->neg = 1;
548 return (1);
549 }
550 i = 0;
551 for (;;) {
552 if (a->d[i] >= w) {
553 a->d[i] -= w;
554 break;
555 } else {
556 a->d[i] = (a->d[i] - w) & BN_MASK2;
557 i++;
558 w = 1;
559 }
560 }
561 if ((a->d[i] == 0) && (i == (a->top - 1)))
562 a->top--;
563 bn_check_top(a);
564 return (1);
565}
566
567BN_ULONG BN_div_word(BIGNUM *a, BN_ULONG w)
568{
569 BN_ULONG ret = 0;
570 int i, j;
571
572 bn_check_top(a);
573 w &= BN_MASK2;
574
575 if (!w)
576 /* actually this an error (division by zero) */
577 return (BN_ULONG)-1;
578 if (a->top == 0)
579 return 0;
580
581 /* normalize input (so bn_div_words doesn't complain) */
582 j = BN_BITS2 - BN_num_bits_word(w);
583 w <<= j;
584 if (!BN_lshift(a, a, j))
585 return (BN_ULONG)-1;
586
587 for (i = a->top - 1; i >= 0; i--) {
588 BN_ULONG l, d;
589
590 l = a->d[i];
591 d = bn_div_words(ret, l, w);
592 ret = (l - ((d * w) & BN_MASK2)) & BN_MASK2;
593 a->d[i] = d;
594 }
595 if ((a->top > 0) && (a->d[a->top - 1] == 0))
596 a->top--;
597 ret >>= j;
598 bn_check_top(a);
599 return (ret);
600}
601
602int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
603{
604 int i, nw, lb, rb;
605 BN_ULONG *t, *f;
606 BN_ULONG l;
607
608 bn_check_top(r);
609 bn_check_top(a);
610
611 if (n < 0) {
612 BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT);
613 return 0;
614 }
615
616 r->neg = a->neg;
617 nw = n / BN_BITS2;
618 if (bn_wexpand(r, a->top + nw + 1) == NULL)
619 return (0);
620 lb = n % BN_BITS2;
621 rb = BN_BITS2 - lb;
622 f = a->d;
623 t = r->d;
624 t[a->top + nw] = 0;
625 if (lb == 0)
626 for (i = a->top - 1; i >= 0; i--)
627 t[nw + i] = f[i];
628 else
629 for (i = a->top - 1; i >= 0; i--) {
630 l = f[i];
631 t[nw + i + 1] |= (l >> rb) & BN_MASK2;
632 t[nw + i] = (l << lb) & BN_MASK2;
633 }
634 memset(t, 0, nw * sizeof(t[0]));
635 /*
636 * for (i=0; i<nw; i++) t[i]=0;
637 */
638 r->top = a->top + nw + 1;
639 bn_correct_top(r);
640 bn_check_top(r);
641 return (1);
642}
643
644int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
645{
646 int i, j, nw, lb, rb;
647 BN_ULONG *t, *f;
648 BN_ULONG l, tmp;
649
650 bn_check_top(r);
651 bn_check_top(a);
652
653 if (n < 0) {
654 BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
655 return 0;
656 }
657
658 nw = n / BN_BITS2;
659 rb = n % BN_BITS2;
660 lb = BN_BITS2 - rb;
661 if (nw >= a->top || a->top == 0) {
662 BN_zero(r);
663 return (1);
664 }
665 i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2;
666 if (r != a) {
667 r->neg = a->neg;
668 if (bn_wexpand(r, i) == NULL)
669 return (0);
670 } else {
671 if (n == 0)
672 return 1; /* or the copying loop will go berserk */
673 }
674
675 f = &(a->d[nw]);
676 t = r->d;
677 j = a->top - nw;
678 r->top = i;
679
680 if (rb == 0) {
681 for (i = j; i != 0; i--)
682 *(t++) = *(f++);
683 } else {
684 l = *(f++);
685 for (i = j - 1; i != 0; i--) {
686 tmp = (l >> rb) & BN_MASK2;
687 l = *(f++);
688 *(t++) = (tmp | (l << lb)) & BN_MASK2;
689 }
690 if ((l = (l >> rb) & BN_MASK2))
691 *(t) = l;
692 }
693 bn_check_top(r);
694 return (1);
695}
696
697int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
698{
699 int i;
700 BN_ULONG t1, t2, *ap, *bp;
701
702 bn_check_top(a);
703 bn_check_top(b);
704
705 i = a->top - b->top;
706 if (i != 0)
707 return (i);
708 ap = a->d;
709 bp = b->d;
710 for (i = a->top - 1; i >= 0; i--) {
711 t1 = ap[i];
712 t2 = bp[i];
713 if (t1 != t2)
714 return ((t1 > t2) ? 1 : -1);
715 }
716 return (0);
717}
718
719int BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
720{
721 int max, min, dif;
722 BN_ULONG *ap, *bp, *rp, carry, t1, t2;
723 const BIGNUM *tmp;
724
725 bn_check_top(a);
726 bn_check_top(b);
727
728 if (a->top < b->top) {
729 tmp = a;
730 a = b;
731 b = tmp;
732 }
733 max = a->top;
734 min = b->top;
735 dif = max - min;
736
737 if (bn_wexpand(r, max + 1) == NULL)
738 return 0;
739
740 r->top = max;
741
742 ap = a->d;
743 bp = b->d;
744 rp = r->d;
745
746 carry = bn_add_words(rp, ap, bp, min);
747 rp += min;
748 ap += min;
749 bp += min;
750
751 if (carry) {
752 while (dif) {
753 dif--;
754 t1 = *(ap++);
755 t2 = (t1 + 1) & BN_MASK2;
756 *(rp++) = t2;
757 if (t2) {
758 carry = 0;
759 break;
760 }
761 }
762 if (carry) {
763 /* carry != 0 => dif == 0 */
764 *rp = 1;
765 r->top++;
766 }
767 }
768 if (dif && rp != ap)
769 while (dif--)
770 /* copy remaining words if ap != rp */
771 *(rp++) = *(ap++);
772 r->neg = 0;
773 bn_check_top(r);
774 return 1;
775}
776
777int BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
778{
779 int max, min, dif;
780 register BN_ULONG t1, t2, *ap, *bp, *rp;
781 int i, carry;
782#if defined(IRIX_CC_BUG) && !defined(LINT)
783 int dummy;
784#endif
785
786 bn_check_top(a);
787 bn_check_top(b);
788
789 max = a->top;
790 min = b->top;
791 dif = max - min;
792
793 if (dif < 0) { /* hmm... should not be happening */
794 BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3);
795 return (0);
796 }
797
798 if (bn_wexpand(r, max) == NULL)
799 return (0);
800
801 ap = a->d;
802 bp = b->d;
803 rp = r->d;
804
805#if 1
806 carry = 0;
807 for (i = min; i != 0; i--) {
808 t1 = *(ap++);
809 t2 = *(bp++);
810 if (carry) {
811 carry = (t1 <= t2);
812 t1 = (t1 - t2 - 1) & BN_MASK2;
813 } else {
814 carry = (t1 < t2);
815 t1 = (t1 - t2) & BN_MASK2;
816 }
817# if defined(IRIX_CC_BUG) && !defined(LINT)
818 dummy = t1;
819# endif
820 *(rp++) = t1 & BN_MASK2;
821 }
822#else
823 carry = bn_sub_words(rp, ap, bp, min);
824 ap += min;
825 bp += min;
826 rp += min;
827#endif
828 if (carry) { /* subtracted */
829 if (!dif)
830 /* error: a < b */
831 return 0;
832 while (dif) {
833 dif--;
834 t1 = *(ap++);
835 t2 = (t1 - 1) & BN_MASK2;
836 *(rp++) = t2;
837 if (t1)
838 break;
839 }
840 }
841#if 0
842 memcpy(rp, ap, sizeof(*rp) * (max - i));
843#else
844 if (rp != ap) {
845 for (;;) {
846 if (!dif--)
847 break;
848 rp[0] = ap[0];
849 if (!dif--)
850 break;
851 rp[1] = ap[1];
852 if (!dif--)
853 break;
854 rp[2] = ap[2];
855 if (!dif--)
856 break;
857 rp[3] = ap[3];
858 rp += 4;
859 ap += 4;
860 }
861 }
862#endif
863
864 r->top = max;
865 r->neg = 0;
866 bn_correct_top(r);
867 return (1);
868}
869
870int BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
871{
872 const BIGNUM *tmp;
873 int a_neg = a->neg, ret;
874
875 bn_check_top(a);
876 bn_check_top(b);
877
878 /*-
879 * a + b a+b
880 * a + -b a-b
881 * -a + b b-a
882 * -a + -b -(a+b)
883 */
884 if (a_neg ^ b->neg) {
885 /* only one is negative */
886 if (a_neg) {
887 tmp = a;
888 a = b;
889 b = tmp;
890 }
891
892 /* we are now a - b */
893
894 if (BN_ucmp(a, b) < 0) {
895 if (!BN_usub(r, b, a))
896 return (0);
897 r->neg = 1;
898 } else {
899 if (!BN_usub(r, a, b))
900 return (0);
901 r->neg = 0;
902 }
903 return (1);
904 }
905
906 ret = BN_uadd(r, a, b);
907 r->neg = a_neg;
908 bn_check_top(r);
909 return ret;
910}
911
912int BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
913{
914 int max;
915 int add = 0, neg = 0;
916 const BIGNUM *tmp;
917
918 bn_check_top(a);
919 bn_check_top(b);
920
921 /*-
922 * a - b a-b
923 * a - -b a+b
924 * -a - b -(a+b)
925 * -a - -b b-a
926 */
927 if (a->neg) {
928 if (b->neg) {
929 tmp = a;
930 a = b;
931 b = tmp;
932 } else {
933 add = 1;
934 neg = 1;
935 }
936 } else {
937 if (b->neg) {
938 add = 1;
939 neg = 0;
940 }
941 }
942
943 if (add) {
944 if (!BN_uadd(r, a, b))
945 return (0);
946 r->neg = neg;
947 return (1);
948 }
949
950 /* We are actually doing a - b :-) */
951
952 max = (a->top > b->top) ? a->top : b->top;
953 if (bn_wexpand(r, max) == NULL)
954 return (0);
955 if (BN_ucmp(a, b) < 0) {
956 if (!BN_usub(r, b, a))
957 return (0);
958 r->neg = 1;
959 } else {
960 if (!BN_usub(r, a, b))
961 return (0);
962 r->neg = 0;
963 }
964 bn_check_top(r);
965 return (1);
966}
967
968int BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
969{
970 int i, bits, ret = 0;
971 BIGNUM *v, *rr;
972
973 if (BN_get_flags(p, BN_FLG_CONSTTIME) != 0) {
974 /* BN_FLG_CONSTTIME only supported by BN_mod_exp_mont() */
975 BNerr(BN_F_BN_EXP, ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
976 return -1;
977 }
978
979 BN_CTX_start(ctx);
980 if ((r == a) || (r == p))
981 rr = BN_CTX_get(ctx);
982 else
983 rr = r;
984 v = BN_CTX_get(ctx);
985 if (rr == NULL || v == NULL)
986 goto err;
987
988 if (BN_copy(v, a) == NULL)
989 goto err;
990 bits = BN_num_bits(p);
991
992 if (BN_is_odd(p)) {
993 if (BN_copy(rr, a) == NULL)
994 goto err;
995 } else {
996 if (!BN_one(rr))
997 goto err;
998 }
999
1000 for (i = 1; i < bits; i++) {
1001 if (!BN_sqr(v, v, ctx))
1002 goto err;
1003 if (BN_is_bit_set(p, i)) {
1004 if (!BN_mul(rr, rr, v, ctx))
1005 goto err;
1006 }
1007 }
1008 if (r != rr && BN_copy(r, rr) == NULL)
1009 goto err;
1010
1011 ret = 1;
1012 err:
1013 BN_CTX_end(ctx);
1014 bn_check_top(r);
1015 return (ret);
1016}
1017
1018char *BN_bn2dec(const BIGNUM *a)
1019{
1020 int i = 0, num, ok = 0;
1021 char *buf = NULL;
1022 char *p;
1023 BIGNUM *t = NULL;
1024 BN_ULONG *bn_data = NULL, *lp;
1025 int bn_data_num;
1026
1027 /*-
1028 * get an upper bound for the length of the decimal integer
1029 * num <= (BN_num_bits(a) + 1) * log(2)
1030 * <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1 (rounding error)
1031 * <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1
1032 */
1033 i = BN_num_bits(a) * 3;
1034 num = (i / 10 + i / 1000 + 1) + 1;
1035 bn_data_num = num / BN_DEC_NUM + 1;
1036 bn_data = (BN_ULONG *)OPENSSL_malloc(bn_data_num * sizeof(BN_ULONG));
1037 buf = (char *)OPENSSL_malloc(num + 3);
1038 if ((buf == NULL) || (bn_data == NULL)) {
1039 BNerr(BN_F_BN_BN2DEC, ERR_R_MALLOC_FAILURE);
1040 goto err;
1041 }
1042 if ((t = BN_dup(a)) == NULL)
1043 goto err;
1044
1045#define BUF_REMAIN (num+3 - (size_t)(p - buf))
1046 p = buf;
1047 lp = bn_data;
1048 if (BN_is_zero(t)) {
1049 *(p++) = '0';
1050 *(p++) = '\0';
1051 } else {
1052 if (BN_is_negative(t))
1053 *p++ = '-';
1054
1055 while (!BN_is_zero(t)) {
1056 if (lp - bn_data >= bn_data_num)
1057 goto err;
1058 *lp = BN_div_word(t, BN_DEC_CONV);
1059 if (*lp == (BN_ULONG)-1)
1060 goto err;
1061 lp++;
1062 }
1063 lp--;
1064 /*
1065 * We now have a series of blocks, BN_DEC_NUM chars in length, where
1066 * the last one needs truncation. The blocks need to be reversed in
1067 * order.
1068 */
1069 snprintf(p, BUF_REMAIN, BN_DEC_FMT1, *lp);
1070 while (*p)
1071 p++;
1072 while (lp != bn_data) {
1073 lp--;
1074 snprintf(p, BUF_REMAIN, BN_DEC_FMT2, *lp);
1075 while (*p)
1076 p++;
1077 }
1078 }
1079 ok = 1;
1080 err:
1081 if (bn_data != NULL)
1082 OPENSSL_free(bn_data);
1083 if (t != NULL)
1084 BN_free(t);
1085 if (!ok && buf) {
1086 OPENSSL_free(buf);
1087 buf = NULL;
1088 }
1089
1090 return (buf);
1091}
1092
1093void ERR_put_error(int lib, int func, int reason, const char *file, int line)
1094{
1095}
1096
1097void OPENSSL_cleanse(void *ptr, size_t len)
1098{
1099}
1100
1101void *CRYPTO_malloc(int num, const char *file, int line)
1102{
1103 return malloc(num);
1104}
1105
1106void CRYPTO_free(void *ptr)
1107{
1108 free(ptr);
1109}
1110