2 * bn.c: Big Number routines. Needed by Diffie Hellman implementation.
4 * Code copied from openssl distribution and
5 * Modified just enough so that compiles and runs standalone
7 * Copyright (C) 2010, Broadcom Corporation. All Rights Reserved.
9 * Permission to use, copy, modify, and/or distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
16 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
18 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
19 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
21 * $Id: bn.c,v 1.7 2007-10-13 00:50:05 Exp $
23 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
24 * All rights reserved.
26 * This package is an SSL implementation written
27 * by Eric Young (eay@cryptsoft.com).
28 * The implementation was written so as to conform with Netscapes SSL.
30 * This library is free for commercial and non-commercial use as long as
31 * the following conditions are aheared to. The following conditions
32 * apply to all code found in this distribution, be it the RC4, RSA,
33 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
34 * included with this distribution is covered by the same copyright terms
35 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
37 * Copyright remains Eric Young's, and as such any Copyright notices in
38 * the code are not to be removed.
39 * If this package is used in a product, Eric Young should be given attribution
40 * as the author of the parts of the library used.
41 * This can be in the form of a textual message at program startup or
42 * in documentation (online or textual) provided with the package.
44 * Redistribution and use in source and binary forms, with or without
45 * modification, are permitted provided that the following conditions
47 * 1. Redistributions of source code must retain the copyright
48 * notice, this list of conditions and the following disclaimer.
49 * 2. Redistributions in binary form must reproduce the above copyright
50 * notice, this list of conditions and the following disclaimer in the
51 * documentation and/or other materials provided with the distribution.
52 * 3. All advertising materials mentioning features or use of this software
53 * must display the following acknowledgement:
54 * "This product includes cryptographic software written by
55 * Eric Young (eay@cryptsoft.com)"
56 * The word 'cryptographic' can be left out if the rouines from the library
57 * being used are not cryptographic related :-).
58 * 4. If you include any Windows specific code (or a derivative thereof) from
59 * the apps directory (application code) you must include an acknowledgement:
60 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
62 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
63 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
64 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
65 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
66 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
67 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
68 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
69 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
70 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
71 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
74 * The licence and distribution terms for any publically available version or
75 * derivative of this code cannot be changed. i.e. this code cannot simply be
76 * copied and put under another distribution licence
77 * [including the GNU Public Licence.]
80 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
82 * Redistribution and use in source and binary forms, with or without
83 * modification, are permitted provided that the following conditions
86 * 1. Redistributions of source code must retain the above copyright
87 * notice, this list of conditions and the following disclaimer.
89 * 2. Redistributions in binary form must reproduce the above copyright
90 * notice, this list of conditions and the following disclaimer in
91 * the documentation and/or other materials provided with the
94 * 3. All advertising materials mentioning features or use of this
95 * software must display the following acknowledgment:
96 * "This product includes software developed by the OpenSSL Project
97 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
99 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
100 * endorse or promote products derived from this software without
101 * prior written permission. For written permission, please contact
102 * openssl-core@openssl.org.
104 * 5. Products derived from this software may not be called "OpenSSL"
105 * nor may "OpenSSL" appear in their names without prior written
106 * permission of the OpenSSL Project.
108 * 6. Redistributions of any form whatsoever must retain the following
110 * "This product includes software developed by the OpenSSL Project
111 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
113 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
114 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
115 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
116 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
117 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
118 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
119 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
120 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
121 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
122 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
123 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
124 * OF THE POSSIBILITY OF SUCH DAMAGE.
126 * This product includes cryptographic software written by Eric Young
127 * (eay@cryptsoft.com). This product includes software written by Tim
128 * Hudson (tjh@cryptsoft.com).
131 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
132 * for the OpenSSL project.
135 #include <typedefs.h>
140 #include <bcmcrypto/bn.h>
143 #define OPENSSL_malloc malloc
144 #define OPENSSL_free free
145 #define OPENSSL_cleanse(buf, size) memset(buf, 0, size)
148 static bn_rand_fn_t bn_rand_fn
= NULL
;
151 BN_register_RAND(bn_rand_fn_t fn
)
156 /* r can == a or b */
158 BN_add(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
)
171 if (a_neg
^ b
->neg
) {
172 /* only one is negative */
174 tmp
= a
; a
= b
; b
= tmp
;
177 /* we are now a - b */
179 if (BN_ucmp(a
, b
) < 0) {
180 if (!BN_usub(r
, b
, a
)) return (0);
183 if (!BN_usub(r
, a
, b
)) return (0);
189 if (!BN_uadd(r
, a
, b
)) return (0);
190 if (a_neg
) /* both are neg */
197 /* unsigned add of b to a, r must be large enough */
199 BN_uadd(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
)
203 BN_ULONG
*ap
, *bp
, *rp
, carry
, t1
;
209 if (a
->top
< b
->top
) {
210 tmp
= a
; a
= b
; b
= tmp
;
215 if (bn_wexpand(r
, max
+1) == NULL
)
226 carry
= bn_add_words(rp
, ap
, bp
, min
);
236 if ((*(rp
++) = (t1
+1)&BN_MASK2
) >= t1
) {
241 if ((i
>= max
) && carry
) {
250 /* memcpy(rp, ap, sizeof(*ap)*(max-i)); */
255 /* unsigned subtraction of b from a, a must be larger than b. */
257 BN_usub(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
)
260 register BN_ULONG t1
, t2
, *ap
, *bp
, *rp
;
262 #if defined(IRIX_CC_BUG) && !defined(LINT)
269 if (a
->top
< b
->top
) /* hmm... should not be happening */ {
270 BNerr(BN_F_BN_USUB
, BN_R_ARG2_LT_ARG3
);
276 if (bn_wexpand(r
, max
) == NULL
) return (0);
283 for (i
= 0; i
< min
; i
++) {
288 t1
= (t1
-t2
-1)&BN_MASK2
;
292 t1
= (t1
-t2
)&BN_MASK2
;
294 #if defined(IRIX_CC_BUG) && !defined(LINT)
297 *(rp
++) = t1
&BN_MASK2
;
299 if (carry
) /* subtracted */ {
303 t2
= (t1
-1)&BN_MASK2
;
310 if (i
++ >= max
) break;
312 if (i
++ >= max
) break;
314 if (i
++ >= max
) break;
316 if (i
++ >= max
) break;
330 BN_sub(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
)
333 int add
= 0, neg
= 0;
345 if (b
->neg
) { tmp
= a
; a
= b
; b
= tmp
; }
346 else { add
= 1; neg
= 1; }
349 if (b
->neg
) { add
= 1; neg
= 0; }
353 if (!BN_uadd(r
, a
, b
)) return (0);
358 /* We are actually doing a - b :-) */
360 max
= (a
->top
> b
->top
)?a
->top
:b
->top
;
361 if (bn_wexpand(r
, max
) == NULL
) return (0);
362 if (BN_ucmp(a
, b
) < 0) {
363 if (!BN_usub(r
, b
, a
)) return (0);
367 if (!BN_usub(r
, a
, b
)) return (0);
374 #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
377 bn_mul_add_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
382 if (num
<= 0) return (c1
);
385 mul_add(rp
[0], ap
[0], w
, c1
);
386 mul_add(rp
[1], ap
[1], w
, c1
);
387 mul_add(rp
[2], ap
[2], w
, c1
);
388 mul_add(rp
[3], ap
[3], w
, c1
);
389 ap
+= 4; rp
+= 4; num
-= 4;
392 mul_add(rp
[0], ap
[0], w
, c1
); if (--num
== 0) return c1
;
393 mul_add(rp
[1], ap
[1], w
, c1
); if (--num
== 0) return c1
;
394 mul_add(rp
[2], ap
[2], w
, c1
); return c1
;
401 bn_mul_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
406 if (num
<= 0) return (c1
);
409 mul(rp
[0], ap
[0], w
, c1
);
410 mul(rp
[1], ap
[1], w
, c1
);
411 mul(rp
[2], ap
[2], w
, c1
);
412 mul(rp
[3], ap
[3], w
, c1
);
413 ap
+= 4; rp
+= 4; num
-= 4;
416 mul(rp
[0], ap
[0], w
, c1
); if (--num
== 0) return c1
;
417 mul(rp
[1], ap
[1], w
, c1
); if (--num
== 0) return c1
;
418 mul(rp
[2], ap
[2], w
, c1
);
424 bn_sqr_words(BN_ULONG
*r
, const BN_ULONG
*a
, int n
)
429 sqr(r
[0], r
[1], a
[0]);
430 sqr(r
[2], r
[3], a
[1]);
431 sqr(r
[4], r
[5], a
[2]);
432 sqr(r
[6], r
[7], a
[3]);
433 a
+= 4; r
+= 8; n
-= 4;
436 sqr(r
[0], r
[1], a
[0]); if (--n
== 0) return;
437 sqr(r
[2], r
[3], a
[1]); if (--n
== 0) return;
438 sqr(r
[4], r
[5], a
[2]);
442 #else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
445 bn_mul_add_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
451 if (num
<= 0) return ((BN_ULONG
)0);
457 mul_add(rp
[0], ap
[0], bl
, bh
, c
);
458 if (--num
== 0) break;
459 mul_add(rp
[1], ap
[1], bl
, bh
, c
);
460 if (--num
== 0) break;
461 mul_add(rp
[2], ap
[2], bl
, bh
, c
);
462 if (--num
== 0) break;
463 mul_add(rp
[3], ap
[3], bl
, bh
, c
);
464 if (--num
== 0) break;
472 bn_mul_words(BN_ULONG
*rp
, const BN_ULONG
*ap
, int num
, BN_ULONG w
)
478 if (num
<= 0) return ((BN_ULONG
)0);
484 mul(rp
[0], ap
[0], bl
, bh
, carry
);
485 if (--num
== 0) break;
486 mul(rp
[1], ap
[1], bl
, bh
, carry
);
487 if (--num
== 0) break;
488 mul(rp
[2], ap
[2], bl
, bh
, carry
);
489 if (--num
== 0) break;
490 mul(rp
[3], ap
[3], bl
, bh
, carry
);
491 if (--num
== 0) break;
499 bn_sqr_words(BN_ULONG
*r
, const BN_ULONG
*a
, int n
)
504 sqr64(r
[0], r
[1], a
[0]);
507 sqr64(r
[2], r
[3], a
[1]);
510 sqr64(r
[4], r
[5], a
[2]);
513 sqr64(r
[6], r
[7], a
[3]);
521 #endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
523 #if defined(BN_LLONG) && defined(BN_DIV2W)
526 bn_div_words(BN_ULONG h
, BN_ULONG l
, BN_ULONG d
)
528 return ((BN_ULONG
)(((((BN_ULLONG
)h
) << BN_BITS2
)|l
) / (BN_ULLONG
)d
));
533 /* Divide h, l by d and return the result. */
534 /* I need to test this some more :-( */
535 BN_ULONG
bn_div_words(BN_ULONG h
, BN_ULONG l
, BN_ULONG d
)
537 BN_ULONG dh
, dl
, q
, ret
= 0, th
, tl
, t
;
540 if (d
== 0) return (BN_MASK2
);
542 i
= BN_num_bits_word(d
);
543 assert((i
== BN_BITS2
) || (h
> (BN_ULONG
)1 << i
));
550 h
= (h
<< i
) | (l
>> (BN_BITS2
- i
));
553 dh
= (d
&BN_MASK2h
) >> BN_BITS4
;
556 if ((h
>>BN_BITS4
) == dh
)
566 ((tl
) <= ((t
<< BN_BITS4
) |
567 ((l
& BN_MASK2h
) >> BN_BITS4
))))
573 t
= (tl
>> BN_BITS4
);
574 tl
= (tl
<< BN_BITS4
) & BN_MASK2h
;
585 if (--count
== 0) break;
588 h
= ((h
<< BN_BITS4
) | (l
>> BN_BITS4
)) & BN_MASK2
;
589 l
= (l
& BN_MASK2l
) << BN_BITS4
;
594 #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
598 bn_add_words(BN_ULONG
*r
, const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
603 if (n
<= 0) return ((BN_ULONG
)0);
606 ll
+= (BN_ULLONG
)a
[0]+b
[0];
607 r
[0] = (BN_ULONG
)ll
&BN_MASK2
;
611 ll
+= (BN_ULLONG
)a
[1]+b
[1];
612 r
[1] = (BN_ULONG
)ll
&BN_MASK2
;
616 ll
+= (BN_ULLONG
)a
[2]+b
[2];
617 r
[2] = (BN_ULONG
)ll
&BN_MASK2
;
621 ll
+= (BN_ULLONG
)a
[3]+b
[3];
622 r
[3] = (BN_ULONG
)ll
&BN_MASK2
;
630 return ((BN_ULONG
)ll
);
633 #else /* !BN_LLONG */
636 bn_add_words(BN_ULONG
*r
, const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
641 if (n
<= 0) return ((BN_ULONG
)0);
648 l
= (t
+b
[0])&BN_MASK2
;
656 l
= (t
+b
[1])&BN_MASK2
;
664 l
= (t
+b
[2])&BN_MASK2
;
672 l
= (t
+b
[3])&BN_MASK2
;
681 return ((BN_ULONG
)c
);
683 #endif /* !BN_LLONG */
686 bn_sub_words(BN_ULONG
*r
, const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
692 if (n
<= 0) return ((BN_ULONG
)0);
695 t1
= a
[0]; t2
= b
[0];
696 r
[0] = (t1
-t2
-c
)&BN_MASK2
;
697 if (t1
!= t2
) c
= (t1
< t2
);
700 t1
= a
[1]; t2
= b
[1];
701 r
[1] = (t1
-t2
-c
)&BN_MASK2
;
702 if (t1
!= t2
) c
= (t1
< t2
);
705 t1
= a
[2]; t2
= b
[2];
706 r
[2] = (t1
-t2
-c
)&BN_MASK2
;
707 if (t1
!= t2
) c
= (t1
< t2
);
710 t1
= a
[3]; t2
= b
[3];
711 r
[3] = (t1
-t2
-c
)&BN_MASK2
;
712 if (t1
!= t2
) c
= (t1
< t2
);
729 /* mul_add_c(a, b, c0, c1, c2) -- c += a*b for three word number c = (c2, c1, c0) */
730 /* mul_add_c2(a, b, c0, c1, c2) -- c += 2*a*b for three word number c = (c2, c1, c0) */
731 /* sqr_add_c(a, i, c0, c1, c2) -- c += a[i]^2 for three word number c = (c2, c1, c0) */
732 /* sqr_add_c2(a, i, c0, c1, c2) -- c += 2*a[i]*a[j] for three word number c = (c2, c1, c0) */
735 #define mul_add_c(a, b, c0, c1, c2) \
736 t = (BN_ULLONG)a * b; \
737 t1 = (BN_ULONG)Lw(t); \
738 t2 = (BN_ULONG)Hw(t); \
739 c0 = (c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
740 c1 = (c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
742 #define mul_add_c2(a, b, c0, c1, c2) \
743 t = (BN_ULLONG)a * b; \
744 tt = (t + t) & BN_MASK; \
746 t1 = (BN_ULONG)Lw(tt); \
747 t2 = (BN_ULONG)Hw(tt); \
748 c0 = (c0+t1)&BN_MASK2; \
749 if ((c0 < t1) && (((++t2) & BN_MASK2) == 0)) c2++; \
750 c1 = (c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
752 #define sqr_add_c(a, i, c0, c1, c2) \
753 t = (BN_ULLONG)a[i]*a[i]; \
754 t1 = (BN_ULONG)Lw(t); \
755 t2 = (BN_ULONG)Hw(t); \
756 c0 = (c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
757 c1 = (c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
759 #define sqr_add_c2(a, i, j, c0, c1, c2) \
760 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
762 #elif defined(BN_UMULT_HIGH)
764 #define mul_add_c(a, b, c0, c1, c2) { \
765 BN_ULONG ta = (a), tb = (b); \
767 t2 = BN_UMULT_HIGH(ta, tb); \
768 c0 += t1; t2 += (c0 < t1) ? 1 : 0; \
769 c1 += t2; c2 += (c1 < t2) ? 1 : 0; \
772 #define mul_add_c2(a, b, c0, c1, c2) { \
773 BN_ULONG ta = (a), tb = (b), t0; \
774 t1 = BN_UMULT_HIGH(ta, tb); \
776 t2 = t1 + t1; c2 += (t2 < t1) ? 1 : 0; \
777 t1 = t0 + t0; t2 += (t1 < t0) ? 1 : 0; \
778 c0 += t1; t2 += (c0 < t1) ? 1 : 0; \
779 c1 += t2; c2 += (c1 < t2) ? 1 : 0; \
782 #define sqr_add_c(a, i, c0, c1, c2) { \
783 BN_ULONG ta = (a)[i]; \
785 t2 = BN_UMULT_HIGH(ta, ta); \
786 c0 += t1; t2 += (c0 < t1) ? 1 : 0; \
787 c1 += t2; c2 += (c1 < t2) ? 1 : 0; \
790 #define sqr_add_c2(a, i, j, c0, c1, c2) \
791 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
793 #else /* !BN_LLONG */
795 #define mul_add_c(a, b, c0, c1, c2) \
796 t1 = LBITS(a); t2 = HBITS(a); \
797 bl = LBITS(b); bh = HBITS(b); \
798 mul64(t1, t2, bl, bh); \
799 c0 = (c0+t1)&BN_MASK2; if ((c0) < t1) t2++; \
800 c1 = (c1+t2)&BN_MASK2; if ((c1) < t2) c2++;
802 #define mul_add_c2(a, b, c0, c1, c2) \
803 t1 = LBITS(a); t2 = HBITS(a); \
804 bl = LBITS(b); bh = HBITS(b); \
805 mul64(t1, t2, bl, bh); \
806 if (t2 & BN_TBIT) c2++; \
807 t2 = (t2+t2) & BN_MASK2; \
808 if (t1 & BN_TBIT) t2++; \
809 t1 = (t1+t1) & BN_MASK2; \
810 c0 = (c0+t1) & BN_MASK2; \
811 if ((c0 < t1) && (((++t2) & BN_MASK2) == 0)) c2++; \
812 c1 = (c1+t2) & BN_MASK2; if ((c1) < t2) c2++;
814 #define sqr_add_c(a, i, c0, c1, c2) \
815 sqr64(t1, t2, (a)[i]); \
816 c0 = (c0+t1) & BN_MASK2; if ((c0) < t1) t2++; \
817 c1 = (c1+t2) & BN_MASK2; if ((c1) < t2) c2++;
819 #define sqr_add_c2(a, i, j, c0, c1, c2) \
820 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
821 #endif /* !BN_LLONG */
824 bn_mul_comba8(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
837 mul_add_c(a
[0], b
[0], c1
, c2
, c3
);
840 mul_add_c(a
[0], b
[1], c2
, c3
, c1
);
841 mul_add_c(a
[1], b
[0], c2
, c3
, c1
);
844 mul_add_c(a
[2], b
[0], c3
, c1
, c2
);
845 mul_add_c(a
[1], b
[1], c3
, c1
, c2
);
846 mul_add_c(a
[0], b
[2], c3
, c1
, c2
);
849 mul_add_c(a
[0], b
[3], c1
, c2
, c3
);
850 mul_add_c(a
[1], b
[2], c1
, c2
, c3
);
851 mul_add_c(a
[2], b
[1], c1
, c2
, c3
);
852 mul_add_c(a
[3], b
[0], c1
, c2
, c3
);
855 mul_add_c(a
[4], b
[0], c2
, c3
, c1
);
856 mul_add_c(a
[3], b
[1], c2
, c3
, c1
);
857 mul_add_c(a
[2], b
[2], c2
, c3
, c1
);
858 mul_add_c(a
[1], b
[3], c2
, c3
, c1
);
859 mul_add_c(a
[0], b
[4], c2
, c3
, c1
);
862 mul_add_c(a
[0], b
[5], c3
, c1
, c2
);
863 mul_add_c(a
[1], b
[4], c3
, c1
, c2
);
864 mul_add_c(a
[2], b
[3], c3
, c1
, c2
);
865 mul_add_c(a
[3], b
[2], c3
, c1
, c2
);
866 mul_add_c(a
[4], b
[1], c3
, c1
, c2
);
867 mul_add_c(a
[5], b
[0], c3
, c1
, c2
);
870 mul_add_c(a
[6], b
[0], c1
, c2
, c3
);
871 mul_add_c(a
[5], b
[1], c1
, c2
, c3
);
872 mul_add_c(a
[4], b
[2], c1
, c2
, c3
);
873 mul_add_c(a
[3], b
[3], c1
, c2
, c3
);
874 mul_add_c(a
[2], b
[4], c1
, c2
, c3
);
875 mul_add_c(a
[1], b
[5], c1
, c2
, c3
);
876 mul_add_c(a
[0], b
[6], c1
, c2
, c3
);
879 mul_add_c(a
[0], b
[7], c2
, c3
, c1
);
880 mul_add_c(a
[1], b
[6], c2
, c3
, c1
);
881 mul_add_c(a
[2], b
[5], c2
, c3
, c1
);
882 mul_add_c(a
[3], b
[4], c2
, c3
, c1
);
883 mul_add_c(a
[4], b
[3], c2
, c3
, c1
);
884 mul_add_c(a
[5], b
[2], c2
, c3
, c1
);
885 mul_add_c(a
[6], b
[1], c2
, c3
, c1
);
886 mul_add_c(a
[7], b
[0], c2
, c3
, c1
);
889 mul_add_c(a
[7], b
[1], c3
, c1
, c2
);
890 mul_add_c(a
[6], b
[2], c3
, c1
, c2
);
891 mul_add_c(a
[5], b
[3], c3
, c1
, c2
);
892 mul_add_c(a
[4], b
[4], c3
, c1
, c2
);
893 mul_add_c(a
[3], b
[5], c3
, c1
, c2
);
894 mul_add_c(a
[2], b
[6], c3
, c1
, c2
);
895 mul_add_c(a
[1], b
[7], c3
, c1
, c2
);
898 mul_add_c(a
[2], b
[7], c1
, c2
, c3
);
899 mul_add_c(a
[3], b
[6], c1
, c2
, c3
);
900 mul_add_c(a
[4], b
[5], c1
, c2
, c3
);
901 mul_add_c(a
[5], b
[4], c1
, c2
, c3
);
902 mul_add_c(a
[6], b
[3], c1
, c2
, c3
);
903 mul_add_c(a
[7], b
[2], c1
, c2
, c3
);
906 mul_add_c(a
[7], b
[3], c2
, c3
, c1
);
907 mul_add_c(a
[6], b
[4], c2
, c3
, c1
);
908 mul_add_c(a
[5], b
[5], c2
, c3
, c1
);
909 mul_add_c(a
[4], b
[6], c2
, c3
, c1
);
910 mul_add_c(a
[3], b
[7], c2
, c3
, c1
);
913 mul_add_c(a
[4], b
[7], c3
, c1
, c2
);
914 mul_add_c(a
[5], b
[6], c3
, c1
, c2
);
915 mul_add_c(a
[6], b
[5], c3
, c1
, c2
);
916 mul_add_c(a
[7], b
[4], c3
, c1
, c2
);
919 mul_add_c(a
[7], b
[5], c1
, c2
, c3
);
920 mul_add_c(a
[6], b
[6], c1
, c2
, c3
);
921 mul_add_c(a
[5], b
[7], c1
, c2
, c3
);
924 mul_add_c(a
[6], b
[7], c2
, c3
, c1
);
925 mul_add_c(a
[7], b
[6], c2
, c3
, c1
);
928 mul_add_c(a
[7], b
[7], c3
, c1
, c2
);
933 void bn_mul_comba4(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
946 mul_add_c(a
[0], b
[0], c1
, c2
, c3
);
949 mul_add_c(a
[0], b
[1], c2
, c3
, c1
);
950 mul_add_c(a
[1], b
[0], c2
, c3
, c1
);
953 mul_add_c(a
[2], b
[0], c3
, c1
, c2
);
954 mul_add_c(a
[1], b
[1], c3
, c1
, c2
);
955 mul_add_c(a
[0], b
[2], c3
, c1
, c2
);
958 mul_add_c(a
[0], b
[3], c1
, c2
, c3
);
959 mul_add_c(a
[1], b
[2], c1
, c2
, c3
);
960 mul_add_c(a
[2], b
[1], c1
, c2
, c3
);
961 mul_add_c(a
[3], b
[0], c1
, c2
, c3
);
964 mul_add_c(a
[3], b
[1], c2
, c3
, c1
);
965 mul_add_c(a
[2], b
[2], c2
, c3
, c1
);
966 mul_add_c(a
[1], b
[3], c2
, c3
, c1
);
969 mul_add_c(a
[2], b
[3], c3
, c1
, c2
);
970 mul_add_c(a
[3], b
[2], c3
, c1
, c2
);
973 mul_add_c(a
[3], b
[3], c1
, c2
, c3
);
979 bn_sqr_comba8(BN_ULONG
*r
, const BN_ULONG
*a
)
992 sqr_add_c(a
, 0, c1
, c2
, c3
);
995 sqr_add_c2(a
, 1, 0, c2
, c3
, c1
);
998 sqr_add_c(a
, 1, c3
, c1
, c2
);
999 sqr_add_c2(a
, 2, 0, c3
, c1
, c2
);
1002 sqr_add_c2(a
, 3, 0, c1
, c2
, c3
);
1003 sqr_add_c2(a
, 2, 1, c1
, c2
, c3
);
1006 sqr_add_c(a
, 2, c2
, c3
, c1
);
1007 sqr_add_c2(a
, 3, 1, c2
, c3
, c1
);
1008 sqr_add_c2(a
, 4, 0, c2
, c3
, c1
);
1011 sqr_add_c2(a
, 5, 0, c3
, c1
, c2
);
1012 sqr_add_c2(a
, 4, 1, c3
, c1
, c2
);
1013 sqr_add_c2(a
, 3, 2, c3
, c1
, c2
);
1016 sqr_add_c(a
, 3, c1
, c2
, c3
);
1017 sqr_add_c2(a
, 4, 2, c1
, c2
, c3
);
1018 sqr_add_c2(a
, 5, 1, c1
, c2
, c3
);
1019 sqr_add_c2(a
, 6, 0, c1
, c2
, c3
);
1022 sqr_add_c2(a
, 7, 0, c2
, c3
, c1
);
1023 sqr_add_c2(a
, 6, 1, c2
, c3
, c1
);
1024 sqr_add_c2(a
, 5, 2, c2
, c3
, c1
);
1025 sqr_add_c2(a
, 4, 3, c2
, c3
, c1
);
1028 sqr_add_c(a
, 4, c3
, c1
, c2
);
1029 sqr_add_c2(a
, 5, 3, c3
, c1
, c2
);
1030 sqr_add_c2(a
, 6, 2, c3
, c1
, c2
);
1031 sqr_add_c2(a
, 7, 1, c3
, c1
, c2
);
1034 sqr_add_c2(a
, 7, 2, c1
, c2
, c3
);
1035 sqr_add_c2(a
, 6, 3, c1
, c2
, c3
);
1036 sqr_add_c2(a
, 5, 4, c1
, c2
, c3
);
1039 sqr_add_c(a
, 5, c2
, c3
, c1
);
1040 sqr_add_c2(a
, 6, 4, c2
, c3
, c1
);
1041 sqr_add_c2(a
, 7, 3, c2
, c3
, c1
);
1044 sqr_add_c2(a
, 7, 4, c3
, c1
, c2
);
1045 sqr_add_c2(a
, 6, 5, c3
, c1
, c2
);
1048 sqr_add_c(a
, 6, c1
, c2
, c3
);
1049 sqr_add_c2(a
, 7, 5, c1
, c2
, c3
);
1052 sqr_add_c2(a
, 7, 6, c2
, c3
, c1
);
1055 sqr_add_c(a
, 7, c3
, c1
, c2
);
1061 bn_sqr_comba4(BN_ULONG
*r
, const BN_ULONG
*a
)
1069 BN_ULONG c1
, c2
, c3
;
1074 sqr_add_c(a
, 0, c1
, c2
, c3
);
1077 sqr_add_c2(a
, 1, 0, c2
, c3
, c1
);
1080 sqr_add_c(a
, 1, c3
, c1
, c2
);
1081 sqr_add_c2(a
, 2, 0, c3
, c1
, c2
);
1084 sqr_add_c2(a
, 3, 0, c1
, c2
, c3
);
1085 sqr_add_c2(a
, 2, 1, c1
, c2
, c3
);
1088 sqr_add_c(a
, 2, c2
, c3
, c1
);
1089 sqr_add_c2(a
, 3, 1, c2
, c3
, c1
);
1092 sqr_add_c2(a
, 3, 2, c3
, c1
, c2
);
1095 sqr_add_c(a
, 3, c1
, c2
, c3
);
1099 #else /* !BN_MUL_COMBA */
1101 /* hmm... is it faster just to do a multiply? */
1102 #undef bn_sqr_comba4
1104 bn_sqr_comba4(BN_ULONG
*r
, BN_ULONG
*a
)
1107 bn_sqr_normal(r
, a
, 4, t
);
1110 #undef bn_sqr_comba8
1112 bn_sqr_comba8(BN_ULONG
*r
, BN_ULONG
*a
)
1115 bn_sqr_normal(r
, a
, 8, t
);
1119 bn_mul_comba4(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
1121 r
[4] = bn_mul_words(&(r
[0]), a
, 4, b
[0]);
1122 r
[5] = bn_mul_add_words(&(r
[1]), a
, 4, b
[1]);
1123 r
[6] = bn_mul_add_words(&(r
[2]), a
, 4, b
[2]);
1124 r
[7] = bn_mul_add_words(&(r
[3]), a
, 4, b
[3]);
1128 bn_mul_comba8(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
)
1130 r
[ 8] = bn_mul_words(&(r
[0]), a
, 8, b
[0]);
1131 r
[ 9] = bn_mul_add_words(&(r
[1]), a
, 8, b
[1]);
1132 r
[10] = bn_mul_add_words(&(r
[2]), a
, 8, b
[2]);
1133 r
[11] = bn_mul_add_words(&(r
[3]), a
, 8, b
[3]);
1134 r
[12] = bn_mul_add_words(&(r
[4]), a
, 8, b
[4]);
1135 r
[13] = bn_mul_add_words(&(r
[5]), a
, 8, b
[5]);
1136 r
[14] = bn_mul_add_words(&(r
[6]), a
, 8, b
[6]);
1137 r
[15] = bn_mul_add_words(&(r
[7]), a
, 8, b
[7]);
1140 #endif /* !BN_MUL_COMBA */
1148 ret
= (BN_CTX
*)OPENSSL_malloc(sizeof(BN_CTX
));
1150 BNerr(BN_F_BN_CTX_NEW
, ERR_R_MALLOC_FAILURE
);
1155 ret
->flags
= BN_FLG_MALLOCED
;
1160 BN_CTX_init(BN_CTX
*ctx
)
1162 memset(ctx
, 0, sizeof(*ctx
));
1166 BN_CTX_free(BN_CTX
*ctx
)
1170 if (ctx
== NULL
) return;
1171 assert(ctx
->depth
== 0);
1173 for (i
= 0; i
< BN_CTX_NUM
; i
++)
1174 BN_clear_free(&(ctx
->bn
[i
]));
1175 if (ctx
->flags
& BN_FLG_MALLOCED
)
1180 BN_CTX_start(BN_CTX
*ctx
)
1182 if (ctx
->depth
< BN_CTX_NUM_POS
)
1183 ctx
->pos
[ctx
->depth
] = ctx
->tos
;
1189 BN_CTX_get(BN_CTX
*ctx
)
1191 /* Note: If BN_CTX_get is ever changed to allocate BIGNUMs dynamically,
1192 * make sure that if BN_CTX_get fails once it will return NULL again
1193 * until BN_CTX_end is called. (This is so that callers have to check
1194 * only the last return value.)
1196 if (ctx
->depth
> BN_CTX_NUM_POS
|| ctx
->tos
>= BN_CTX_NUM
) {
1197 if (!ctx
->too_many
) {
1198 BNerr(BN_F_BN_CTX_GET
, BN_R_TOO_MANY_TEMPORARY_VARIABLES
);
1199 /* disable error code until BN_CTX_end is called: */
1204 return (&(ctx
->bn
[ctx
->tos
++]));
1208 BN_CTX_end(BN_CTX
*ctx
)
1210 if (ctx
== NULL
) return;
1211 assert(ctx
->depth
> 0);
1212 if (ctx
->depth
== 0) {
1213 /* should never happen, but we can tolerate it if not in
1214 * debug mode (could be a 'goto err' in the calling function
1215 * before BN_CTX_start was reached)
1221 if (ctx
->depth
< BN_CTX_NUM_POS
)
1222 ctx
->tos
= ctx
->pos
[ctx
->depth
];
1225 /* The old slow way */
1227 #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) && !defined(PEDANTIC) \
1228 && !defined(BN_DIV3W)
1229 #if defined(__GNUC__) && __GNUC__ >= 2
1230 #if defined(__i386) || defined(__i386__)
1232 * There were two reasons for implementing this template:
1233 * - GNU C generates a call to a function (__udivdi3 to be exact)
1234 * in reply to ((((BN_ULLONG)n0) << BN_BITS2) | n1) / d0 (I fail to
1235 * understand why...);
1236 * - divl doesn't only calculate quotient, but also leaves
1237 * remainder in %edx which we can definitely use here:-)
1239 * <appro@fy.chalmers.se>
1241 #define bn_div_words(n0, n1, d0) \
1242 ({ asm volatile("divl %4" \
1243 : " = a"(q), " = d"(rem) \
1244 : "a"(n1), "d"(n0), "g"(d0) \
1248 #define REMAINDER_IS_ALREADY_CALCULATED
1249 #elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG)
1251 * Same story here, but it's 128-bit by 64-bit division. Wow!
1252 * <appro@fy.chalmers.se>
1254 #define bn_div_words(n0, n1, d0) \
1255 ({ asm volatile("divq %4" \
1256 : " = a"(q), " = d"(rem) \
1257 : "a"(n1), "d"(n0), "g"(d0) \
1261 #define REMAINDER_IS_ALREADY_CALCULATED
1262 #endif /* __<cpu> */
1263 #endif /* __GNUC__ */
1264 #endif /* OPENSSL_NO_ASM */
1267 /* BN_div computes dv : = num / divisor, rounding towards zero, and sets up
1268 * rm such that dv*divisor + rm = num holds.
1270 * dv->neg == num->neg ^ divisor->neg (unless the result is zero)
1271 * rm->neg == num->neg (unless the remainder is zero)
1272 * If 'dv' or 'rm' is NULL, the respective value is not returned.
1275 BN_div(BIGNUM
*dv
, BIGNUM
*rm
, const BIGNUM
*num
, const BIGNUM
*divisor
, BN_CTX
*ctx
)
1277 int norm_shift
, i
, j
, loop
;
1278 BIGNUM
*tmp
, wnum
, *snum
, *sdiv
, *res
;
1279 BN_ULONG
*resp
, *wnump
;
1284 bn_check_top(divisor
);
1286 if (BN_is_zero(divisor
)) {
1287 BNerr(BN_F_BN_DIV
, BN_R_DIV_BY_ZERO
);
1291 if (BN_ucmp(num
, divisor
) < 0) {
1292 if (rm
!= NULL
) { if (BN_copy(rm
, num
) == NULL
) return (0); }
1293 if (dv
!= NULL
) BN_zero(dv
);
1298 tmp
= BN_CTX_get(ctx
);
1299 snum
= BN_CTX_get(ctx
);
1300 sdiv
= BN_CTX_get(ctx
);
1302 res
= BN_CTX_get(ctx
);
1304 if (sdiv
== NULL
|| res
== NULL
) goto err
;
1307 /* First we normalise the numbers */
1308 norm_shift
= BN_BITS2
-((BN_num_bits(divisor
))%BN_BITS2
);
1309 if (!(BN_lshift(sdiv
, divisor
, norm_shift
))) goto err
;
1311 norm_shift
+= BN_BITS2
;
1312 if (!(BN_lshift(snum
, num
, norm_shift
))) goto err
;
1318 /* Lets setup a 'window' into snum
1319 * This is the part that corresponds to the current
1320 * 'area' being divided
1323 wnum
.d
= &(snum
->d
[loop
]);
1325 wnum
.dmax
= snum
->dmax
+1; /* a bit of a lie */
1327 /* Get the top 2 words of sdiv */
1328 /* i = sdiv->top; */
1329 d0
= sdiv
->d
[div_n
-1];
1330 d1
= (div_n
== 1)?0:sdiv
->d
[div_n
-2];
1332 /* pointer to the 'top' of snum */
1333 wnump
= &(snum
->d
[num_n
-1]);
1335 /* Setup to 'res' */
1336 res
->neg
= (num
->neg
^divisor
->neg
);
1337 if (!bn_wexpand(res
, (loop
+1))) goto err
;
1339 resp
= &(res
->d
[loop
-1]);
1341 /* space for temp */
1342 if (!bn_wexpand(tmp
, (div_n
+1))) goto err
;
1344 if (BN_ucmp(&wnum
, sdiv
) >= 0) {
1345 if (!BN_usub(&wnum
, &wnum
, sdiv
)) goto err
;
1347 res
->d
[res
->top
-1] = 1;
1354 for (i
= 0; i
< loop
- 1; i
++) {
1356 #if defined(BN_DIV3W) && !defined(OPENSSL_NO_ASM)
1357 BN_ULONG
bn_div_3_words(BN_ULONG
*, BN_ULONG
, BN_ULONG
);
1358 q
= bn_div_3_words(wnump
, d1
, d0
);
1360 BN_ULONG n0
, n1
, rem
= 0;
1366 else /* n0 < d0 */ {
1370 #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
1371 q
= (BN_ULONG
)(((((BN_ULLONG
)n0
) << BN_BITS2
) | n1
) / d0
);
1373 q
= bn_div_words(n0
, n1
, d0
);
1374 #ifdef BN_DEBUG_LEVITTE
1375 fprintf(stderr
, "DEBUG: bn_div_words(0x%08X, 0x%08X, 0x%08X) -> 0x%08X\n",
1377 #endif /* BN_DEBUG_LEVITTE */
1378 #endif /* BN_LLONG && BN_DIV2W && !bn_div_words */
1380 #ifndef REMAINDER_IS_ALREADY_CALCULATED
1382 * rem doesn't have to be BN_ULLONG. The least we
1383 * know it's less that d0, isn't it?
1385 rem
= (n1
- q
* d0
) & BN_MASK2
;
1386 #endif /* !REMAINDER_IS_ALREADY_CALCULATED */
1387 t2
= (BN_ULLONG
)d1
* q
;
1390 if (t2
<= ((((BN_ULLONG
)rem
) << BN_BITS2
) | wnump
[-2]))
1394 if (rem
< d0
) break; /* don't let rem overflow */
1397 #else /* !BN_LLONG */
1398 BN_ULONG t2l
, t2h
, ql
, qh
;
1400 q
= bn_div_words(n0
, n1
, d0
);
1401 #ifdef BN_DEBUG_LEVITTE
1402 fprintf(stderr
, "DEBUG: bn_div_words(0x%08X, 0x%08X, 0x%08X) -> 0x%08X\n",
1405 #ifndef REMAINDER_IS_ALREADY_CALCULATED
1406 rem
= (n1
- q
* d0
) & BN_MASK2
;
1409 #if defined(BN_UMULT_LOHI)
1410 BN_UMULT_LOHI(t2l
, t2h
, d1
, q
);
1411 #elif defined(BN_UMULT_HIGH)
1413 t2h
= BN_UMULT_HIGH(d1
, q
);
1415 t2l
= LBITS(d1
); t2h
= HBITS(d1
);
1416 ql
= LBITS(q
); qh
= HBITS(q
);
1417 mul64(t2l
, t2h
, ql
, qh
); /* t2 = (BN_ULLONG)d1 * q; */
1421 if ((t2h
< rem
) || ((t2h
== rem
) && (t2l
<= wnump
[-2])))
1425 if (rem
< d0
) break; /* don't let rem overflow */
1430 #endif /* !BN_LLONG */
1432 #endif /* !BN_DIV3W */
1434 l0
= bn_mul_words(tmp
->d
, sdiv
->d
, div_n
, q
);
1435 wnum
.d
--; wnum
.top
++;
1437 for (j
= div_n
+ 1; j
> 0; j
--)
1438 if (tmp
->d
[j
- 1]) break;
1442 if (!BN_sub(&wnum
, &wnum
, tmp
)) goto err
;
1444 snum
->top
= snum
->top
+ wnum
.top
- j
;
1449 if (!BN_add(&wnum
, &wnum
, sdiv
)) goto err
;
1450 snum
->top
+= wnum
.top
- j
;
1456 /* Keep a copy of the neg flag in num because if rm == num
1457 * BN_rshift() will overwrite it.
1460 BN_rshift(rm
, snum
, norm_shift
);
1461 if (!BN_is_zero(rm
))
1473 #define TABLE_SIZE 32
1475 #ifdef NOT_NEEDED_FOR_DH
1476 /* this one works - simple but works */
1478 BN_exp(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, BN_CTX
*ctx
)
1480 int i
, bits
, ret
= 0;
1484 if ((r
== a
) || (r
== p
))
1485 rr
= BN_CTX_get(ctx
);
1488 if ((v
= BN_CTX_get(ctx
)) == NULL
) goto err
;
1490 if (BN_copy(v
, a
) == NULL
) goto err
;
1491 bits
= BN_num_bits(p
);
1494 if (BN_copy(rr
, a
) == NULL
)
1501 for (i
= 1; i
< bits
; i
++) {
1502 if (!BN_sqr(v
, v
, ctx
)) goto err
;
1503 if (BN_is_bit_set(p
, i
)) {
1504 if (!BN_mul(rr
, rr
, v
, ctx
)) goto err
;
1509 if (r
!= rr
) BN_copy(r
, rr
);
1515 BN_mod_exp(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, const BIGNUM
*m
, BN_CTX
*ctx
)
1523 /* For even modulus m = 2^k*m_odd, it might make sense to compute
1524 * a^p mod m_odd and a^p mod 2^k separately (with Montgomery
1525 * exponentiation for the odd part), using appropriate exponent
1526 * reductions, and combine the results using the CRT.
1528 * For now, we use Montgomery only if the modulus is odd; otherwise,
1529 * exponentiation using the reciprocal-based quick remaindering
1530 * algorithm is used.
1532 * (Timing obtained with expspeed.c [computations a^p mod m
1533 * where a, p, m are of the same length: 256, 512, 1024, 2048,
1534 * 4096, 8192 bits], compared to the running time of the
1535 * standard algorithm:
1537 * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration]
1538 * 55 .. 77 % [UltraSparc processor, but
1539 * debug-solaris-sparcv8-gcc conf.]
1541 * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration]
1542 * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
1544 * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
1545 * at 2048 and more bits, but at 512 and 1024 bits, it was
1546 * slower even than the standard algorithm!
1548 * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
1549 * should be obtained when the new Montgomery reduction code
1550 * has been integrated into OpenSSL.)
1553 #define MONT_MUL_MOD
1554 #define MONT_EXP_WORD
1555 #define RECP_MUL_MOD
1558 /* I have finally been able to take out this pre-condition of
1559 * the top bit being set. It was caused by an error in BN_div
1560 * with negatives. There was also another problem when for a^b%m
1561 * a >= m. eay 07-May-97
1563 /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
1566 #ifdef MONT_EXP_WORD
1567 if (a
->top
== 1 && !a
->neg
) {
1568 BN_ULONG A
= a
->d
[0];
1569 ret
= BN_mod_exp_mont_word(r
, A
, p
, m
, ctx
, NULL
);
1572 ret
= BN_mod_exp_mont(r
, a
, p
, m
, ctx
, NULL
);
1574 #endif /* MONT_MUL_MOD */
1577 ret
= BN_mod_exp_recp(r
, a
, p
, m
, ctx
);
1581 ret
= BN_mod_exp_simple(r
, a
, p
, m
, ctx
);
1590 BN_mod_exp_recp(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, const BIGNUM
*m
, BN_CTX
*ctx
)
1592 int i
, j
, bits
, ret
= 0, wstart
, wend
, window
, wvalue
;
1593 int start
= 1, ts
= 0;
1595 BIGNUM val
[TABLE_SIZE
];
1598 bits
= BN_num_bits(p
);
1606 if ((aa
= BN_CTX_get(ctx
)) == NULL
) goto err
;
1608 BN_RECP_CTX_init(&recp
);
1610 /* ignore sign of 'm' */
1611 if (!BN_copy(aa
, m
)) goto err
;
1613 if (BN_RECP_CTX_set(&recp
, aa
, ctx
) <= 0) goto err
;
1615 if (BN_RECP_CTX_set(&recp
, m
, ctx
) <= 0) goto err
;
1621 if (!BN_nnmod(&(val
[0]), a
, m
, ctx
)) goto err
; /* 1 */
1622 if (BN_is_zero(&(val
[0]))) {
1627 window
= BN_window_bits_for_exponent_size(bits
);
1629 if (!BN_mod_mul_reciprocal(aa
, &(val
[0]), &(val
[0]), &recp
, ctx
))
1631 j
= 1 << (window
- 1);
1632 for (i
= 1; i
< j
; i
++) {
1634 if (!BN_mod_mul_reciprocal(&(val
[i
]), &(val
[i
- 1]), aa
, &recp
, ctx
))
1640 start
= 1; /* This is used to avoid multiplication etc
1641 * when there is only the value '1' in the
1644 wvalue
= 0; /* The 'value' of the window */
1645 wstart
= bits
- 1; /* The top bit of the window */
1646 wend
= 0; /* The bottom bit of the window */
1648 if (!BN_one(r
)) goto err
;
1651 if (BN_is_bit_set(p
, wstart
) == 0) {
1653 if (!BN_mod_mul_reciprocal(r
, r
, r
, &recp
, ctx
))
1655 if (wstart
== 0) break;
1659 /* We now have wstart on a 'set' bit, we now need to work out
1660 * how bit a window to do. To do this we need to scan
1661 * forward until the last set bit before the end of the
1667 for (i
= 1; i
< window
; i
++) {
1668 if (wstart
- i
< 0) break;
1669 if (BN_is_bit_set(p
, wstart
-i
)) {
1670 wvalue
<<= (i
- wend
);
1676 /* wend is the size of the current window */
1678 /* add the 'bytes above' */
1680 for (i
= 0; i
< j
; i
++) {
1681 if (!BN_mod_mul_reciprocal(r
, r
, r
, &recp
, ctx
))
1685 /* wvalue will be an odd number < 2^window */
1686 if (!BN_mod_mul_reciprocal(r
, r
, &(val
[wvalue
>> 1]), &recp
, ctx
))
1689 /* move the 'window' down further */
1693 if (wstart
< 0) break;
1698 for (i
= 0; i
< ts
; i
++)
1699 BN_clear_free(&(val
[i
]));
1700 BN_RECP_CTX_free(&recp
);
1703 #endif /* NOT_NEEDED_FOR_DH */
1707 BN_mod_exp_mont(BIGNUM
*rr
, const BIGNUM
*a
, const BIGNUM
*p
,
1708 const BIGNUM
*m
, BN_CTX
*ctx
, BN_MONT_CTX
*in_mont
)
1710 int i
, j
, bits
, ret
= 0, wstart
, wend
, window
, wvalue
;
1711 int start
= 1, ts
= 0;
1714 BIGNUM val
[TABLE_SIZE
];
1715 BN_MONT_CTX
*mont
= NULL
;
1721 if (!(m
->d
[0] & 1)) {
1722 BNerr(BN_F_BN_MOD_EXP_MONT
, BN_R_CALLED_WITH_EVEN_MODULUS
);
1725 bits
= BN_num_bits(p
);
1732 d
= BN_CTX_get(ctx
);
1733 r
= BN_CTX_get(ctx
);
1734 if (d
== NULL
|| r
== NULL
) goto err
;
1736 /* If this is not done, things will break in the montgomery part */
1738 if (in_mont
!= NULL
)
1741 if ((mont
= BN_MONT_CTX_new()) == NULL
) goto err
;
1742 if (!BN_MONT_CTX_set(mont
, m
, ctx
)) goto err
;
1747 if (a
->neg
|| BN_ucmp(a
, m
) >= 0) {
1748 if (!BN_nnmod(&(val
[0]), a
, m
, ctx
))
1753 if (BN_is_zero(aa
)) {
1757 if (!BN_to_montgomery(&(val
[0]), aa
, mont
, ctx
)) goto err
; /* 1 */
1759 window
= BN_window_bits_for_exponent_size(bits
);
1761 if (!BN_mod_mul_montgomery(d
, &(val
[0]), &(val
[0]), mont
, ctx
)) goto err
; /* 2 */
1762 j
= 1 << (window
- 1);
1763 for (i
= 1; i
< j
; i
++) {
1765 if (!BN_mod_mul_montgomery(&(val
[i
]), &(val
[i
- 1]), d
, mont
, ctx
))
1771 start
= 1; /* This is used to avoid multiplication etc
1772 * when there is only the value '1' in the
1775 wvalue
= 0; /* The 'value' of the window */
1776 wstart
= bits
-1; /* The top bit of the window */
1777 wend
= 0; /* The bottom bit of the window */
1779 if (!BN_to_montgomery(r
, BN_value_one(), mont
, ctx
)) goto err
;
1781 if (BN_is_bit_set(p
, wstart
) == 0) {
1783 if (!BN_mod_mul_montgomery(r
, r
, r
, mont
, ctx
))
1786 if (wstart
== 0) break;
1790 /* We now have wstart on a 'set' bit, we now need to work out
1791 * how bit a window to do. To do this we need to scan
1792 * forward until the last set bit before the end of the
1798 for (i
= 1; i
< window
; i
++) {
1799 if (wstart
- i
< 0) break;
1800 if (BN_is_bit_set(p
, wstart
- i
)) {
1801 wvalue
<<= (i
- wend
);
1807 /* wend is the size of the current window */
1809 /* add the 'bytes above' */
1811 for (i
= 0; i
< j
; i
++) {
1812 if (!BN_mod_mul_montgomery(r
, r
, r
, mont
, ctx
))
1816 /* wvalue will be an odd number < 2^window */
1817 if (!BN_mod_mul_montgomery(r
, r
, &(val
[wvalue
>> 1]), mont
, ctx
))
1820 /* move the 'window' down further */
1824 if (wstart
< 0) break;
1826 if (!BN_from_montgomery(rr
, r
, mont
, ctx
)) goto err
;
1829 if ((in_mont
== NULL
) && (mont
!= NULL
)) BN_MONT_CTX_free(mont
);
1831 for (i
= 0; i
< ts
; i
++)
1832 BN_clear_free(&(val
[i
]));
1837 BN_mod_exp_mont_word(BIGNUM
*rr
, BN_ULONG a
, const BIGNUM
*p
,
1838 const BIGNUM
*m
, BN_CTX
*ctx
, BN_MONT_CTX
*in_mont
)
1840 BN_MONT_CTX
*mont
= NULL
;
1841 int b
, bits
, ret
= 0;
1846 #define BN_MOD_MUL_WORD(r, w, m) \
1847 (BN_mul_word(r, (w)) && \
1848 (/* BN_ucmp(r, (m)) < 0 ? 1 : */ \
1849 (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
1850 /* BN_MOD_MUL_WORD is only used with 'w' large,
1851 * so the BN_ucmp test is probably more overhead
1852 * than always using BN_mod (which uses BN_copy if
1853 * a similar test returns true).
1855 /* We can use BN_mod and do not need BN_nnmod because our
1856 * accumulator is never negative (the result of BN_mod does
1857 * not depend on the sign of the modulus).
1859 #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
1860 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
1865 if (m
->top
== 0 || !(m
->d
[0] & 1)) {
1866 BNerr(BN_F_BN_MOD_EXP_MONT_WORD
, BN_R_CALLED_WITH_EVEN_MODULUS
);
1870 a
%= m
->d
[0]; /* make sure that 'a' is reduced */
1872 bits
= BN_num_bits(p
);
1883 d
= BN_CTX_get(ctx
);
1884 r
= BN_CTX_get(ctx
);
1885 t
= BN_CTX_get(ctx
);
1886 if (d
== NULL
|| r
== NULL
|| t
== NULL
) goto err
;
1888 if (in_mont
!= NULL
)
1891 if ((mont
= BN_MONT_CTX_new()) == NULL
) goto err
;
1892 if (!BN_MONT_CTX_set(mont
, m
, ctx
)) goto err
;
1895 r_is_one
= 1; /* except for Montgomery factor */
1899 /* The result is accumulated in the product r*w. */
1900 w
= a
; /* bit 'bits-1' of 'p' is always set */
1901 for (b
= bits
-2; b
>= 0; b
--) {
1902 /* First, square r*w. */
1904 if ((next_w
/w
) != w
) /* overflow */ {
1906 if (!BN_TO_MONTGOMERY_WORD(r
, w
, mont
)) goto err
;
1909 if (!BN_MOD_MUL_WORD(r
, w
, m
)) goto err
;
1915 if (!BN_mod_mul_montgomery(r
, r
, r
, mont
, ctx
)) goto err
;
1918 /* Second, multiply r*w by 'a' if exponent bit is set. */
1919 if (BN_is_bit_set(p
, b
)) {
1921 if ((next_w
/a
) != w
) /* overflow */ {
1923 if (!BN_TO_MONTGOMERY_WORD(r
, w
, mont
)) goto err
;
1926 if (!BN_MOD_MUL_WORD(r
, w
, m
)) goto err
;
1934 /* Finally, set r: = r*w. */
1937 if (!BN_TO_MONTGOMERY_WORD(r
, w
, mont
)) goto err
;
1940 if (!BN_MOD_MUL_WORD(r
, w
, m
)) goto err
;
1944 if (r_is_one
) /* can happen only if a == 1 */ {
1945 if (!BN_one(rr
)) goto err
;
1947 if (!BN_from_montgomery(rr
, r
, mont
, ctx
)) goto err
;
1951 if ((in_mont
== NULL
) && (mont
!= NULL
)) BN_MONT_CTX_free(mont
);
1957 #ifdef NOT_NEEDED_FOR_DH
1958 /* The old fallback, simple version :-) */
1960 BN_mod_exp_simple(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*p
, const BIGNUM
*m
, BN_CTX
*ctx
)
1962 int i
, j
, bits
, ret
= 0, wstart
, wend
, window
, wvalue
, ts
= 0;
1965 BIGNUM val
[TABLE_SIZE
];
1967 bits
= BN_num_bits(p
);
1975 if ((d
= BN_CTX_get(ctx
)) == NULL
) goto err
;
1979 if (!BN_nnmod(&(val
[0]), a
, m
, ctx
)) goto err
; /* 1 */
1980 if (BN_is_zero(&(val
[0]))) {
1985 window
= BN_window_bits_for_exponent_size(bits
);
1987 if (!BN_mod_mul(d
, &(val
[0]), &(val
[0]), m
, ctx
))
1989 j
= 1 << (window
- 1);
1990 for (i
= 1; i
< j
; i
++) {
1992 if (!BN_mod_mul(&(val
[i
]), &(val
[i
- 1]), d
, m
, ctx
))
1998 start
= 1; /* This is used to avoid multiplication etc
1999 * when there is only the value '1' in the
2002 wvalue
= 0; /* The 'value' of the window */
2003 wstart
= bits
-1; /* The top bit of the window */
2004 wend
= 0; /* The bottom bit of the window */
2006 if (!BN_one(r
)) goto err
;
2009 if (BN_is_bit_set(p
, wstart
) == 0) {
2011 if (!BN_mod_mul(r
, r
, r
, m
, ctx
))
2013 if (wstart
== 0) break;
2017 /* We now have wstart on a 'set' bit, we now need to work out
2018 * how bit a window to do. To do this we need to scan
2019 * forward until the last set bit before the end of the
2025 for (i
= 1; i
< window
; i
++) {
2026 if (wstart
- i
< 0) break;
2027 if (BN_is_bit_set(p
, wstart
- i
)) {
2028 wvalue
<<= (i
- wend
);
2034 /* wend is the size of the current window */
2036 /* add the 'bytes above' */
2038 for (i
= 0; i
< j
; i
++) {
2039 if (!BN_mod_mul(r
, r
, r
, m
, ctx
))
2043 /* wvalue will be an odd number < 2^window */
2044 if (!BN_mod_mul(r
, r
, &(val
[wvalue
>> 1]), m
, ctx
))
2047 /* move the 'window' down further */
2051 if (wstart
< 0) break;
2056 for (i
= 0; i
< ts
; i
++)
2057 BN_clear_free(&(val
[i
]));
2061 static BIGNUM
*euclid(BIGNUM
*a
, BIGNUM
*b
);
2064 BN_gcd(BIGNUM
*r
, const BIGNUM
*in_a
, const BIGNUM
*in_b
, BN_CTX
*ctx
)
2073 a
= BN_CTX_get(ctx
);
2074 b
= BN_CTX_get(ctx
);
2075 if (a
== NULL
|| b
== NULL
) goto err
;
2077 if (BN_copy(a
, in_a
) == NULL
) goto err
;
2078 if (BN_copy(b
, in_b
) == NULL
) goto err
;
2082 if (BN_cmp(a
, b
) < 0) { t
= a
; a
= b
; b
= t
; }
2084 if (t
== NULL
) goto err
;
2086 if (BN_copy(r
, t
) == NULL
) goto err
;
2094 euclid(BIGNUM
*a
, BIGNUM
*b
)
2103 while (!BN_is_zero(b
)) {
2108 if (!BN_sub(a
, a
, b
)) goto err
;
2109 if (!BN_rshift1(a
, a
)) goto err
;
2110 if (BN_cmp(a
, b
) < 0) { t
= a
; a
= b
; b
= t
; }
2111 } else /* a odd - b even */ {
2112 if (!BN_rshift1(b
, b
)) goto err
;
2113 if (BN_cmp(a
, b
) < 0) { t
= a
; a
= b
; b
= t
; }
2115 } else /* a is even */ {
2117 if (!BN_rshift1(a
, a
)) goto err
;
2118 if (BN_cmp(a
, b
) < 0) { t
= a
; a
= b
; b
= t
; }
2119 } else /* a even - b even */ {
2120 if (!BN_rshift1(a
, a
)) goto err
;
2121 if (!BN_rshift1(b
, b
)) goto err
;
2129 if (!BN_lshift(a
, a
, shifts
)) goto err
;
2135 #endif /* NOT_NEEDED_FOR_DH */
2138 /* solves ax == 1 (mod n) */
2140 BN_mod_inverse(BIGNUM
*in
, const BIGNUM
*a
, const BIGNUM
*n
, BN_CTX
*ctx
)
2142 BIGNUM
*A
, *B
, *X
, *Y
, *M
, *D
, *T
, *R
= NULL
;
2150 A
= BN_CTX_get(ctx
);
2151 B
= BN_CTX_get(ctx
);
2152 X
= BN_CTX_get(ctx
);
2153 D
= BN_CTX_get(ctx
);
2154 M
= BN_CTX_get(ctx
);
2155 Y
= BN_CTX_get(ctx
);
2156 T
= BN_CTX_get(ctx
);
2157 if (T
== NULL
) goto err
;
2163 if (R
== NULL
) goto err
;
2167 if (BN_copy(B
, a
) == NULL
) goto err
;
2168 if (BN_copy(A
, n
) == NULL
) goto err
;
2170 if (B
->neg
|| (BN_ucmp(B
, A
) >= 0)) {
2171 if (!BN_nnmod(B
, B
, A
, ctx
)) goto err
;
2174 /* From B = a mod |n|, A = |n| it follows that
2177 * -sign*X*a == B (mod |n|),
2178 * sign*Y*a == A (mod |n|).
2181 if (BN_is_odd(n
) && (BN_num_bits(n
) <= (BN_BITS
<= 32 ? 450 : 2048))) {
2182 /* Binary inversion algorithm; requires odd modulus.
2183 * This is faster than the general algorithm if the modulus
2184 * is sufficiently small (about 400 .. 500 bits on 32-bit
2185 * sytems, but much more on 64-bit systems)
2189 while (!BN_is_zero(B
)) {
2193 * (1) -sign*X*a == B (mod |n|),
2194 * (2) sign*Y*a == A (mod |n|)
2197 /* Now divide B by the maximum possible power of two in the integers,
2198 * and divide X by the same value mod |n|.
2199 * When we're done, (1) still holds.
2202 while (!BN_is_bit_set(B
, shift
)) /* note that 0 < B */ {
2206 if (!BN_uadd(X
, X
, n
)) goto err
;
2208 /* now X is even, so we can easily divide it by two */
2209 if (!BN_rshift1(X
, X
)) goto err
;
2212 if (!BN_rshift(B
, B
, shift
)) goto err
;
2216 /* Same for A and Y. Afterwards, (2) still holds. */
2218 while (!BN_is_bit_set(A
, shift
)) /* note that 0 < A */ {
2222 if (!BN_uadd(Y
, Y
, n
)) goto err
;
2225 if (!BN_rshift1(Y
, Y
)) goto err
;
2228 if (!BN_rshift(A
, A
, shift
)) goto err
;
2231 /* We still have (1) and (2).
2232 * Both A and B are odd.
2233 * The following computations ensure that
2237 * (1) -sign*X*a == B (mod |n|),
2238 * (2) sign*Y*a == A (mod |n|),
2240 * and that either A or B is even in the next iteration.
2242 if (BN_ucmp(B
, A
) >= 0) {
2243 /* -sign*(X + Y)*a == B - A (mod |n|) */
2244 if (!BN_uadd(X
, X
, Y
)) goto err
;
2245 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that
2246 * actually makes the algorithm slower
2248 if (!BN_usub(B
, B
, A
)) goto err
;
2250 /* sign*(X + Y)*a == A - B (mod |n|) */
2251 if (!BN_uadd(Y
, Y
, X
)) goto err
;
2252 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */
2253 if (!BN_usub(A
, A
, B
)) goto err
;
2257 /* general inversion algorithm */
2259 while (!BN_is_zero(B
)) {
2264 * (*) -sign*X*a == B (mod |n|),
2265 * sign*Y*a == A (mod |n|)
2268 /* (D, M) : = (A/B, A%B) ... */
2269 if (BN_num_bits(A
) == BN_num_bits(B
)) {
2270 if (!BN_one(D
)) goto err
;
2271 if (!BN_sub(M
, A
, B
)) goto err
;
2272 } else if (BN_num_bits(A
) == BN_num_bits(B
) + 1) {
2273 /* A/B is 1, 2, or 3 */
2274 if (!BN_lshift1(T
, B
)) goto err
;
2275 if (BN_ucmp(A
, T
) < 0) {
2276 /* A < 2*B, so D = 1 */
2277 if (!BN_one(D
)) goto err
;
2278 if (!BN_sub(M
, A
, B
)) goto err
;
2280 /* A >= 2*B, so D = 2 or D = 3 */
2281 if (!BN_sub(M
, A
, T
)) goto err
;
2282 if (!BN_add(D
, T
, B
)) goto err
;
2283 /* use D ( := 3 * B) as temp */
2284 if (BN_ucmp(A
, D
) < 0) {
2285 /* A < 3*B, so D = 2 */
2286 if (!BN_set_word(D
, 2)) goto err
;
2287 /* M ( = A - 2*B) already has the correct value */
2289 /* only D = 3 remains */
2290 if (!BN_set_word(D
, 3)) goto err
;
2291 /* currently M = A - 2 * B,
2292 * but we need M = A - 3 * B
2294 if (!BN_sub(M
, M
, B
)) goto err
;
2298 if (!BN_div(D
, M
, A
, B
, ctx
)) goto err
;
2304 * (**) sign*Y*a == D*B + M (mod |n|).
2307 tmp
= A
; /* keep the BIGNUM object, the value does not matter */
2309 /* (A, B) : = (B, A mod B) ... */
2312 /* ... so we have 0 <= B < A again */
2314 /* Since the former M is now B and the former B is now A,
2315 * (**) translates into
2316 * sign*Y*a == D*A + B (mod |n|),
2318 * sign*Y*a - D*A == B (mod |n|).
2319 * Similarly, (*) translates into
2320 * -sign*X*a == A (mod |n|).
2323 * sign*Y*a + D*sign*X*a == B (mod |n|),
2325 * sign*(Y + D*X)*a == B (mod |n|).
2327 * So if we set (X, Y, sign) : = (Y + D*X, X, -sign), we arrive back at
2328 * -sign*X*a == B (mod |n|),
2329 * sign*Y*a == A (mod |n|).
2330 * Note that X and Y stay non-negative all the time.
2333 /* most of the time D is very small, so we can optimize tmp : = D*X+Y */
2335 if (!BN_add(tmp
, X
, Y
)) goto err
;
2337 if (BN_is_word(D
, 2)) {
2338 if (!BN_lshift1(tmp
, X
)) goto err
;
2339 } else if (BN_is_word(D
, 4)) {
2340 if (!BN_lshift(tmp
, X
, 2)) goto err
;
2341 } else if (D
->top
== 1) {
2342 if (!BN_copy(tmp
, X
)) goto err
;
2343 if (!BN_mul_word(tmp
, D
->d
[0])) goto err
;
2345 if (!BN_mul(tmp
, D
, X
, ctx
)) goto err
;
2347 if (!BN_add(tmp
, tmp
, Y
)) goto err
;
2350 M
= Y
; /* keep the BIGNUM object, the value does not matter */
2358 * The while loop (Euclid's algorithm) ends when
2361 * sign*Y*a == A (mod |n|),
2362 * where Y is non-negative.
2366 if (!BN_sub(Y
, n
, Y
)) goto err
;
2368 /* Now Y*a == A (mod |n|). */
2372 /* Y*a == 1 (mod |n|) */
2373 if (!Y
->neg
&& BN_ucmp(Y
, n
) < 0) {
2374 if (!BN_copy(R
, Y
)) goto err
;
2376 if (!BN_nnmod(R
, Y
, n
, ctx
)) goto err
;
2379 BNerr(BN_F_BN_MOD_INVERSE
, BN_R_NO_INVERSE
);
2384 if ((ret
== NULL
) && (in
== NULL
)) BN_free(R
);
2391 #ifdef NOT_NEEDED_FOR_DH
2392 /* For a 32 bit machine
2401 static int bn_limit_bits
= 0;
2402 static int bn_limit_num
= 8; /* (1 << bn_limit_bits) */
2403 static int bn_limit_bits_low
= 0;
2404 static int bn_limit_num_low
= 8; /* (1 << bn_limit_bits_low) */
2405 static int bn_limit_bits_high
= 0;
2406 static int bn_limit_num_high
= 8; /* (1 << bn_limit_bits_high) */
2407 static int bn_limit_bits_mont
= 0;
2408 static int bn_limit_num_mont
= 8; /* (1 << bn_limit_bits_mont) */
2411 BN_set_params(int mult
, int high
, int low
, int mont
)
2414 if (mult
> (sizeof(int)*8)-1)
2415 mult
= sizeof(int)*8-1;
2416 bn_limit_bits
= mult
;
2417 bn_limit_num
= 1 << mult
;
2420 if (high
> (sizeof(int)*8)-1)
2421 high
= sizeof(int)*8-1;
2422 bn_limit_bits_high
= high
;
2423 bn_limit_num_high
= 1 << high
;
2426 if (low
> (sizeof(int)*8)-1)
2427 low
= sizeof(int)*8-1;
2428 bn_limit_bits_low
= low
;
2429 bn_limit_num_low
= 1 << low
;
2432 if (mont
> (sizeof(int)*8)-1)
2433 mont
= sizeof(int)*8-1;
2434 bn_limit_bits_mont
= mont
;
2435 bn_limit_num_mont
= 1 << mont
;
2440 BN_get_params(int which
)
2442 if (which
== 0) return (bn_limit_bits
);
2443 else if (which
== 1) return (bn_limit_bits_high
);
2444 else if (which
== 2) return (bn_limit_bits_low
);
2445 else if (which
== 3) return (bn_limit_bits_mont
);
2452 static int init
= 0;
2453 static char data
[16];
2458 sprintf(data
, "bn(%d, %d)", (int)sizeof(BN_ULLONG
)*8,
2459 (int)sizeof(BN_ULONG
)*8);
2461 sprintf(data
, "bn(%d, %d)", (int)sizeof(BN_ULONG
)*8,
2462 (int)sizeof(BN_ULONG
)*8);
2467 #endif /* NOT_NEEDED_FOR_DH */
2472 static BN_ULONG data_one
= 1L;
2473 static BIGNUM const_one
= {&data_one
, 1, 1, 0};
2475 return (&const_one
);
2479 BN_num_bits_word(BN_ULONG l
)
2481 static const char bits
[256] = {
2482 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
2483 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
2484 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
2485 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
2486 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2487 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2488 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2489 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
2490 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2491 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2492 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2493 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2494 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2495 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2496 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
2497 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8
2500 #if defined(SIXTY_FOUR_BIT_LONG)
2501 if (l
& 0xffffffff00000000L
) {
2502 if (l
& 0xffff000000000000L
) {
2503 if (l
& 0xff00000000000000L
) {
2504 return (bits
[(int)(l
>> 56)] + 56);
2506 return (bits
[(int)(l
>> 48)] + 48);
2508 if (l
& 0x0000ff0000000000L
) {
2509 return (bits
[(int)(l
>> 40)] + 40);
2511 return (bits
[(int)(l
>> 32)] + 32);
2515 #ifdef SIXTY_FOUR_BIT
2516 if (l
& 0xffffffff00000000LL
) {
2517 if (l
& 0xffff000000000000LL
) {
2518 if (l
& 0xff00000000000000LL
) {
2519 return (bits
[(int)(l
>> 56)] + 56);
2521 return (bits
[(int)(l
>> 48)] + 48);
2523 if (l
& 0x0000ff0000000000LL
) {
2524 return (bits
[(int)(l
>> 40)] + 40);
2526 return (bits
[(int)(l
>> 32)] + 32);
2530 #endif /* SIXTY_FOUR_BIT_LONG */
2532 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
2533 if (l
& 0xffff0000L
) {
2534 if (l
& 0xff000000L
)
2535 return (bits
[(int)(l
>> 24L)] + 24);
2537 return (bits
[(int)(l
>> 16L)] + 16);
2541 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || \
2542 defined(SIXTY_FOUR_BIT_LONG)
2544 return (bits
[(int)(l
>> 8)] + 8);
2547 return (bits
[(int)(l
)]);
2553 BN_num_bits(const BIGNUM
*a
)
2560 if (a
->top
== 0) return (0);
2563 i
= (a
->top
-1)*BN_BITS2
;
2564 return (i
+BN_num_bits_word(l
));
2568 BN_clear_free(BIGNUM
*a
)
2572 if (a
== NULL
) return;
2574 OPENSSL_cleanse(a
->d
, a
->dmax
*sizeof(a
->d
[0]));
2575 if (!(BN_get_flags(a
, BN_FLG_STATIC_DATA
)))
2578 i
= BN_get_flags(a
, BN_FLG_MALLOCED
);
2579 OPENSSL_cleanse(a
, sizeof(BIGNUM
));
2587 if (a
== NULL
) return;
2588 if ((a
->d
!= NULL
) && !(BN_get_flags(a
, BN_FLG_STATIC_DATA
)))
2590 a
->flags
|= BN_FLG_FREE
; /* REMOVE? */
2591 if (a
->flags
& BN_FLG_MALLOCED
)
2598 memset(a
, 0, sizeof(BIGNUM
));
2606 if ((ret
= (BIGNUM
*)OPENSSL_malloc(sizeof(BIGNUM
))) == NULL
) {
2607 BNerr(BN_F_BN_NEW
, ERR_R_MALLOC_FAILURE
);
2610 ret
->flags
= BN_FLG_MALLOCED
;
2618 /* This is used both by bn_expand2() and bn_dup_expand() */
2619 /* The caller MUST check that words > b->dmax before calling this */
2621 bn_expand_internal(const BIGNUM
*b
, int words
)
2623 BN_ULONG
*A
, *a
= NULL
;
2627 if (words
> (INT_MAX
/(4*BN_BITS2
))) {
2628 BNerr(BN_F_BN_EXPAND_INTERNAL
, BN_R_BIGNUM_TOO_LONG
);
2633 if (BN_get_flags(b
, BN_FLG_STATIC_DATA
)) {
2634 BNerr(BN_F_BN_EXPAND_INTERNAL
, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA
);
2637 a
= A
= (BN_ULONG
*)OPENSSL_malloc(sizeof(BN_ULONG
)*(words
+1));
2639 BNerr(BN_F_BN_EXPAND_INTERNAL
, ERR_R_MALLOC_FAILURE
);
2643 /* Check if the previous number needs to be copied */
2645 for (i
= b
->top
>> 2; i
> 0; i
--, A
+= 4, B
+= 4) {
2647 * The fact that the loop is unrolled
2648 * 4-wise is a tribute to Intel. It's
2649 * the one that doesn't have enough
2650 * registers to accomodate more data.
2651 * I'd unroll it 8-wise otherwise:-)
2653 * <appro@fy.chalmers.se>
2655 BN_ULONG a0
, a1
, a2
, a3
;
2656 a0
= B
[0]; a1
= B
[1]; a2
= B
[2]; a3
= B
[3];
2657 A
[0] = a0
; A
[1] = a1
; A
[2] = a2
; A
[3] = a3
;
2660 case 3: A
[2] = B
[2];
2661 case 2: A
[1] = B
[1];
2662 case 1: A
[0] = B
[0];
2668 /* Now need to zero any data between b->top and b->max */
2671 for (i
= (words
- b
->top
) >> 3; i
> 0; i
--, A
+= 8) {
2672 A
[0] = 0; A
[1] = 0; A
[2] = 0; A
[3] = 0;
2673 A
[4] = 0; A
[5] = 0; A
[6] = 0; A
[7] = 0;
2675 for (i
= (words
- b
->top
) & 7; i
> 0; i
--, A
++)
2681 #ifdef NOT_NEEDED_FOR_DH
2682 /* This is an internal function that can be used instead of bn_expand2()
2683 * when there is a need to copy BIGNUMs instead of only expanding the
2684 * data part, while still expanding them.
2685 * Especially useful when needing to expand BIGNUMs that are declared
2686 * 'const' and should therefore not be changed.
2687 * The reason to use this instead of a BN_dup() followed by a bn_expand2()
2688 * is memory allocation overhead. A BN_dup() followed by a bn_expand2()
2689 * will allocate new memory for the BIGNUM data twice, and free it once,
2690 * while bn_dup_expand() makes sure allocation is made only once.
2694 bn_dup_expand(const BIGNUM
*b
, int words
)
2698 /* This function does not work if
2699 * words <= b->dmax && top < words
2700 * because BN_dup() does not preserve 'dmax'!
2701 * (But bn_dup_expand() is not used anywhere yet.)
2704 if (words
> b
->dmax
) {
2705 BN_ULONG
*a
= bn_expand_internal(b
, words
);
2715 /* r == NULL, BN_new failure */
2719 /* If a == NULL, there was an error in allocation in
2720 * bn_expand_internal(), and NULL should be returned
2728 #endif /* NOT_NEEDED_FOR_DH */
2730 /* This is an internal function that should not be used in applications.
2731 * It ensures that 'b' has enough room for a 'words' word number number.
2732 * It is mostly used by the various BIGNUM routines. If there is an error,
2733 * NULL is returned. If not, 'b' is returned.
2737 bn_expand2(BIGNUM
*b
, int words
)
2739 if (words
> b
->dmax
) {
2740 BN_ULONG
*a
= bn_expand_internal(b
, words
);
2755 BN_dup(const BIGNUM
*a
)
2759 if (a
== NULL
) return NULL
;
2764 if (t
== NULL
) return (NULL
);
2766 /* now r == t || r == NULL */
2771 #endif /* BCMDH_TEST */
2774 BN_copy(BIGNUM
*a
, const BIGNUM
*b
)
2782 if (a
== b
) return (a
);
2783 if (bn_wexpand(a
, b
->top
) == NULL
) return (NULL
);
2787 for (i
= b
->top
>> 2; i
> 0; i
--, A
+= 4, B
+= 4) {
2788 BN_ULONG a0
, a1
, a2
, a3
;
2789 a0
= B
[0]; a1
= B
[1]; a2
= B
[2]; a3
= B
[3];
2790 A
[0] = a0
; A
[1] = a1
; A
[2] = a2
; A
[3] = a3
;
2792 switch (b
->top
& 3) {
2793 case 3: A
[2] = B
[2];
2794 case 2: A
[1] = B
[1];
2795 case 1: A
[0] = B
[0];
2799 /* memset(&(a->d[b->top]), 0, sizeof(a->d[0])*(a->max-b->top)); */
2801 if ((a
->top
== 0) && (a
->d
!= NULL
))
2807 #ifdef NOT_NEEDED_FOR_DH
2809 BN_swap(BIGNUM
*a
, BIGNUM
*b
)
2811 int flags_old_a
, flags_old_b
;
2813 int tmp_top
, tmp_dmax
, tmp_neg
;
2815 flags_old_a
= a
->flags
;
2816 flags_old_b
= b
->flags
;
2833 a
->flags
= (flags_old_a
& BN_FLG_MALLOCED
) | (flags_old_b
& BN_FLG_STATIC_DATA
);
2834 b
->flags
= (flags_old_b
& BN_FLG_MALLOCED
) | (flags_old_a
& BN_FLG_STATIC_DATA
);
2842 memset(a
->d
, 0, a
->dmax
*sizeof(a
->d
[0]));
2848 BN_get_word(const BIGNUM
*a
)
2853 n
= BN_num_bytes(a
);
2854 if (n
> sizeof(BN_ULONG
))
2856 for (i
= a
->top
-1; i
>= 0; i
--) {
2857 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
2858 ret
<<= BN_BITS4
; /* stops the compiler complaining */
2867 #endif /* NOT_NEEDED_FOR_DH */
2870 BN_set_word(BIGNUM
*a
, BN_ULONG w
)
2873 if (bn_expand(a
, (int)sizeof(BN_ULONG
)*8) == NULL
) return (0);
2875 n
= sizeof(BN_ULONG
)/BN_BYTES
;
2878 a
->d
[0] = (BN_ULONG
)w
&BN_MASK2
;
2879 if (a
->d
[0] != 0) a
->top
= 1;
2880 for (i
= 1; i
< n
; i
++) {
2881 /* the following is done instead of
2882 * w >>= BN_BITS2 so compilers don't complain
2883 * on builds where sizeof(long) == BN_TYPES
2885 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
2891 a
->d
[i
] = (BN_ULONG
)w
&BN_MASK2
;
2892 if (a
->d
[i
] != 0) a
->top
= i
+1;
2898 BN_bin2bn(const unsigned char *s
, int len
, BIGNUM
*ret
)
2904 if (ret
== NULL
) ret
= BN_new();
2905 if (ret
== NULL
) return (NULL
);
2912 if (bn_expand(ret
, (int)(n
+2)*8) == NULL
)
2914 i
= ((n
-1)/BN_BYTES
)+1;
2915 m
= ((n
-1)%(BN_BYTES
));
2919 l
= (l
<< 8L)| *(s
++);
2926 /* need to call this due to clear byte at top if avoiding
2927 * having the top bit set (-ve number)
2933 /* ignore negative */
2935 BN_bn2bin(const BIGNUM
*a
, unsigned char *to
)
2940 n
= i
= BN_num_bytes(a
);
2942 l
= a
->d
[i
/BN_BYTES
];
2943 *(to
++) = (unsigned char)(l
>>(8*(i
%BN_BYTES
)))&0xff;
2949 BN_ucmp(const BIGNUM
*a
, const BIGNUM
*b
)
2952 BN_ULONG t1
, t2
, *ap
, *bp
;
2958 if (i
!= 0) return (i
);
2961 for (i
= a
->top
-1; i
>= 0; i
--) {
2965 return (t1
> t2
?1:-1);
2972 BN_cmp(const BIGNUM
*a
, const BIGNUM
*b
)
2978 if ((a
== NULL
) || (b
== NULL
)) {
2990 if (a
->neg
!= b
->neg
) {
3001 if (a
->top
> b
->top
) return (gt
);
3002 if (a
->top
< b
->top
) return (lt
);
3003 for (i
= a
->top
-1; i
>= 0; i
--) {
3006 if (t1
> t2
) return (gt
);
3007 if (t1
< t2
) return (lt
);
3011 #endif /* BCMDH_TEST */
3014 BN_set_bit(BIGNUM
*a
, int n
)
3021 if (bn_wexpand(a
, i
+ 1) == NULL
) return (0);
3022 for (k
= a
->top
; k
< i
+ 1; k
++)
3027 a
->d
[i
] |= (((BN_ULONG
)1) << j
);
3031 #ifdef NOT_NEEDED_FOR_DH
3033 BN_clear_bit(BIGNUM
*a
, int n
)
3039 if (a
->top
<= i
) return (0);
3041 a
->d
[i
] &= (~(((BN_ULONG
)1) << j
));
3045 #endif /* NOT_NEEDED_FOR_DH */
3048 BN_is_bit_set(const BIGNUM
*a
, int n
)
3052 if (n
< 0) return (0);
3055 if (a
->top
<= i
) return (0);
3056 return ((a
->d
[i
]&(((BN_ULONG
)1) << j
)) ? 1 : 0);
3059 #ifdef NOT_NEEDED_FOR_DH
3061 BN_mask_bits(BIGNUM
*a
, int n
)
3067 if (w
>= a
->top
) return (0);
3072 a
->d
[w
] &= ~(BN_MASK2
<< b
);
3077 #endif /* NOT_NEEDED_FOR_DH */
3080 bn_cmp_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int n
)
3087 if (aa
!= bb
) return ((aa
> bb
)?1:-1);
3088 for (i
= n
-2; i
>= 0; i
--) {
3091 if (aa
!= bb
) return ((aa
> bb
)?1:-1);
3096 #ifdef NOT_NEEDED_FOR_DH
3097 /* Here follows a specialised variants of bn_cmp_words(). It has the
3098 * property of performing the operation on arrays of different sizes.
3099 * The sizes of those arrays is expressed through cl, which is the
3100 * common length ( basicall, min(len(a), len(b)) ), and dl, which is the
3101 * delta between the two lengths, calculated as len(a)-len(b).
3102 * All lengths are the number of BN_ULONGs...
3106 bn_cmp_part_words(const BN_ULONG
*a
, const BN_ULONG
*b
, int cl
, int dl
)
3112 for (i
= dl
; i
< 0; i
++) {
3114 return -1; /* a < b */
3118 for (i
= dl
; i
> 0; i
--) {
3120 return 1; /* a > b */
3123 return bn_cmp_words(a
, b
, cl
);
3125 #endif /* NOT_NEEDED_FOR_DH */
3130 BN_nnmod(BIGNUM
*r
, const BIGNUM
*m
, const BIGNUM
*d
, BN_CTX
*ctx
)
3132 /* like BN_mod, but returns non-negative remainder
3133 * (i.e., 0 <= r < |d| always holds)
3136 if (!(BN_mod(r
, m
, d
, ctx
)))
3140 /* now -|d| < r < 0, so we have to set r : = r + |d| */
3141 return (d
->neg
? BN_sub
: BN_add
)(r
, r
, d
);
3145 #ifdef NOT_NEEDED_FOR_DH
3147 BN_mod_add(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
, BN_CTX
*ctx
)
3149 if (!BN_add(r
, a
, b
))
3151 return BN_nnmod(r
, r
, m
, ctx
);
3155 /* BN_mod_add variant that may be used if both a and b are non-negative
3159 BN_mod_add_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
)
3161 if (!BN_add(r
, a
, b
)) return 0;
3162 if (BN_ucmp(r
, m
) >= 0)
3163 return BN_usub(r
, r
, m
);
3168 BN_mod_sub(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
, BN_CTX
*ctx
)
3170 if (!BN_sub(r
, a
, b
)) return 0;
3171 return BN_nnmod(r
, r
, m
, ctx
);
3174 /* BN_mod_sub variant that may be used if both a and b are non-negative
3178 BN_mod_sub_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
)
3180 if (!BN_sub(r
, a
, b
))
3183 return BN_add(r
, r
, m
);
3186 #endif /* NOT_NEEDED_FOR_DH */
3189 /* slow but works */
3191 BN_mod_mul(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, const BIGNUM
*m
, BN_CTX
*ctx
)
3201 if ((t
= BN_CTX_get(ctx
)) == NULL
) goto err
;
3202 if (a
== b
) { if (!BN_sqr(t
, a
, ctx
)) goto err
; }
3203 else { if (!BN_mul(t
, a
, b
, ctx
)) goto err
; }
3204 if (!BN_nnmod(r
, t
, m
, ctx
)) goto err
;
3210 #endif /* BCMDH_TEST */
3213 #ifdef NOT_NEEDED_FOR_DH
3215 BN_mod_sqr(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
, BN_CTX
*ctx
)
3217 if (!BN_sqr(r
, a
, ctx
)) return 0;
3218 /* r->neg == 0, thus we don't need BN_nnmod */
3219 return BN_mod(r
, r
, m
, ctx
);
3224 BN_mod_lshift1(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
, BN_CTX
*ctx
)
3226 if (!BN_lshift1(r
, a
))
3228 return BN_nnmod(r
, r
, m
, ctx
);
3232 /* BN_mod_lshift1 variant that may be used if a is non-negative
3236 BN_mod_lshift1_quick(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*m
)
3238 if (!BN_lshift1(r
, a
)) return 0;
3239 if (BN_cmp(r
, m
) >= 0)
3240 return BN_sub(r
, r
, m
);
3246 BN_mod_lshift(BIGNUM
*r
, const BIGNUM
*a
, int n
, const BIGNUM
*m
, BN_CTX
*ctx
)
3248 BIGNUM
*abs_m
= NULL
;
3251 if (!BN_nnmod(r
, a
, m
, ctx
))
3256 if (abs_m
== NULL
) return 0;
3260 ret
= BN_mod_lshift_quick(r
, r
, n
, (abs_m
? abs_m
: m
));
3268 /* BN_mod_lshift variant that may be used if a is non-negative
3272 BN_mod_lshift_quick(BIGNUM
*r
, const BIGNUM
*a
, int n
, const BIGNUM
*m
)
3275 if (BN_copy(r
, a
) == NULL
) return 0;
3282 max_shift
= BN_num_bits(m
) - BN_num_bits(r
);
3283 /* max_shift >= 0 */
3285 if (max_shift
< 0) {
3286 BNerr(BN_F_BN_MOD_LSHIFT_QUICK
, BN_R_INPUT_NOT_REDUCED
);
3294 if (!BN_lshift(r
, r
, max_shift
)) return 0;
3297 if (!BN_lshift1(r
, r
)) return 0;
3301 /* BN_num_bits(r) <= BN_num_bits(m) */
3303 if (BN_cmp(r
, m
) >= 0) {
3304 if (!BN_sub(r
, r
, m
)) return 0;
3310 #endif /* NOT_NEEDED_FOR_DH */
3313 * Details about Montgomery multiplication algorithms can be found at
3314 * http://security.ece.orst.edu/publications.html, e.g.
3315 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
3316 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
3320 #define MONT_WORD /* use the faster word-based algorithm */
3323 BN_mod_mul_montgomery(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, BN_MONT_CTX
*mont
, BN_CTX
*ctx
)
3329 tmp
= BN_CTX_get(ctx
);
3330 if (tmp
== NULL
) goto err
;
3334 if (!BN_sqr(tmp
, a
, ctx
)) goto err
;
3336 if (!BN_mul(tmp
, a
, b
, ctx
)) goto err
;
3338 /* reduce from aRR to aR */
3339 if (!BN_from_montgomery(r
, tmp
, mont
, ctx
)) goto err
;
3347 BN_from_montgomery(BIGNUM
*ret
, const BIGNUM
*a
, BN_MONT_CTX
*mont
, BN_CTX
*ctx
)
3353 BN_ULONG
*ap
, *np
, *rp
, n0
, v
, *nrp
;
3354 int al
, nl
, max
, i
, x
, ri
;
3357 if ((r
= BN_CTX_get(ctx
)) == NULL
) goto err
;
3359 if (!BN_copy(r
, a
)) goto err
;
3363 /* mont->ri is the size of mont->N in bits (rounded up
3366 al
= ri
= mont
->ri
/BN_BITS2
;
3369 if ((al
== 0) || (nl
== 0)) {
3374 max
= (nl
+ al
+ 1);
3375 if (bn_wexpand(r
, max
) == NULL
)
3377 if (bn_wexpand(ret
, max
) == NULL
)
3380 r
->neg
= a
->neg
^n
->neg
;
3385 /* clear the top words of T */
3386 for (i
= r
->top
; i
< max
; i
++)
3393 fprintf(stderr
, "word BN_from_montgomery %d * %d\n", nl
, nl
);
3395 for (i
= 0; i
< nl
; i
++) {
3401 t1
= rp
[0] * (n0
& 0177777);
3404 t3
= rp
[0] & 0177777;
3405 t2
= (t3
* t2
) & BN_MASK2
;
3407 v
= bn_mul_add_words(rp
, np
, nl
, (BN_ULONG
) t1
);
3410 v
= bn_mul_add_words(rp
, np
, nl
, (rp
[0]*n0
)&BN_MASK2
);
3414 if (((nrp
[-1] += v
)&BN_MASK2
) >= v
)
3417 if (((++nrp
[0])&BN_MASK2
) != 0) continue;
3418 if (((++nrp
[1])&BN_MASK2
) != 0) continue;
3419 for (x
= 2; (((++nrp
[x
]) & BN_MASK2
) == 0); x
++)
3425 /* mont->ri will be a multiple of the word size */
3436 for (i
= 0; i
< al
; i
+= 4) {
3437 BN_ULONG t1
, t2
, t3
, t4
;
3451 #else /* !MONT_WORD */
3455 t1
= BN_CTX_get(ctx
);
3456 t2
= BN_CTX_get(ctx
);
3457 if (t1
== NULL
|| t2
== NULL
) goto err
;
3459 if (!BN_copy(t1
, a
)) goto err
;
3460 BN_mask_bits(t1
, mont
->ri
);
3462 if (!BN_mul(t2
, t1
, &mont
->Ni
, ctx
)) goto err
;
3463 BN_mask_bits(t2
, mont
->ri
);
3465 if (!BN_mul(t1
, t2
, &mont
->N
, ctx
)) goto err
;
3466 if (!BN_add(t2
, a
, t1
)) goto err
;
3467 if (!BN_rshift(ret
, t2
, mont
->ri
)) goto err
;
3468 #endif /* MONT_WORD */
3470 if (BN_ucmp(ret
, &(mont
->N
)) >= 0) {
3471 if (!BN_usub(ret
, ret
, &(mont
->N
))) goto err
;
3480 BN_MONT_CTX_new(void)
3484 if ((ret
= (BN_MONT_CTX
*)OPENSSL_malloc(sizeof(BN_MONT_CTX
))) == NULL
)
3487 BN_MONT_CTX_init(ret
);
3488 ret
->flags
= BN_FLG_MALLOCED
;
3493 BN_MONT_CTX_init(BN_MONT_CTX
*ctx
)
3496 BN_init(&(ctx
->RR
));
3498 BN_init(&(ctx
->Ni
));
3503 BN_MONT_CTX_free(BN_MONT_CTX
*mont
)
3508 BN_free(&(mont
->RR
));
3509 BN_free(&(mont
->N
));
3510 BN_free(&(mont
->Ni
));
3511 if (mont
->flags
& BN_FLG_MALLOCED
)
3516 BN_MONT_CTX_set(BN_MONT_CTX
*mont
, const BIGNUM
*mod
, BN_CTX
*ctx
)
3521 R
= &(mont
->RR
); /* grab RR as a temp */
3522 BN_copy(&(mont
->N
), mod
); /* Set N */
3530 mont
->ri
= (BN_num_bits(mod
)+(BN_BITS2
-1))/BN_BITS2
*BN_BITS2
;
3531 if (!(BN_zero(R
))) goto err
;
3532 if (!(BN_set_bit(R
, BN_BITS2
))) goto err
; /* R */
3534 buf
[0] = mod
->d
[0]; /* tmod = N mod word size */
3540 /* Ri = R^-1 mod N */
3541 if ((BN_mod_inverse(&Ri
, R
, &tmod
, ctx
)) == NULL
)
3543 if (!BN_lshift(&Ri
, &Ri
, BN_BITS2
)) goto err
; /* R*Ri */
3544 if (!BN_is_zero(&Ri
)) {
3545 if (!BN_sub_word(&Ri
, 1)) goto err
;
3547 /* if N mod word size == 1 */
3548 if (!BN_set_word(&Ri
, BN_MASK2
)) goto err
; /* Ri-- (mod word size) */
3550 if (!BN_div(&Ri
, NULL
, &Ri
, &tmod
, ctx
)) goto err
;
3552 * keep only least significant word:
3554 mont
->n0
= (Ri
.top
> 0) ? Ri
.d
[0] : 0;
3557 #else /* !MONT_WORD */
3559 /* bignum version */
3560 mont
->ri
= BN_num_bits(&mont
->N
);
3561 if (!BN_zero(R
)) goto err
;
3562 if (!BN_set_bit(R
, mont
->ri
)) goto err
; /* R = 2^ri */
3563 /* Ri = R^-1 mod N */
3564 if ((BN_mod_inverse(&Ri
, R
, &mont
->N
, ctx
)) == NULL
)
3566 if (!BN_lshift(&Ri
, &Ri
, mont
->ri
)) goto err
; /* R*Ri */
3567 if (!BN_sub_word(&Ri
, 1)) goto err
;
3568 /* Ni = (R*Ri-1) / N */
3569 if (!BN_div(&(mont
->Ni
), NULL
, &Ri
, &mont
->N
, ctx
)) goto err
;
3572 #endif /* MONT_WORD */
3574 /* setup RR for conversions */
3575 if (!BN_zero(&(mont
->RR
))) goto err
;
3576 if (!BN_set_bit(&(mont
->RR
), mont
->ri
*2)) goto err
;
3577 if (!BN_mod(&(mont
->RR
), &(mont
->RR
), &(mont
->N
), ctx
)) goto err
;
3584 #ifdef NOT_NEEDED_FOR_DH
3586 BN_MONT_CTX_copy(BN_MONT_CTX
*to
, BN_MONT_CTX
*from
)
3588 if (to
== from
) return (to
);
3590 if (!BN_copy(&(to
->RR
), &(from
->RR
))) return NULL
;
3591 if (!BN_copy(&(to
->N
), &(from
->N
))) return NULL
;
3592 if (!BN_copy(&(to
->Ni
), &(from
->Ni
))) return NULL
;
3597 #endif /* NOT_NEEDED_FOR_DH */
3601 /* Karatsuba recursive multiplication algorithm
3602 * (cf. Knuth, The Art of Computer Programming, Vol. 2)
3605 /* r is 2*n2 words in size,
3606 * a and b are both n2 words in size.
3607 * n2 must be a power of 2.
3608 * We multiply and return the result.
3609 * t must be 2*n2 words in size
3612 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
3616 bn_mul_recursive(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, int n2
, BN_ULONG
*t
)
3618 int n
= n2
/2, c1
, c2
;
3619 unsigned int neg
, zero
;
3620 BN_ULONG ln
, lo
, *p
;
3623 printf(" bn_mul_recursive %d * %d\n", n2
, n2
);
3627 bn_mul_comba8(r
, a
, b
);
3630 #endif /* BN_MUL_COMBA */
3631 if (n2
< BN_MUL_RECURSIVE_SIZE_NORMAL
) {
3632 /* This should not happen */
3633 bn_mul_normal(r
, a
, n2
, b
, n2
);
3636 /* r = (a[0]-a[1])*(b[1]-b[0]) */
3637 c1
= bn_cmp_words(a
, &(a
[n
]), n
);
3638 c2
= bn_cmp_words(&(b
[n
]), b
, n
);
3642 bn_sub_words(t
, &(a
[n
]), a
, n
); /* - */
3643 bn_sub_words(&(t
[n
]), b
, &(b
[n
]), n
); /* - */
3649 bn_sub_words(t
, &(a
[n
]), a
, n
); /* - */
3650 bn_sub_words(&(t
[n
]), &(b
[n
]), b
, n
); /* + */
3659 bn_sub_words(t
, a
, &(a
[n
]), n
); /* + */
3660 bn_sub_words(&(t
[n
]), b
, &(b
[n
]), n
); /* - */
3667 bn_sub_words(t
, a
, &(a
[n
]), n
);
3668 bn_sub_words(&(t
[n
]), &(b
[n
]), b
, n
);
3672 # ifdef BN_MUL_COMBA
3675 bn_mul_comba4(&(t
[n2
]), t
, &(t
[n
]));
3677 memset(&(t
[n2
]), 0, 8*sizeof(BN_ULONG
));
3679 bn_mul_comba4(r
, a
, b
);
3680 bn_mul_comba4(&(r
[n2
]), &(a
[n
]), &(b
[n
]));
3681 } else if (n
== 8) {
3683 bn_mul_comba8(&(t
[n2
]), t
, &(t
[n
]));
3685 memset(&(t
[n2
]), 0, 16*sizeof(BN_ULONG
));
3687 bn_mul_comba8(r
, a
, b
);
3688 bn_mul_comba8(&(r
[n2
]), &(a
[n
]), &(b
[n
]));
3690 # endif /* BN_MUL_COMBA */
3694 bn_mul_recursive(&(t
[n2
]), t
, &(t
[n
]), n
, p
);
3696 memset(&(t
[n2
]), 0, n2
*sizeof(BN_ULONG
));
3697 bn_mul_recursive(r
, a
, b
, n
, p
);
3698 bn_mul_recursive(&(r
[n2
]), &(a
[n
]), &(b
[n
]), n
, p
);
3701 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
3702 * r[10] holds (a[0]*b[0])
3703 * r[32] holds (b[1]*b[1])
3706 c1
= (int)(bn_add_words(t
, r
, &(r
[n2
]), n2
));
3709 /* if t[32] is negative */
3710 c1
-= (int)(bn_sub_words(&(t
[n2
]), t
, &(t
[n2
]), n2
));
3712 /* Might have a carry */
3713 c1
+= (int)(bn_add_words(&(t
[n2
]), &(t
[n2
]), t
, n2
));
3716 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
3717 * r[10] holds (a[0]*b[0])
3718 * r[32] holds (b[1]*b[1])
3719 * c1 holds the carry bits
3721 c1
+= (int)(bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[n2
]), n2
));
3725 ln
= (lo
+c1
)&BN_MASK2
;
3728 /* The overflow will stop before we over write
3729 * words we should not overwrite
3731 if (ln
< (BN_ULONG
)c1
) {
3735 ln
= (lo
+1)&BN_MASK2
;
3742 /* n+tn is the word length
3743 * t needs to be n*4 is size, as does r
3746 bn_mul_part_recursive(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, int tn
, int n
, BN_ULONG
*t
)
3749 int c1
, c2
, neg
, zero
;
3750 BN_ULONG ln
, lo
, *p
;
3753 printf(" bn_mul_part_recursive %d * %d\n", tn
+n
, tn
+n
);
3757 bn_mul_normal(r
, a
, i
, b
, i
);
3761 /* r = (a[0]-a[1])*(b[1]-b[0]) */
3762 c1
= bn_cmp_words(a
, &(a
[n
]), n
);
3763 c2
= bn_cmp_words(&(b
[n
]), b
, n
);
3765 switch (c1
* 3 + c2
) {
3767 bn_sub_words(t
, &(a
[n
]), a
, n
); /* - */
3768 bn_sub_words(&(t
[n
]), b
, &(b
[n
]), n
); /* - */
3774 bn_sub_words(t
, &(a
[n
]), a
, n
); /* - */
3775 bn_sub_words(&(t
[n
]), &(b
[n
]), b
, n
); /* + */
3784 bn_sub_words(t
, a
, &(a
[n
]), n
); /* + */
3785 bn_sub_words(&(t
[n
]), b
, &(b
[n
]), n
); /* - */
3792 bn_sub_words(t
, a
, &(a
[n
]), n
);
3793 bn_sub_words(&(t
[n
]), &(b
[n
]), b
, n
);
3796 /* The zero case isn't yet implemented here. The speedup
3797 * would probably be negligible.
3800 bn_mul_comba8(&(t
[n2
]), t
, &(t
[n
]));
3801 bn_mul_comba8(r
, a
, b
);
3802 bn_mul_normal(&(r
[n2
]), &(a
[n
]), tn
, &(b
[n
]), tn
);
3803 memset(&(r
[n2
+tn
*2]), 0, sizeof(BN_ULONG
)*(n2
-tn
*2));
3806 bn_mul_recursive(&(t
[n2
]), t
, &(t
[n
]), n
, p
);
3807 bn_mul_recursive(r
, a
, b
, n
, p
);
3809 /* If there is only a bottom half to the number,
3814 bn_mul_recursive(&(r
[n2
]), &(a
[n
]), &(b
[n
]), i
, p
);
3815 memset(&(r
[n2
+i
*2]), 0, sizeof(BN_ULONG
)*(n2
-i
*2));
3817 /* eg, n == 16, i == 8 and tn == 11 */
3818 bn_mul_part_recursive(&(r
[n2
]), &(a
[n
]), &(b
[n
]), j
, i
, p
);
3819 memset(&(r
[n2
+tn
*2]), 0, sizeof(BN_ULONG
)*(n2
-tn
*2));
3821 /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
3822 memset(&(r
[n2
]), 0, sizeof(BN_ULONG
)*n2
);
3823 if (tn
< BN_MUL_RECURSIVE_SIZE_NORMAL
) {
3824 bn_mul_normal(&(r
[n2
]), &(a
[n
]), tn
, &(b
[n
]), tn
);
3829 bn_mul_part_recursive(&(r
[n2
]),
3833 } else if (i
== tn
) {
3834 bn_mul_recursive(&(r
[n2
]),
3844 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
3845 * r[10] holds (a[0]*b[0])
3846 * r[32] holds (b[1]*b[1])
3849 c1
= (int)(bn_add_words(t
, r
, &(r
[n2
]), n2
));
3851 if (neg
) /* if t[32] is negative */ {
3852 c1
-= (int)(bn_sub_words(&(t
[n2
]), t
, &(t
[n2
]), n2
));
3854 /* Might have a carry */
3855 c1
+= (int)(bn_add_words(&(t
[n2
]), &(t
[n2
]), t
, n2
));
3858 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
3859 * r[10] holds (a[0]*b[0])
3860 * r[32] holds (b[1]*b[1])
3861 * c1 holds the carry bits
3863 c1
+= (int)(bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[n2
]), n2
));
3867 ln
= (lo
+c1
)&BN_MASK2
;
3870 /* The overflow will stop before we over write
3871 * words we should not overwrite
3873 if (ln
< (BN_ULONG
)c1
) {
3877 ln
= (lo
+1)&BN_MASK2
;
3884 #ifdef NOT_NEEDED_FOR_DH
3885 /* a and b must be the same size, which is n2.
3886 * r needs to be n2 words and t needs to be n2*2
3889 bn_mul_low_recursive(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, int n2
, BN_ULONG
*t
)
3894 printf(" bn_mul_low_recursive %d * %d\n", n2
, n2
);
3897 bn_mul_recursive(r
, a
, b
, n
, &(t
[0]));
3898 if (n
>= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL
) {
3899 bn_mul_low_recursive(&(t
[0]), &(a
[0]), &(b
[n
]), n
, &(t
[n2
]));
3900 bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[0]), n
);
3901 bn_mul_low_recursive(&(t
[0]), &(a
[n
]), &(b
[0]), n
, &(t
[n2
]));
3902 bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[0]), n
);
3904 bn_mul_low_normal(&(t
[0]), &(a
[0]), &(b
[n
]), n
);
3905 bn_mul_low_normal(&(t
[n
]), &(a
[n
]), &(b
[0]), n
);
3906 bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[0]), n
);
3907 bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[n
]), n
);
3910 #endif /* NOT_NEEDED_FOR_DH */
3912 /* a and b must be the same size, which is n2.
3913 * r needs to be n2 words and t needs to be n2*2
3914 * l is the low words of the output.
3915 * t needs to be n2*3
3918 bn_mul_high(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, BN_ULONG
*l
, int n2
, BN_ULONG
*t
)
3922 int neg
, oneg
, zero
;
3923 BN_ULONG ll
, lc
, *lp
, *mp
;
3926 printf(" bn_mul_high %d * %d\n", n2
, n2
);
3930 /* Calculate (al - ah) * (bh - bl) */
3932 c1
= bn_cmp_words(&(a
[0]), &(a
[n
]), n
);
3933 c2
= bn_cmp_words(&(b
[n
]), &(b
[0]), n
);
3934 switch (c1
* 3 + c2
) {
3936 bn_sub_words(&(r
[0]), &(a
[n
]), &(a
[0]), n
);
3937 bn_sub_words(&(r
[n
]), &(b
[0]), &(b
[n
]), n
);
3943 bn_sub_words(&(r
[0]), &(a
[n
]), &(a
[0]), n
);
3944 bn_sub_words(&(r
[n
]), &(b
[n
]), &(b
[0]), n
);
3953 bn_sub_words(&(r
[0]), &(a
[0]), &(a
[n
]), n
);
3954 bn_sub_words(&(r
[n
]), &(b
[0]), &(b
[n
]), n
);
3961 bn_sub_words(&(r
[0]), &(a
[0]), &(a
[n
]), n
);
3962 bn_sub_words(&(r
[n
]), &(b
[n
]), &(b
[0]), n
);
3967 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
3968 /* r[10] = (a[1]*b[1]) */
3969 # ifdef BN_MUL_COMBA
3971 bn_mul_comba8(&(t
[0]), &(r
[0]), &(r
[n
]));
3972 bn_mul_comba8(r
, &(a
[n
]), &(b
[n
]));
3976 bn_mul_recursive(&(t
[0]), &(r
[0]), &(r
[n
]), n
, &(t
[n2
]));
3977 bn_mul_recursive(r
, &(a
[n
]), &(b
[n
]), n
, &(t
[n2
]));
3981 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
3982 * We know s0 and s1 so the only unknown is high(al*bl)
3983 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
3984 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
3988 c1
= (int)(bn_add_words(lp
, &(r
[0]), &(l
[0]), n
));
3995 neg
= (int)(bn_sub_words(&(t
[n2
]), lp
, &(t
[0]), n
));
3997 bn_add_words(&(t
[n2
]), lp
, &(t
[0]), n
);
4002 bn_sub_words(&(t
[n2
+n
]), &(l
[n
]), &(t
[n2
]), n
);
4006 for (i
= 0; i
< n
; i
++)
4007 lp
[i
] = ((~mp
[i
])+1)&BN_MASK2
;
4010 /* s[0] = low(al*bl)
4011 * t[3] = high(al*bl)
4012 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
4013 * r[10] = (a[1]*b[1])
4016 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
4019 /* R[1] = t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
4020 * R[2] = r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
4021 * R[3] = r[1]+(carry/borrow)
4025 c1
= (int)(bn_add_words(lp
, &(t
[n2
+n
]), &(l
[0]), n
));
4030 c1
+= (int)(bn_add_words(&(t
[n2
]), lp
, &(r
[0]), n
));
4032 c1
-= (int)(bn_sub_words(&(t
[n2
]), &(t
[n2
]), &(t
[0]), n
));
4034 c1
+= (int)(bn_add_words(&(t
[n2
]), &(t
[n2
]), &(t
[0]), n
));
4036 c2
= (int)(bn_add_words(&(r
[0]), &(r
[0]), &(t
[n2
+n
]), n
));
4037 c2
+= (int)(bn_add_words(&(r
[0]), &(r
[0]), &(r
[n
]), n
));
4039 c2
-= (int)(bn_sub_words(&(r
[0]), &(r
[0]), &(t
[n
]), n
));
4041 c2
+= (int)(bn_add_words(&(r
[0]), &(r
[0]), &(t
[n
]), n
));
4044 /* Add starting at r[0], could be +ve or -ve */
4049 ll
= (r
[i
]+lc
)&BN_MASK2
;
4057 r
[i
++] = (ll
-lc
)&BN_MASK2
;
4063 /* Add starting at r[1] */
4068 ll
= (r
[i
]+lc
)&BN_MASK2
;
4076 r
[i
++] = (ll
-lc
)&BN_MASK2
;
4082 #endif /* BN_RECURSION */
4085 BN_mul(BIGNUM
*r
, const BIGNUM
*a
, const BIGNUM
*b
, BN_CTX
*ctx
)
4090 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
4099 printf("BN_mul %d * %d\n", a
->top
, b
->top
);
4109 if ((al
== 0) || (bl
== 0)) {
4110 if (!BN_zero(r
)) goto err
;
4116 if ((r
== a
) || (r
== b
)) {
4117 if ((rr
= BN_CTX_get(ctx
)) == NULL
) goto err
;
4120 rr
->neg
= a
->neg
^b
->neg
;
4122 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
4128 if (bn_wexpand(rr
, 16) == NULL
) goto err
;
4130 bn_mul_comba8(rr
->d
, a
->d
, b
->d
);
4134 #endif /* BN_MUL_COMBA */
4136 if ((al
>= BN_MULL_SIZE_NORMAL
) && (bl
>= BN_MULL_SIZE_NORMAL
)) {
4137 if (i
== 1 && !BN_get_flags(b
, BN_FLG_STATIC_DATA
) && bl
< b
->dmax
) {
4141 } else if (i
== -1 && !BN_get_flags(a
, BN_FLG_STATIC_DATA
) && al
< a
->dmax
) {
4147 /* symmetric and > 4 */
4149 j
= BN_num_bits_word((BN_ULONG
)al
);
4152 t
= BN_CTX_get(ctx
);
4154 /* exact multiple */
4155 if (bn_wexpand(t
, k
*2) == NULL
) goto err
;
4156 if (bn_wexpand(rr
, k
*2) == NULL
) goto err
;
4157 bn_mul_recursive(rr
->d
, a
->d
, b
->d
, al
, t
->d
);
4163 #endif /* BN_RECURSION */
4164 if (bn_wexpand(rr
, top
) == NULL
) goto err
;
4166 bn_mul_normal(rr
->d
, a
->d
, al
, b
->d
, bl
);
4168 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
4172 if (r
!= rr
) BN_copy(r
, rr
);
4180 bn_mul_normal(BN_ULONG
*r
, BN_ULONG
*a
, int na
, BN_ULONG
*b
, int nb
)
4185 printf(" bn_mul_normal %d * %d\n", na
, nb
);
4192 itmp
= na
; na
= nb
; nb
= itmp
;
4193 ltmp
= a
; a
= b
; b
= ltmp
;
4196 rr
[0] = bn_mul_words(r
, a
, na
, b
[0]);
4199 if (--nb
<= 0) return;
4200 rr
[1] = bn_mul_add_words(&(r
[1]), a
, na
, b
[1]);
4201 if (--nb
<= 0) return;
4202 rr
[2] = bn_mul_add_words(&(r
[2]), a
, na
, b
[2]);
4203 if (--nb
<= 0) return;
4204 rr
[3] = bn_mul_add_words(&(r
[3]), a
, na
, b
[3]);
4205 if (--nb
<= 0) return;
4206 rr
[4] = bn_mul_add_words(&(r
[4]), a
, na
, b
[4]);
4213 #ifdef NOT_NEEDED_FOR_DH
4215 bn_mul_low_normal(BN_ULONG
*r
, BN_ULONG
*a
, BN_ULONG
*b
, int n
)
4218 printf(" bn_mul_low_normal %d * %d\n", n
, n
);
4220 bn_mul_words(r
, a
, n
, b
[0]);
4223 if (--n
<= 0) return;
4224 bn_mul_add_words(&(r
[1]), a
, n
, b
[1]);
4225 if (--n
<= 0) return;
4226 bn_mul_add_words(&(r
[2]), a
, n
, b
[2]);
4227 if (--n
<= 0) return;
4228 bn_mul_add_words(&(r
[3]), a
, n
, b
[3]);
4229 if (--n
<= 0) return;
4230 bn_mul_add_words(&(r
[4]), a
, n
, b
[4]);
4235 #endif /* NOT_NEEDED_FOR_DH */
4238 bnrand(int pseudorand
, BIGNUM
*rnd
, int bits
, int top
, int bottom
)
4240 unsigned char *buf
= NULL
;
4241 int ret
= 0, bit
, bytes
, mask
;
4248 bytes
= (bits
+ 7) / 8;
4249 bit
= (bits
- 1) % 8;
4250 mask
= 0xff << (bit
+ 1);
4252 buf
= (unsigned char *)OPENSSL_malloc(bytes
);
4254 BNerr(BN_F_BN_RAND
, ERR_R_MALLOC_FAILURE
);
4260 bn_rand_fn(buf
, bytes
);
4262 if (pseudorand
== 2) {
4263 /* generate patterns that are more likely to trigger BN
4269 for (i
= 0; i
< bytes
; i
++) {
4270 /* RAND_pseudo_bytes(&c, 1); */
4272 if (c
>= 128 && i
> 0)
4287 buf
[0] |= (3 << (bit
- 1));
4290 buf
[0] |= (1 << bit
);
4294 if (bottom
) /* set bottom bit if requested */
4296 if (!BN_bin2bn(buf
, bytes
, rnd
)) goto err
;
4300 OPENSSL_cleanse(buf
, bytes
);
4307 BN_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
4309 return bnrand(0, rnd
, bits
, top
, bottom
);
4314 BN_pseudo_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
4316 return bnrand(1, rnd
, bits
, top
, bottom
);
4318 #endif /* BCMDH_TEST */
4320 #ifdef NOT_NEEDED_FOR_DH
4322 BN_bntest_rand(BIGNUM
*rnd
, int bits
, int top
, int bottom
)
4324 return bnrand(2, rnd
, bits
, top
, bottom
);
4326 #endif /* NOT_NEEDED_FOR_DH */
4330 /* random number r: 0 <= r < range */
4332 bn_rand_range(int pseudo
, BIGNUM
*r
, BIGNUM
*range
)
4334 int (*bn_rand
)(BIGNUM
*, int, int, int) = pseudo
? BN_pseudo_rand
: BN_rand
;
4337 if (range
->neg
|| BN_is_zero(range
)) {
4338 BNerr(BN_F_BN_RAND_RANGE
, BN_R_INVALID_RANGE
);
4342 n
= BN_num_bits(range
); /* n > 0 */
4344 /* BN_is_bit_set(range, n - 1) always holds */
4347 if (!BN_zero(r
)) return 0;
4348 } else if (!BN_is_bit_set(range
, n
- 2) && !BN_is_bit_set(range
, n
- 3)) {
4349 /* range = 100..._2,
4350 * so 3*range ( = 11..._2) is exactly one bit longer than range
4353 if (!bn_rand(r
, n
+ 1, -1, 0)) return 0;
4354 /* If r < 3*range, use r : = r MOD range
4355 * (which is either r, r - range, or r - 2*range).
4356 * Otherwise, iterate once more.
4357 * Since 3*range = 11..._2, each iteration succeeds with
4358 * probability >= .75.
4360 if (BN_cmp(r
, range
) >= 0) {
4361 if (!BN_sub(r
, r
, range
)) return 0;
4362 if (BN_cmp(r
, range
) >= 0)
4363 if (!BN_sub(r
, r
, range
)) return 0;
4366 while (BN_cmp(r
, range
) >= 0)
4370 /* range = 11..._2 or range = 101..._2 */
4371 if (!bn_rand(r
, n
, -1, 0))
4373 } while (BN_cmp(r
, range
) >= 0);
4378 #endif /* BCMDH_TEST */
4380 #ifdef NOT_NEEDED_FOR_DH
4382 BN_rand_range(BIGNUM
*r
, BIGNUM
*range
)
4384 return bn_rand_range(0, r
, range
);
4386 #endif /* NOT_NEEDED_FOR_DH */
4390 BN_pseudo_rand_range(BIGNUM
*r
, BIGNUM
*range
)
4392 return bn_rand_range(1, r
, range
);
4394 #endif /* BCMDH_TEST */
4396 #ifdef NOT_NEEDED_FOR_DH
4398 BN_RECP_CTX_init(BN_RECP_CTX
*recp
)
4400 BN_init(&(recp
->N
));
4401 BN_init(&(recp
->Nr
));
4407 BN_RECP_CTX_new(void)
4411 if ((ret
= (BN_RECP_CTX
*)OPENSSL_malloc(sizeof(BN_RECP_CTX
))) == NULL
)
4414 BN_RECP_CTX_init(ret
);
4415 ret
->flags
= BN_FLG_MALLOCED
;
4420 BN_RECP_CTX_free(BN_RECP_CTX
*recp
)
4425 BN_free(&(recp
->N
));
4426 BN_free(&(recp
->Nr
));
4427 if (recp
->flags
& BN_FLG_MALLOCED
)
4432 BN_RECP_CTX_set(BN_RECP_CTX
*recp
, const BIGNUM
*d
, BN_CTX
*ctx
)
4434 if (!BN_copy(&(recp
->N
), d
)) return 0;
4435 if (!BN_zero(&(recp
->Nr
))) return 0;
4436 recp
->num_bits
= BN_num_bits(d
);
4442 BN_mod_mul_reciprocal(BIGNUM
*r
, const BIGNUM
*x
, const BIGNUM
*y
,
4443 BN_RECP_CTX
*recp
, BN_CTX
*ctx
)
4450 if ((a
= BN_CTX_get(ctx
)) == NULL
)
4454 if (!BN_sqr(a
, x
, ctx
))
4457 if (!BN_mul(a
, x
, y
, ctx
))
4462 ca
= x
; /* Just do the mod */
4464 ret
= BN_div_recp(NULL
, r
, ca
, recp
, ctx
);
4471 BN_div_recp(BIGNUM
*dv
, BIGNUM
*rem
, const BIGNUM
*m
, BN_RECP_CTX
*recp
, BN_CTX
*ctx
)
4474 BIGNUM
*a
, *b
, *d
, *r
;
4477 a
= BN_CTX_get(ctx
);
4478 b
= BN_CTX_get(ctx
);
4482 d
= BN_CTX_get(ctx
);
4486 r
= BN_CTX_get(ctx
);
4487 if (a
== NULL
|| b
== NULL
|| d
== NULL
|| r
== NULL
)
4490 if (BN_ucmp(m
, &(recp
->N
)) < 0) {
4491 if (!BN_zero(d
)) return 0;
4492 if (!BN_copy(r
, m
)) return 0;
4497 /* We want the remainder
4498 * Given input of ABCDEF / ab
4499 * we need multiply ABCDEF by 3 digests of the reciprocal of ab
4503 /* i : = max(BN_num_bits(m), 2*BN_num_bits(N)) */
4505 j
= recp
->num_bits
<< 1;
4508 /* Nr : = round(2^i / N) */
4509 if (i
!= recp
->shift
)
4510 recp
->shift
= BN_reciprocal(&(recp
->Nr
), &(recp
->N
),
4511 i
, ctx
); /* BN_reciprocal returns i, or -1 for an error */
4512 if (recp
->shift
== -1) goto err
;
4514 /* d : = |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
4515 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
4516 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
4519 if (!BN_rshift(a
, m
, recp
->num_bits
)) goto err
;
4520 if (!BN_mul(b
, a
, &(recp
->Nr
), ctx
)) goto err
;
4521 if (!BN_rshift(d
, b
, i
-recp
->num_bits
)) goto err
;
4524 if (!BN_mul(b
, &(recp
->N
), d
, ctx
)) goto err
;
4525 if (!BN_usub(r
, m
, b
)) goto err
;
4529 while (BN_ucmp(r
, &(recp
->N
)) >= 0) {
4531 BNerr(BN_F_BN_MOD_MUL_RECIPROCAL
, BN_R_BAD_RECIPROCAL
);
4534 if (!BN_usub(r
, r
, &(recp
->N
))) goto err
;
4535 if (!BN_add_word(d
, 1)) goto err
;
4538 r
->neg
= BN_is_zero(r
)?0:m
->neg
;
4539 d
->neg
= m
->neg
^recp
->N
.neg
;
4546 /* len is the expected size of the result
4547 * We actually calculate with an extra word of precision, so
4548 * we can do faster division if the remainder is not required.
4550 /* r : = 2^len / m */
4552 BN_reciprocal(BIGNUM
*r
, const BIGNUM
*m
, int len
, BN_CTX
*ctx
)
4559 if (!BN_zero(&t
)) goto err
;
4560 if (!BN_set_bit(&t
, len
)) goto err
;
4562 if (!BN_div(r
, NULL
, &t
, m
, ctx
)) goto err
;
4569 #endif /* NOT_NEEDED_FOR_DH */
4572 BN_lshift1(BIGNUM
*r
, const BIGNUM
*a
)
4574 register BN_ULONG
*ap
, *rp
, t
, c
;
4579 if (bn_wexpand(r
, a
->top
+1) == NULL
) return (0);
4582 if (bn_wexpand(r
, a
->top
+1) == NULL
) return (0);
4587 for (i
= 0; i
< a
->top
; i
++) {
4589 *(rp
++) = ((t
<< 1) | c
) & BN_MASK2
;
4590 c
= (t
& BN_TBIT
)?1:0;
4600 BN_rshift1(BIGNUM
*r
, const BIGNUM
*a
)
4602 BN_ULONG
*ap
, *rp
, t
, c
;
4605 if (BN_is_zero(a
)) {
4610 if (bn_wexpand(r
, a
->top
) == NULL
) return (0);
4617 for (i
= a
->top
- 1; i
>= 0; i
--) {
4619 rp
[i
] = ((t
>> 1) & BN_MASK2
) | c
;
4620 c
= (t
& 1) ? BN_TBIT
: 0;
4627 BN_lshift(BIGNUM
*r
, const BIGNUM
*a
, int n
)
4635 if (bn_wexpand(r
, a
->top
+ nw
+ 1) == NULL
)
4643 for (i
= a
->top
- 1; i
>= 0; i
--)
4646 for (i
= a
->top
-1; i
>= 0; i
--) {
4648 t
[nw
+ i
+ 1] |= (l
>> rb
) & BN_MASK2
;
4649 t
[nw
+ i
] = (l
<< lb
) & BN_MASK2
;
4651 memset(t
, 0, nw
* sizeof(t
[0]));
4652 /* for (i = 0; i < nw; i++)
4655 r
->top
= a
->top
+ nw
+ 1;
4661 BN_rshift(BIGNUM
*r
, const BIGNUM
*a
, int n
)
4663 int i
, j
, nw
, lb
, rb
;
4670 if (nw
> a
->top
|| a
->top
== 0) {
4676 if (bn_wexpand(r
, a
->top
-nw
+1) == NULL
) return (0);
4679 return 1; /* or the copying loop will go berserk */
4688 for (i
= j
+1; i
> 0; i
--)
4692 for (i
= 1; i
< j
; i
++) {
4693 tmp
= (l
>> rb
)&BN_MASK2
;
4695 *(t
++) = (tmp
| (l
<< lb
)) & BN_MASK2
;
4697 *(t
++) = (l
>>rb
)&BN_MASK2
;
4704 /* r must not be a */
4705 /* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */
4707 BN_sqr(BIGNUM
*r
, const BIGNUM
*a
, BN_CTX
*ctx
)
4714 fprintf(stderr
, "BN_sqr %d * %d\n", a
->top
, a
->top
);
4725 rr
= (a
!= r
) ? r
: BN_CTX_get(ctx
);
4726 tmp
= BN_CTX_get(ctx
);
4727 if (tmp
== NULL
) goto err
;
4730 if (bn_wexpand(rr
, max
+ 1) == NULL
)
4734 #ifndef BN_SQR_COMBA
4736 bn_sqr_normal(rr
->d
, a
->d
, 4, t
);
4738 bn_sqr_comba4(rr
->d
, a
->d
);
4740 } else if (al
== 8) {
4741 #ifndef BN_SQR_COMBA
4743 bn_sqr_normal(rr
->d
, a
->d
, 8, t
);
4745 bn_sqr_comba8(rr
->d
, a
->d
);
4748 #if defined(BN_RECURSION)
4749 if (al
< BN_SQR_RECURSIVE_SIZE_NORMAL
) {
4750 BN_ULONG t
[BN_SQR_RECURSIVE_SIZE_NORMAL
*2];
4751 bn_sqr_normal(rr
->d
, a
->d
, al
, t
);
4755 j
= BN_num_bits_word((BN_ULONG
)al
);
4759 if (bn_wexpand(tmp
, k
*2) == NULL
) goto err
;
4760 bn_sqr_recursive(rr
->d
, a
->d
, al
, tmp
->d
);
4762 if (bn_wexpand(tmp
, max
) == NULL
) goto err
;
4763 bn_sqr_normal(rr
->d
, a
->d
, al
, tmp
->d
);
4767 if (bn_wexpand(tmp
, max
) == NULL
)
4769 bn_sqr_normal(rr
->d
, a
->d
, al
, tmp
->d
);
4770 #endif /* BN_RECURSION */
4775 if ((max
> 0) && (rr
->d
[max
-1] == 0)) rr
->top
--;
4776 if (rr
!= r
) BN_copy(r
, rr
);
4783 /* tmp must have 2*n words */
4785 bn_sqr_normal(BN_ULONG
*r
, const BN_ULONG
*a
, int n
, BN_ULONG
*tmp
)
4794 rp
[0] = rp
[max
-1] = 0;
4800 rp
[j
] = bn_mul_words(rp
, ap
, j
, ap
[-1]);
4804 for (i
= n
- 2; i
> 0; i
--) {
4807 rp
[j
] = bn_mul_add_words(rp
, ap
, j
, ap
[-1]);
4811 bn_add_words(r
, r
, r
, max
);
4813 /* There will not be a carry */
4815 bn_sqr_words(tmp
, a
, n
);
4817 bn_add_words(r
, r
, tmp
, max
);
4821 /* r is 2*n words in size,
4822 * a and b are both n words in size. (There's not actually a 'b' here ...)
4823 * n must be a power of 2.
4824 * We multiply and return the result.
4825 * t must be 2*n words in size
4828 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
4832 bn_sqr_recursive(BN_ULONG
*r
, const BN_ULONG
*a
, int n2
, BN_ULONG
*t
)
4836 BN_ULONG ln
, lo
, *p
;
4839 fprintf(stderr
, " bn_sqr_recursive %d * %d\n", n2
, n2
);
4842 #ifndef BN_SQR_COMBA
4843 bn_sqr_normal(r
, a
, 4, t
);
4845 bn_sqr_comba4(r
, a
);
4848 } else if (n2
== 8) {
4849 #ifndef BN_SQR_COMBA
4850 bn_sqr_normal(r
, a
, 8, t
);
4852 bn_sqr_comba8(r
, a
);
4856 if (n2
< BN_SQR_RECURSIVE_SIZE_NORMAL
) {
4857 bn_sqr_normal(r
, a
, n2
, t
);
4860 /* r = (a[0]-a[1])*(a[1]-a[0]) */
4861 c1
= bn_cmp_words(a
, &(a
[n
]), n
);
4864 bn_sub_words(t
, a
, &(a
[n
]), n
);
4866 bn_sub_words(t
, &(a
[n
]), a
, n
);
4870 /* The result will always be negative unless it is zero */
4874 bn_sqr_recursive(&(t
[n2
]), t
, n
, p
);
4876 memset(&(t
[n2
]), 0, n2
*sizeof(BN_ULONG
));
4877 bn_sqr_recursive(r
, a
, n
, p
);
4878 bn_sqr_recursive(&(r
[n2
]), &(a
[n
]), n
, p
);
4880 /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
4881 * r[10] holds (a[0]*b[0])
4882 * r[32] holds (b[1]*b[1])
4885 c1
= (int)(bn_add_words(t
, r
, &(r
[n2
]), n2
));
4887 /* t[32] is negative */
4888 c1
-= (int)(bn_sub_words(&(t
[n2
]), t
, &(t
[n2
]), n2
));
4890 /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
4891 * r[10] holds (a[0]*a[0])
4892 * r[32] holds (a[1]*a[1])
4893 * c1 holds the carry bits
4895 c1
+= (int)(bn_add_words(&(r
[n
]), &(r
[n
]), &(t
[n2
]), n2
));
4899 ln
= (lo
+c1
)&BN_MASK2
;
4902 /* The overflow will stop before we over write
4903 * words we should not overwrite
4905 if (ln
< (BN_ULONG
)c1
) {
4909 ln
= (lo
+1)&BN_MASK2
;
4915 #endif /* BN_RECURSION */
4919 BN_mod_word(const BIGNUM
*a
, BN_ULONG w
)
4929 for (i
= a
->top
-1; i
>= 0; i
--) {
4931 ret
= ((ret
<< BN_BITS4
) | ((a
->d
[i
] >> BN_BITS4
) & BN_MASK2l
)) % w
;
4932 ret
= ((ret
<< BN_BITS4
) | (a
->d
[i
] & BN_MASK2l
)) % w
;
4934 ret
= (BN_ULLONG
)(((ret
<< (BN_ULLONG
)BN_BITS2
) | a
->d
[i
]) % (BN_ULLONG
)w
);
4937 return ((BN_ULONG
)ret
);
4939 #endif /* BCMDH_TEST */
4941 #ifdef NOT_NEEDED_FOR_DH
4943 BN_div_word(BIGNUM
*a
, BN_ULONG w
)
4948 if (a
->top
== 0) return (0);
4951 for (i
= a
->top
-1; i
>= 0; i
--) {
4955 d
= bn_div_words(ret
, l
, w
);
4956 ret
= (l
-((d
*w
)&BN_MASK2
))&BN_MASK2
;
4959 if ((a
->top
> 0) && (a
->d
[a
->top
-1] == 0))
4963 #endif /* NOT_NEEDED_FOR_DH */
4966 BN_add_word(BIGNUM
*a
, BN_ULONG w
)
4973 i
= BN_sub_word(a
, w
);
4979 if (bn_wexpand(a
, a
->top
+1) == NULL
) return (0);
4985 l
= (a
->d
[i
]+(BN_ULONG
)w
)&BN_MASK2
;
4999 BN_sub_word(BIGNUM
*a
, BN_ULONG w
)
5003 if (BN_is_zero(a
) || a
->neg
) {
5005 i
= BN_add_word(a
, w
);
5011 if ((a
->top
== 1) && (a
->d
[0] < w
)) {
5012 a
->d
[0] = w
-a
->d
[0];
5022 a
->d
[i
] = (a
->d
[i
]-w
)&BN_MASK2
;
5027 if ((a
->d
[i
] == 0) && (i
== (a
->top
-1)))
5033 BN_mul_word(BIGNUM
*a
, BN_ULONG w
)
5042 ll
= bn_mul_words(a
->d
, a
->d
, a
->top
, w
);
5044 if (bn_wexpand(a
, a
->top
+1) == NULL
) return (0);
5045 a
->d
[a
->top
++] = ll
;
5053 /* The quick sieve algorithm approach to weeding out primes is
5054 * Philip Zimmermann's, as implemented in PGP. I have had a read of
5055 * his comments and implemented my own version.
5059 #define NUMPRIMES 2048
5061 #define NUMPRIMES 54
5063 static const unsigned int primes
[NUMPRIMES
] =
5065 2, 3, 5, 7, 11, 13, 17, 19,
5066 23, 29, 31, 37, 41, 43, 47, 53,
5067 59, 61, 67, 71, 73, 79, 83, 89,
5068 97, 101, 103, 107, 109, 113, 127, 131,
5069 137, 139, 149, 151, 157, 163, 167, 173,
5070 179, 181, 191, 193, 197, 199, 211, 223,
5071 227, 229, 233, 239, 241, 251,
5074 269, 271, 277, 281, 283, 293, 307, 311,
5075 313, 317, 331, 337, 347, 349, 353, 359,
5076 367, 373, 379, 383, 389, 397, 401, 409,
5077 419, 421, 431, 433, 439, 443, 449, 457,
5078 461, 463, 467, 479, 487, 491, 499, 503,
5079 509, 521, 523, 541, 547, 557, 563, 569,
5080 571, 577, 587, 593, 599, 601, 607, 613,
5081 617, 619, 631, 641, 643, 647, 653, 659,
5082 661, 673, 677, 683, 691, 701, 709, 719,
5083 727, 733, 739, 743, 751, 757, 761, 769,
5084 773, 787, 797, 809, 811, 821, 823, 827,
5085 829, 839, 853, 857, 859, 863, 877, 881,
5086 883, 887, 907, 911, 919, 929, 937, 941,
5087 947, 953, 967, 971, 977, 983, 991, 997,
5088 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
5089 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
5090 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
5091 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
5092 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
5093 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
5094 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
5095 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
5096 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
5097 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
5098 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
5099 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
5100 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
5101 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
5102 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
5103 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
5104 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
5105 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
5106 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
5107 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
5108 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
5109 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,
5110 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
5111 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
5112 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
5113 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
5114 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
5115 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
5116 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
5117 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
5118 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
5119 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
5120 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
5121 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
5122 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
5123 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
5124 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,
5125 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
5126 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
5127 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,
5128 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
5129 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
5130 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,
5131 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
5132 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
5133 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
5134 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
5135 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
5136 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
5137 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
5138 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
5139 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259,
5140 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
5141 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
5142 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
5143 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
5144 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
5145 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673,
5146 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
5147 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
5148 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909,
5149 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967,
5150 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
5151 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
5152 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167,
5153 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
5154 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
5155 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
5156 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
5157 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507,
5158 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573,
5159 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
5160 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711,
5161 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
5162 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
5163 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897,
5164 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
5165 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
5166 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
5167 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
5168 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
5169 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329,
5170 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
5171 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
5172 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563,
5173 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
5174 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
5175 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
5176 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
5177 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
5178 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971,
5179 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027,
5180 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
5181 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
5182 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
5183 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
5184 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
5185 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
5186 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
5187 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
5188 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
5189 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
5190 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853,
5191 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
5192 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
5193 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
5194 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
5195 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231,
5196 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
5197 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369,
5198 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443,
5199 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537,
5200 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609,
5201 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
5202 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731,
5203 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803,
5204 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861,
5205 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941,
5206 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
5207 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091,
5208 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161,
5209 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
5210 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311,
5211 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
5212 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433,
5213 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491,
5214 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587,
5215 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649,
5216 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
5217 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791,
5218 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857,
5219 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929,
5220 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037,
5221 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
5222 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163,
5223 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247,
5224 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303,
5225 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369,
5226 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
5227 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531,
5228 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627,
5229 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691,
5230 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771,
5231 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
5232 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937,
5233 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003,
5234 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087,
5235 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161,
5236 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
5237 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317,
5238 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399,
5239 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483,
5240 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551,
5241 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
5242 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
5243 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813,
5244 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887,
5245 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941,
5246 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
5247 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101,
5248 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161,
5249 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251,
5250 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323,
5251 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
5252 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473,
5253 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
5254 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589,
5255 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653,
5256 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
5257 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821,
5258 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907,
5259 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967,
5260 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033,
5261 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
5262 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177,
5263 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259,
5264 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
5265 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421,
5266 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
5267 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597,
5268 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681,
5269 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723,
5270 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799,
5271 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
5272 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933,
5273 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033,
5274 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143,
5275 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
5276 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
5277 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407,
5278 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461,
5279 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549,
5280 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627,
5281 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
5282 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753,
5283 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821,
5284 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887,
5285 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957,
5286 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
5287 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137,
5288 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217,
5289 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277,
5290 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331,
5291 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
5292 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473,
5293 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569,
5294 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643,
5295 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727,
5296 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
5297 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
5298 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919,
5299 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007,
5300 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087,
5301 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
5302 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249,
5303 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349,
5304 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427,
5305 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493,
5306 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
5307 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661,
5308 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
5309 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843,
5310 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927,
5311 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
5312 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053,
5313 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159,
5314 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231,
5315 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327,
5316 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
5317 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467,
5318 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519,
5319 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
5320 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683,
5321 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
5322 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863
5323 #endif /* !EIGHT_BIT */
5326 static int witness(BIGNUM
*w
, const BIGNUM
*a
, const BIGNUM
*a1
,
5327 const BIGNUM
*a1_odd
, int k
, BN_CTX
*ctx
, BN_MONT_CTX
*mont
);
5328 static int probable_prime(BIGNUM
*rnd
, int bits
);
5329 static int probable_prime_dh(BIGNUM
*rnd
, int bits
,
5330 const BIGNUM
*add
, const BIGNUM
*rem
, BN_CTX
*ctx
);
5331 static int probable_prime_dh_safe(BIGNUM
*rnd
, int bits
,
5332 const BIGNUM
*add
, const BIGNUM
*rem
, BN_CTX
*ctx
);
5335 BN_generate_prime(BIGNUM
*ret
, int bits
, int safe
, const BIGNUM
*add
, const BIGNUM
*rem
,
5336 void (*callback
)(int, int, void *), void *cb_arg
)
5343 int checks
= BN_prime_checks_for_size(bits
);
5347 if (ctx
== NULL
) goto err
;
5349 if ((rnd
= BN_new()) == NULL
) goto err
;
5353 /* make a random number and set the top and bottom bits */
5355 if (!probable_prime(rnd
, bits
)) goto err
;
5358 if (!probable_prime_dh_safe(rnd
, bits
, add
, rem
, ctx
))
5361 if (!probable_prime_dh(rnd
, bits
, add
, rem
, ctx
))
5365 /* if (BN_mod_word(rnd, (BN_ULONG)3) == 1) goto loop; */
5366 if (callback
!= NULL
)
5367 callback(0, c1
++, cb_arg
);
5370 i
= BN_is_prime_fasttest(rnd
, checks
, callback
, ctx
, cb_arg
, 0);
5371 if (i
== -1) goto err
;
5372 if (i
== 0) goto loop
;
5374 /* for "safe prime" generation,
5375 * check that (p-1)/2 is prime.
5376 * Since a prime is odd, We just
5377 * need to divide by 2
5379 if (!BN_rshift1(&t
, rnd
)) goto err
;
5381 for (i
= 0; i
< checks
; i
++) {
5382 j
= BN_is_prime_fasttest(rnd
, 1, callback
, ctx
, cb_arg
, 0);
5383 if (j
== -1) goto err
;
5384 if (j
== 0) goto loop
;
5386 j
= BN_is_prime_fasttest(&t
, 1, callback
, ctx
, cb_arg
, 0);
5387 if (j
== -1) goto err
;
5388 if (j
== 0) goto loop
;
5390 if (callback
!= NULL
) callback(2, c1
-1, cb_arg
);
5391 /* We have a safe prime test pass */
5394 /* we have a prime :-) */
5397 if (!found
&& (ret
== NULL
) && (rnd
!= NULL
)) BN_free(rnd
);
5399 if (ctx
!= NULL
) BN_CTX_free(ctx
);
5400 return (found
? rnd
: NULL
);
5404 BN_is_prime(const BIGNUM
*a
, int checks
, void (*callback
)(int, int, void *),
5405 BN_CTX
*ctx_passed
, void *cb_arg
)
5407 return BN_is_prime_fasttest(a
, checks
, callback
, ctx_passed
, cb_arg
, 0);
5411 BN_is_prime_fasttest(const BIGNUM
*a
, int checks
, void (*callback
)(int, int, void *),
5412 BN_CTX
*ctx_passed
, void *cb_arg
, int do_trial_division
)
5417 BIGNUM
*A1
, *A1_odd
, *check
; /* taken from ctx */
5418 BN_MONT_CTX
*mont
= NULL
;
5419 const BIGNUM
*A
= NULL
;
5421 if (BN_cmp(a
, BN_value_one()) <= 0)
5424 if (checks
== BN_prime_checks
)
5425 checks
= BN_prime_checks_for_size(BN_num_bits(a
));
5427 /* first look for small factors */
5430 if (do_trial_division
) {
5431 for (i
= 1; i
< NUMPRIMES
; i
++)
5432 if (BN_mod_word(a
, primes
[i
]) == 0)
5434 if (callback
!= NULL
)
5435 callback(1, -1, cb_arg
);
5438 if (ctx_passed
!= NULL
)
5441 if ((ctx
= BN_CTX_new()) == NULL
)
5448 if ((t
= BN_CTX_get(ctx
)) == NULL
) goto err
;
5454 A1
= BN_CTX_get(ctx
);
5455 A1_odd
= BN_CTX_get(ctx
);
5456 check
= BN_CTX_get(ctx
);
5457 if (check
== NULL
) goto err
;
5459 /* compute A1 : = A - 1 */
5460 if (!BN_copy(A1
, A
))
5462 if (!BN_sub_word(A1
, 1))
5464 if (BN_is_zero(A1
)) {
5469 /* write A1 as A1_odd * 2^k */
5471 while (!BN_is_bit_set(A1
, k
))
5473 if (!BN_rshift(A1_odd
, A1
, k
))
5476 /* Montgomery setup for computations mod A */
5477 mont
= BN_MONT_CTX_new();
5480 if (!BN_MONT_CTX_set(mont
, A
, ctx
))
5483 for (i
= 0; i
< checks
; i
++) {
5484 if (!BN_pseudo_rand_range(check
, A1
))
5486 if (!BN_add_word(check
, 1))
5488 /* now 1 <= check < A */
5490 j
= witness(check
, A
, A1
, A1_odd
, k
, ctx
, mont
);
5491 if (j
== -1) goto err
;
5496 if (callback
!= NULL
)
5497 callback(1, i
, cb_arg
);
5503 if (ctx_passed
== NULL
)
5507 BN_MONT_CTX_free(mont
);
5513 witness(BIGNUM
*w
, const BIGNUM
*a
, const BIGNUM
*a1
,
5514 const BIGNUM
*a1_odd
, int k
, BN_CTX
*ctx
, BN_MONT_CTX
*mont
)
5516 if (!BN_mod_exp_mont(w
, w
, a1_odd
, a
, ctx
, mont
)) /* w : = w^a1_odd mod a */
5519 return 0; /* probably prime */
5520 if (BN_cmp(w
, a1
) == 0)
5521 return 0; /* w == -1 (mod a), 'a' is probably prime */
5523 if (!BN_mod_mul(w
, w
, w
, a
, ctx
)) /* w : = w^2 mod a */
5526 return 1; /* 'a' is composite, otherwise a previous 'w' would
5527 * have been == -1 (mod 'a')
5529 if (BN_cmp(w
, a1
) == 0)
5530 return 0; /* w == -1 (mod a), 'a' is probably prime */
5532 /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
5533 * and it is neither -1 nor +1 -- so 'a' cannot be prime
5539 probable_prime(BIGNUM
*rnd
, int bits
)
5542 BN_ULONG mods
[NUMPRIMES
];
5546 if (!BN_rand(rnd
, bits
, 1, 1)) return (0);
5547 /* we now have a random number 'rand' to test. */
5548 for (i
= 1; i
< NUMPRIMES
; i
++)
5549 mods
[i
] = BN_mod_word(rnd
, (BN_ULONG
)primes
[i
]);
5552 for (i
= 1; i
< NUMPRIMES
; i
++) {
5553 /* check that rnd is not a prime and also
5554 * that gcd(rnd-1, primes) == 1 (except for 2)
5556 if (((mods
[i
]+delta
)%primes
[i
]) <= 1) {
5559 /* perhaps need to check for overflow of
5560 * delta (but delta can be up to 2^32)
5561 * 21-May-98 eay - added overflow check
5563 if (delta
< d
) goto again
;
5567 if (!BN_add_word(rnd
, delta
)) return (0);
5572 probable_prime_dh(BIGNUM
*rnd
, int bits
, const BIGNUM
*add
, const BIGNUM
*rem
, BN_CTX
*ctx
)
5578 if ((t1
= BN_CTX_get(ctx
)) == NULL
) goto err
;
5580 if (!BN_rand(rnd
, bits
, 0, 1))
5583 /* we need ((rnd-rem) % add) == 0 */
5585 if (!BN_mod(t1
, rnd
, add
, ctx
))
5587 if (!BN_sub(rnd
, rnd
, t1
))
5590 if (!BN_add_word(rnd
, 1))
5593 if (!BN_add(rnd
, rnd
, rem
))
5597 /* we now have a random number 'rand' to test. */
5599 loop
: for (i
= 1; i
< NUMPRIMES
; i
++) {
5600 /* check that rnd is a prime */
5601 if (BN_mod_word(rnd
, (BN_ULONG
)primes
[i
]) <= 1) {
5602 if (!BN_add(rnd
, rnd
, add
)) goto err
;
5613 probable_prime_dh_safe(BIGNUM
*p
, int bits
, const BIGNUM
*padd
, const BIGNUM
*rem
, BN_CTX
*ctx
)
5616 BIGNUM
*t1
, *qadd
, *q
;
5620 t1
= BN_CTX_get(ctx
);
5621 q
= BN_CTX_get(ctx
);
5622 qadd
= BN_CTX_get(ctx
);
5623 if (qadd
== NULL
) goto err
;
5625 if (!BN_rshift1(qadd
, padd
)) goto err
;
5627 if (!BN_rand(q
, bits
, 0, 1)) goto err
;
5629 /* we need ((rnd-rem) % add) == 0 */
5630 if (!BN_mod(t1
, q
, qadd
, ctx
)) goto err
;
5631 if (!BN_sub(q
, q
, t1
)) goto err
;
5633 if (!BN_add_word(q
, 1)) goto err
;
5635 if (!BN_rshift1(t1
, rem
)) goto err
;
5636 if (!BN_add(q
, q
, t1
)) goto err
;
5639 /* we now have a random number 'rand' to test. */
5640 if (!BN_lshift1(p
, q
)) goto err
;
5641 if (!BN_add_word(p
, 1)) goto err
;
5644 for (i
= 1; i
< NUMPRIMES
; i
++) {
5645 /* check that p and q are prime */
5646 /* check that for p and q
5647 * gcd(p-1, primes) == 1 (except for 2)
5649 if ((BN_mod_word(p
, (BN_ULONG
)primes
[i
]) == 0) ||
5650 (BN_mod_word(q
, (BN_ULONG
)primes
[i
]) == 0)) {
5651 if (!BN_add(p
, p
, padd
)) goto err
;
5652 if (!BN_add(q
, q
, qadd
)) goto err
;
5661 #endif /* BCMDH_TEST */