?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
GUI: Fix Tomato RAF theme for all builds. Compilation typo.
[tomato.git] / release / src-rt-6.x.4708 / bcmcrypto / bn.c
blob7632c23a08d4fde68f049d4fb906979d48f34964
1 /*
2 * bn.c: Big Number routines. Needed by Diffie Hellman implementation.
3 *
4 * Code copied from openssl distribution and
5 * Modified just enough so that compiles and runs standalone
6 *
7 * Copyright (C) 2012, Broadcom Corporation. All Rights Reserved.
8 *
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.
12 *
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.
20 *
21 * $Id: bn.c 241182 2011-02-17 21:50:03Z $
22 */
23 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
24 * All rights reserved.
25 *
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.
29 *
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).
36 *
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.
43 *
44 * Redistribution and use in source and binary forms, with or without
45 * modification, are permitted provided that the following conditions
46 * are met:
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)"
61 *
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
72 * SUCH DAMAGE.
73 *
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.]
78 */
79 /*
80 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved.
81 *
82 * Redistribution and use in source and binary forms, with or without
83 * modification, are permitted provided that the following conditions
84 * are met:
85 *
86 * 1. Redistributions of source code must retain the above copyright
87 * notice, this list of conditions and the following disclaimer.
88 *
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
92 * distribution.
93 *
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/)"
98 *
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.
103 *
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.
107 *
108 * 6. Redistributions of any form whatsoever must retain the following
109 * acknowledgment:
110 * "This product includes software developed by the OpenSSL Project
111 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
112 *
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.
125 *
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).
129 *
130 */
131 /* Includes code written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
132 * for the OpenSSL project.
133 */
134
135 #include <typedefs.h>
136 #include <stdio.h>
137 #include <stdlib.h>
138 #include <string.h>
139 #include <assert.h>
140 #include <bcmcrypto/bn.h>
141 #include "bn_lcl.h"
142
143 #define OPENSSL_malloc malloc
144 #define OPENSSL_free free
145 #define OPENSSL_cleanse(buf, size) memset(buf, 0, size)
146 #define BNerr(a, b)
147
148 static bn_rand_fn_t bn_rand_fn = NULL;
149
150 void
151 BN_register_RAND(bn_rand_fn_t fn)
152 {
153 bn_rand_fn = fn;
154 }
155
156 /* r can == a or b */
157 int
158 BN_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
159 {
160 const BIGNUM *tmp;
161 int a_neg = a->neg;
162
163 bn_check_top(a);
164 bn_check_top(b);
165
166 /* a + b a+b
167 * a + -b a-b
168 * -a + b b-a
169 * -a + -b -(a+b)
170 */
171 if (a_neg ^ b->neg) {
172 /* only one is negative */
173 if (a_neg) {
174 tmp = a; a = b; b = tmp;
175 }
176
177 /* we are now a - b */
178
179 if (BN_ucmp(a, b) < 0) {
180 if (!BN_usub(r, b, a)) return (0);
181 r->neg = 1;
182 } else {
183 if (!BN_usub(r, a, b)) return (0);
184 r->neg = 0;
185 }
186 return (1);
187 }
188
189 if (!BN_uadd(r, a, b)) return (0);
190 if (a_neg) /* both are neg */
191 r->neg = 1;
192 else
193 r->neg = 0;
194 return (1);
195 }
196
197 /* unsigned add of b to a, r must be large enough */
198 int
199 BN_uadd(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
200 {
201 register int i;
202 int max, min;
203 BN_ULONG *ap, *bp, *rp, carry, t1;
204 const BIGNUM *tmp;
205
206 bn_check_top(a);
207 bn_check_top(b);
208
209 if (a->top < b->top) {
210 tmp = a; a = b; b = tmp;
211 }
212 max = a->top;
213 min = b->top;
214
215 if (bn_wexpand(r, max+1) == NULL)
216 return (0);
217
218 r->top = max;
219
220
221 ap = a->d;
222 bp = b->d;
223 rp = r->d;
224 carry = 0;
225
226 carry = bn_add_words(rp, ap, bp, min);
227 rp += min;
228 ap += min;
229 bp += min;
230 i = min;
231
232 if (carry) {
233 while (i < max) {
234 i++;
235 t1 = *(ap++);
236 if ((*(rp++) = (t1+1)&BN_MASK2) >= t1) {
237 carry = 0;
238 break;
239 }
240 }
241 if ((i >= max) && carry) {
242 *(rp++) = 1;
243 r->top++;
244 }
245 }
246 if (rp != ap) {
247 for (; i < max; i++)
248 *(rp++) = *(ap++);
249 }
250 /* memcpy(rp, ap, sizeof(*ap)*(max-i)); */
251 r->neg = 0;
252 return (1);
253 }
254
255 /* unsigned subtraction of b from a, a must be larger than b. */
256 int
257 BN_usub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
258 {
259 int max, min;
260 register BN_ULONG t1, t2, *ap, *bp, *rp;
261 int i, carry;
262 #if defined(IRIX_CC_BUG) && !defined(LINT)
263 int dummy;
264 #endif
265
266 bn_check_top(a);
267 bn_check_top(b);
268
269 if (a->top < b->top) /* hmm... should not be happening */ {
270 BNerr(BN_F_BN_USUB, BN_R_ARG2_LT_ARG3);
271 return (0);
272 }
273
274 max = a->top;
275 min = b->top;
276 if (bn_wexpand(r, max) == NULL) return (0);
277
278 ap = a->d;
279 bp = b->d;
280 rp = r->d;
281
282 carry = 0;
283 for (i = 0; i < min; i++) {
284 t1 = *(ap++);
285 t2 = *(bp++);
286 if (carry) {
287 carry = (t1 <= t2);
288 t1 = (t1-t2-1)&BN_MASK2;
289 }
290 else {
291 carry = (t1 < t2);
292 t1 = (t1-t2)&BN_MASK2;
293 }
294 #if defined(IRIX_CC_BUG) && !defined(LINT)
295 dummy = t1;
296 #endif
297 *(rp++) = t1&BN_MASK2;
298 }
299 if (carry) /* subtracted */ {
300 while (i < max) {
301 i++;
302 t1 = *(ap++);
303 t2 = (t1-1)&BN_MASK2;
304 *(rp++) = t2;
305 if (t1 > t2) break;
306 }
307 }
308 if (rp != ap) {
309 for (;;) {
310 if (i++ >= max) break;
311 rp[0] = ap[0];
312 if (i++ >= max) break;
313 rp[1] = ap[1];
314 if (i++ >= max) break;
315 rp[2] = ap[2];
316 if (i++ >= max) break;
317 rp[3] = ap[3];
318 rp += 4;
319 ap += 4;
320 }
321 }
322
323 r->top = max;
324 r->neg = 0;
325 bn_fix_top(r);
326 return (1);
327 }
328
329 int
330 BN_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b)
331 {
332 int max;
333 int add = 0, neg = 0;
334 const BIGNUM *tmp;
335
336 bn_check_top(a);
337 bn_check_top(b);
338
339 /* a - b a-b
340 * a - -b a+b
341 * -a - b -(a+b)
342 * -a - -b b-a
343 */
344 if (a->neg) {
345 if (b->neg) { tmp = a; a = b; b = tmp; }
346 else { add = 1; neg = 1; }
347 }
348 else {
349 if (b->neg) { add = 1; neg = 0; }
350 }
351
352 if (add) {
353 if (!BN_uadd(r, a, b)) return (0);
354 r->neg = neg;
355 return (1);
356 }
357
358 /* We are actually doing a - b :-) */
359
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);
364 r->neg = 1;
365 }
366 else {
367 if (!BN_usub(r, a, b)) return (0);
368 r->neg = 0;
369 }
370 return (1);
371 }
372
373
374 #if defined(BN_LLONG) || defined(BN_UMULT_HIGH)
375
376 BN_ULONG
377 bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
378 {
379 BN_ULONG c1 = 0;
380
381 assert(num >= 0);
382 if (num <= 0) return (c1);
383
384 while (num&~3) {
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;
390 }
391 if (num) {
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;
395 }
396
397 return (c1);
398 }
399
400 BN_ULONG
401 bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
402 {
403 BN_ULONG c1 = 0;
404
405 assert(num >= 0);
406 if (num <= 0) return (c1);
407
408 while (num&~3) {
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;
414 }
415 if (num) {
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);
419 }
420 return (c1);
421 }
422
423 void
424 bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
425 {
426 assert(n >= 0);
427 if (n <= 0) return;
428 while (n & ~3) {
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;
434 }
435 if (n) {
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]);
439 }
440 }
441
442 #else /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
443
444 BN_ULONG
445 bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
446 {
447 BN_ULONG c = 0;
448 BN_ULONG bl, bh;
449
450 assert(num >= 0);
451 if (num <= 0) return ((BN_ULONG)0);
452
453 bl = LBITS(w);
454 bh = HBITS(w);
455
456 for (;;) {
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;
465 ap += 4;
466 rp += 4;
467 }
468 return (c);
469 }
470
471 BN_ULONG
472 bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w)
473 {
474 BN_ULONG carry = 0;
475 BN_ULONG bl, bh;
476
477 assert(num >= 0);
478 if (num <= 0) return ((BN_ULONG)0);
479
480 bl = LBITS(w);
481 bh = HBITS(w);
482
483 for (;;) {
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;
492 ap += 4;
493 rp += 4;
494 }
495 return (carry);
496 }
497
498 void
499 bn_sqr_words(BN_ULONG *r, const BN_ULONG *a, int n)
500 {
501 assert(n >= 0);
502 if (n <= 0) return;
503 for (;;) {
504 sqr64(r[0], r[1], a[0]);
505 if (--n == 0) break;
506
507 sqr64(r[2], r[3], a[1]);
508 if (--n == 0) break;
509
510 sqr64(r[4], r[5], a[2]);
511 if (--n == 0) break;
512
513 sqr64(r[6], r[7], a[3]);
514 if (--n == 0) break;
515
516 a += 4;
517 r += 8;
518 }
519 }
520
521 #endif /* !(defined(BN_LLONG) || defined(BN_UMULT_HIGH)) */
522
523 #if defined(BN_LLONG) && defined(BN_DIV2W)
524
525 BN_ULONG
526 bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d)
527 {
528 return ((BN_ULONG)(((((BN_ULLONG)h) << BN_BITS2)|l) / (BN_ULLONG)d));
529 }
530
531 #else
532
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)
536 {
537 BN_ULONG dh, dl, q, ret = 0, th, tl, t;
538 int i, count = 2;
539
540 if (d == 0) return (BN_MASK2);
541
542 i = BN_num_bits_word(d);
543 assert((i == BN_BITS2) || (h > (BN_ULONG)1 << i));
544
545 i = BN_BITS2-i;
546 if (h >= d) h -= d;
547
548 if (i) {
549 d <<= i;
550 h = (h << i) | (l >> (BN_BITS2 - i));
551 l <<= i;
552 }
553 dh = (d&BN_MASK2h) >> BN_BITS4;
554 dl = (d&BN_MASK2l);
555 for (;;) {
556 if ((h>>BN_BITS4) == dh)
557 q = BN_MASK2l;
558 else
559 q = h/dh;
560
561 th = q*dh;
562 tl = dl*q;
563 for (;;) {
564 t = h-th;
565 if ((t&BN_MASK2h) ||
566 ((tl) <= ((t << BN_BITS4) |
567 ((l & BN_MASK2h) >> BN_BITS4))))
568 break;
569 q--;
570 th -= dh;
571 tl -= dl;
572 }
573 t = (tl >> BN_BITS4);
574 tl = (tl << BN_BITS4) & BN_MASK2h;
575 th += t;
576
577 if (l < tl) th++;
578 l -= tl;
579 if (h < th) {
580 h += d;
581 q--;
582 }
583 h -= th;
584
585 if (--count == 0) break;
586
587 ret = q << BN_BITS4;
588 h = ((h << BN_BITS4) | (l >> BN_BITS4)) & BN_MASK2;
589 l = (l & BN_MASK2l) << BN_BITS4;
590 }
591 ret |= q;
592 return (ret);
593 }
594 #endif /* !defined(BN_LLONG) && defined(BN_DIV2W) */
595
596 #ifdef BN_LLONG
597 BN_ULONG
598 bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
599 {
600 BN_ULLONG ll = 0;
601
602 assert(n >= 0);
603 if (n <= 0) return ((BN_ULONG)0);
604
605 for (;;) {
606 ll += (BN_ULLONG)a[0]+b[0];
607 r[0] = (BN_ULONG)ll&BN_MASK2;
608 ll >>= BN_BITS2;
609 if (--n <= 0) break;
610
611 ll += (BN_ULLONG)a[1]+b[1];
612 r[1] = (BN_ULONG)ll&BN_MASK2;
613 ll >>= BN_BITS2;
614 if (--n <= 0) break;
615
616 ll += (BN_ULLONG)a[2]+b[2];
617 r[2] = (BN_ULONG)ll&BN_MASK2;
618 ll >>= BN_BITS2;
619 if (--n <= 0) break;
620
621 ll += (BN_ULLONG)a[3]+b[3];
622 r[3] = (BN_ULONG)ll&BN_MASK2;
623 ll >>= BN_BITS2;
624 if (--n <= 0) break;
625
626 a += 4;
627 b += 4;
628 r += 4;
629 }
630 return ((BN_ULONG)ll);
631 }
632
633 #else /* !BN_LLONG */
634
635 BN_ULONG
636 bn_add_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
637 {
638 BN_ULONG c, l, t;
639
640 assert(n >= 0);
641 if (n <= 0) return ((BN_ULONG)0);
642
643 c = 0;
644 for (;;) {
645 t = a[0];
646 t = (t+c)&BN_MASK2;
647 c = (t < c);
648 l = (t+b[0])&BN_MASK2;
649 c += (l < t);
650 r[0] = l;
651 if (--n <= 0) break;
652
653 t = a[1];
654 t = (t+c)&BN_MASK2;
655 c = (t < c);
656 l = (t+b[1])&BN_MASK2;
657 c += (l < t);
658 r[1] = l;
659 if (--n <= 0) break;
660
661 t = a[2];
662 t = (t+c)&BN_MASK2;
663 c = (t < c);
664 l = (t+b[2])&BN_MASK2;
665 c += (l < t);
666 r[2] = l;
667 if (--n <= 0) break;
668
669 t = a[3];
670 t = (t+c)&BN_MASK2;
671 c = (t < c);
672 l = (t+b[3])&BN_MASK2;
673 c += (l < t);
674 r[3] = l;
675 if (--n <= 0) break;
676
677 a += 4;
678 b += 4;
679 r += 4;
680 }
681 return ((BN_ULONG)c);
682 }
683 #endif /* !BN_LLONG */
684
685 BN_ULONG
686 bn_sub_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, int n)
687 {
688 BN_ULONG t1, t2;
689 int c = 0;
690
691 assert(n >= 0);
692 if (n <= 0) return ((BN_ULONG)0);
693
694 for (;;) {
695 t1 = a[0]; t2 = b[0];
696 r[0] = (t1-t2-c)&BN_MASK2;
697 if (t1 != t2) c = (t1 < t2);
698 if (--n <= 0) break;
699
700 t1 = a[1]; t2 = b[1];
701 r[1] = (t1-t2-c)&BN_MASK2;
702 if (t1 != t2) c = (t1 < t2);
703 if (--n <= 0) break;
704
705 t1 = a[2]; t2 = b[2];
706 r[2] = (t1-t2-c)&BN_MASK2;
707 if (t1 != t2) c = (t1 < t2);
708 if (--n <= 0) break;
709
710 t1 = a[3]; t2 = b[3];
711 r[3] = (t1-t2-c)&BN_MASK2;
712 if (t1 != t2) c = (t1 < t2);
713 if (--n <= 0) break;
714
715 a += 4;
716 b += 4;
717 r += 4;
718 }
719 return (c);
720 }
721
722 #ifdef BN_MUL_COMBA
723
724 #undef bn_mul_comba8
725 #undef bn_mul_comba4
726 #undef bn_sqr_comba8
727 #undef bn_sqr_comba4
728
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) */
733
734 #ifdef BN_LLONG
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++;
741
742 #define mul_add_c2(a, b, c0, c1, c2) \
743 t = (BN_ULLONG)a * b; \
744 tt = (t + t) & BN_MASK; \
745 if (tt < t) c2++; \
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++;
751
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++;
758
759 #define sqr_add_c2(a, i, j, c0, c1, c2) \
760 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
761
762 #elif defined(BN_UMULT_HIGH)
763
764 #define mul_add_c(a, b, c0, c1, c2) { \
765 BN_ULONG ta = (a), tb = (b); \
766 t1 = ta * tb; \
767 t2 = BN_UMULT_HIGH(ta, tb); \
768 c0 += t1; t2 += (c0 < t1) ? 1 : 0; \
769 c1 += t2; c2 += (c1 < t2) ? 1 : 0; \
770 }
771
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); \
775 t0 = 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; \
780 }
781
782 #define sqr_add_c(a, i, c0, c1, c2) { \
783 BN_ULONG ta = (a)[i]; \
784 t1 = ta * ta; \
785 t2 = BN_UMULT_HIGH(ta, ta); \
786 c0 += t1; t2 += (c0 < t1) ? 1 : 0; \
787 c1 += t2; c2 += (c1 < t2) ? 1 : 0; \
788 }
789
790 #define sqr_add_c2(a, i, j, c0, c1, c2) \
791 mul_add_c2((a)[i], (a)[j], c0, c1, c2)
792
793 #else /* !BN_LLONG */
794
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++;
801
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++;
813
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++;
818
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 */
822
823 void
824 bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
825 {
826 #ifdef BN_LLONG
827 BN_ULLONG t;
828 #else
829 BN_ULONG bl, bh;
830 #endif
831 BN_ULONG t1, t2;
832 BN_ULONG c1, c2, c3;
833
834 c1 = 0;
835 c2 = 0;
836 c3 = 0;
837 mul_add_c(a[0], b[0], c1, c2, c3);
838 r[0] = c1;
839 c1 = 0;
840 mul_add_c(a[0], b[1], c2, c3, c1);
841 mul_add_c(a[1], b[0], c2, c3, c1);
842 r[1] = c2;
843 c2 = 0;
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);
847 r[2] = c3;
848 c3 = 0;
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);
853 r[3] = c1;
854 c1 = 0;
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);
860 r[4] = c2;
861 c2 = 0;
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);
868 r[5] = c3;
869 c3 = 0;
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);
877 r[6] = c1;
878 c1 = 0;
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);
887 r[7] = c2;
888 c2 = 0;
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);
896 r[8] = c3;
897 c3 = 0;
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);
904 r[9] = c1;
905 c1 = 0;
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);
911 r[10] = c2;
912 c2 = 0;
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);
917 r[11] = c3;
918 c3 = 0;
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);
922 r[12] = c1;
923 c1 = 0;
924 mul_add_c(a[6], b[7], c2, c3, c1);
925 mul_add_c(a[7], b[6], c2, c3, c1);
926 r[13] = c2;
927 c2 = 0;
928 mul_add_c(a[7], b[7], c3, c1, c2);
929 r[14] = c3;
930 r[15] = c1;
931 }
932
933 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
934 {
935 #ifdef BN_LLONG
936 BN_ULLONG t;
937 #else
938 BN_ULONG bl, bh;
939 #endif
940 BN_ULONG t1, t2;
941 BN_ULONG c1, c2, c3;
942
943 c1 = 0;
944 c2 = 0;
945 c3 = 0;
946 mul_add_c(a[0], b[0], c1, c2, c3);
947 r[0] = c1;
948 c1 = 0;
949 mul_add_c(a[0], b[1], c2, c3, c1);
950 mul_add_c(a[1], b[0], c2, c3, c1);
951 r[1] = c2;
952 c2 = 0;
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);
956 r[2] = c3;
957 c3 = 0;
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);
962 r[3] = c1;
963 c1 = 0;
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);
967 r[4] = c2;
968 c2 = 0;
969 mul_add_c(a[2], b[3], c3, c1, c2);
970 mul_add_c(a[3], b[2], c3, c1, c2);
971 r[5] = c3;
972 c3 = 0;
973 mul_add_c(a[3], b[3], c1, c2, c3);
974 r[6] = c1;
975 r[7] = c2;
976 }
977
978 void
979 bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a)
980 {
981 #ifdef BN_LLONG
982 BN_ULLONG t, tt;
983 #else
984 BN_ULONG bl, bh;
985 #endif
986 BN_ULONG t1, t2;
987 BN_ULONG c1, c2, c3;
988
989 c1 = 0;
990 c2 = 0;
991 c3 = 0;
992 sqr_add_c(a, 0, c1, c2, c3);
993 r[0] = c1;
994 c1 = 0;
995 sqr_add_c2(a, 1, 0, c2, c3, c1);
996 r[1] = c2;
997 c2 = 0;
998 sqr_add_c(a, 1, c3, c1, c2);
999 sqr_add_c2(a, 2, 0, c3, c1, c2);
1000 r[2] = c3;
1001 c3 = 0;
1002 sqr_add_c2(a, 3, 0, c1, c2, c3);
1003 sqr_add_c2(a, 2, 1, c1, c2, c3);
1004 r[3] = c1;
1005 c1 = 0;
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);
1009 r[4] = c2;
1010 c2 = 0;
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);
1014 r[5] = c3;
1015 c3 = 0;
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);
1020 r[6] = c1;
1021 c1 = 0;
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);
1026 r[7] = c2;
1027 c2 = 0;
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);
1032 r[8] = c3;
1033 c3 = 0;
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);
1037 r[9] = c1;
1038 c1 = 0;
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);
1042 r[10] = c2;
1043 c2 = 0;
1044 sqr_add_c2(a, 7, 4, c3, c1, c2);
1045 sqr_add_c2(a, 6, 5, c3, c1, c2);
1046 r[11] = c3;
1047 c3 = 0;
1048 sqr_add_c(a, 6, c1, c2, c3);
1049 sqr_add_c2(a, 7, 5, c1, c2, c3);
1050 r[12] = c1;
1051 c1 = 0;
1052 sqr_add_c2(a, 7, 6, c2, c3, c1);
1053 r[13] = c2;
1054 c2 = 0;
1055 sqr_add_c(a, 7, c3, c1, c2);
1056 r[14] = c3;
1057 r[15] = c1;
1058 }
1059
1060 void
1061 bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a)
1062 {
1063 #ifdef BN_LLONG
1064 BN_ULLONG t, tt;
1065 #else
1066 BN_ULONG bl, bh;
1067 #endif
1068 BN_ULONG t1, t2;
1069 BN_ULONG c1, c2, c3;
1070
1071 c1 = 0;
1072 c2 = 0;
1073 c3 = 0;
1074 sqr_add_c(a, 0, c1, c2, c3);
1075 r[0] = c1;
1076 c1 = 0;
1077 sqr_add_c2(a, 1, 0, c2, c3, c1);
1078 r[1] = c2;
1079 c2 = 0;
1080 sqr_add_c(a, 1, c3, c1, c2);
1081 sqr_add_c2(a, 2, 0, c3, c1, c2);
1082 r[2] = c3;
1083 c3 = 0;
1084 sqr_add_c2(a, 3, 0, c1, c2, c3);
1085 sqr_add_c2(a, 2, 1, c1, c2, c3);
1086 r[3] = c1;
1087 c1 = 0;
1088 sqr_add_c(a, 2, c2, c3, c1);
1089 sqr_add_c2(a, 3, 1, c2, c3, c1);
1090 r[4] = c2;
1091 c2 = 0;
1092 sqr_add_c2(a, 3, 2, c3, c1, c2);
1093 r[5] = c3;
1094 c3 = 0;
1095 sqr_add_c(a, 3, c1, c2, c3);
1096 r[6] = c1;
1097 r[7] = c2;
1098 }
1099 #else /* !BN_MUL_COMBA */
1100
1101 /* hmm... is it faster just to do a multiply? */
1102 #undef bn_sqr_comba4
1103 void
1104 bn_sqr_comba4(BN_ULONG *r, BN_ULONG *a)
1105 {
1106 BN_ULONG t[8];
1107 bn_sqr_normal(r, a, 4, t);
1108 }
1109
1110 #undef bn_sqr_comba8
1111 void
1112 bn_sqr_comba8(BN_ULONG *r, BN_ULONG *a)
1113 {
1114 BN_ULONG t[16];
1115 bn_sqr_normal(r, a, 8, t);
1116 }
1117
1118 void
1119 bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
1120 {
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]);
1125 }
1126
1127 void
1128 bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b)
1129 {
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]);
1138 }
1139
1140 #endif /* !BN_MUL_COMBA */
1141
1142
1143 BN_CTX *
1144 BN_CTX_new(void)
1145 {
1146 BN_CTX *ret;
1147
1148 ret = (BN_CTX *)OPENSSL_malloc(sizeof(BN_CTX));
1149 if (ret == NULL) {
1150 BNerr(BN_F_BN_CTX_NEW, ERR_R_MALLOC_FAILURE);
1151 return (NULL);
1152 }
1153
1154 BN_CTX_init(ret);
1155 ret->flags = BN_FLG_MALLOCED;
1156 return (ret);
1157 }
1158
1159 void
1160 BN_CTX_init(BN_CTX *ctx)
1161 {
1162 memset(ctx, 0, sizeof(*ctx));
1163 }
1164
1165 void
1166 BN_CTX_free(BN_CTX *ctx)
1167 {
1168 int i;
1169
1170 if (ctx == NULL) return;
1171 assert(ctx->depth == 0);
1172
1173 for (i = 0; i < BN_CTX_NUM; i++)
1174 BN_clear_free(&(ctx->bn[i]));
1175 if (ctx->flags & BN_FLG_MALLOCED)
1176 OPENSSL_free(ctx);
1177 }
1178
1179 void
1180 BN_CTX_start(BN_CTX *ctx)
1181 {
1182 if (ctx->depth < BN_CTX_NUM_POS)
1183 ctx->pos[ctx->depth] = ctx->tos;
1184 ctx->depth++;
1185 }
1186
1187
1188 BIGNUM *
1189 BN_CTX_get(BN_CTX *ctx)
1190 {
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.)
1195 */
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: */
1200 ctx->too_many = 1;
1201 }
1202 return NULL;
1203 }
1204 return (&(ctx->bn[ctx->tos++]));
1205 }
1206
1207 void
1208 BN_CTX_end(BN_CTX *ctx)
1209 {
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)
1216 */
1217 BN_CTX_start(ctx);
1218 }
1219 ctx->too_many = 0;
1220 ctx->depth--;
1221 if (ctx->depth < BN_CTX_NUM_POS)
1222 ctx->tos = ctx->pos[ctx->depth];
1223 }
1224
1225 /* The old slow way */
1226
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__)
1231 /*
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:-)
1238 *
1239 * <appro@fy.chalmers.se>
1240 */
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) \
1245 : "cc"); \
1246 q; \
1247 })
1248 #define REMAINDER_IS_ALREADY_CALCULATED
1249 #elif defined(__x86_64) && defined(SIXTY_FOUR_BIT_LONG)
1250 /*
1251 * Same story here, but it's 128-bit by 64-bit division. Wow!
1252 * <appro@fy.chalmers.se>
1253 */
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) \
1258 : "cc"); \
1259 q; \
1260 })
1261 #define REMAINDER_IS_ALREADY_CALCULATED
1262 #endif /* __<cpu> */
1263 #endif /* __GNUC__ */
1264 #endif /* OPENSSL_NO_ASM */
1265
1266
1267 /* BN_div computes dv : = num / divisor, rounding towards zero, and sets up
1268 * rm such that dv*divisor + rm = num holds.
1269 * Thus:
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.
1273 */
1274 int
1275 BN_div(BIGNUM *dv, BIGNUM *rm, const BIGNUM *num, const BIGNUM *divisor, BN_CTX *ctx)
1276 {
1277 int norm_shift, i, j, loop;
1278 BIGNUM *tmp, wnum, *snum, *sdiv, *res;
1279 BN_ULONG *resp, *wnump;
1280 BN_ULONG d0, d1;
1281 int num_n, div_n;
1282
1283 bn_check_top(num);
1284 bn_check_top(divisor);
1285
1286 if (BN_is_zero(divisor)) {
1287 BNerr(BN_F_BN_DIV, BN_R_DIV_BY_ZERO);
1288 return (0);
1289 }
1290
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);
1294 return (1);
1295 }
1296
1297 BN_CTX_start(ctx);
1298 tmp = BN_CTX_get(ctx);
1299 snum = BN_CTX_get(ctx);
1300 sdiv = BN_CTX_get(ctx);
1301 if (dv == NULL)
1302 res = BN_CTX_get(ctx);
1303 else res = dv;
1304 if (sdiv == NULL || res == NULL) goto err;
1305 tmp->neg = 0;
1306
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;
1310 sdiv->neg = 0;
1311 norm_shift += BN_BITS2;
1312 if (!(BN_lshift(snum, num, norm_shift))) goto err;
1313 snum->neg = 0;
1314 div_n = sdiv->top;
1315 num_n = snum->top;
1316 loop = num_n-div_n;
1317
1318 /* Lets setup a 'window' into snum
1319 * This is the part that corresponds to the current
1320 * 'area' being divided
1321 */
1322 BN_init(&wnum);
1323 wnum.d = &(snum->d[loop]);
1324 wnum.top = div_n;
1325 wnum.dmax = snum->dmax+1; /* a bit of a lie */
1326
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];
1331
1332 /* pointer to the 'top' of snum */
1333 wnump = &(snum->d[num_n-1]);
1334
1335 /* Setup to 'res' */
1336 res->neg = (num->neg^divisor->neg);
1337 if (!bn_wexpand(res, (loop+1))) goto err;
1338 res->top = loop;
1339 resp = &(res->d[loop-1]);
1340
1341 /* space for temp */
1342 if (!bn_wexpand(tmp, (div_n+1))) goto err;
1343
1344 if (BN_ucmp(&wnum, sdiv) >= 0) {
1345 if (!BN_usub(&wnum, &wnum, sdiv)) goto err;
1346 *resp = 1;
1347 res->d[res->top-1] = 1;
1348 } else
1349 res->top--;
1350 if (res->top == 0)
1351 res->neg = 0;
1352 resp--;
1353
1354 for (i = 0; i < loop - 1; i++) {
1355 BN_ULONG q, l0;
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);
1359 #else
1360 BN_ULONG n0, n1, rem = 0;
1361
1362 n0 = wnump[0];
1363 n1 = wnump[-1];
1364 if (n0 == d0)
1365 q = BN_MASK2;
1366 else /* n0 < d0 */ {
1367 #ifdef BN_LLONG
1368 BN_ULLONG t2;
1369
1370 #if defined(BN_LLONG) && defined(BN_DIV2W) && !defined(bn_div_words)
1371 q = (BN_ULONG)(((((BN_ULLONG)n0) << BN_BITS2) | n1) / d0);
1372 #else
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",
1376 n0, n1, d0, q);
1377 #endif /* BN_DEBUG_LEVITTE */
1378 #endif /* BN_LLONG && BN_DIV2W && !bn_div_words */
1379
1380 #ifndef REMAINDER_IS_ALREADY_CALCULATED
1381 /*
1382 * rem doesn't have to be BN_ULLONG. The least we
1383 * know it's less that d0, isn't it?
1384 */
1385 rem = (n1 - q * d0) & BN_MASK2;
1386 #endif /* !REMAINDER_IS_ALREADY_CALCULATED */
1387 t2 = (BN_ULLONG)d1 * q;
1388
1389 for (;;) {
1390 if (t2 <= ((((BN_ULLONG)rem) << BN_BITS2) | wnump[-2]))
1391 break;
1392 q--;
1393 rem += d0;
1394 if (rem < d0) break; /* don't let rem overflow */
1395 t2 -= d1;
1396 }
1397 #else /* !BN_LLONG */
1398 BN_ULONG t2l, t2h, ql, qh;
1399
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",
1403 n0, n1, d0, q);
1404 #endif
1405 #ifndef REMAINDER_IS_ALREADY_CALCULATED
1406 rem = (n1 - q * d0) & BN_MASK2;
1407 #endif
1408
1409 #if defined(BN_UMULT_LOHI)
1410 BN_UMULT_LOHI(t2l, t2h, d1, q);
1411 #elif defined(BN_UMULT_HIGH)
1412 t2l = d1 * q;
1413 t2h = BN_UMULT_HIGH(d1, q);
1414 #else
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; */
1418 #endif
1419
1420 for (;;) {
1421 if ((t2h < rem) || ((t2h == rem) && (t2l <= wnump[-2])))
1422 break;
1423 q--;
1424 rem += d0;
1425 if (rem < d0) break; /* don't let rem overflow */
1426 if (t2l < d1)
1427 t2h--;
1428 t2l -= d1;
1429 }
1430 #endif /* !BN_LLONG */
1431 }
1432 #endif /* !BN_DIV3W */
1433
1434 l0 = bn_mul_words(tmp->d, sdiv->d, div_n, q);
1435 wnum.d--; wnum.top++;
1436 tmp->d[div_n] = l0;
1437 for (j = div_n + 1; j > 0; j--)
1438 if (tmp->d[j - 1]) break;
1439 tmp->top = j;
1440
1441 j = wnum.top;
1442 if (!BN_sub(&wnum, &wnum, tmp)) goto err;
1443
1444 snum->top = snum->top + wnum.top - j;
1445
1446 if (wnum.neg) {
1447 q--;
1448 j = wnum.top;
1449 if (!BN_add(&wnum, &wnum, sdiv)) goto err;
1450 snum->top += wnum.top - j;
1451 }
1452 *(resp--) = q;
1453 wnump--;
1454 }
1455 if (rm != NULL) {
1456 /* Keep a copy of the neg flag in num because if rm == num
1457 * BN_rshift() will overwrite it.
1458 */
1459 int neg = num->neg;
1460 BN_rshift(rm, snum, norm_shift);
1461 if (!BN_is_zero(rm))
1462 rm->neg = neg;
1463 }
1464 BN_CTX_end(ctx);
1465 return (1);
1466 err:
1467 BN_CTX_end(ctx);
1468 return (0);
1469 }
1470
1471
1472 #define TABLE_SIZE 32
1473
1474 #ifdef NOT_NEEDED_FOR_DH
1475 /* this one works - simple but works */
1476 int
1477 BN_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
1478 {
1479 int i, bits, ret = 0;
1480 BIGNUM *v, *rr;
1481
1482 BN_CTX_start(ctx);
1483 if ((r == a) || (r == p))
1484 rr = BN_CTX_get(ctx);
1485 else
1486 rr = r;
1487 if ((v = BN_CTX_get(ctx)) == NULL) goto err;
1488
1489 if (BN_copy(v, a) == NULL) goto err;
1490 bits = BN_num_bits(p);
1491
1492 if (BN_is_odd(p)) {
1493 if (BN_copy(rr, a) == NULL)
1494 goto err;
1495 } else {
1496 if (!BN_one(rr))
1497 goto err;
1498 }
1499
1500 for (i = 1; i < bits; i++) {
1501 if (!BN_sqr(v, v, ctx)) goto err;
1502 if (BN_is_bit_set(p, i)) {
1503 if (!BN_mul(rr, rr, v, ctx)) goto err;
1504 }
1505 }
1506 ret = 1;
1507 err:
1508 if (r != rr) BN_copy(r, rr);
1509 BN_CTX_end(ctx);
1510 return (ret);
1511 }
1512
1513 int
1514 BN_mod_exp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx)
1515 {
1516 int ret;
1517
1518 bn_check_top(a);
1519 bn_check_top(p);
1520 bn_check_top(m);
1521
1522 /* For even modulus m = 2^k*m_odd, it might make sense to compute
1523 * a^p mod m_odd and a^p mod 2^k separately (with Montgomery
1524 * exponentiation for the odd part), using appropriate exponent
1525 * reductions, and combine the results using the CRT.
1526 *
1527 * For now, we use Montgomery only if the modulus is odd; otherwise,
1528 * exponentiation using the reciprocal-based quick remaindering
1529 * algorithm is used.
1530 *
1531 * (Timing obtained with expspeed.c [computations a^p mod m
1532 * where a, p, m are of the same length: 256, 512, 1024, 2048,
1533 * 4096, 8192 bits], compared to the running time of the
1534 * standard algorithm:
1535 *
1536 * BN_mod_exp_mont 33 .. 40 % [AMD K6-2, Linux, debug configuration]
1537 * 55 .. 77 % [UltraSparc processor, but
1538 * debug-solaris-sparcv8-gcc conf.]
1539 *
1540 * BN_mod_exp_recp 50 .. 70 % [AMD K6-2, Linux, debug configuration]
1541 * 62 .. 118 % [UltraSparc, debug-solaris-sparcv8-gcc]
1542 *
1543 * On the Sparc, BN_mod_exp_recp was faster than BN_mod_exp_mont
1544 * at 2048 and more bits, but at 512 and 1024 bits, it was
1545 * slower even than the standard algorithm!
1546 *
1547 * "Real" timings [linux-elf, solaris-sparcv9-gcc configurations]
1548 * should be obtained when the new Montgomery reduction code
1549 * has been integrated into OpenSSL.)
1550 */
1551
1552 #define MONT_MUL_MOD
1553 #define MONT_EXP_WORD
1554 #define RECP_MUL_MOD
1555
1556 #ifdef MONT_MUL_MOD
1557 /* I have finally been able to take out this pre-condition of
1558 * the top bit being set. It was caused by an error in BN_div
1559 * with negatives. There was also another problem when for a^b%m
1560 * a >= m. eay 07-May-97
1561 */
1562 /* if ((m->d[m->top-1]&BN_TBIT) && BN_is_odd(m)) */
1563
1564 if (BN_is_odd(m)) {
1565 #ifdef MONT_EXP_WORD
1566 if (a->top == 1 && !a->neg) {
1567 BN_ULONG A = a->d[0];
1568 ret = BN_mod_exp_mont_word(r, A, p, m, ctx, NULL);
1569 } else
1570 #endif
1571 ret = BN_mod_exp_mont(r, a, p, m, ctx, NULL);
1572 } else
1573 #endif /* MONT_MUL_MOD */
1574 #ifdef RECP_MUL_MOD
1575 {
1576 ret = BN_mod_exp_recp(r, a, p, m, ctx);
1577 }
1578 #else
1579 {
1580 ret = BN_mod_exp_simple(r, a, p, m, ctx);
1581 }
1582 #endif
1583
1584 return (ret);
1585 }
1586
1587
1588 int
1589 BN_mod_exp_recp(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx)
1590 {
1591 int i, j, bits, ret = 0, wstart, wend, window, wvalue;
1592 int start = 1, ts = 0;
1593 BIGNUM *aa;
1594 BIGNUM val[TABLE_SIZE];
1595 BN_RECP_CTX recp;
1596
1597 bits = BN_num_bits(p);
1598
1599 if (bits == 0) {
1600 ret = BN_one(r);
1601 return ret;
1602 }
1603
1604 BN_CTX_start(ctx);
1605 if ((aa = BN_CTX_get(ctx)) == NULL) goto err;
1606
1607 BN_RECP_CTX_init(&recp);
1608 if (m->neg) {
1609 /* ignore sign of 'm' */
1610 if (!BN_copy(aa, m)) goto err;
1611 aa->neg = 0;
1612 if (BN_RECP_CTX_set(&recp, aa, ctx) <= 0) goto err;
1613 } else {
1614 if (BN_RECP_CTX_set(&recp, m, ctx) <= 0) goto err;
1615 }
1616
1617 BN_init(&(val[0]));
1618 ts = 1;
1619
1620 if (!BN_nnmod(&(val[0]), a, m, ctx)) goto err; /* 1 */
1621 if (BN_is_zero(&(val[0]))) {
1622 ret = BN_zero(r);
1623 goto err;
1624 }
1625
1626 window = BN_window_bits_for_exponent_size(bits);
1627 if (window > 1) {
1628 if (!BN_mod_mul_reciprocal(aa, &(val[0]), &(val[0]), &recp, ctx))
1629 goto err; /* 2 */
1630 j = 1 << (window - 1);
1631 for (i = 1; i < j; i++) {
1632 BN_init(&val[i]);
1633 if (!BN_mod_mul_reciprocal(&(val[i]), &(val[i - 1]), aa, &recp, ctx))
1634 goto err;
1635 }
1636 ts = i;
1637 }
1638
1639 start = 1; /* This is used to avoid multiplication etc
1640 * when there is only the value '1' in the
1641 * buffer.
1642 */
1643 wvalue = 0; /* The 'value' of the window */
1644 wstart = bits - 1; /* The top bit of the window */
1645 wend = 0; /* The bottom bit of the window */
1646
1647 if (!BN_one(r)) goto err;
1648
1649 for (;;) {
1650 if (BN_is_bit_set(p, wstart) == 0) {
1651 if (!start)
1652 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
1653 goto err;
1654 if (wstart == 0) break;
1655 wstart--;
1656 continue;
1657 }
1658 /* We now have wstart on a 'set' bit, we now need to work out
1659 * how bit a window to do. To do this we need to scan
1660 * forward until the last set bit before the end of the
1661 * window
1662 */
1663 j = wstart;
1664 wvalue = 1;
1665 wend = 0;
1666 for (i = 1; i < window; i++) {
1667 if (wstart - i < 0) break;
1668 if (BN_is_bit_set(p, wstart-i)) {
1669 wvalue <<= (i - wend);
1670 wvalue |= 1;
1671 wend = i;
1672 }
1673 }
1674
1675 /* wend is the size of the current window */
1676 j = wend+1;
1677 /* add the 'bytes above' */
1678 if (!start)
1679 for (i = 0; i < j; i++) {
1680 if (!BN_mod_mul_reciprocal(r, r, r, &recp, ctx))
1681 goto err;
1682 }
1683
1684 /* wvalue will be an odd number < 2^window */
1685 if (!BN_mod_mul_reciprocal(r, r, &(val[wvalue >> 1]), &recp, ctx))
1686 goto err;
1687
1688 /* move the 'window' down further */
1689 wstart -= wend+1;
1690 wvalue = 0;
1691 start = 0;
1692 if (wstart < 0) break;
1693 }
1694 ret = 1;
1695 err:
1696 BN_CTX_end(ctx);
1697 for (i = 0; i < ts; i++)
1698 BN_clear_free(&(val[i]));
1699 BN_RECP_CTX_free(&recp);
1700 return (ret);
1701 }
1702 #endif /* NOT_NEEDED_FOR_DH */
1703
1704
1705 int
1706 BN_mod_exp_mont(BIGNUM *rr, const BIGNUM *a, const BIGNUM *p,
1707 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
1708 {
1709 int i, j, bits, ret = 0, wstart, wend, window, wvalue;
1710 int start = 1, ts = 0;
1711 BIGNUM *d, *r;
1712 const BIGNUM *aa;
1713 BIGNUM val[TABLE_SIZE];
1714 BN_MONT_CTX *mont = NULL;
1715
1716 bn_check_top(a);
1717 bn_check_top(p);
1718 bn_check_top(m);
1719
1720 if (!(m->d[0] & 1)) {
1721 BNerr(BN_F_BN_MOD_EXP_MONT, BN_R_CALLED_WITH_EVEN_MODULUS);
1722 return (0);
1723 }
1724 bits = BN_num_bits(p);
1725 if (bits == 0) {
1726 ret = BN_one(rr);
1727 return ret;
1728 }
1729
1730 BN_CTX_start(ctx);
1731 d = BN_CTX_get(ctx);
1732 r = BN_CTX_get(ctx);
1733 if (d == NULL || r == NULL) goto err;
1734
1735 /* If this is not done, things will break in the montgomery part */
1736
1737 if (in_mont != NULL)
1738 mont = in_mont;
1739 else {
1740 if ((mont = BN_MONT_CTX_new()) == NULL) goto err;
1741 if (!BN_MONT_CTX_set(mont, m, ctx)) goto err;
1742 }
1743
1744 BN_init(&val[0]);
1745 ts = 1;
1746 if (a->neg || BN_ucmp(a, m) >= 0) {
1747 if (!BN_nnmod(&(val[0]), a, m, ctx))
1748 goto err;
1749 aa = &(val[0]);
1750 } else
1751 aa = a;
1752 if (BN_is_zero(aa)) {
1753 ret = BN_zero(rr);
1754 goto err;
1755 }
1756 if (!BN_to_montgomery(&(val[0]), aa, mont, ctx)) goto err; /* 1 */
1757
1758 window = BN_window_bits_for_exponent_size(bits);
1759 if (window > 1) {
1760 if (!BN_mod_mul_montgomery(d, &(val[0]), &(val[0]), mont, ctx)) goto err; /* 2 */
1761 j = 1 << (window - 1);
1762 for (i = 1; i < j; i++) {
1763 BN_init(&(val[i]));
1764 if (!BN_mod_mul_montgomery(&(val[i]), &(val[i - 1]), d, mont, ctx))
1765 goto err;
1766 }
1767 ts = i;
1768 }
1769
1770 start = 1; /* This is used to avoid multiplication etc
1771 * when there is only the value '1' in the
1772 * buffer.
1773 */
1774 wvalue = 0; /* The 'value' of the window */
1775 wstart = bits-1; /* The top bit of the window */
1776 wend = 0; /* The bottom bit of the window */
1777
1778 if (!BN_to_montgomery(r, BN_value_one(), mont, ctx)) goto err;
1779 for (;;) {
1780 if (BN_is_bit_set(p, wstart) == 0) {
1781 if (!start) {
1782 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
1783 goto err;
1784 }
1785 if (wstart == 0) break;
1786 wstart--;
1787 continue;
1788 }
1789 /* We now have wstart on a 'set' bit, we now need to work out
1790 * how bit a window to do. To do this we need to scan
1791 * forward until the last set bit before the end of the
1792 * window
1793 */
1794 j = wstart;
1795 wvalue = 1;
1796 wend = 0;
1797 for (i = 1; i < window; i++) {
1798 if (wstart - i < 0) break;
1799 if (BN_is_bit_set(p, wstart - i)) {
1800 wvalue <<= (i - wend);
1801 wvalue |= 1;
1802 wend = i;
1803 }
1804 }
1805
1806 /* wend is the size of the current window */
1807 j = wend + 1;
1808 /* add the 'bytes above' */
1809 if (!start)
1810 for (i = 0; i < j; i++) {
1811 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx))
1812 goto err;
1813 }
1814
1815 /* wvalue will be an odd number < 2^window */
1816 if (!BN_mod_mul_montgomery(r, r, &(val[wvalue >> 1]), mont, ctx))
1817 goto err;
1818
1819 /* move the 'window' down further */
1820 wstart -= wend+1;
1821 wvalue = 0;
1822 start = 0;
1823 if (wstart < 0) break;
1824 }
1825 if (!BN_from_montgomery(rr, r, mont, ctx)) goto err;
1826 ret = 1;
1827 err:
1828 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
1829 BN_CTX_end(ctx);
1830 for (i = 0; i < ts; i++)
1831 BN_clear_free(&(val[i]));
1832 return (ret);
1833 }
1834
1835 int
1836 BN_mod_exp_mont_word(BIGNUM *rr, BN_ULONG a, const BIGNUM *p,
1837 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *in_mont)
1838 {
1839 BN_MONT_CTX *mont = NULL;
1840 int b, bits, ret = 0;
1841 int r_is_one;
1842 BN_ULONG w, next_w;
1843 BIGNUM *d, *r, *t;
1844 BIGNUM *swap_tmp;
1845 #define BN_MOD_MUL_WORD(r, w, m) \
1846 (BN_mul_word(r, (w)) && \
1847 (/* BN_ucmp(r, (m)) < 0 ? 1 : */ \
1848 (BN_mod(t, r, m, ctx) && (swap_tmp = r, r = t, t = swap_tmp, 1))))
1849 /* BN_MOD_MUL_WORD is only used with 'w' large,
1850 * so the BN_ucmp test is probably more overhead
1851 * than always using BN_mod (which uses BN_copy if
1852 * a similar test returns true).
1853 */
1854 /* We can use BN_mod and do not need BN_nnmod because our
1855 * accumulator is never negative (the result of BN_mod does
1856 * not depend on the sign of the modulus).
1857 */
1858 #define BN_TO_MONTGOMERY_WORD(r, w, mont) \
1859 (BN_set_word(r, (w)) && BN_to_montgomery(r, r, (mont), ctx))
1860
1861 bn_check_top(p);
1862 bn_check_top(m);
1863
1864 if (m->top == 0 || !(m->d[0] & 1)) {
1865 BNerr(BN_F_BN_MOD_EXP_MONT_WORD, BN_R_CALLED_WITH_EVEN_MODULUS);
1866 return (0);
1867 }
1868 if (m->top == 1)
1869 a %= m->d[0]; /* make sure that 'a' is reduced */
1870
1871 bits = BN_num_bits(p);
1872 if (bits == 0) {
1873 ret = BN_one(rr);
1874 return ret;
1875 }
1876 if (a == 0) {
1877 ret = BN_zero(rr);
1878 return ret;
1879 }
1880
1881 BN_CTX_start(ctx);
1882 d = BN_CTX_get(ctx);
1883 r = BN_CTX_get(ctx);
1884 t = BN_CTX_get(ctx);
1885 if (d == NULL || r == NULL || t == NULL) goto err;
1886
1887 if (in_mont != NULL)
1888 mont = in_mont;
1889 else {
1890 if ((mont = BN_MONT_CTX_new()) == NULL) goto err;
1891 if (!BN_MONT_CTX_set(mont, m, ctx)) goto err;
1892 }
1893
1894 r_is_one = 1; /* except for Montgomery factor */
1895
1896 /* bits-1 >= 0 */
1897
1898 /* The result is accumulated in the product r*w. */
1899 w = a; /* bit 'bits-1' of 'p' is always set */
1900 for (b = bits-2; b >= 0; b--) {
1901 /* First, square r*w. */
1902 next_w = w*w;
1903 if ((next_w/w) != w) /* overflow */ {
1904 if (r_is_one) {
1905 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
1906 r_is_one = 0;
1907 } else {
1908 if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
1909 }
1910 next_w = 1;
1911 }
1912 w = next_w;
1913 if (!r_is_one) {
1914 if (!BN_mod_mul_montgomery(r, r, r, mont, ctx)) goto err;
1915 }
1916
1917 /* Second, multiply r*w by 'a' if exponent bit is set. */
1918 if (BN_is_bit_set(p, b)) {
1919 next_w = w*a;
1920 if ((next_w/a) != w) /* overflow */ {
1921 if (r_is_one) {
1922 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
1923 r_is_one = 0;
1924 } else {
1925 if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
1926 }
1927 next_w = a;
1928 }
1929 w = next_w;
1930 }
1931 }
1932
1933 /* Finally, set r: = r*w. */
1934 if (w != 1) {
1935 if (r_is_one) {
1936 if (!BN_TO_MONTGOMERY_WORD(r, w, mont)) goto err;
1937 r_is_one = 0;
1938 } else {
1939 if (!BN_MOD_MUL_WORD(r, w, m)) goto err;
1940 }
1941 }
1942
1943 if (r_is_one) /* can happen only if a == 1 */ {
1944 if (!BN_one(rr)) goto err;
1945 } else {
1946 if (!BN_from_montgomery(rr, r, mont, ctx)) goto err;
1947 }
1948 ret = 1;
1949 err:
1950 if ((in_mont == NULL) && (mont != NULL)) BN_MONT_CTX_free(mont);
1951 BN_CTX_end(ctx);
1952 return (ret);
1953 }
1954
1955
1956 #ifdef NOT_NEEDED_FOR_DH
1957 /* The old fallback, simple version :-) */
1958 int
1959 BN_mod_exp_simple(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, const BIGNUM *m, BN_CTX *ctx)
1960 {
1961 int i, j, bits, ret = 0, wstart, wend, window, wvalue, ts = 0;
1962 int start = 1;
1963 BIGNUM *d;
1964 BIGNUM val[TABLE_SIZE];
1965
1966 bits = BN_num_bits(p);
1967
1968 if (bits == 0) {
1969 ret = BN_one(r);
1970 return ret;
1971 }
1972
1973 BN_CTX_start(ctx);
1974 if ((d = BN_CTX_get(ctx)) == NULL) goto err;
1975
1976 BN_init(&(val[0]));
1977 ts = 1;
1978 if (!BN_nnmod(&(val[0]), a, m, ctx)) goto err; /* 1 */
1979 if (BN_is_zero(&(val[0]))) {
1980 ret = BN_zero(r);
1981 goto err;
1982 }
1983
1984 window = BN_window_bits_for_exponent_size(bits);
1985 if (window > 1) {
1986 if (!BN_mod_mul(d, &(val[0]), &(val[0]), m, ctx))
1987 goto err; /* 2 */
1988 j = 1 << (window - 1);
1989 for (i = 1; i < j; i++) {
1990 BN_init(&(val[i]));
1991 if (!BN_mod_mul(&(val[i]), &(val[i - 1]), d, m, ctx))
1992 goto err;
1993 }
1994 ts = i;
1995 }
1996
1997 start = 1; /* This is used to avoid multiplication etc
1998 * when there is only the value '1' in the
1999 * buffer.
2000 */
2001 wvalue = 0; /* The 'value' of the window */
2002 wstart = bits-1; /* The top bit of the window */
2003 wend = 0; /* The bottom bit of the window */
2004
2005 if (!BN_one(r)) goto err;
2006
2007 for (;;) {
2008 if (BN_is_bit_set(p, wstart) == 0) {
2009 if (!start)
2010 if (!BN_mod_mul(r, r, r, m, ctx))
2011 goto err;
2012 if (wstart == 0) break;
2013 wstart--;
2014 continue;
2015 }
2016 /* We now have wstart on a 'set' bit, we now need to work out
2017 * how bit a window to do. To do this we need to scan
2018 * forward until the last set bit before the end of the
2019 * window
2020 */
2021 j = wstart;
2022 wvalue = 1;
2023 wend = 0;
2024 for (i = 1; i < window; i++) {
2025 if (wstart - i < 0) break;
2026 if (BN_is_bit_set(p, wstart - i)) {
2027 wvalue <<= (i - wend);
2028 wvalue |= 1;
2029 wend = i;
2030 }
2031 }
2032
2033 /* wend is the size of the current window */
2034 j = wend+1;
2035 /* add the 'bytes above' */
2036 if (!start)
2037 for (i = 0; i < j; i++) {
2038 if (!BN_mod_mul(r, r, r, m, ctx))
2039 goto err;
2040 }
2041
2042 /* wvalue will be an odd number < 2^window */
2043 if (!BN_mod_mul(r, r, &(val[wvalue >> 1]), m, ctx))
2044 goto err;
2045
2046 /* move the 'window' down further */
2047 wstart -= wend+1;
2048 wvalue = 0;
2049 start = 0;
2050 if (wstart < 0) break;
2051 }
2052 ret = 1;
2053 err:
2054 BN_CTX_end(ctx);
2055 for (i = 0; i < ts; i++)
2056 BN_clear_free(&(val[i]));
2057 return (ret);
2058 }
2059
2060 static BIGNUM *euclid(BIGNUM *a, BIGNUM *b);
2061
2062 int
2063 BN_gcd(BIGNUM *r, const BIGNUM *in_a, const BIGNUM *in_b, BN_CTX *ctx)
2064 {
2065 BIGNUM *a, *b, *t;
2066 int ret = 0;
2067
2068 bn_check_top(in_a);
2069 bn_check_top(in_b);
2070
2071 BN_CTX_start(ctx);
2072 a = BN_CTX_get(ctx);
2073 b = BN_CTX_get(ctx);
2074 if (a == NULL || b == NULL) goto err;
2075
2076 if (BN_copy(a, in_a) == NULL) goto err;
2077 if (BN_copy(b, in_b) == NULL) goto err;
2078 a->neg = 0;
2079 b->neg = 0;
2080
2081 if (BN_cmp(a, b) < 0) { t = a; a = b; b = t; }
2082 t = euclid(a, b);
2083 if (t == NULL) goto err;
2084
2085 if (BN_copy(r, t) == NULL) goto err;
2086 ret = 1;
2087 err:
2088 BN_CTX_end(ctx);
2089 return (ret);
2090 }
2091
2092 static BIGNUM *
2093 euclid(BIGNUM *a, BIGNUM *b)
2094 {
2095 BIGNUM *t;
2096 int shifts = 0;
2097
2098 bn_check_top(a);
2099 bn_check_top(b);
2100
2101 /* 0 <= b <= a */
2102 while (!BN_is_zero(b)) {
2103 /* 0 < b <= a */
2104
2105 if (BN_is_odd(a)) {
2106 if (BN_is_odd(b)) {
2107 if (!BN_sub(a, a, b)) goto err;
2108 if (!BN_rshift1(a, a)) goto err;
2109 if (BN_cmp(a, b) < 0) { t = a; a = b; b = t; }
2110 } else /* a odd - b even */ {
2111 if (!BN_rshift1(b, b)) goto err;
2112 if (BN_cmp(a, b) < 0) { t = a; a = b; b = t; }
2113 }
2114 } else /* a is even */ {
2115 if (BN_is_odd(b)) {
2116 if (!BN_rshift1(a, a)) goto err;
2117 if (BN_cmp(a, b) < 0) { t = a; a = b; b = t; }
2118 } else /* a even - b even */ {
2119 if (!BN_rshift1(a, a)) goto err;
2120 if (!BN_rshift1(b, b)) goto err;
2121 shifts++;
2122 }
2123 }
2124 /* 0 <= b <= a */
2125 }
2126
2127 if (shifts) {
2128 if (!BN_lshift(a, a, shifts)) goto err;
2129 }
2130 return (a);
2131 err:
2132 return (NULL);
2133 }
2134 #endif /* NOT_NEEDED_FOR_DH */
2135
2136
2137 /* solves ax == 1 (mod n) */
2138 BIGNUM *
2139 BN_mod_inverse(BIGNUM *in, const BIGNUM *a, const BIGNUM *n, BN_CTX *ctx)
2140 {
2141 BIGNUM *A, *B, *X, *Y, *M, *D, *T, *R = NULL;
2142 BIGNUM *ret = NULL;
2143 int sign;
2144
2145 bn_check_top(a);
2146 bn_check_top(n);
2147
2148 BN_CTX_start(ctx);
2149 A = BN_CTX_get(ctx);
2150 B = BN_CTX_get(ctx);
2151 X = BN_CTX_get(ctx);
2152 D = BN_CTX_get(ctx);
2153 M = BN_CTX_get(ctx);
2154 Y = BN_CTX_get(ctx);
2155 T = BN_CTX_get(ctx);
2156 if (T == NULL) goto err;
2157
2158 if (in == NULL)
2159 R = BN_new();
2160 else
2161 R = in;
2162 if (R == NULL) goto err;
2163
2164 BN_one(X);
2165 BN_zero(Y);
2166 if (BN_copy(B, a) == NULL) goto err;
2167 if (BN_copy(A, n) == NULL) goto err;
2168 A->neg = 0;
2169 if (B->neg || (BN_ucmp(B, A) >= 0)) {
2170 if (!BN_nnmod(B, B, A, ctx)) goto err;
2171 }
2172 sign = -1;
2173 /* From B = a mod |n|, A = |n| it follows that
2174 *
2175 * 0 <= B < A,
2176 * -sign*X*a == B (mod |n|),
2177 * sign*Y*a == A (mod |n|).
2178 */
2179
2180 if (BN_is_odd(n) && (BN_num_bits(n) <= (BN_BITS <= 32 ? 450 : 2048))) {
2181 /* Binary inversion algorithm; requires odd modulus.
2182 * This is faster than the general algorithm if the modulus
2183 * is sufficiently small (about 400 .. 500 bits on 32-bit
2184 * sytems, but much more on 64-bit systems)
2185 */
2186 int shift;
2187
2188 while (!BN_is_zero(B)) {
2189 /*
2190 * 0 < B < |n|,
2191 * 0 < A <= |n|,
2192 * (1) -sign*X*a == B (mod |n|),
2193 * (2) sign*Y*a == A (mod |n|)
2194 */
2195
2196 /* Now divide B by the maximum possible power of two in the integers,
2197 * and divide X by the same value mod |n|.
2198 * When we're done, (1) still holds.
2199 */
2200 shift = 0;
2201 while (!BN_is_bit_set(B, shift)) /* note that 0 < B */ {
2202 shift++;
2203
2204 if (BN_is_odd(X)) {
2205 if (!BN_uadd(X, X, n)) goto err;
2206 }
2207 /* now X is even, so we can easily divide it by two */
2208 if (!BN_rshift1(X, X)) goto err;
2209 }
2210 if (shift > 0) {
2211 if (!BN_rshift(B, B, shift)) goto err;
2212 }
2213
2214
2215 /* Same for A and Y. Afterwards, (2) still holds. */
2216 shift = 0;
2217 while (!BN_is_bit_set(A, shift)) /* note that 0 < A */ {
2218 shift++;
2219
2220 if (BN_is_odd(Y)) {
2221 if (!BN_uadd(Y, Y, n)) goto err;
2222 }
2223 /* now Y is even */
2224 if (!BN_rshift1(Y, Y)) goto err;
2225 }
2226 if (shift > 0) {
2227 if (!BN_rshift(A, A, shift)) goto err;
2228 }
2229
2230 /* We still have (1) and (2).
2231 * Both A and B are odd.
2232 * The following computations ensure that
2233 *
2234 * 0 <= B < |n|,
2235 * 0 < A < |n|,
2236 * (1) -sign*X*a == B (mod |n|),
2237 * (2) sign*Y*a == A (mod |n|),
2238 *
2239 * and that either A or B is even in the next iteration.
2240 */
2241 if (BN_ucmp(B, A) >= 0) {
2242 /* -sign*(X + Y)*a == B - A (mod |n|) */
2243 if (!BN_uadd(X, X, Y)) goto err;
2244 /* NB: we could use BN_mod_add_quick(X, X, Y, n), but that
2245 * actually makes the algorithm slower
2246 */
2247 if (!BN_usub(B, B, A)) goto err;
2248 } else {
2249 /* sign*(X + Y)*a == A - B (mod |n|) */
2250 if (!BN_uadd(Y, Y, X)) goto err;
2251 /* as above, BN_mod_add_quick(Y, Y, X, n) would slow things down */
2252 if (!BN_usub(A, A, B)) goto err;
2253 }
2254 }
2255 } else {
2256 /* general inversion algorithm */
2257
2258 while (!BN_is_zero(B)) {
2259 BIGNUM *tmp;
2260
2261 /*
2262 * 0 < B < A,
2263 * (*) -sign*X*a == B (mod |n|),
2264 * sign*Y*a == A (mod |n|)
2265 */
2266
2267 /* (D, M) : = (A/B, A%B) ... */
2268 if (BN_num_bits(A) == BN_num_bits(B)) {
2269 if (!BN_one(D)) goto err;
2270 if (!BN_sub(M, A, B)) goto err;
2271 } else if (BN_num_bits(A) == BN_num_bits(B) + 1) {
2272 /* A/B is 1, 2, or 3 */
2273 if (!BN_lshift1(T, B)) goto err;
2274 if (BN_ucmp(A, T) < 0) {
2275 /* A < 2*B, so D = 1 */
2276 if (!BN_one(D)) goto err;
2277 if (!BN_sub(M, A, B)) goto err;
2278 } else {
2279 /* A >= 2*B, so D = 2 or D = 3 */
2280 if (!BN_sub(M, A, T)) goto err;
2281 if (!BN_add(D, T, B)) goto err;
2282 /* use D ( := 3 * B) as temp */
2283 if (BN_ucmp(A, D) < 0) {
2284 /* A < 3*B, so D = 2 */
2285 if (!BN_set_word(D, 2)) goto err;
2286 /* M ( = A - 2*B) already has the correct value */
2287 } else {
2288 /* only D = 3 remains */
2289 if (!BN_set_word(D, 3)) goto err;
2290 /* currently M = A - 2 * B,
2291 * but we need M = A - 3 * B
2292 */
2293 if (!BN_sub(M, M, B)) goto err;
2294 }
2295 }
2296 } else {
2297 if (!BN_div(D, M, A, B, ctx)) goto err;
2298 }
2299
2300 /* Now
2301 * A = D*B + M;
2302 * thus we have
2303 * (**) sign*Y*a == D*B + M (mod |n|).
2304 */
2305
2306 tmp = A; /* keep the BIGNUM object, the value does not matter */
2307
2308 /* (A, B) : = (B, A mod B) ... */
2309 A = B;
2310 B = M;
2311 /* ... so we have 0 <= B < A again */
2312
2313 /* Since the former M is now B and the former B is now A,
2314 * (**) translates into
2315 * sign*Y*a == D*A + B (mod |n|),
2316 * i.e.
2317 * sign*Y*a - D*A == B (mod |n|).
2318 * Similarly, (*) translates into
2319 * -sign*X*a == A (mod |n|).
2320 *
2321 * Thus,
2322 * sign*Y*a + D*sign*X*a == B (mod |n|),
2323 * i.e.
2324 * sign*(Y + D*X)*a == B (mod |n|).
2325 *
2326 * So if we set (X, Y, sign) : = (Y + D*X, X, -sign), we arrive back at
2327 * -sign*X*a == B (mod |n|),
2328 * sign*Y*a == A (mod |n|).
2329 * Note that X and Y stay non-negative all the time.
2330 */
2331
2332 /* most of the time D is very small, so we can optimize tmp : = D*X+Y */
2333 if (BN_is_one(D)) {
2334 if (!BN_add(tmp, X, Y)) goto err;
2335 } else {
2336 if (BN_is_word(D, 2)) {
2337 if (!BN_lshift1(tmp, X)) goto err;
2338 } else if (BN_is_word(D, 4)) {
2339 if (!BN_lshift(tmp, X, 2)) goto err;
2340 } else if (D->top == 1) {
2341 if (!BN_copy(tmp, X)) goto err;
2342 if (!BN_mul_word(tmp, D->d[0])) goto err;
2343 } else {
2344 if (!BN_mul(tmp, D, X, ctx)) goto err;
2345 }
2346 if (!BN_add(tmp, tmp, Y)) goto err;
2347 }
2348
2349 M = Y; /* keep the BIGNUM object, the value does not matter */
2350 Y = X;
2351 X = tmp;
2352 sign = -sign;
2353 }
2354 }
2355
2356 /*
2357 * The while loop (Euclid's algorithm) ends when
2358 * A == gcd(a, n);
2359 * we have
2360 * sign*Y*a == A (mod |n|),
2361 * where Y is non-negative.
2362 */
2363
2364 if (sign < 0) {
2365 if (!BN_sub(Y, n, Y)) goto err;
2366 }
2367 /* Now Y*a == A (mod |n|). */
2368
2369
2370 if (BN_is_one(A)) {
2371 /* Y*a == 1 (mod |n|) */
2372 if (!Y->neg && BN_ucmp(Y, n) < 0) {
2373 if (!BN_copy(R, Y)) goto err;
2374 } else {
2375 if (!BN_nnmod(R, Y, n, ctx)) goto err;
2376 }
2377 } else {
2378 BNerr(BN_F_BN_MOD_INVERSE, BN_R_NO_INVERSE);
2379 goto err;
2380 }
2381 ret = R;
2382 err:
2383 if ((ret == NULL) && (in == NULL)) BN_free(R);
2384 BN_CTX_end(ctx);
2385 return (ret);
2386 }
2387
2388 #include <limits.h>
2389
2390 #ifdef NOT_NEEDED_FOR_DH
2391 /* For a 32 bit machine
2392 * 2 - 4 == 128
2393 * 3 - 8 == 256
2394 * 4 - 16 == 512
2395 * 5 - 32 == 1024
2396 * 6 - 64 == 2048
2397 * 7 - 128 == 4096
2398 * 8 - 256 == 8192
2399 */
2400 static int bn_limit_bits = 0;
2401 static int bn_limit_num = 8; /* (1 << bn_limit_bits) */
2402 static int bn_limit_bits_low = 0;
2403 static int bn_limit_num_low = 8; /* (1 << bn_limit_bits_low) */
2404 static int bn_limit_bits_high = 0;
2405 static int bn_limit_num_high = 8; /* (1 << bn_limit_bits_high) */
2406 static int bn_limit_bits_mont = 0;
2407 static int bn_limit_num_mont = 8; /* (1 << bn_limit_bits_mont) */
2408
2409 void
2410 BN_set_params(int mult, int high, int low, int mont)
2411 {
2412 if (mult >= 0) {
2413 if (mult > (sizeof(int)*8)-1)
2414 mult = sizeof(int)*8-1;
2415 bn_limit_bits = mult;
2416 bn_limit_num = 1 << mult;
2417 }
2418 if (high >= 0) {
2419 if (high > (sizeof(int)*8)-1)
2420 high = sizeof(int)*8-1;
2421 bn_limit_bits_high = high;
2422 bn_limit_num_high = 1 << high;
2423 }
2424 if (low >= 0) {
2425 if (low > (sizeof(int)*8)-1)
2426 low = sizeof(int)*8-1;
2427 bn_limit_bits_low = low;
2428 bn_limit_num_low = 1 << low;
2429 }
2430 if (mont >= 0) {
2431 if (mont > (sizeof(int)*8)-1)
2432 mont = sizeof(int)*8-1;
2433 bn_limit_bits_mont = mont;
2434 bn_limit_num_mont = 1 << mont;
2435 }
2436 }
2437
2438 int
2439 BN_get_params(int which)
2440 {
2441 if (which == 0) return (bn_limit_bits);
2442 else if (which == 1) return (bn_limit_bits_high);
2443 else if (which == 2) return (bn_limit_bits_low);
2444 else if (which == 3) return (bn_limit_bits_mont);
2445 else return (0);
2446 }
2447
2448 char *
2449 BN_options(void)
2450 {
2451 static int init = 0;
2452 static char data[16];
2453
2454 if (!init) {
2455 init++;
2456 #ifdef BN_LLONG
2457 sprintf(data, "bn(%d, %d)", (int)sizeof(BN_ULLONG)*8,
2458 (int)sizeof(BN_ULONG)*8);
2459 #else
2460 sprintf(data, "bn(%d, %d)", (int)sizeof(BN_ULONG)*8,
2461 (int)sizeof(BN_ULONG)*8);
2462 #endif
2463 }
2464 return (data);
2465 }
2466 #endif /* NOT_NEEDED_FOR_DH */
2467
2468 const BIGNUM *
2469 BN_value_one(void)
2470 {
2471 static BN_ULONG data_one = 1L;
2472 static BIGNUM const_one = {&data_one, 1, 1, 0};
2473
2474 return (&const_one);
2475 }
2476
2477 int
2478 BN_num_bits_word(BN_ULONG l)
2479 {
2480 static const char bits[256] = {
2481 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
2482 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
2483 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
2484 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
2485 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
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 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
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 };
2498
2499 #if defined(SIXTY_FOUR_BIT_LONG)
2500 if (l & 0xffffffff00000000L) {
2501 if (l & 0xffff000000000000L) {
2502 if (l & 0xff00000000000000L) {
2503 return (bits[(int)(l >> 56)] + 56);
2504 } else
2505 return (bits[(int)(l >> 48)] + 48);
2506 } else {
2507 if (l & 0x0000ff0000000000L) {
2508 return (bits[(int)(l >> 40)] + 40);
2509 } else
2510 return (bits[(int)(l >> 32)] + 32);
2511 }
2512 } else
2513 #else
2514 #ifdef SIXTY_FOUR_BIT
2515 if (l & 0xffffffff00000000LL) {
2516 if (l & 0xffff000000000000LL) {
2517 if (l & 0xff00000000000000LL) {
2518 return (bits[(int)(l >> 56)] + 56);
2519 } else
2520 return (bits[(int)(l >> 48)] + 48);
2521 } else {
2522 if (l & 0x0000ff0000000000LL) {
2523 return (bits[(int)(l >> 40)] + 40);
2524 } else
2525 return (bits[(int)(l >> 32)] + 32);
2526 }
2527 } else
2528 #endif
2529 #endif /* SIXTY_FOUR_BIT_LONG */
2530 {
2531 #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
2532 if (l & 0xffff0000L) {
2533 if (l & 0xff000000L)
2534 return (bits[(int)(l >> 24L)] + 24);
2535 else
2536 return (bits[(int)(l >> 16L)] + 16);
2537 } else
2538 #endif
2539 {
2540 #if defined(SIXTEEN_BIT) || defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || \
2541 defined(SIXTY_FOUR_BIT_LONG)
2542 if (l & 0xff00L)
2543 return (bits[(int)(l >> 8)] + 8);
2544 else
2545 #endif
2546 return (bits[(int)(l)]);
2547 }
2548 }
2549 }
2550
2551 int
2552 BN_num_bits(const BIGNUM *a)
2553 {
2554 BN_ULONG l;
2555 int i;
2556
2557 bn_check_top(a);
2558
2559 if (a->top == 0) return (0);
2560 l = a->d[a->top-1];
2561 assert(l != 0);
2562 i = (a->top-1)*BN_BITS2;
2563 return (i+BN_num_bits_word(l));
2564 }
2565
2566 void
2567 BN_clear_free(BIGNUM *a)
2568 {
2569 int i;
2570
2571 if (a == NULL) return;
2572 if (a->d != NULL) {
2573 OPENSSL_cleanse(a->d, a->dmax*sizeof(a->d[0]));
2574 if (!(BN_get_flags(a, BN_FLG_STATIC_DATA)))
2575 OPENSSL_free(a->d);
2576 }
2577 i = BN_get_flags(a, BN_FLG_MALLOCED);
2578 OPENSSL_cleanse(a, sizeof(BIGNUM));
2579 if (i)
2580 OPENSSL_free(a);
2581 }
2582
2583 void
2584 BN_free(BIGNUM *a)
2585 {
2586 if (a == NULL) return;
2587 if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA)))
2588 OPENSSL_free(a->d);
2589 a->flags |= BN_FLG_FREE; /* REMOVE? */
2590 if (a->flags & BN_FLG_MALLOCED)
2591 OPENSSL_free(a);
2592 }
2593
2594 void
2595 BN_init(BIGNUM *a)
2596 {
2597 memset(a, 0, sizeof(BIGNUM));
2598 }
2599
2600 BIGNUM *
2601 BN_new(void)
2602 {
2603 BIGNUM *ret;
2604
2605 if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) {
2606 BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
2607 return (NULL);
2608 }
2609 ret->flags = BN_FLG_MALLOCED;
2610 ret->top = 0;
2611 ret->neg = 0;
2612 ret->dmax = 0;
2613 ret->d = NULL;
2614 return (ret);
2615 }
2616
2617 /* This is used both by bn_expand2() and bn_dup_expand() */
2618 /* The caller MUST check that words > b->dmax before calling this */
2619 static BN_ULONG *
2620 bn_expand_internal(const BIGNUM *b, int words)
2621 {
2622 BN_ULONG *A, *a = NULL;
2623 const BN_ULONG *B;
2624 int i;
2625
2626 if (words > (INT_MAX/(4*BN_BITS2))) {
2627 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
2628 return NULL;
2629 }
2630
2631 bn_check_top(b);
2632 if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
2633 BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
2634 return (NULL);
2635 }
2636 a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG)*(words+1));
2637 if (A == NULL) {
2638 BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
2639 return (NULL);
2640 }
2641 B = b->d;
2642 /* Check if the previous number needs to be copied */
2643 if (B != NULL) {
2644 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
2645 /*
2646 * The fact that the loop is unrolled
2647 * 4-wise is a tribute to Intel. It's
2648 * the one that doesn't have enough
2649 * registers to accomodate more data.
2650 * I'd unroll it 8-wise otherwise:-)
2651 *
2652 * <appro@fy.chalmers.se>
2653 */
2654 BN_ULONG a0, a1, a2, a3;
2655 a0 = B[0]; a1 = B[1]; a2 = B[2]; a3 = B[3];
2656 A[0] = a0; A[1] = a1; A[2] = a2; A[3] = a3;
2657 }
2658 switch (b->top&3) {
2659 case 3: A[2] = B[2];
2660 case 2: A[1] = B[1];
2661 case 1: A[0] = B[0];
2662 case 0:
2663 ;
2664 }
2665 }
2666
2667 /* Now need to zero any data between b->top and b->max */
2668
2669 A = &(a[b->top]);
2670 for (i = (words - b->top) >> 3; i > 0; i--, A += 8) {
2671 A[0] = 0; A[1] = 0; A[2] = 0; A[3] = 0;
2672 A[4] = 0; A[5] = 0; A[6] = 0; A[7] = 0;
2673 }
2674 for (i = (words - b->top) & 7; i > 0; i--, A++)
2675 A[0] = 0;
2676
2677 return (a);
2678 }
2679
2680 #ifdef NOT_NEEDED_FOR_DH
2681 /* This is an internal function that can be used instead of bn_expand2()
2682 * when there is a need to copy BIGNUMs instead of only expanding the
2683 * data part, while still expanding them.
2684 * Especially useful when needing to expand BIGNUMs that are declared
2685 * 'const' and should therefore not be changed.
2686 * The reason to use this instead of a BN_dup() followed by a bn_expand2()
2687 * is memory allocation overhead. A BN_dup() followed by a bn_expand2()
2688 * will allocate new memory for the BIGNUM data twice, and free it once,
2689 * while bn_dup_expand() makes sure allocation is made only once.
2690 */
2691
2692 BIGNUM *
2693 bn_dup_expand(const BIGNUM *b, int words)
2694 {
2695 BIGNUM *r = NULL;
2696
2697 /* This function does not work if
2698 * words <= b->dmax && top < words
2699 * because BN_dup() does not preserve 'dmax'!
2700 * (But bn_dup_expand() is not used anywhere yet.)
2701 */
2702
2703 if (words > b->dmax) {
2704 BN_ULONG *a = bn_expand_internal(b, words);
2705
2706 if (a) {
2707 r = BN_new();
2708 if (r) {
2709 r->top = b->top;
2710 r->dmax = words;
2711 r->neg = b->neg;
2712 r->d = a;
2713 } else {
2714 /* r == NULL, BN_new failure */
2715 OPENSSL_free(a);
2716 }
2717 }
2718 /* If a == NULL, there was an error in allocation in
2719 * bn_expand_internal(), and NULL should be returned
2720 */
2721 } else {
2722 r = BN_dup(b);
2723 }
2724
2725 return r;
2726 }
2727 #endif /* NOT_NEEDED_FOR_DH */
2728
2729 /* This is an internal function that should not be used in applications.
2730 * It ensures that 'b' has enough room for a 'words' word number number.
2731 * It is mostly used by the various BIGNUM routines. If there is an error,
2732 * NULL is returned. If not, 'b' is returned.
2733 */
2734
2735 BIGNUM *
2736 bn_expand2(BIGNUM *b, int words)
2737 {
2738 if (words > b->dmax) {
2739 BN_ULONG *a = bn_expand_internal(b, words);
2740
2741 if (a) {
2742 if (b->d)
2743 OPENSSL_free(b->d);
2744 b->d = a;
2745 b->dmax = words;
2746 } else
2747 b = NULL;
2748 }
2749 return b;
2750 }
2751
2752 #ifdef BCMDH_TEST
2753 BIGNUM *
2754 BN_dup(const BIGNUM *a)
2755 {
2756 BIGNUM *r, *t;
2757
2758 if (a == NULL) return NULL;
2759
2760 bn_check_top(a);
2761
2762 t = BN_new();
2763 if (t == NULL) return (NULL);
2764 r = BN_copy(t, a);
2765 /* now r == t || r == NULL */
2766 if (r == NULL)
2767 BN_free(t);
2768 return r;
2769 }
2770 #endif /* BCMDH_TEST */
2771
2772 BIGNUM *
2773 BN_copy(BIGNUM *a, const BIGNUM *b)
2774 {
2775 int i;
2776 BN_ULONG *A;
2777 const BN_ULONG *B;
2778
2779 bn_check_top(b);
2780
2781 if (a == b) return (a);
2782 if (bn_wexpand(a, b->top) == NULL) return (NULL);
2783
2784 A = a->d;
2785 B = b->d;
2786 for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
2787 BN_ULONG a0, a1, a2, a3;
2788 a0 = B[0]; a1 = B[1]; a2 = B[2]; a3 = B[3];
2789 A[0] = a0; A[1] = a1; A[2] = a2; A[3] = a3;
2790 }
2791 switch (b->top & 3) {
2792 case 3: A[2] = B[2];
2793 case 2: A[1] = B[1];
2794 case 1: A[0] = B[0];
2795 case 0: ;
2796 }
2797
2798 /* memset(&(a->d[b->top]), 0, sizeof(a->d[0])*(a->max-b->top)); */
2799 a->top = b->top;
2800 if ((a->top == 0) && (a->d != NULL))
2801 a->d[0] = 0;
2802 a->neg = b->neg;
2803 return (a);
2804 }
2805
2806 #ifdef NOT_NEEDED_FOR_DH
2807 void
2808 BN_swap(BIGNUM *a, BIGNUM *b)
2809 {
2810 int flags_old_a, flags_old_b;
2811 BN_ULONG *tmp_d;
2812 int tmp_top, tmp_dmax, tmp_neg;
2813
2814 flags_old_a = a->flags;
2815 flags_old_b = b->flags;
2816
2817 tmp_d = a->d;
2818 tmp_top = a->top;
2819 tmp_dmax = a->dmax;
2820 tmp_neg = a->neg;
2821
2822 a->d = b->d;
2823 a->top = b->top;
2824 a->dmax = b->dmax;
2825 a->neg = b->neg;
2826
2827 b->d = tmp_d;
2828 b->top = tmp_top;
2829 b->dmax = tmp_dmax;
2830 b->neg = tmp_neg;
2831
2832 a->flags = (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA);
2833 b->flags = (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA);
2834 }
2835
2836
2837 void
2838 BN_clear(BIGNUM *a)
2839 {
2840 if (a->d != NULL)
2841 memset(a->d, 0, a->dmax*sizeof(a->d[0]));
2842 a->top = 0;
2843 a->neg = 0;
2844 }
2845
2846 BN_ULONG
2847 BN_get_word(const BIGNUM *a)
2848 {
2849 int i, n;
2850 BN_ULONG ret = 0;
2851
2852 n = BN_num_bytes(a);
2853 if (n > sizeof(BN_ULONG))
2854 return (BN_MASK2);
2855 for (i = a->top-1; i >= 0; i--) {
2856 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
2857 ret <<= BN_BITS4; /* stops the compiler complaining */
2858 ret <<= BN_BITS4;
2859 #else
2860 ret = 0;
2861 #endif
2862 ret |= a->d[i];
2863 }
2864 return (ret);
2865 }
2866 #endif /* NOT_NEEDED_FOR_DH */
2867
2868 int
2869 BN_set_word(BIGNUM *a, BN_ULONG w)
2870 {
2871 int i, n;
2872 if (bn_expand(a, (int)sizeof(BN_ULONG)*8) == NULL) return (0);
2873
2874 n = sizeof(BN_ULONG)/BN_BYTES;
2875 a->neg = 0;
2876 a->top = 0;
2877 a->d[0] = (BN_ULONG)w&BN_MASK2;
2878 if (a->d[0] != 0) a->top = 1;
2879 for (i = 1; i < n; i++) {
2880 /* the following is done instead of
2881 * w >>= BN_BITS2 so compilers don't complain
2882 * on builds where sizeof(long) == BN_TYPES
2883 */
2884 #ifndef SIXTY_FOUR_BIT /* the data item > unsigned long */
2885 w >>= BN_BITS4;
2886 w >>= BN_BITS4;
2887 #else
2888 w = 0;
2889 #endif
2890 a->d[i] = (BN_ULONG)w&BN_MASK2;
2891 if (a->d[i] != 0) a->top = i+1;
2892 }
2893 return (1);
2894 }
2895
2896 BIGNUM *
2897 BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
2898 {
2899 unsigned int i, m;
2900 unsigned int n;
2901 BN_ULONG l;
2902
2903 if (ret == NULL) ret = BN_new();
2904 if (ret == NULL) return (NULL);
2905 l = 0;
2906 n = len;
2907 if (n == 0) {
2908 ret->top = 0;
2909 return (ret);
2910 }
2911 if (bn_expand(ret, (int)(n+2)*8) == NULL)
2912 return (NULL);
2913 i = ((n-1)/BN_BYTES)+1;
2914 m = ((n-1)%(BN_BYTES));
2915 ret->top = i;
2916 ret->neg = 0;
2917 while (n-- > 0) {
2918 l = (l << 8L)| *(s++);
2919 if (m-- == 0) {
2920 ret->d[--i] = l;
2921 l = 0;
2922 m = BN_BYTES-1;
2923 }
2924 }
2925 /* need to call this due to clear byte at top if avoiding
2926 * having the top bit set (-ve number)
2927 */
2928 bn_fix_top(ret);
2929 return (ret);
2930 }
2931
2932 /* ignore negative */
2933 int
2934 BN_bn2bin(const BIGNUM *a, unsigned char *to)
2935 {
2936 int n, i;
2937 BN_ULONG l;
2938
2939 n = i = BN_num_bytes(a);
2940 while (i-- > 0) {
2941 l = a->d[i/BN_BYTES];
2942 *(to++) = (unsigned char)(l>>(8*(i%BN_BYTES)))&0xff;
2943 }
2944 return (n);
2945 }
2946
2947 int
2948 BN_ucmp(const BIGNUM *a, const BIGNUM *b)
2949 {
2950 int i;
2951 BN_ULONG t1, t2, *ap, *bp;
2952
2953 bn_check_top(a);
2954 bn_check_top(b);
2955
2956 i = a->top-b->top;
2957 if (i != 0) return (i);
2958 ap = a->d;
2959 bp = b->d;
2960 for (i = a->top-1; i >= 0; i--) {
2961 t1 = ap[i];
2962 t2 = bp[i];
2963 if (t1 != t2)
2964 return (t1 > t2?1:-1);
2965 }
2966 return (0);
2967 }
2968
2969 #ifdef BCMDH_TEST
2970 int
2971 BN_cmp(const BIGNUM *a, const BIGNUM *b)
2972 {
2973 int i;
2974 int gt, lt;
2975 BN_ULONG t1, t2;
2976
2977 if ((a == NULL) || (b == NULL)) {
2978 if (a != NULL)
2979 return (-1);
2980 else if (b != NULL)
2981 return (1);
2982 else
2983 return (0);
2984 }
2985
2986 bn_check_top(a);
2987 bn_check_top(b);
2988
2989 if (a->neg != b->neg) {
2990 if (a->neg)
2991 return (-1);
2992 else return (1);
2993 }
2994 if (a->neg == 0) {
2995 gt = 1; lt = -1;
2996 } else {
2997 gt = -1; lt = 1;
2998 }
2999
3000 if (a->top > b->top) return (gt);
3001 if (a->top < b->top) return (lt);
3002 for (i = a->top-1; i >= 0; i--) {
3003 t1 = a->d[i];
3004 t2 = b->d[i];
3005 if (t1 > t2) return (gt);
3006 if (t1 < t2) return (lt);
3007 }
3008 return (0);
3009 }
3010 #endif /* BCMDH_TEST */
3011
3012 int
3013 BN_set_bit(BIGNUM *a, int n)
3014 {
3015 int i, j, k;
3016
3017 i = n/BN_BITS2;
3018 j = n%BN_BITS2;
3019 if (a->top <= i) {
3020 if (bn_wexpand(a, i + 1) == NULL) return (0);
3021 for (k = a->top; k < i + 1; k++)
3022 a->d[k] = 0;
3023 a->top = i+1;
3024 }
3025
3026 a->d[i] |= (((BN_ULONG)1) << j);
3027 return (1);
3028 }
3029
3030 #ifdef NOT_NEEDED_FOR_DH
3031 int
3032 BN_clear_bit(BIGNUM *a, int n)
3033 {
3034 int i, j;
3035
3036 i = n/BN_BITS2;
3037 j = n%BN_BITS2;
3038 if (a->top <= i) return (0);
3039
3040 a->d[i] &= (~(((BN_ULONG)1) << j));
3041 bn_fix_top(a);
3042 return (1);
3043 }
3044 #endif /* NOT_NEEDED_FOR_DH */
3045
3046 int
3047 BN_is_bit_set(const BIGNUM *a, int n)
3048 {
3049 int i, j;
3050
3051 if (n < 0) return (0);
3052 i = n/BN_BITS2;
3053 j = n%BN_BITS2;
3054 if (a->top <= i) return (0);
3055 return ((a->d[i]&(((BN_ULONG)1) << j)) ? 1 : 0);
3056 }
3057
3058 #ifdef NOT_NEEDED_FOR_DH
3059 int
3060 BN_mask_bits(BIGNUM *a, int n)
3061 {
3062 int b, w;
3063
3064 w = n/BN_BITS2;
3065 b = n%BN_BITS2;
3066 if (w >= a->top) return (0);
3067 if (b == 0)
3068 a->top = w;
3069 else {
3070 a->top = w+1;
3071 a->d[w] &= ~(BN_MASK2 << b);
3072 }
3073 bn_fix_top(a);
3074 return (1);
3075 }
3076 #endif /* NOT_NEEDED_FOR_DH */
3077
3078 int
3079 bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
3080 {
3081 int i;
3082 BN_ULONG aa, bb;
3083
3084 aa = a[n-1];
3085 bb = b[n-1];
3086 if (aa != bb) return ((aa > bb)?1:-1);
3087 for (i = n-2; i >= 0; i--) {
3088 aa = a[i];
3089 bb = b[i];
3090 if (aa != bb) return ((aa > bb)?1:-1);
3091 }
3092 return (0);
3093 }
3094
3095 #ifdef NOT_NEEDED_FOR_DH
3096 /* Here follows a specialised variants of bn_cmp_words(). It has the
3097 * property of performing the operation on arrays of different sizes.
3098 * The sizes of those arrays is expressed through cl, which is the
3099 * common length ( basicall, min(len(a), len(b)) ), and dl, which is the
3100 * delta between the two lengths, calculated as len(a)-len(b).
3101 * All lengths are the number of BN_ULONGs...
3102 */
3103
3104 int
3105 bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
3106 {
3107 int n, i;
3108 n = cl-1;
3109
3110 if (dl < 0) {
3111 for (i = dl; i < 0; i++) {
3112 if (b[n - i] != 0)
3113 return -1; /* a < b */
3114 }
3115 }
3116 if (dl > 0) {
3117 for (i = dl; i > 0; i--) {
3118 if (a[n + i] != 0)
3119 return 1; /* a > b */
3120 }
3121 }
3122 return bn_cmp_words(a, b, cl);
3123 }
3124 #endif /* NOT_NEEDED_FOR_DH */
3125
3126
3127
3128 int
3129 BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx)
3130 {
3131 /* like BN_mod, but returns non-negative remainder
3132 * (i.e., 0 <= r < |d| always holds)
3133 */
3134
3135 if (!(BN_mod(r, m, d, ctx)))
3136 return 0;
3137 if (!r->neg)
3138 return 1;
3139 /* now -|d| < r < 0, so we have to set r : = r + |d| */
3140 return (d->neg ? BN_sub : BN_add)(r, r, d);
3141 }
3142
3143
3144 #ifdef NOT_NEEDED_FOR_DH
3145 int
3146 BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
3147 {
3148 if (!BN_add(r, a, b))
3149 return 0;
3150 return BN_nnmod(r, r, m, ctx);
3151 }
3152
3153
3154 /* BN_mod_add variant that may be used if both a and b are non-negative
3155 * and less than m
3156 */
3157 int
3158 BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
3159 {
3160 if (!BN_add(r, a, b)) return 0;
3161 if (BN_ucmp(r, m) >= 0)
3162 return BN_usub(r, r, m);
3163 return 1;
3164 }
3165
3166 int
3167 BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
3168 {
3169 if (!BN_sub(r, a, b)) return 0;
3170 return BN_nnmod(r, r, m, ctx);
3171 }
3172
3173 /* BN_mod_sub variant that may be used if both a and b are non-negative
3174 * and less than m
3175 */
3176 int
3177 BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m)
3178 {
3179 if (!BN_sub(r, a, b))
3180 return 0;
3181 if (r->neg)
3182 return BN_add(r, r, m);
3183 return 1;
3184 }
3185 #endif /* NOT_NEEDED_FOR_DH */
3186
3187 #ifdef BCMDH_TEST
3188 /* slow but works */
3189 int
3190 BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, BN_CTX *ctx)
3191 {
3192 BIGNUM *t;
3193 int ret = 0;
3194
3195 bn_check_top(a);
3196 bn_check_top(b);
3197 bn_check_top(m);
3198
3199 BN_CTX_start(ctx);
3200 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
3201 if (a == b) { if (!BN_sqr(t, a, ctx)) goto err; }
3202 else { if (!BN_mul(t, a, b, ctx)) goto err; }
3203 if (!BN_nnmod(r, t, m, ctx)) goto err;
3204 ret = 1;
3205 err:
3206 BN_CTX_end(ctx);
3207 return (ret);
3208 }
3209 #endif /* BCMDH_TEST */
3210
3211
3212 #ifdef NOT_NEEDED_FOR_DH
3213 int
3214 BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
3215 {
3216 if (!BN_sqr(r, a, ctx)) return 0;
3217 /* r->neg == 0, thus we don't need BN_nnmod */
3218 return BN_mod(r, r, m, ctx);
3219 }
3220
3221
3222 int
3223 BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx)
3224 {
3225 if (!BN_lshift1(r, a))
3226 return 0;
3227 return BN_nnmod(r, r, m, ctx);
3228 }
3229
3230
3231 /* BN_mod_lshift1 variant that may be used if a is non-negative
3232 * and less than m
3233 */
3234 int
3235 BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m)
3236 {
3237 if (!BN_lshift1(r, a)) return 0;
3238 if (BN_cmp(r, m) >= 0)
3239 return BN_sub(r, r, m);
3240 return 1;
3241 }
3242
3243
3244 int
3245 BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, BN_CTX *ctx)
3246 {
3247 BIGNUM *abs_m = NULL;
3248 int ret;
3249
3250 if (!BN_nnmod(r, a, m, ctx))
3251 return 0;
3252
3253 if (m->neg) {
3254 abs_m = BN_dup(m);
3255 if (abs_m == NULL) return 0;
3256 abs_m->neg = 0;
3257 }
3258
3259 ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m));
3260
3261 if (abs_m)
3262 BN_free(abs_m);
3263 return ret;
3264 }
3265
3266
3267 /* BN_mod_lshift variant that may be used if a is non-negative
3268 * and less than m
3269 */
3270 int
3271 BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m)
3272 {
3273 if (r != a) {
3274 if (BN_copy(r, a) == NULL) return 0;
3275 }
3276
3277 while (n > 0) {
3278 int max_shift;
3279
3280 /* 0 < r < m */
3281 max_shift = BN_num_bits(m) - BN_num_bits(r);
3282 /* max_shift >= 0 */
3283
3284 if (max_shift < 0) {
3285 BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED);
3286 return 0;
3287 }
3288
3289 if (max_shift > n)
3290 max_shift = n;
3291
3292 if (max_shift) {
3293 if (!BN_lshift(r, r, max_shift)) return 0;
3294 n -= max_shift;
3295 } else {
3296 if (!BN_lshift1(r, r)) return 0;
3297 --n;
3298 }
3299
3300 /* BN_num_bits(r) <= BN_num_bits(m) */
3301
3302 if (BN_cmp(r, m) >= 0) {
3303 if (!BN_sub(r, r, m)) return 0;
3304 }
3305 }
3306
3307 return 1;
3308 }
3309 #endif /* NOT_NEEDED_FOR_DH */
3310
3311 /*
3312 * Details about Montgomery multiplication algorithms can be found at
3313 * http://security.ece.orst.edu/publications.html, e.g.
3314 * http://security.ece.orst.edu/koc/papers/j37acmon.pdf and
3315 * sections 3.8 and 4.2 in http://security.ece.orst.edu/koc/papers/r01rsasw.pdf
3316 */
3317
3318
3319 #define MONT_WORD /* use the faster word-based algorithm */
3320
3321 int
3322 BN_mod_mul_montgomery(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_MONT_CTX *mont, BN_CTX *ctx)
3323 {
3324 BIGNUM *tmp;
3325 int ret = 0;
3326
3327 BN_CTX_start(ctx);
3328 tmp = BN_CTX_get(ctx);
3329 if (tmp == NULL) goto err;
3330
3331 bn_check_top(tmp);
3332 if (a == b) {
3333 if (!BN_sqr(tmp, a, ctx)) goto err;
3334 } else {
3335 if (!BN_mul(tmp, a, b, ctx)) goto err;
3336 }
3337 /* reduce from aRR to aR */
3338 if (!BN_from_montgomery(r, tmp, mont, ctx)) goto err;
3339 ret = 1;
3340 err:
3341 BN_CTX_end(ctx);
3342 return (ret);
3343 }
3344
3345 int
3346 BN_from_montgomery(BIGNUM *ret, const BIGNUM *a, BN_MONT_CTX *mont, BN_CTX *ctx)
3347 {
3348 int retn = 0;
3349
3350 #ifdef MONT_WORD
3351 BIGNUM *n, *r;
3352 BN_ULONG *ap, *np, *rp, n0, v, *nrp;
3353 int al, nl, max, i, x, ri;
3354
3355 BN_CTX_start(ctx);
3356 if ((r = BN_CTX_get(ctx)) == NULL) goto err;
3357
3358 if (!BN_copy(r, a)) goto err;
3359 n = &(mont->N);
3360
3361 ap = a->d;
3362 /* mont->ri is the size of mont->N in bits (rounded up
3363 * to the word size)
3364 */
3365 al = ri = mont->ri/BN_BITS2;
3366
3367 nl = n->top;
3368 if ((al == 0) || (nl == 0)) {
3369 r->top = 0;
3370 return (1);
3371 }
3372
3373 max = (nl + al + 1);
3374 if (bn_wexpand(r, max) == NULL)
3375 goto err;
3376 if (bn_wexpand(ret, max) == NULL)
3377 goto err;
3378
3379 r->neg = a->neg^n->neg;
3380 np = n->d;
3381 rp = r->d;
3382 nrp = &(r->d[nl]);
3383
3384 /* clear the top words of T */
3385 for (i = r->top; i < max; i++)
3386 r->d[i] = 0;
3387
3388 r->top = max;
3389 n0 = mont->n0;
3390
3391 #ifdef BN_COUNT
3392 fprintf(stderr, "word BN_from_montgomery %d * %d\n", nl, nl);
3393 #endif
3394 for (i = 0; i < nl; i++) {
3395 #ifdef __TANDEM
3396 {
3397 long long t1;
3398 long long t2;
3399 long long t3;
3400 t1 = rp[0] * (n0 & 0177777);
3401 t2 = 037777600000l;
3402 t2 = n0 & t2;
3403 t3 = rp[0] & 0177777;
3404 t2 = (t3 * t2) & BN_MASK2;
3405 t1 = t1 + t2;
3406 v = bn_mul_add_words(rp, np, nl, (BN_ULONG) t1);
3407 }
3408 #else
3409 v = bn_mul_add_words(rp, np, nl, (rp[0]*n0)&BN_MASK2);
3410 #endif
3411 nrp++;
3412 rp++;
3413 if (((nrp[-1] += v)&BN_MASK2) >= v)
3414 continue;
3415 else {
3416 if (((++nrp[0])&BN_MASK2) != 0) continue;
3417 if (((++nrp[1])&BN_MASK2) != 0) continue;
3418 for (x = 2; (((++nrp[x]) & BN_MASK2) == 0); x++)
3419 ;
3420 }
3421 }
3422 bn_fix_top(r);
3423
3424 /* mont->ri will be a multiple of the word size */
3425 ret->neg = r->neg;
3426 x = ri;
3427 rp = ret->d;
3428 ap = &(r->d[x]);
3429 if (r->top < x)
3430 al = 0;
3431 else
3432 al = r->top-x;
3433 ret->top = al;
3434 al -= 4;
3435 for (i = 0; i < al; i += 4) {
3436 BN_ULONG t1, t2, t3, t4;
3437
3438 t1 = ap[i+0];
3439 t2 = ap[i+1];
3440 t3 = ap[i+2];
3441 t4 = ap[i+3];
3442 rp[i+0] = t1;
3443 rp[i+1] = t2;
3444 rp[i+2] = t3;
3445 rp[i+3] = t4;
3446 }
3447 al += 4;
3448 for (; i < al; i++)
3449 rp[i] = ap[i];
3450 #else /* !MONT_WORD */
3451 BIGNUM *t1, *t2;
3452
3453 BN_CTX_start(ctx);
3454 t1 = BN_CTX_get(ctx);
3455 t2 = BN_CTX_get(ctx);
3456 if (t1 == NULL || t2 == NULL) goto err;
3457
3458 if (!BN_copy(t1, a)) goto err;
3459 BN_mask_bits(t1, mont->ri);
3460
3461 if (!BN_mul(t2, t1, &mont->Ni, ctx)) goto err;
3462 BN_mask_bits(t2, mont->ri);
3463
3464 if (!BN_mul(t1, t2, &mont->N, ctx)) goto err;
3465 if (!BN_add(t2, a, t1)) goto err;
3466 if (!BN_rshift(ret, t2, mont->ri)) goto err;
3467 #endif /* MONT_WORD */
3468
3469 if (BN_ucmp(ret, &(mont->N)) >= 0) {
3470 if (!BN_usub(ret, ret, &(mont->N))) goto err;
3471 }
3472 retn = 1;
3473 err:
3474 BN_CTX_end(ctx);
3475 return (retn);
3476 }
3477
3478 BN_MONT_CTX *
3479 BN_MONT_CTX_new(void)
3480 {
3481 BN_MONT_CTX *ret;
3482
3483 if ((ret = (BN_MONT_CTX *)OPENSSL_malloc(sizeof(BN_MONT_CTX))) == NULL)
3484 return (NULL);
3485
3486 BN_MONT_CTX_init(ret);
3487 ret->flags = BN_FLG_MALLOCED;
3488 return (ret);
3489 }
3490
3491 void
3492 BN_MONT_CTX_init(BN_MONT_CTX *ctx)
3493 {
3494 ctx->ri = 0;
3495 BN_init(&(ctx->RR));
3496 BN_init(&(ctx->N));
3497 BN_init(&(ctx->Ni));
3498 ctx->flags = 0;
3499 }
3500
3501 void
3502 BN_MONT_CTX_free(BN_MONT_CTX *mont)
3503 {
3504 if (mont == NULL)
3505 return;
3506
3507 BN_free(&(mont->RR));
3508 BN_free(&(mont->N));
3509 BN_free(&(mont->Ni));
3510 if (mont->flags & BN_FLG_MALLOCED)
3511 OPENSSL_free(mont);
3512 }
3513
3514 int
3515 BN_MONT_CTX_set(BN_MONT_CTX *mont, const BIGNUM *mod, BN_CTX *ctx)
3516 {
3517 BIGNUM Ri, *R;
3518
3519 BN_init(&Ri);
3520 R = &(mont->RR); /* grab RR as a temp */
3521 BN_copy(&(mont->N), mod); /* Set N */
3522 mont->N.neg = 0;
3523
3524 #ifdef MONT_WORD
3525 {
3526 BIGNUM tmod;
3527 BN_ULONG buf[2];
3528
3529 mont->ri = (BN_num_bits(mod)+(BN_BITS2-1))/BN_BITS2*BN_BITS2;
3530 if (!(BN_zero(R))) goto err;
3531 if (!(BN_set_bit(R, BN_BITS2))) goto err; /* R */
3532
3533 buf[0] = mod->d[0]; /* tmod = N mod word size */
3534 buf[1] = 0;
3535 tmod.d = buf;
3536 tmod.top = 1;
3537 tmod.dmax = 2;
3538 tmod.neg = 0;
3539 /* Ri = R^-1 mod N */
3540 if ((BN_mod_inverse(&Ri, R, &tmod, ctx)) == NULL)
3541 goto err;
3542 if (!BN_lshift(&Ri, &Ri, BN_BITS2)) goto err; /* R*Ri */
3543 if (!BN_is_zero(&Ri)) {
3544 if (!BN_sub_word(&Ri, 1)) goto err;
3545 } else {
3546 /* if N mod word size == 1 */
3547 if (!BN_set_word(&Ri, BN_MASK2)) goto err; /* Ri-- (mod word size) */
3548 }
3549 if (!BN_div(&Ri, NULL, &Ri, &tmod, ctx)) goto err;
3550 /* Ni = (R*Ri-1)/N,
3551 * keep only least significant word:
3552 */
3553 mont->n0 = (Ri.top > 0) ? Ri.d[0] : 0;
3554 BN_free(&Ri);
3555 }
3556 #else /* !MONT_WORD */
3557 {
3558 /* bignum version */
3559 mont->ri = BN_num_bits(&mont->N);
3560 if (!BN_zero(R)) goto err;
3561 if (!BN_set_bit(R, mont->ri)) goto err; /* R = 2^ri */
3562 /* Ri = R^-1 mod N */
3563 if ((BN_mod_inverse(&Ri, R, &mont->N, ctx)) == NULL)
3564 goto err;
3565 if (!BN_lshift(&Ri, &Ri, mont->ri)) goto err; /* R*Ri */
3566 if (!BN_sub_word(&Ri, 1)) goto err;
3567 /* Ni = (R*Ri-1) / N */
3568 if (!BN_div(&(mont->Ni), NULL, &Ri, &mont->N, ctx)) goto err;
3569 BN_free(&Ri);
3570 }
3571 #endif /* MONT_WORD */
3572
3573 /* setup RR for conversions */
3574 if (!BN_zero(&(mont->RR))) goto err;
3575 if (!BN_set_bit(&(mont->RR), mont->ri*2)) goto err;
3576 if (!BN_mod(&(mont->RR), &(mont->RR), &(mont->N), ctx)) goto err;
3577
3578 return (1);
3579 err:
3580 return (0);
3581 }
3582
3583 #ifdef NOT_NEEDED_FOR_DH
3584 BN_MONT_CTX *
3585 BN_MONT_CTX_copy(BN_MONT_CTX *to, BN_MONT_CTX *from)
3586 {
3587 if (to == from) return (to);
3588
3589 if (!BN_copy(&(to->RR), &(from->RR))) return NULL;
3590 if (!BN_copy(&(to->N), &(from->N))) return NULL;
3591 if (!BN_copy(&(to->Ni), &(from->Ni))) return NULL;
3592 to->ri = from->ri;
3593 to->n0 = from->n0;
3594 return (to);
3595 }
3596 #endif /* NOT_NEEDED_FOR_DH */
3597
3598
3599 #ifdef BN_RECURSION
3600 /* Karatsuba recursive multiplication algorithm
3601 * (cf. Knuth, The Art of Computer Programming, Vol. 2)
3602 */
3603
3604 /* r is 2*n2 words in size,
3605 * a and b are both n2 words in size.
3606 * n2 must be a power of 2.
3607 * We multiply and return the result.
3608 * t must be 2*n2 words in size
3609 * We calculate
3610 * a[0]*b[0]
3611 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
3612 * a[1]*b[1]
3613 */
3614 void
3615 bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t)
3616 {
3617 int n = n2/2, c1, c2;
3618 unsigned int neg, zero;
3619 BN_ULONG ln, lo, *p;
3620
3621 #ifdef BN_COUNT
3622 printf(" bn_mul_recursive %d * %d\n", n2, n2);
3623 #endif
3624 #ifdef BN_MUL_COMBA
3625 if (n2 == 8) {
3626 bn_mul_comba8(r, a, b);
3627 return;
3628 }
3629 #endif /* BN_MUL_COMBA */
3630 if (n2 < BN_MUL_RECURSIVE_SIZE_NORMAL) {
3631 /* This should not happen */
3632 bn_mul_normal(r, a, n2, b, n2);
3633 return;
3634 }
3635 /* r = (a[0]-a[1])*(b[1]-b[0]) */
3636 c1 = bn_cmp_words(a, &(a[n]), n);
3637 c2 = bn_cmp_words(&(b[n]), b, n);
3638 zero = neg = 0;
3639 switch (c1*3+c2) {
3640 case -4:
3641 bn_sub_words(t, &(a[n]), a, n); /* - */
3642 bn_sub_words(&(t[n]), b, &(b[n]), n); /* - */
3643 break;
3644 case -3:
3645 zero = 1;
3646 break;
3647 case -2:
3648 bn_sub_words(t, &(a[n]), a, n); /* - */
3649 bn_sub_words(&(t[n]), &(b[n]), b, n); /* + */
3650 neg = 1;
3651 break;
3652 case -1:
3653 case 0:
3654 case 1:
3655 zero = 1;
3656 break;
3657 case 2:
3658 bn_sub_words(t, a, &(a[n]), n); /* + */
3659 bn_sub_words(&(t[n]), b, &(b[n]), n); /* - */
3660 neg = 1;
3661 break;
3662 case 3:
3663 zero = 1;
3664 break;
3665 case 4:
3666 bn_sub_words(t, a, &(a[n]), n);
3667 bn_sub_words(&(t[n]), &(b[n]), b, n);
3668 break;
3669 }
3670
3671 # ifdef BN_MUL_COMBA
3672 if (n == 4) {
3673 if (!zero)
3674 bn_mul_comba4(&(t[n2]), t, &(t[n]));
3675 else
3676 memset(&(t[n2]), 0, 8*sizeof(BN_ULONG));
3677
3678 bn_mul_comba4(r, a, b);
3679 bn_mul_comba4(&(r[n2]), &(a[n]), &(b[n]));
3680 } else if (n == 8) {
3681 if (!zero)
3682 bn_mul_comba8(&(t[n2]), t, &(t[n]));
3683 else
3684 memset(&(t[n2]), 0, 16*sizeof(BN_ULONG));
3685
3686 bn_mul_comba8(r, a, b);
3687 bn_mul_comba8(&(r[n2]), &(a[n]), &(b[n]));
3688 } else
3689 # endif /* BN_MUL_COMBA */
3690 {
3691 p = &(t[n2*2]);
3692 if (!zero)
3693 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, p);
3694 else
3695 memset(&(t[n2]), 0, n2*sizeof(BN_ULONG));
3696 bn_mul_recursive(r, a, b, n, p);
3697 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), n, p);
3698 }
3699
3700 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
3701 * r[10] holds (a[0]*b[0])
3702 * r[32] holds (b[1]*b[1])
3703 */
3704
3705 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
3706
3707 if (neg) {
3708 /* if t[32] is negative */
3709 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
3710 } else {
3711 /* Might have a carry */
3712 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
3713 }
3714
3715 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
3716 * r[10] holds (a[0]*b[0])
3717 * r[32] holds (b[1]*b[1])
3718 * c1 holds the carry bits
3719 */
3720 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
3721 if (c1) {
3722 p = &(r[n+n2]);
3723 lo = *p;
3724 ln = (lo+c1)&BN_MASK2;
3725 *p = ln;
3726
3727 /* The overflow will stop before we over write
3728 * words we should not overwrite
3729 */
3730 if (ln < (BN_ULONG)c1) {
3731 do {
3732 p++;
3733 lo = *p;
3734 ln = (lo+1)&BN_MASK2;
3735 *p = ln;
3736 } while (ln == 0);
3737 }
3738 }
3739 }
3740
3741 /* n+tn is the word length
3742 * t needs to be n*4 is size, as does r
3743 */
3744 void
3745 bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int tn, int n, BN_ULONG *t)
3746 {
3747 int i, j, n2 = n*2;
3748 int c1, c2, neg, zero;
3749 BN_ULONG ln, lo, *p;
3750
3751 # ifdef BN_COUNT
3752 printf(" bn_mul_part_recursive %d * %d\n", tn+n, tn+n);
3753 # endif
3754 if (n < 8) {
3755 i = tn+n;
3756 bn_mul_normal(r, a, i, b, i);
3757 return;
3758 }
3759
3760 /* r = (a[0]-a[1])*(b[1]-b[0]) */
3761 c1 = bn_cmp_words(a, &(a[n]), n);
3762 c2 = bn_cmp_words(&(b[n]), b, n);
3763 zero = neg = 0;
3764 switch (c1 * 3 + c2) {
3765 case -4:
3766 bn_sub_words(t, &(a[n]), a, n); /* - */
3767 bn_sub_words(&(t[n]), b, &(b[n]), n); /* - */
3768 break;
3769 case -3:
3770 zero = 1;
3771 /* break; */
3772 case -2:
3773 bn_sub_words(t, &(a[n]), a, n); /* - */
3774 bn_sub_words(&(t[n]), &(b[n]), b, n); /* + */
3775 neg = 1;
3776 break;
3777 case -1:
3778 case 0:
3779 case 1:
3780 zero = 1;
3781 /* break; */
3782 case 2:
3783 bn_sub_words(t, a, &(a[n]), n); /* + */
3784 bn_sub_words(&(t[n]), b, &(b[n]), n); /* - */
3785 neg = 1;
3786 break;
3787 case 3:
3788 zero = 1;
3789 /* break; */
3790 case 4:
3791 bn_sub_words(t, a, &(a[n]), n);
3792 bn_sub_words(&(t[n]), &(b[n]), b, n);
3793 break;
3794 }
3795 /* The zero case isn't yet implemented here. The speedup
3796 * would probably be negligible.
3797 */
3798 if (n == 8) {
3799 bn_mul_comba8(&(t[n2]), t, &(t[n]));
3800 bn_mul_comba8(r, a, b);
3801 bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
3802 memset(&(r[n2+tn*2]), 0, sizeof(BN_ULONG)*(n2-tn*2));
3803 } else {
3804 p = &(t[n2*2]);
3805 bn_mul_recursive(&(t[n2]), t, &(t[n]), n, p);
3806 bn_mul_recursive(r, a, b, n, p);
3807 i = n/2;
3808 /* If there is only a bottom half to the number,
3809 * just do it
3810 */
3811 j = tn-i;
3812 if (j == 0) {
3813 bn_mul_recursive(&(r[n2]), &(a[n]), &(b[n]), i, p);
3814 memset(&(r[n2+i*2]), 0, sizeof(BN_ULONG)*(n2-i*2));
3815 } else if (j > 0) {
3816 /* eg, n == 16, i == 8 and tn == 11 */
3817 bn_mul_part_recursive(&(r[n2]), &(a[n]), &(b[n]), j, i, p);
3818 memset(&(r[n2+tn*2]), 0, sizeof(BN_ULONG)*(n2-tn*2));
3819 } else {
3820 /* (j < 0) eg, n == 16, i == 8 and tn == 5 */
3821 memset(&(r[n2]), 0, sizeof(BN_ULONG)*n2);
3822 if (tn < BN_MUL_RECURSIVE_SIZE_NORMAL) {
3823 bn_mul_normal(&(r[n2]), &(a[n]), tn, &(b[n]), tn);
3824 } else {
3825 for (;;) {
3826 i /= 2;
3827 if (i < tn) {
3828 bn_mul_part_recursive(&(r[n2]),
3829 &(a[n]), &(b[n]),
3830 tn-i, i, p);
3831 break;
3832 } else if (i == tn) {
3833 bn_mul_recursive(&(r[n2]),
3834 &(a[n]), &(b[n]),
3835 i, p);
3836 break;
3837 }
3838 }
3839 }
3840 }
3841 }
3842
3843 /* t[32] holds (a[0]-a[1])*(b[1]-b[0]), c1 is the sign
3844 * r[10] holds (a[0]*b[0])
3845 * r[32] holds (b[1]*b[1])
3846 */
3847
3848 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
3849
3850 if (neg) /* if t[32] is negative */ {
3851 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
3852 } else {
3853 /* Might have a carry */
3854 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), t, n2));
3855 }
3856
3857 /* t[32] holds (a[0]-a[1])*(b[1]-b[0])+(a[0]*b[0])+(a[1]*b[1])
3858 * r[10] holds (a[0]*b[0])
3859 * r[32] holds (b[1]*b[1])
3860 * c1 holds the carry bits
3861 */
3862 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
3863 if (c1) {
3864 p = &(r[n+n2]);
3865 lo = *p;
3866 ln = (lo+c1)&BN_MASK2;
3867 *p = ln;
3868
3869 /* The overflow will stop before we over write
3870 * words we should not overwrite
3871 */
3872 if (ln < (BN_ULONG)c1) {
3873 do {
3874 p++;
3875 lo = *p;
3876 ln = (lo+1)&BN_MASK2;
3877 *p = ln;
3878 } while (ln == 0);
3879 }
3880 }
3881 }
3882
3883 #ifdef NOT_NEEDED_FOR_DH
3884 /* a and b must be the same size, which is n2.
3885 * r needs to be n2 words and t needs to be n2*2
3886 */
3887 void
3888 bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, BN_ULONG *t)
3889 {
3890 int n = n2/2;
3891
3892 # ifdef BN_COUNT
3893 printf(" bn_mul_low_recursive %d * %d\n", n2, n2);
3894 # endif
3895
3896 bn_mul_recursive(r, a, b, n, &(t[0]));
3897 if (n >= BN_MUL_LOW_RECURSIVE_SIZE_NORMAL) {
3898 bn_mul_low_recursive(&(t[0]), &(a[0]), &(b[n]), n, &(t[n2]));
3899 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
3900 bn_mul_low_recursive(&(t[0]), &(a[n]), &(b[0]), n, &(t[n2]));
3901 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
3902 } else {
3903 bn_mul_low_normal(&(t[0]), &(a[0]), &(b[n]), n);
3904 bn_mul_low_normal(&(t[n]), &(a[n]), &(b[0]), n);
3905 bn_add_words(&(r[n]), &(r[n]), &(t[0]), n);
3906 bn_add_words(&(r[n]), &(r[n]), &(t[n]), n);
3907 }
3908 }
3909 #endif /* NOT_NEEDED_FOR_DH */
3910
3911 /* a and b must be the same size, which is n2.
3912 * r needs to be n2 words and t needs to be n2*2
3913 * l is the low words of the output.
3914 * t needs to be n2*3
3915 */
3916 void
3917 bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, BN_ULONG *t)
3918 {
3919 int i, n;
3920 int c1, c2;
3921 int neg, oneg, zero;
3922 BN_ULONG ll, lc, *lp, *mp;
3923
3924 # ifdef BN_COUNT
3925 printf(" bn_mul_high %d * %d\n", n2, n2);
3926 # endif
3927 n = n2 / 2;
3928
3929 /* Calculate (al - ah) * (bh - bl) */
3930 neg = zero = 0;
3931 c1 = bn_cmp_words(&(a[0]), &(a[n]), n);
3932 c2 = bn_cmp_words(&(b[n]), &(b[0]), n);
3933 switch (c1 * 3 + c2) {
3934 case -4:
3935 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
3936 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
3937 break;
3938 case -3:
3939 zero = 1;
3940 break;
3941 case -2:
3942 bn_sub_words(&(r[0]), &(a[n]), &(a[0]), n);
3943 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
3944 neg = 1;
3945 break;
3946 case -1:
3947 case 0:
3948 case 1:
3949 zero = 1;
3950 break;
3951 case 2:
3952 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
3953 bn_sub_words(&(r[n]), &(b[0]), &(b[n]), n);
3954 neg = 1;
3955 break;
3956 case 3:
3957 zero = 1;
3958 break;
3959 case 4:
3960 bn_sub_words(&(r[0]), &(a[0]), &(a[n]), n);
3961 bn_sub_words(&(r[n]), &(b[n]), &(b[0]), n);
3962 break;
3963 }
3964
3965 oneg = neg;
3966 /* t[10] = (a[0]-a[1])*(b[1]-b[0]) */
3967 /* r[10] = (a[1]*b[1]) */
3968 # ifdef BN_MUL_COMBA
3969 if (n == 8) {
3970 bn_mul_comba8(&(t[0]), &(r[0]), &(r[n]));
3971 bn_mul_comba8(r, &(a[n]), &(b[n]));
3972 } else
3973 # endif
3974 {
3975 bn_mul_recursive(&(t[0]), &(r[0]), &(r[n]), n, &(t[n2]));
3976 bn_mul_recursive(r, &(a[n]), &(b[n]), n, &(t[n2]));
3977 }
3978
3979 /* s0 == low(al*bl)
3980 * s1 == low(ah*bh)+low((al-ah)*(bh-bl))+low(al*bl)+high(al*bl)
3981 * We know s0 and s1 so the only unknown is high(al*bl)
3982 * high(al*bl) == s1 - low(ah*bh+s0+(al-ah)*(bh-bl))
3983 * high(al*bl) == s1 - (r[0]+l[0]+t[0])
3984 */
3985 if (l != NULL) {
3986 lp = &(t[n2+n]);
3987 c1 = (int)(bn_add_words(lp, &(r[0]), &(l[0]), n));
3988 } else {
3989 c1 = 0;
3990 lp = &(r[0]);
3991 }
3992
3993 if (neg)
3994 neg = (int)(bn_sub_words(&(t[n2]), lp, &(t[0]), n));
3995 else {
3996 bn_add_words(&(t[n2]), lp, &(t[0]), n);
3997 neg = 0;
3998 }
3999
4000 if (l != NULL) {
4001 bn_sub_words(&(t[n2+n]), &(l[n]), &(t[n2]), n);
4002 } else {
4003 lp = &(t[n2+n]);
4004 mp = &(t[n2]);
4005 for (i = 0; i < n; i++)
4006 lp[i] = ((~mp[i])+1)&BN_MASK2;
4007 }
4008
4009 /* s[0] = low(al*bl)
4010 * t[3] = high(al*bl)
4011 * t[10] = (a[0]-a[1])*(b[1]-b[0]) neg is the sign
4012 * r[10] = (a[1]*b[1])
4013 */
4014 /* R[10] = al*bl
4015 * R[21] = al*bl + ah*bh + (a[0]-a[1])*(b[1]-b[0])
4016 * R[32] = ah*bh
4017 */
4018 /* R[1] = t[3]+l[0]+r[0](+-)t[0] (have carry/borrow)
4019 * R[2] = r[0]+t[3]+r[1](+-)t[1] (have carry/borrow)
4020 * R[3] = r[1]+(carry/borrow)
4021 */
4022 if (l != NULL) {
4023 lp = &(t[n2]);
4024 c1 = (int)(bn_add_words(lp, &(t[n2+n]), &(l[0]), n));
4025 } else {
4026 lp = &(t[n2+n]);
4027 c1 = 0;
4028 }
4029 c1 += (int)(bn_add_words(&(t[n2]), lp, &(r[0]), n));
4030 if (oneg)
4031 c1 -= (int)(bn_sub_words(&(t[n2]), &(t[n2]), &(t[0]), n));
4032 else
4033 c1 += (int)(bn_add_words(&(t[n2]), &(t[n2]), &(t[0]), n));
4034
4035 c2 = (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n2+n]), n));
4036 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(r[n]), n));
4037 if (oneg)
4038 c2 -= (int)(bn_sub_words(&(r[0]), &(r[0]), &(t[n]), n));
4039 else
4040 c2 += (int)(bn_add_words(&(r[0]), &(r[0]), &(t[n]), n));
4041
4042 if (c1 != 0) {
4043 /* Add starting at r[0], could be +ve or -ve */
4044 i = 0;
4045 if (c1 > 0) {
4046 lc = c1;
4047 do {
4048 ll = (r[i]+lc)&BN_MASK2;
4049 r[i++] = ll;
4050 lc = (lc > ll);
4051 } while (lc);
4052 } else {
4053 lc = -c1;
4054 do {
4055 ll = r[i];
4056 r[i++] = (ll-lc)&BN_MASK2;
4057 lc = (lc > ll);
4058 } while (lc);
4059 }
4060 }
4061 if (c2 != 0) {
4062 /* Add starting at r[1] */
4063 i = n;
4064 if (c2 > 0) {
4065 lc = c2;
4066 do {
4067 ll = (r[i]+lc)&BN_MASK2;
4068 r[i++] = ll;
4069 lc = (lc > ll);
4070 } while (lc);
4071 } else {
4072 lc = -c2;
4073 do {
4074 ll = r[i];
4075 r[i++] = (ll-lc)&BN_MASK2;
4076 lc = (lc > ll);
4077 } while (lc);
4078 }
4079 }
4080 }
4081 #endif /* BN_RECURSION */
4082
4083 int
4084 BN_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx)
4085 {
4086 int top, al, bl;
4087 BIGNUM *rr;
4088 int ret = 0;
4089 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
4090 int i;
4091 #endif
4092 #ifdef BN_RECURSION
4093 BIGNUM *t;
4094 int j, k;
4095 #endif
4096
4097 #ifdef BN_COUNT
4098 printf("BN_mul %d * %d\n", a->top, b->top);
4099 #endif
4100
4101 bn_check_top(a);
4102 bn_check_top(b);
4103 bn_check_top(r);
4104
4105 al = a->top;
4106 bl = b->top;
4107
4108 if ((al == 0) || (bl == 0)) {
4109 if (!BN_zero(r)) goto err;
4110 return (1);
4111 }
4112 top = al+bl;
4113
4114 BN_CTX_start(ctx);
4115 if ((r == a) || (r == b)) {
4116 if ((rr = BN_CTX_get(ctx)) == NULL) goto err;
4117 } else
4118 rr = r;
4119 rr->neg = a->neg^b->neg;
4120
4121 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
4122 i = al-bl;
4123 #endif
4124 #ifdef BN_MUL_COMBA
4125 if (i == 0) {
4126 if (al == 8) {
4127 if (bn_wexpand(rr, 16) == NULL) goto err;
4128 rr->top = 16;
4129 bn_mul_comba8(rr->d, a->d, b->d);
4130 goto end;
4131 }
4132 }
4133 #endif /* BN_MUL_COMBA */
4134 #ifdef BN_RECURSION
4135 if ((al >= BN_MULL_SIZE_NORMAL) && (bl >= BN_MULL_SIZE_NORMAL)) {
4136 if (i == 1 && !BN_get_flags(b, BN_FLG_STATIC_DATA) && bl < b->dmax) {
4137 b->d[bl] = 0;
4138 bl++;
4139 i--;
4140 } else if (i == -1 && !BN_get_flags(a, BN_FLG_STATIC_DATA) && al < a->dmax) {
4141 a->d[al] = 0;
4142 al++;
4143 i++;
4144 }
4145 if (i == 0) {
4146 /* symmetric and > 4 */
4147 /* 16 or larger */
4148 j = BN_num_bits_word((BN_ULONG)al);
4149 j = 1 << (j - 1);
4150 k = j + j;
4151 t = BN_CTX_get(ctx);
4152 if (al == j) {
4153 /* exact multiple */
4154 if (bn_wexpand(t, k*2) == NULL) goto err;
4155 if (bn_wexpand(rr, k*2) == NULL) goto err;
4156 bn_mul_recursive(rr->d, a->d, b->d, al, t->d);
4157 rr->top = top;
4158 goto end;
4159 }
4160 }
4161 }
4162 #endif /* BN_RECURSION */
4163 if (bn_wexpand(rr, top) == NULL) goto err;
4164 rr->top = top;
4165 bn_mul_normal(rr->d, a->d, al, b->d, bl);
4166
4167 #if defined(BN_MUL_COMBA) || defined(BN_RECURSION)
4168 end:
4169 #endif
4170 bn_fix_top(rr);
4171 if (r != rr) BN_copy(r, rr);
4172 ret = 1;
4173 err:
4174 BN_CTX_end(ctx);
4175 return (ret);
4176 }
4177
4178 void
4179 bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb)
4180 {
4181 BN_ULONG *rr;
4182
4183 #ifdef BN_COUNT
4184 printf(" bn_mul_normal %d * %d\n", na, nb);
4185 #endif
4186
4187 if (na < nb) {
4188 int itmp;
4189 BN_ULONG *ltmp;
4190
4191 itmp = na; na = nb; nb = itmp;
4192 ltmp = a; a = b; b = ltmp;
4193 }
4194 rr = &(r[na]);
4195 rr[0] = bn_mul_words(r, a, na, b[0]);
4196
4197 for (;;) {
4198 if (--nb <= 0) return;
4199 rr[1] = bn_mul_add_words(&(r[1]), a, na, b[1]);
4200 if (--nb <= 0) return;
4201 rr[2] = bn_mul_add_words(&(r[2]), a, na, b[2]);
4202 if (--nb <= 0) return;
4203 rr[3] = bn_mul_add_words(&(r[3]), a, na, b[3]);
4204 if (--nb <= 0) return;
4205 rr[4] = bn_mul_add_words(&(r[4]), a, na, b[4]);
4206 rr += 4;
4207 r += 4;
4208 b += 4;
4209 }
4210 }
4211
4212 #ifdef NOT_NEEDED_FOR_DH
4213 void
4214 bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n)
4215 {
4216 #ifdef BN_COUNT
4217 printf(" bn_mul_low_normal %d * %d\n", n, n);
4218 #endif
4219 bn_mul_words(r, a, n, b[0]);
4220
4221 for (;;) {
4222 if (--n <= 0) return;
4223 bn_mul_add_words(&(r[1]), a, n, b[1]);
4224 if (--n <= 0) return;
4225 bn_mul_add_words(&(r[2]), a, n, b[2]);
4226 if (--n <= 0) return;
4227 bn_mul_add_words(&(r[3]), a, n, b[3]);
4228 if (--n <= 0) return;
4229 bn_mul_add_words(&(r[4]), a, n, b[4]);
4230 r += 4;
4231 b += 4;
4232 }
4233 }
4234 #endif /* NOT_NEEDED_FOR_DH */
4235
4236 static int
4237 bnrand(int pseudorand, BIGNUM *rnd, int bits, int top, int bottom)
4238 {
4239 unsigned char *buf = NULL;
4240 int ret = 0, bit, bytes, mask;
4241
4242 if (bits == 0) {
4243 BN_zero(rnd);
4244 return 1;
4245 }
4246
4247 bytes = (bits + 7) / 8;
4248 bit = (bits - 1) % 8;
4249 mask = 0xff << (bit + 1);
4250
4251 buf = (unsigned char *)OPENSSL_malloc(bytes);
4252 if (buf == NULL) {
4253 BNerr(BN_F_BN_RAND, ERR_R_MALLOC_FAILURE);
4254 goto err;
4255 }
4256
4257
4258 assert(bn_rand_fn);
4259 bn_rand_fn(buf, bytes);
4260
4261 if (pseudorand == 2) {
4262 /* generate patterns that are more likely to trigger BN
4263 * library bugs
4264 */
4265 int i;
4266 unsigned char c;
4267
4268 for (i = 0; i < bytes; i++) {
4269 /* RAND_pseudo_bytes(&c, 1); */
4270 bn_rand_fn(&c, 1);
4271 if (c >= 128 && i > 0)
4272 buf[i] = buf[i-1];
4273 else if (c < 42)
4274 buf[i] = 0;
4275 else if (c < 84)
4276 buf[i] = 255;
4277 }
4278 }
4279
4280 if (top != -1) {
4281 if (top) {
4282 if (bit == 0) {
4283 buf[0] = 1;
4284 buf[1] |= 0x80;
4285 } else {
4286 buf[0] |= (3 << (bit - 1));
4287 }
4288 } else {
4289 buf[0] |= (1 << bit);
4290 }
4291 }
4292 buf[0] &= ~mask;
4293 if (bottom) /* set bottom bit if requested */
4294 buf[bytes-1] |= 1;
4295 if (!BN_bin2bn(buf, bytes, rnd)) goto err;
4296 ret = 1;
4297 err:
4298 if (buf != NULL) {
4299 OPENSSL_cleanse(buf, bytes);
4300 OPENSSL_free(buf);
4301 }
4302 return (ret);
4303 }
4304
4305 int
4306 BN_rand(BIGNUM *rnd, int bits, int top, int bottom)
4307 {
4308 return bnrand(0, rnd, bits, top, bottom);
4309 }
4310
4311 #ifdef BCMDH_TEST
4312 int
4313 BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom)
4314 {
4315 return bnrand(1, rnd, bits, top, bottom);
4316 }
4317 #endif /* BCMDH_TEST */
4318
4319 #ifdef NOT_NEEDED_FOR_DH
4320 int
4321 BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom)
4322 {
4323 return bnrand(2, rnd, bits, top, bottom);
4324 }
4325 #endif /* NOT_NEEDED_FOR_DH */
4326
4327
4328 #ifdef BCMDH_TEST
4329 /* random number r: 0 <= r < range */
4330 static int
4331 bn_rand_range(int pseudo, BIGNUM *r, BIGNUM *range)
4332 {
4333 int (*bn_rand)(BIGNUM *, int, int, int) = pseudo ? BN_pseudo_rand : BN_rand;
4334 int n;
4335
4336 if (range->neg || BN_is_zero(range)) {
4337 BNerr(BN_F_BN_RAND_RANGE, BN_R_INVALID_RANGE);
4338 return 0;
4339 }
4340
4341 n = BN_num_bits(range); /* n > 0 */
4342
4343 /* BN_is_bit_set(range, n - 1) always holds */
4344
4345 if (n == 1) {
4346 if (!BN_zero(r)) return 0;
4347 } else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
4348 /* range = 100..._2,
4349 * so 3*range ( = 11..._2) is exactly one bit longer than range
4350 */
4351 do {
4352 if (!bn_rand(r, n + 1, -1, 0)) return 0;
4353 /* If r < 3*range, use r : = r MOD range
4354 * (which is either r, r - range, or r - 2*range).
4355 * Otherwise, iterate once more.
4356 * Since 3*range = 11..._2, each iteration succeeds with
4357 * probability >= .75.
4358 */
4359 if (BN_cmp(r, range) >= 0) {
4360 if (!BN_sub(r, r, range)) return 0;
4361 if (BN_cmp(r, range) >= 0)
4362 if (!BN_sub(r, r, range)) return 0;
4363 }
4364 }
4365 while (BN_cmp(r, range) >= 0)
4366 ;
4367 } else {
4368 do {
4369 /* range = 11..._2 or range = 101..._2 */
4370 if (!bn_rand(r, n, -1, 0))
4371 return 0;
4372 } while (BN_cmp(r, range) >= 0);
4373 }
4374
4375 return 1;
4376 }
4377 #endif /* BCMDH_TEST */
4378
4379 #ifdef NOT_NEEDED_FOR_DH
4380 int
4381 BN_rand_range(BIGNUM *r, BIGNUM *range)
4382 {
4383 return bn_rand_range(0, r, range);
4384 }
4385 #endif /* NOT_NEEDED_FOR_DH */
4386
4387 #ifdef BCMDH_TEST
4388 int
4389 BN_pseudo_rand_range(BIGNUM *r, BIGNUM *range)
4390 {
4391 return bn_rand_range(1, r, range);
4392 }
4393 #endif /* BCMDH_TEST */
4394
4395 #ifdef NOT_NEEDED_FOR_DH
4396 void
4397 BN_RECP_CTX_init(BN_RECP_CTX *recp)
4398 {
4399 BN_init(&(recp->N));
4400 BN_init(&(recp->Nr));
4401 recp->num_bits = 0;
4402 recp->flags = 0;
4403 }
4404
4405 BN_RECP_CTX *
4406 BN_RECP_CTX_new(void)
4407 {
4408 BN_RECP_CTX *ret;
4409
4410 if ((ret = (BN_RECP_CTX *)OPENSSL_malloc(sizeof(BN_RECP_CTX))) == NULL)
4411 return (NULL);
4412
4413 BN_RECP_CTX_init(ret);
4414 ret->flags = BN_FLG_MALLOCED;
4415 return (ret);
4416 }
4417
4418 void
4419 BN_RECP_CTX_free(BN_RECP_CTX *recp)
4420 {
4421 if (recp == NULL)
4422 return;
4423
4424 BN_free(&(recp->N));
4425 BN_free(&(recp->Nr));
4426 if (recp->flags & BN_FLG_MALLOCED)
4427 OPENSSL_free(recp);
4428 }
4429
4430 int
4431 BN_RECP_CTX_set(BN_RECP_CTX *recp, const BIGNUM *d, BN_CTX *ctx)
4432 {
4433 if (!BN_copy(&(recp->N), d)) return 0;
4434 if (!BN_zero(&(recp->Nr))) return 0;
4435 recp->num_bits = BN_num_bits(d);
4436 recp->shift = 0;
4437 return (1);
4438 }
4439
4440 int
4441 BN_mod_mul_reciprocal(BIGNUM *r, const BIGNUM *x, const BIGNUM *y,
4442 BN_RECP_CTX *recp, BN_CTX *ctx)
4443 {
4444 int ret = 0;
4445 BIGNUM *a;
4446 const BIGNUM *ca;
4447
4448 BN_CTX_start(ctx);
4449 if ((a = BN_CTX_get(ctx)) == NULL)
4450 goto err;
4451 if (y != NULL) {
4452 if (x == y) {
4453 if (!BN_sqr(a, x, ctx))
4454 goto err;
4455 } else {
4456 if (!BN_mul(a, x, y, ctx))
4457 goto err;
4458 }
4459 ca = a;
4460 } else
4461 ca = x; /* Just do the mod */
4462
4463 ret = BN_div_recp(NULL, r, ca, recp, ctx);
4464 err:
4465 BN_CTX_end(ctx);
4466 return (ret);
4467 }
4468
4469 int
4470 BN_div_recp(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, BN_RECP_CTX *recp, BN_CTX *ctx)
4471 {
4472 int i, j, ret = 0;
4473 BIGNUM *a, *b, *d, *r;
4474
4475 BN_CTX_start(ctx);
4476 a = BN_CTX_get(ctx);
4477 b = BN_CTX_get(ctx);
4478 if (dv != NULL)
4479 d = dv;
4480 else
4481 d = BN_CTX_get(ctx);
4482 if (rem != NULL)
4483 r = rem;
4484 else
4485 r = BN_CTX_get(ctx);
4486 if (a == NULL || b == NULL || d == NULL || r == NULL)
4487 goto err;
4488
4489 if (BN_ucmp(m, &(recp->N)) < 0) {
4490 if (!BN_zero(d)) return 0;
4491 if (!BN_copy(r, m)) return 0;
4492 BN_CTX_end(ctx);
4493 return (1);
4494 }
4495
4496 /* We want the remainder
4497 * Given input of ABCDEF / ab
4498 * we need multiply ABCDEF by 3 digests of the reciprocal of ab
4499 *
4500 */
4501
4502 /* i : = max(BN_num_bits(m), 2*BN_num_bits(N)) */
4503 i = BN_num_bits(m);
4504 j = recp->num_bits << 1;
4505 if (j > i) i = j;
4506
4507 /* Nr : = round(2^i / N) */
4508 if (i != recp->shift)
4509 recp->shift = BN_reciprocal(&(recp->Nr), &(recp->N),
4510 i, ctx); /* BN_reciprocal returns i, or -1 for an error */
4511 if (recp->shift == -1) goto err;
4512
4513 /* d : = |round(round(m / 2^BN_num_bits(N)) * recp->Nr / 2^(i - BN_num_bits(N)))|
4514 * = |round(round(m / 2^BN_num_bits(N)) * round(2^i / N) / 2^(i - BN_num_bits(N)))|
4515 * <= |(m / 2^BN_num_bits(N)) * (2^i / N) * (2^BN_num_bits(N) / 2^i)|
4516 * = |m/N|
4517 */
4518 if (!BN_rshift(a, m, recp->num_bits)) goto err;
4519 if (!BN_mul(b, a, &(recp->Nr), ctx)) goto err;
4520 if (!BN_rshift(d, b, i-recp->num_bits)) goto err;
4521 d->neg = 0;
4522
4523 if (!BN_mul(b, &(recp->N), d, ctx)) goto err;
4524 if (!BN_usub(r, m, b)) goto err;
4525 r->neg = 0;
4526
4527 j = 0;
4528 while (BN_ucmp(r, &(recp->N)) >= 0) {
4529 if (j++ > 2) {
4530 BNerr(BN_F_BN_MOD_MUL_RECIPROCAL, BN_R_BAD_RECIPROCAL);
4531 goto err;
4532 }
4533 if (!BN_usub(r, r, &(recp->N))) goto err;
4534 if (!BN_add_word(d, 1)) goto err;
4535 }
4536
4537 r->neg = BN_is_zero(r)?0:m->neg;
4538 d->neg = m->neg^recp->N.neg;
4539 ret = 1;
4540 err:
4541 BN_CTX_end(ctx);
4542 return (ret);
4543 }
4544
4545 /* len is the expected size of the result
4546 * We actually calculate with an extra word of precision, so
4547 * we can do faster division if the remainder is not required.
4548 */
4549 /* r : = 2^len / m */
4550 int
4551 BN_reciprocal(BIGNUM *r, const BIGNUM *m, int len, BN_CTX *ctx)
4552 {
4553 int ret = -1;
4554 BIGNUM t;
4555
4556 BN_init(&t);
4557
4558 if (!BN_zero(&t)) goto err;
4559 if (!BN_set_bit(&t, len)) goto err;
4560
4561 if (!BN_div(r, NULL, &t, m, ctx)) goto err;
4562
4563 ret = len;
4564 err:
4565 BN_free(&t);
4566 return (ret);
4567 }
4568 #endif /* NOT_NEEDED_FOR_DH */
4569
4570 int
4571 BN_lshift1(BIGNUM *r, const BIGNUM *a)
4572 {
4573 register BN_ULONG *ap, *rp, t, c;
4574 int i;
4575
4576 if (r != a) {
4577 r->neg = a->neg;
4578 if (bn_wexpand(r, a->top+1) == NULL) return (0);
4579 r->top = a->top;
4580 } else {
4581 if (bn_wexpand(r, a->top+1) == NULL) return (0);
4582 }
4583 ap = a->d;
4584 rp = r->d;
4585 c = 0;
4586 for (i = 0; i < a->top; i++) {
4587 t = *(ap++);
4588 *(rp++) = ((t << 1) | c) & BN_MASK2;
4589 c = (t & BN_TBIT)?1:0;
4590 }
4591 if (c) {
4592 *rp = 1;
4593 r->top++;
4594 }
4595 return (1);
4596 }
4597
4598 int
4599 BN_rshift1(BIGNUM *r, const BIGNUM *a)
4600 {
4601 BN_ULONG *ap, *rp, t, c;
4602 int i;
4603
4604 if (BN_is_zero(a)) {
4605 BN_zero(r);
4606 return (1);
4607 }
4608 if (a != r) {
4609 if (bn_wexpand(r, a->top) == NULL) return (0);
4610 r->top = a->top;
4611 r->neg = a->neg;
4612 }
4613 ap = a->d;
4614 rp = r->d;
4615 c = 0;
4616 for (i = a->top - 1; i >= 0; i--) {
4617 t = ap[i];
4618 rp[i] = ((t >> 1) & BN_MASK2) | c;
4619 c = (t & 1) ? BN_TBIT : 0;
4620 }
4621 bn_fix_top(r);
4622 return (1);
4623 }
4624
4625 int
4626 BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
4627 {
4628 int i, nw, lb, rb;
4629 BN_ULONG *t, *f;
4630 BN_ULONG l;
4631
4632 r->neg = a->neg;
4633 nw = n / BN_BITS2;
4634 if (bn_wexpand(r, a->top + nw + 1) == NULL)
4635 return (0);
4636 lb = n % BN_BITS2;
4637 rb = BN_BITS2 - lb;
4638 f = a->d;
4639 t = r->d;
4640 t[a->top + nw] = 0;
4641 if (lb == 0)
4642 for (i = a->top - 1; i >= 0; i--)
4643 t[nw+i] = f[i];
4644 else
4645 for (i = a->top-1; i >= 0; i--) {
4646 l = f[i];
4647 t[nw + i + 1] |= (l >> rb) & BN_MASK2;
4648 t[nw + i] = (l << lb) & BN_MASK2;
4649 }
4650 memset(t, 0, nw * sizeof(t[0]));
4651 /* for (i = 0; i < nw; i++)
4652 * t[i] = 0;
4653 */
4654 r->top = a->top + nw + 1;
4655 bn_fix_top(r);
4656 return (1);
4657 }
4658
4659 int
4660 BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
4661 {
4662 int i, j, nw, lb, rb;
4663 BN_ULONG *t, *f;
4664 BN_ULONG l, tmp;
4665
4666 nw = n/BN_BITS2;
4667 rb = n%BN_BITS2;
4668 lb = BN_BITS2-rb;
4669 if (nw > a->top || a->top == 0) {
4670 BN_zero(r);
4671 return (1);
4672 }
4673 if (r != a) {
4674 r->neg = a->neg;
4675 if (bn_wexpand(r, a->top-nw+1) == NULL) return (0);
4676 } else {
4677 if (n == 0)
4678 return 1; /* or the copying loop will go berserk */
4679 }
4680
4681 f = &(a->d[nw]);
4682 t = r->d;
4683 j = a->top-nw;
4684 r->top = j;
4685
4686 if (rb == 0) {
4687 for (i = j+1; i > 0; i--)
4688 *(t++) = *(f++);
4689 } else {
4690 l = *(f++);
4691 for (i = 1; i < j; i++) {
4692 tmp = (l >> rb)&BN_MASK2;
4693 l = *(f++);
4694 *(t++) = (tmp | (l << lb)) & BN_MASK2;
4695 }
4696 *(t++) = (l>>rb)&BN_MASK2;
4697 }
4698 *t = 0;
4699 bn_fix_top(r);
4700 return (1);
4701 }
4702
4703 /* r must not be a */
4704 /* I've just gone over this and it is now %20 faster on x86 - eay - 27 Jun 96 */
4705 int
4706 BN_sqr(BIGNUM *r, const BIGNUM *a, BN_CTX *ctx)
4707 {
4708 int max, al;
4709 int ret = 0;
4710 BIGNUM *tmp, *rr;
4711
4712 #ifdef BN_COUNT
4713 fprintf(stderr, "BN_sqr %d * %d\n", a->top, a->top);
4714 #endif
4715 bn_check_top(a);
4716
4717 al = a->top;
4718 if (al <= 0) {
4719 r->top = 0;
4720 return (1);
4721 }
4722
4723 BN_CTX_start(ctx);
4724 rr = (a != r) ? r : BN_CTX_get(ctx);
4725 tmp = BN_CTX_get(ctx);
4726 if (tmp == NULL) goto err;
4727
4728 max = (al + al);
4729 if (bn_wexpand(rr, max + 1) == NULL)
4730 goto err;
4731
4732 if (al == 4) {
4733 #ifndef BN_SQR_COMBA
4734 BN_ULONG t[8];
4735 bn_sqr_normal(rr->d, a->d, 4, t);
4736 #else
4737 bn_sqr_comba4(rr->d, a->d);
4738 #endif
4739 } else if (al == 8) {
4740 #ifndef BN_SQR_COMBA
4741 BN_ULONG t[16];
4742 bn_sqr_normal(rr->d, a->d, 8, t);
4743 #else
4744 bn_sqr_comba8(rr->d, a->d);
4745 #endif
4746 } else {
4747 #if defined(BN_RECURSION)
4748 if (al < BN_SQR_RECURSIVE_SIZE_NORMAL) {
4749 BN_ULONG t[BN_SQR_RECURSIVE_SIZE_NORMAL*2];
4750 bn_sqr_normal(rr->d, a->d, al, t);
4751 } else {
4752 int j, k;
4753
4754 j = BN_num_bits_word((BN_ULONG)al);
4755 j = 1 << (j - 1);
4756 k = j + j;
4757 if (al == j) {
4758 if (bn_wexpand(tmp, k*2) == NULL) goto err;
4759 bn_sqr_recursive(rr->d, a->d, al, tmp->d);
4760 } else {
4761 if (bn_wexpand(tmp, max) == NULL) goto err;
4762 bn_sqr_normal(rr->d, a->d, al, tmp->d);
4763 }
4764 }
4765 #else
4766 if (bn_wexpand(tmp, max) == NULL)
4767 goto err;
4768 bn_sqr_normal(rr->d, a->d, al, tmp->d);
4769 #endif /* BN_RECURSION */
4770 }
4771
4772 rr->top = max;
4773 rr->neg = 0;
4774 if ((max > 0) && (rr->d[max-1] == 0)) rr->top--;
4775 if (rr != r) BN_copy(r, rr);
4776 ret = 1;
4777 err:
4778 BN_CTX_end(ctx);
4779 return (ret);
4780 }
4781
4782 /* tmp must have 2*n words */
4783 void
4784 bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp)
4785 {
4786 int i, j, max;
4787 const BN_ULONG *ap;
4788 BN_ULONG *rp;
4789
4790 max = n*2;
4791 ap = a;
4792 rp = r;
4793 rp[0] = rp[max-1] = 0;
4794 rp++;
4795 j = n;
4796
4797 if (--j > 0) {
4798 ap++;
4799 rp[j] = bn_mul_words(rp, ap, j, ap[-1]);
4800 rp += 2;
4801 }
4802
4803 for (i = n - 2; i > 0; i--) {
4804 j--;
4805 ap++;
4806 rp[j] = bn_mul_add_words(rp, ap, j, ap[-1]);
4807 rp += 2;
4808 }
4809
4810 bn_add_words(r, r, r, max);
4811
4812 /* There will not be a carry */
4813
4814 bn_sqr_words(tmp, a, n);
4815
4816 bn_add_words(r, r, tmp, max);
4817 }
4818
4819 #ifdef BN_RECURSION
4820 /* r is 2*n words in size,
4821 * a and b are both n words in size. (There's not actually a 'b' here ...)
4822 * n must be a power of 2.
4823 * We multiply and return the result.
4824 * t must be 2*n words in size
4825 * We calculate
4826 * a[0]*b[0]
4827 * a[0]*b[0]+a[1]*b[1]+(a[0]-a[1])*(b[1]-b[0])
4828 * a[1]*b[1]
4829 */
4830 void
4831 bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t)
4832 {
4833 int n = n2/2;
4834 int zero, c1;
4835 BN_ULONG ln, lo, *p;
4836
4837 #ifdef BN_COUNT
4838 fprintf(stderr, " bn_sqr_recursive %d * %d\n", n2, n2);
4839 #endif
4840 if (n2 == 4) {
4841 #ifndef BN_SQR_COMBA
4842 bn_sqr_normal(r, a, 4, t);
4843 #else
4844 bn_sqr_comba4(r, a);
4845 #endif
4846 return;
4847 } else if (n2 == 8) {
4848 #ifndef BN_SQR_COMBA
4849 bn_sqr_normal(r, a, 8, t);
4850 #else
4851 bn_sqr_comba8(r, a);
4852 #endif
4853 return;
4854 }
4855 if (n2 < BN_SQR_RECURSIVE_SIZE_NORMAL) {
4856 bn_sqr_normal(r, a, n2, t);
4857 return;
4858 }
4859 /* r = (a[0]-a[1])*(a[1]-a[0]) */
4860 c1 = bn_cmp_words(a, &(a[n]), n);
4861 zero = 0;
4862 if (c1 > 0)
4863 bn_sub_words(t, a, &(a[n]), n);
4864 else if (c1 < 0)
4865 bn_sub_words(t, &(a[n]), a, n);
4866 else
4867 zero = 1;
4868
4869 /* The result will always be negative unless it is zero */
4870 p = &(t[n2*2]);
4871
4872 if (!zero)
4873 bn_sqr_recursive(&(t[n2]), t, n, p);
4874 else
4875 memset(&(t[n2]), 0, n2*sizeof(BN_ULONG));
4876 bn_sqr_recursive(r, a, n, p);
4877 bn_sqr_recursive(&(r[n2]), &(a[n]), n, p);
4878
4879 /* t[32] holds (a[0]-a[1])*(a[1]-a[0]), it is negative or zero
4880 * r[10] holds (a[0]*b[0])
4881 * r[32] holds (b[1]*b[1])
4882 */
4883
4884 c1 = (int)(bn_add_words(t, r, &(r[n2]), n2));
4885
4886 /* t[32] is negative */
4887 c1 -= (int)(bn_sub_words(&(t[n2]), t, &(t[n2]), n2));
4888
4889 /* t[32] holds (a[0]-a[1])*(a[1]-a[0])+(a[0]*a[0])+(a[1]*a[1])
4890 * r[10] holds (a[0]*a[0])
4891 * r[32] holds (a[1]*a[1])
4892 * c1 holds the carry bits
4893 */
4894 c1 += (int)(bn_add_words(&(r[n]), &(r[n]), &(t[n2]), n2));
4895 if (c1) {
4896 p = &(r[n+n2]);
4897 lo = *p;
4898 ln = (lo+c1)&BN_MASK2;
4899 *p = ln;
4900
4901 /* The overflow will stop before we over write
4902 * words we should not overwrite
4903 */
4904 if (ln < (BN_ULONG)c1) {
4905 do {
4906 p++;
4907 lo = *p;
4908 ln = (lo+1)&BN_MASK2;
4909 *p = ln;
4910 } while (ln == 0);
4911 }
4912 }
4913 }
4914 #endif /* BN_RECURSION */
4915
4916 #ifdef BCMDH_TEST
4917 BN_ULONG
4918 BN_mod_word(const BIGNUM *a, BN_ULONG w)
4919 {
4920 #ifndef BN_LLONG
4921 BN_ULONG ret = 0;
4922 #else
4923 BN_ULLONG ret = 0;
4924 #endif
4925 int i;
4926
4927 w &= BN_MASK2;
4928 for (i = a->top-1; i >= 0; i--) {
4929 #ifndef BN_LLONG
4930 ret = ((ret << BN_BITS4) | ((a->d[i] >> BN_BITS4) & BN_MASK2l)) % w;
4931 ret = ((ret << BN_BITS4) | (a->d[i] & BN_MASK2l)) % w;
4932 #else
4933 ret = (BN_ULLONG)(((ret << (BN_ULLONG)BN_BITS2) | a->d[i]) % (BN_ULLONG)w);
4934 #endif
4935 }
4936 return ((BN_ULONG)ret);
4937 }
4938 #endif /* BCMDH_TEST */
4939
4940 #ifdef NOT_NEEDED_FOR_DH
4941 BN_ULONG
4942 BN_div_word(BIGNUM *a, BN_ULONG w)
4943 {
4944 BN_ULONG ret;
4945 int i;
4946
4947 if (a->top == 0) return (0);
4948 ret = 0;
4949 w &= BN_MASK2;
4950 for (i = a->top-1; i >= 0; i--) {
4951 BN_ULONG l, d;
4952
4953 l = a->d[i];
4954 d = bn_div_words(ret, l, w);
4955 ret = (l-((d*w)&BN_MASK2))&BN_MASK2;
4956 a->d[i] = d;
4957 }
4958 if ((a->top > 0) && (a->d[a->top-1] == 0))
4959 a->top--;
4960 return (ret);
4961 }
4962 #endif /* NOT_NEEDED_FOR_DH */
4963
4964 int
4965 BN_add_word(BIGNUM *a, BN_ULONG w)
4966 {
4967 BN_ULONG l;
4968 int i;
4969
4970 if (a->neg) {
4971 a->neg = 0;
4972 i = BN_sub_word(a, w);
4973 if (!BN_is_zero(a))
4974 a->neg = !(a->neg);
4975 return (i);
4976 }
4977 w &= BN_MASK2;
4978 if (bn_wexpand(a, a->top+1) == NULL) return (0);
4979 i = 0;
4980 for (;;) {
4981 if (i >= a->top)
4982 l = w;
4983 else
4984 l = (a->d[i]+(BN_ULONG)w)&BN_MASK2;
4985 a->d[i] = l;
4986 if (w > l)
4987 w = 1;
4988 else
4989 break;
4990 i++;
4991 }
4992 if (i >= a->top)
4993 a->top++;
4994 return (1);
4995 }
4996
4997 int
4998 BN_sub_word(BIGNUM *a, BN_ULONG w)
4999 {
5000 int i;
5001
5002 if (BN_is_zero(a) || a->neg) {
5003 a->neg = 0;
5004 i = BN_add_word(a, w);
5005 a->neg = 1;
5006 return (i);
5007 }
5008
5009 w &= BN_MASK2;
5010 if ((a->top == 1) && (a->d[0] < w)) {
5011 a->d[0] = w-a->d[0];
5012 a->neg = 1;
5013 return (1);
5014 }
5015 i = 0;
5016 for (;;) {
5017 if (a->d[i] >= w) {
5018 a->d[i] -= w;
5019 break;
5020 } else {
5021 a->d[i] = (a->d[i]-w)&BN_MASK2;
5022 i++;
5023 w = 1;
5024 }
5025 }
5026 if ((a->d[i] == 0) && (i == (a->top-1)))
5027 a->top--;
5028 return (1);
5029 }
5030
5031 int
5032 BN_mul_word(BIGNUM *a, BN_ULONG w)
5033 {
5034 BN_ULONG ll;
5035
5036 w &= BN_MASK2;
5037 if (a->top) {
5038 if (w == 0)
5039 BN_zero(a);
5040 else {
5041 ll = bn_mul_words(a->d, a->d, a->top, w);
5042 if (ll) {
5043 if (bn_wexpand(a, a->top+1) == NULL) return (0);
5044 a->d[a->top++] = ll;
5045 }
5046 }
5047 }
5048 return (1);
5049 }
5050
5051 #ifdef BCMDH_TEST
5052 /* The quick sieve algorithm approach to weeding out primes is
5053 * Philip Zimmermann's, as implemented in PGP. I have had a read of
5054 * his comments and implemented my own version.
5055 */
5056
5057 #ifndef EIGHT_BIT
5058 #define NUMPRIMES 2048
5059 #else
5060 #define NUMPRIMES 54
5061 #endif
5062 static const unsigned int primes[NUMPRIMES] =
5063 {
5064 2, 3, 5, 7, 11, 13, 17, 19,
5065 23, 29, 31, 37, 41, 43, 47, 53,
5066 59, 61, 67, 71, 73, 79, 83, 89,
5067 97, 101, 103, 107, 109, 113, 127, 131,
5068 137, 139, 149, 151, 157, 163, 167, 173,
5069 179, 181, 191, 193, 197, 199, 211, 223,
5070 227, 229, 233, 239, 241, 251,
5071 #ifndef EIGHT_BIT
5072 257, 263,
5073 269, 271, 277, 281, 283, 293, 307, 311,
5074 313, 317, 331, 337, 347, 349, 353, 359,
5075 367, 373, 379, 383, 389, 397, 401, 409,
5076 419, 421, 431, 433, 439, 443, 449, 457,
5077 461, 463, 467, 479, 487, 491, 499, 503,
5078 509, 521, 523, 541, 547, 557, 563, 569,
5079 571, 577, 587, 593, 599, 601, 607, 613,
5080 617, 619, 631, 641, 643, 647, 653, 659,
5081 661, 673, 677, 683, 691, 701, 709, 719,
5082 727, 733, 739, 743, 751, 757, 761, 769,
5083 773, 787, 797, 809, 811, 821, 823, 827,
5084 829, 839, 853, 857, 859, 863, 877, 881,
5085 883, 887, 907, 911, 919, 929, 937, 941,
5086 947, 953, 967, 971, 977, 983, 991, 997,
5087 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
5088 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
5089 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
5090 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223,
5091 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
5092 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321,
5093 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
5094 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459,
5095 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
5096 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571,
5097 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
5098 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
5099 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747,
5100 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811,
5101 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
5102 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949,
5103 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003,
5104 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069,
5105 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129,
5106 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203,
5107 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267,
5108 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311,
5109 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377,
5110 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423,
5111 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503,
5112 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579,
5113 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657,
5114 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693,
5115 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741,
5116 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801,
5117 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
5118 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939,
5119 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011,
5120 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079,
5121 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167,
5122 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221,
5123 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301,
5124 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347,
5125 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413,
5126 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491,
5127 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541,
5128 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607,
5129 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671,
5130 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727,
5131 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797,
5132 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863,
5133 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923,
5134 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003,
5135 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057,
5136 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
5137 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211,
5138 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259,
5139 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337,
5140 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409,
5141 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481,
5142 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547,
5143 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621,
5144 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673,
5145 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751,
5146 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813,
5147 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909,
5148 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967,
5149 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011,
5150 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087,
5151 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167,
5152 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233,
5153 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309,
5154 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399,
5155 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
5156 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507,
5157 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573,
5158 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653,
5159 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711,
5160 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791,
5161 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849,
5162 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897,
5163 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007,
5164 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073,
5165 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133,
5166 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211,
5167 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271,
5168 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329,
5169 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379,
5170 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473,
5171 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563,
5172 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637,
5173 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701,
5174 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
5175 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833,
5176 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907,
5177 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971,
5178 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027,
5179 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121,
5180 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207,
5181 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253,
5182 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349,
5183 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457,
5184 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517,
5185 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561,
5186 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621,
5187 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691,
5188 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757,
5189 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853,
5190 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919,
5191 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009,
5192 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087,
5193 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
5194 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231,
5195 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291,
5196 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369,
5197 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443,
5198 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537,
5199 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609,
5200 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677,
5201 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731,
5202 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803,
5203 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861,
5204 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941,
5205 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011,
5206 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091,
5207 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161,
5208 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227,
5209 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311,
5210 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377,
5211 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433,
5212 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491,
5213 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587,
5214 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649,
5215 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733,
5216 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791,
5217 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857,
5218 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929,
5219 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037,
5220 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099,
5221 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163,
5222 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247,
5223 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303,
5224 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369,
5225 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459,
5226 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531,
5227 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627,
5228 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691,
5229 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771,
5230 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859,
5231 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937,
5232 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003,
5233 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087,
5234 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161,
5235 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251,
5236 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317,
5237 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399,
5238 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483,
5239 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551,
5240 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657,
5241 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731,
5242 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813,
5243 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887,
5244 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941,
5245 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011,
5246 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101,
5247 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161,
5248 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251,
5249 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323,
5250 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401,
5251 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473,
5252 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527,
5253 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589,
5254 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653,
5255 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739,
5256 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821,
5257 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907,
5258 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967,
5259 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033,
5260 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109,
5261 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177,
5262 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259,
5263 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337,
5264 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421,
5265 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499,
5266 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597,
5267 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681,
5268 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723,
5269 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799,
5270 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879,
5271 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933,
5272 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033,
5273 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143,
5274 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221,
5275 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323,
5276 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407,
5277 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461,
5278 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549,
5279 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627,
5280 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699,
5281 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753,
5282 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821,
5283 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887,
5284 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957,
5285 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073,
5286 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137,
5287 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217,
5288 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277,
5289 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331,
5290 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401,
5291 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473,
5292 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569,
5293 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643,
5294 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727,
5295 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773,
5296 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859,
5297 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919,
5298 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007,
5299 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087,
5300 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183,
5301 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249,
5302 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349,
5303 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427,
5304 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493,
5305 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603,
5306 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661,
5307 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747,
5308 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843,
5309 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927,
5310 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993,
5311 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053,
5312 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159,
5313 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231,
5314 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327,
5315 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389,
5316 17393, 17401, 17417, 17419, 17431, 17443, 17449, 17467,
5317 17471, 17477, 17483, 17489, 17491, 17497, 17509, 17519,
5318 17539, 17551, 17569, 17573, 17579, 17581, 17597, 17599,
5319 17609, 17623, 17627, 17657, 17659, 17669, 17681, 17683,
5320 17707, 17713, 17729, 17737, 17747, 17749, 17761, 17783,
5321 17789, 17791, 17807, 17827, 17837, 17839, 17851, 17863
5322 #endif /* !EIGHT_BIT */
5323 };
5324
5325 static int witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
5326 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont);
5327 static int probable_prime(BIGNUM *rnd, int bits);
5328 static int probable_prime_dh(BIGNUM *rnd, int bits,
5329 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
5330 static int probable_prime_dh_safe(BIGNUM *rnd, int bits,
5331 const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx);
5332
5333 BIGNUM *
5334 BN_generate_prime(BIGNUM *ret, int bits, int safe, const BIGNUM *add, const BIGNUM *rem,
5335 void (*callback)(int, int, void *), void *cb_arg)
5336 {
5337 BIGNUM *rnd = NULL;
5338 BIGNUM t;
5339 int found = 0;
5340 int i, j, c1 = 0;
5341 BN_CTX *ctx;
5342 int checks = BN_prime_checks_for_size(bits);
5343
5344 BN_init(&t);
5345 ctx = BN_CTX_new();
5346 if (ctx == NULL) goto err;
5347 if (ret == NULL) {
5348 if ((rnd = BN_new()) == NULL) goto err;
5349 } else
5350 rnd = ret;
5351 loop:
5352 /* make a random number and set the top and bottom bits */
5353 if (add == NULL) {
5354 if (!probable_prime(rnd, bits)) goto err;
5355 } else {
5356 if (safe) {
5357 if (!probable_prime_dh_safe(rnd, bits, add, rem, ctx))
5358 goto err;
5359 } else {
5360 if (!probable_prime_dh(rnd, bits, add, rem, ctx))
5361 goto err;
5362 }
5363 }
5364 /* if (BN_mod_word(rnd, (BN_ULONG)3) == 1) goto loop; */
5365 if (callback != NULL)
5366 callback(0, c1++, cb_arg);
5367
5368 if (!safe) {
5369 i = BN_is_prime_fasttest(rnd, checks, callback, ctx, cb_arg, 0);
5370 if (i == -1) goto err;
5371 if (i == 0) goto loop;
5372 } else {
5373 /* for "safe prime" generation,
5374 * check that (p-1)/2 is prime.
5375 * Since a prime is odd, We just
5376 * need to divide by 2
5377 */
5378 if (!BN_rshift1(&t, rnd)) goto err;
5379
5380 for (i = 0; i < checks; i++) {
5381 j = BN_is_prime_fasttest(rnd, 1, callback, ctx, cb_arg, 0);
5382 if (j == -1) goto err;
5383 if (j == 0) goto loop;
5384
5385 j = BN_is_prime_fasttest(&t, 1, callback, ctx, cb_arg, 0);
5386 if (j == -1) goto err;
5387 if (j == 0) goto loop;
5388
5389 if (callback != NULL) callback(2, c1-1, cb_arg);
5390 /* We have a safe prime test pass */
5391 }
5392 }
5393 /* we have a prime :-) */
5394 found = 1;
5395 err:
5396 if (!found && (ret == NULL) && (rnd != NULL)) BN_free(rnd);
5397 BN_free(&t);
5398 if (ctx != NULL) BN_CTX_free(ctx);
5399 return (found ? rnd : NULL);
5400 }
5401
5402 int
5403 BN_is_prime(const BIGNUM *a, int checks, void (*callback)(int, int, void *),
5404 BN_CTX *ctx_passed, void *cb_arg)
5405 {
5406 return BN_is_prime_fasttest(a, checks, callback, ctx_passed, cb_arg, 0);
5407 }
5408
5409 int
5410 BN_is_prime_fasttest(const BIGNUM *a, int checks, void (*callback)(int, int, void *),
5411 BN_CTX *ctx_passed, void *cb_arg, int do_trial_division)
5412 {
5413 int i, j, ret = -1;
5414 int k;
5415 BN_CTX *ctx = NULL;
5416 BIGNUM *A1, *A1_odd, *check; /* taken from ctx */
5417 BN_MONT_CTX *mont = NULL;
5418 const BIGNUM *A = NULL;
5419
5420 if (BN_cmp(a, BN_value_one()) <= 0)
5421 return 0;
5422
5423 if (checks == BN_prime_checks)
5424 checks = BN_prime_checks_for_size(BN_num_bits(a));
5425
5426 /* first look for small factors */
5427 if (!BN_is_odd(a))
5428 return 0;
5429 if (do_trial_division) {
5430 for (i = 1; i < NUMPRIMES; i++)
5431 if (BN_mod_word(a, primes[i]) == 0)
5432 return 0;
5433 if (callback != NULL)
5434 callback(1, -1, cb_arg);
5435 }
5436
5437 if (ctx_passed != NULL)
5438 ctx = ctx_passed;
5439 else
5440 if ((ctx = BN_CTX_new()) == NULL)
5441 goto err;
5442 BN_CTX_start(ctx);
5443
5444 /* A : = abs(a) */
5445 if (a->neg) {
5446 BIGNUM *t;
5447 if ((t = BN_CTX_get(ctx)) == NULL) goto err;
5448 BN_copy(t, a);
5449 t->neg = 0;
5450 A = t;
5451 } else
5452 A = a;
5453 A1 = BN_CTX_get(ctx);
5454 A1_odd = BN_CTX_get(ctx);
5455 check = BN_CTX_get(ctx);
5456 if (check == NULL) goto err;
5457
5458 /* compute A1 : = A - 1 */
5459 if (!BN_copy(A1, A))
5460 goto err;
5461 if (!BN_sub_word(A1, 1))
5462 goto err;
5463 if (BN_is_zero(A1)) {
5464 ret = 0;
5465 goto err;
5466 }
5467
5468 /* write A1 as A1_odd * 2^k */
5469 k = 1;
5470 while (!BN_is_bit_set(A1, k))
5471 k++;
5472 if (!BN_rshift(A1_odd, A1, k))
5473 goto err;
5474
5475 /* Montgomery setup for computations mod A */
5476 mont = BN_MONT_CTX_new();
5477 if (mont == NULL)
5478 goto err;
5479 if (!BN_MONT_CTX_set(mont, A, ctx))
5480 goto err;
5481
5482 for (i = 0; i < checks; i++) {
5483 if (!BN_pseudo_rand_range(check, A1))
5484 goto err;
5485 if (!BN_add_word(check, 1))
5486 goto err;
5487 /* now 1 <= check < A */
5488
5489 j = witness(check, A, A1, A1_odd, k, ctx, mont);
5490 if (j == -1) goto err;
5491 if (j) {
5492 ret = 0;
5493 goto err;
5494 }
5495 if (callback != NULL)
5496 callback(1, i, cb_arg);
5497 }
5498 ret = 1;
5499 err:
5500 if (ctx != NULL) {
5501 BN_CTX_end(ctx);
5502 if (ctx_passed == NULL)
5503 BN_CTX_free(ctx);
5504 }
5505 if (mont != NULL)
5506 BN_MONT_CTX_free(mont);
5507
5508 return (ret);
5509 }
5510
5511 static int
5512 witness(BIGNUM *w, const BIGNUM *a, const BIGNUM *a1,
5513 const BIGNUM *a1_odd, int k, BN_CTX *ctx, BN_MONT_CTX *mont)
5514 {
5515 if (!BN_mod_exp_mont(w, w, a1_odd, a, ctx, mont)) /* w : = w^a1_odd mod a */
5516 return -1;
5517 if (BN_is_one(w))
5518 return 0; /* probably prime */
5519 if (BN_cmp(w, a1) == 0)
5520 return 0; /* w == -1 (mod a), 'a' is probably prime */
5521 while (--k) {
5522 if (!BN_mod_mul(w, w, w, a, ctx)) /* w : = w^2 mod a */
5523 return -1;
5524 if (BN_is_one(w))
5525 return 1; /* 'a' is composite, otherwise a previous 'w' would
5526 * have been == -1 (mod 'a')
5527 */
5528 if (BN_cmp(w, a1) == 0)
5529 return 0; /* w == -1 (mod a), 'a' is probably prime */
5530 }
5531 /* If we get here, 'w' is the (a-1)/2-th power of the original 'w',
5532 * and it is neither -1 nor +1 -- so 'a' cannot be prime
5533 */
5534 return 1;
5535 }
5536
5537 static int
5538 probable_prime(BIGNUM *rnd, int bits)
5539 {
5540 int i;
5541 BN_ULONG mods[NUMPRIMES];
5542 BN_ULONG delta, d;
5543
5544 again:
5545 if (!BN_rand(rnd, bits, 1, 1)) return (0);
5546 /* we now have a random number 'rand' to test. */
5547 for (i = 1; i < NUMPRIMES; i++)
5548 mods[i] = BN_mod_word(rnd, (BN_ULONG)primes[i]);
5549 delta = 0;
5550 loop:
5551 for (i = 1; i < NUMPRIMES; i++) {
5552 /* check that rnd is not a prime and also
5553 * that gcd(rnd-1, primes) == 1 (except for 2)
5554 */
5555 if (((mods[i]+delta)%primes[i]) <= 1) {
5556 d = delta;
5557 delta += 2;
5558 /* perhaps need to check for overflow of
5559 * delta (but delta can be up to 2^32)
5560 * 21-May-98 eay - added overflow check
5561 */
5562 if (delta < d) goto again;
5563 goto loop;
5564 }
5565 }
5566 if (!BN_add_word(rnd, delta)) return (0);
5567 return (1);
5568 }
5569
5570 static int
5571 probable_prime_dh(BIGNUM *rnd, int bits, const BIGNUM *add, const BIGNUM *rem, BN_CTX *ctx)
5572 {
5573 int i, ret = 0;
5574 BIGNUM *t1;
5575
5576 BN_CTX_start(ctx);
5577 if ((t1 = BN_CTX_get(ctx)) == NULL) goto err;
5578
5579 if (!BN_rand(rnd, bits, 0, 1))
5580 goto err;
5581
5582 /* we need ((rnd-rem) % add) == 0 */
5583
5584 if (!BN_mod(t1, rnd, add, ctx))
5585 goto err;
5586 if (!BN_sub(rnd, rnd, t1))
5587 goto err;
5588 if (rem == NULL) {
5589 if (!BN_add_word(rnd, 1))
5590 goto err;
5591 } else {
5592 if (!BN_add(rnd, rnd, rem))
5593 goto err;
5594 }
5595
5596 /* we now have a random number 'rand' to test. */
5597
5598 loop: for (i = 1; i < NUMPRIMES; i++) {
5599 /* check that rnd is a prime */
5600 if (BN_mod_word(rnd, (BN_ULONG)primes[i]) <= 1) {
5601 if (!BN_add(rnd, rnd, add)) goto err;
5602 goto loop;
5603 }
5604 }
5605 ret = 1;
5606 err:
5607 BN_CTX_end(ctx);
5608 return (ret);
5609 }
5610
5611 static int
5612 probable_prime_dh_safe(BIGNUM *p, int bits, const BIGNUM *padd, const BIGNUM *rem, BN_CTX *ctx)
5613 {
5614 int i, ret = 0;
5615 BIGNUM *t1, *qadd, *q;
5616
5617 bits--;
5618 BN_CTX_start(ctx);
5619 t1 = BN_CTX_get(ctx);
5620 q = BN_CTX_get(ctx);
5621 qadd = BN_CTX_get(ctx);
5622 if (qadd == NULL) goto err;
5623
5624 if (!BN_rshift1(qadd, padd)) goto err;
5625
5626 if (!BN_rand(q, bits, 0, 1)) goto err;
5627
5628 /* we need ((rnd-rem) % add) == 0 */
5629 if (!BN_mod(t1, q, qadd, ctx)) goto err;
5630 if (!BN_sub(q, q, t1)) goto err;
5631 if (rem == NULL) {
5632 if (!BN_add_word(q, 1)) goto err;
5633 } else {
5634 if (!BN_rshift1(t1, rem)) goto err;
5635 if (!BN_add(q, q, t1)) goto err;
5636 }
5637
5638 /* we now have a random number 'rand' to test. */
5639 if (!BN_lshift1(p, q)) goto err;
5640 if (!BN_add_word(p, 1)) goto err;
5641
5642 loop:
5643 for (i = 1; i < NUMPRIMES; i++) {
5644 /* check that p and q are prime */
5645 /* check that for p and q
5646 * gcd(p-1, primes) == 1 (except for 2)
5647 */
5648 if ((BN_mod_word(p, (BN_ULONG)primes[i]) == 0) ||
5649 (BN_mod_word(q, (BN_ULONG)primes[i]) == 0)) {
5650 if (!BN_add(p, p, padd)) goto err;
5651 if (!BN_add(q, q, qadd)) goto err;
5652 goto loop;
5653 }
5654 }
5655 ret = 1;
5656 err:
5657 BN_CTX_end(ctx);
5658 return (ret);
5659 }
5660 #endif /* BCMDH_TEST */
Tomato firmware and modifications.