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