comparison pre_gen/mpi.c @ 142:d29b64170cf0 libtommath-orig

import of libtommath 0.32
author Matt Johnston <matt@ucc.asn.au>
date Sun, 19 Dec 2004 11:33:56 +0000
parents 86e0b50a9b58
children d8254fc979e9
comparison
equal deleted inserted replaced
19:e1037a1e12e7 142:d29b64170cf0
1 /* Start: bn_error.c */ 1 /* Start: bn_error.c */
2 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2 #include <tommath.h>
3 * 3 #ifdef BN_ERROR_C
4 * LibTomMath is a library that provides multiple-precision 4 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5 * integer arithmetic as well as number theoretic functionality. 5 *
6 * 6 * LibTomMath is a library that provides multiple-precision
7 * The library was designed directly after the MPI library by 7 * integer arithmetic as well as number theoretic functionality.
8 * Michael Fromberger but has been written from scratch with 8 *
9 * additional optimizations in place. 9 * The library was designed directly after the MPI library by
10 * 10 * Michael Fromberger but has been written from scratch with
11 * The library is free for all purposes without any express 11 * additional optimizations in place.
12 * guarantee it works. 12 *
13 * 13 * The library is free for all purposes without any express
14 * Tom St Denis, [email protected], http://math.libtomcrypt.org 14 * guarantee it works.
15 */ 15 *
16 #include <tommath.h> 16 * Tom St Denis, [email protected], http://math.libtomcrypt.org
17 */
17 18
18 static const struct { 19 static const struct {
19 int code; 20 int code;
20 char *msg; 21 char *msg;
21 } msgs[] = { 22 } msgs[] = {
38 39
39 /* generic reply for invalid code */ 40 /* generic reply for invalid code */
40 return "Invalid error code"; 41 return "Invalid error code";
41 } 42 }
42 43
44 #endif
43 45
44 /* End: bn_error.c */ 46 /* End: bn_error.c */
45 47
46 /* Start: bn_fast_mp_invmod.c */ 48 /* Start: bn_fast_mp_invmod.c */
47 /* LibTomMath, multiple-precision integer library -- Tom St Denis 49 #include <tommath.h>
48 * 50 #ifdef BN_FAST_MP_INVMOD_C
49 * LibTomMath is a library that provides multiple-precision 51 /* LibTomMath, multiple-precision integer library -- Tom St Denis
50 * integer arithmetic as well as number theoretic functionality. 52 *
51 * 53 * LibTomMath is a library that provides multiple-precision
52 * The library was designed directly after the MPI library by 54 * integer arithmetic as well as number theoretic functionality.
53 * Michael Fromberger but has been written from scratch with 55 *
54 * additional optimizations in place. 56 * The library was designed directly after the MPI library by
55 * 57 * Michael Fromberger but has been written from scratch with
56 * The library is free for all purposes without any express 58 * additional optimizations in place.
57 * guarantee it works. 59 *
58 * 60 * The library is free for all purposes without any express
59 * Tom St Denis, [email protected], http://math.libtomcrypt.org 61 * guarantee it works.
60 */ 62 *
61 #include <tommath.h> 63 * Tom St Denis, [email protected], http://math.libtomcrypt.org
64 */
62 65
63 /* computes the modular inverse via binary extended euclidean algorithm, 66 /* computes the modular inverse via binary extended euclidean algorithm,
64 * that is c = 1/a mod b 67 * that is c = 1/a mod b
65 * 68 *
66 * Based on mp_invmod except this is optimized for the case where b is 69 * Based on slow invmod except this is optimized for the case where b is
67 * odd as per HAC Note 14.64 on pp. 610 70 * odd as per HAC Note 14.64 on pp. 610
68 */ 71 */
69 int 72 int
70 fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c) 73 fast_mp_invmod (mp_int * a, mp_int * b, mp_int * c)
71 { 74 {
185 res = MP_OKAY; 188 res = MP_OKAY;
186 189
187 __ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL); 190 __ERR:mp_clear_multi (&x, &y, &u, &v, &B, &D, NULL);
188 return res; 191 return res;
189 } 192 }
193 #endif
190 194
191 /* End: bn_fast_mp_invmod.c */ 195 /* End: bn_fast_mp_invmod.c */
192 196
193 /* Start: bn_fast_mp_montgomery_reduce.c */ 197 /* Start: bn_fast_mp_montgomery_reduce.c */
194 /* LibTomMath, multiple-precision integer library -- Tom St Denis 198 #include <tommath.h>
195 * 199 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
196 * LibTomMath is a library that provides multiple-precision 200 /* LibTomMath, multiple-precision integer library -- Tom St Denis
197 * integer arithmetic as well as number theoretic functionality. 201 *
198 * 202 * LibTomMath is a library that provides multiple-precision
199 * The library was designed directly after the MPI library by 203 * integer arithmetic as well as number theoretic functionality.
200 * Michael Fromberger but has been written from scratch with 204 *
201 * additional optimizations in place. 205 * The library was designed directly after the MPI library by
202 * 206 * Michael Fromberger but has been written from scratch with
203 * The library is free for all purposes without any express 207 * additional optimizations in place.
204 * guarantee it works. 208 *
205 * 209 * The library is free for all purposes without any express
206 * Tom St Denis, [email protected], http://math.libtomcrypt.org 210 * guarantee it works.
207 */ 211 *
208 #include <tommath.h> 212 * Tom St Denis, [email protected], http://math.libtomcrypt.org
213 */
209 214
210 /* computes xR**-1 == x (mod N) via Montgomery Reduction 215 /* computes xR**-1 == x (mod N) via Montgomery Reduction
211 * 216 *
212 * This is an optimized implementation of mp_montgomery_reduce 217 * This is an optimized implementation of montgomery_reduce
213 * which uses the comba method to quickly calculate the columns of the 218 * which uses the comba method to quickly calculate the columns of the
214 * reduction. 219 * reduction.
215 * 220 *
216 * Based on Algorithm 14.32 on pp.601 of HAC. 221 * Based on Algorithm 14.32 on pp.601 of HAC.
217 */ 222 */
356 if (mp_cmp_mag (x, n) != MP_LT) { 361 if (mp_cmp_mag (x, n) != MP_LT) {
357 return s_mp_sub (x, n, x); 362 return s_mp_sub (x, n, x);
358 } 363 }
359 return MP_OKAY; 364 return MP_OKAY;
360 } 365 }
366 #endif
361 367
362 /* End: bn_fast_mp_montgomery_reduce.c */ 368 /* End: bn_fast_mp_montgomery_reduce.c */
363 369
364 /* Start: bn_fast_s_mp_mul_digs.c */ 370 /* Start: bn_fast_s_mp_mul_digs.c */
365 /* LibTomMath, multiple-precision integer library -- Tom St Denis 371 #include <tommath.h>
366 * 372 #ifdef BN_FAST_S_MP_MUL_DIGS_C
367 * LibTomMath is a library that provides multiple-precision 373 /* LibTomMath, multiple-precision integer library -- Tom St Denis
368 * integer arithmetic as well as number theoretic functionality. 374 *
369 * 375 * LibTomMath is a library that provides multiple-precision
370 * The library was designed directly after the MPI library by 376 * integer arithmetic as well as number theoretic functionality.
371 * Michael Fromberger but has been written from scratch with 377 *
372 * additional optimizations in place. 378 * The library was designed directly after the MPI library by
373 * 379 * Michael Fromberger but has been written from scratch with
374 * The library is free for all purposes without any express 380 * additional optimizations in place.
375 * guarantee it works. 381 *
376 * 382 * The library is free for all purposes without any express
377 * Tom St Denis, [email protected], http://math.libtomcrypt.org 383 * guarantee it works.
378 */ 384 *
379 #include <tommath.h> 385 * Tom St Denis, [email protected], http://math.libtomcrypt.org
386 */
380 387
381 /* Fast (comba) multiplier 388 /* Fast (comba) multiplier
382 * 389 *
383 * This is the fast column-array [comba] multiplier. It is 390 * This is the fast column-array [comba] multiplier. It is
384 * designed to compute the columns of the product first 391 * designed to compute the columns of the product first
395 * 402 *
396 */ 403 */
397 int 404 int
398 fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs) 405 fast_s_mp_mul_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
399 { 406 {
400 int olduse, res, pa, ix; 407 int olduse, res, pa, ix, iz;
401 mp_word W[MP_WARRAY]; 408 mp_digit W[MP_WARRAY];
409 register mp_word _W;
402 410
403 /* grow the destination as required */ 411 /* grow the destination as required */
404 if (c->alloc < digs) { 412 if (c->alloc < digs) {
405 if ((res = mp_grow (c, digs)) != MP_OKAY) { 413 if ((res = mp_grow (c, digs)) != MP_OKAY) {
406 return res; 414 return res;
407 } 415 }
408 } 416 }
409 417
410 /* clear temp buf (the columns) */ 418 /* number of output digits to produce */
411 memset (W, 0, sizeof (mp_word) * digs); 419 pa = MIN(digs, a->used + b->used);
412 420
413 /* calculate the columns */ 421 /* clear the carry */
414 pa = a->used; 422 _W = 0;
415 for (ix = 0; ix < pa; ix++) { 423 for (ix = 0; ix <= pa; ix++) {
416 /* this multiplier has been modified to allow you to 424 int tx, ty;
417 * control how many digits of output are produced. 425 int iy;
418 * So at most we want to make upto "digs" digits of output. 426 mp_digit *tmpx, *tmpy;
419 * 427
420 * this adds products to distinct columns (at ix+iy) of W 428 /* get offsets into the two bignums */
421 * note that each step through the loop is not dependent on 429 ty = MIN(b->used-1, ix);
422 * the previous which means the compiler can easily unroll 430 tx = ix - ty;
423 * the loop without scheduling problems 431
424 */ 432 /* setup temp aliases */
425 { 433 tmpx = a->dp + tx;
426 register mp_digit tmpx, *tmpy; 434 tmpy = b->dp + ty;
427 register mp_word *_W; 435
428 register int iy, pb; 436 /* this is the number of times the loop will iterrate, essentially its
429 437 while (tx++ < a->used && ty-- >= 0) { ... }
430 /* alias for the the word on the left e.g. A[ix] * A[iy] */
431 tmpx = a->dp[ix];
432
433 /* alias for the right side */
434 tmpy = b->dp;
435
436 /* alias for the columns, each step through the loop adds a new
437 term to each column
438 */ 438 */
439 _W = W + ix; 439 iy = MIN(a->used-tx, ty+1);
440 440
441 /* the number of digits is limited by their placement. E.g. 441 /* execute loop */
442 we avoid multiplying digits that will end up above the # of 442 for (iz = 0; iz < iy; ++iz) {
443 digits of precision requested 443 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
444 */
445 pb = MIN (b->used, digs - ix);
446
447 for (iy = 0; iy < pb; iy++) {
448 *_W++ += ((mp_word)tmpx) * ((mp_word)*tmpy++);
449 } 444 }
450 } 445
451 446 /* store term */
447 W[ix] = ((mp_digit)_W) & MP_MASK;
448
449 /* make next carry */
450 _W = _W >> ((mp_word)DIGIT_BIT);
452 } 451 }
453 452
454 /* setup dest */ 453 /* setup dest */
455 olduse = c->used; 454 olduse = c->used;
456 c->used = digs; 455 c->used = digs;
457 456
458 { 457 {
459 register mp_digit *tmpc; 458 register mp_digit *tmpc;
460
461 /* At this point W[] contains the sums of each column. To get the
462 * correct result we must take the extra bits from each column and
463 * carry them down
464 *
465 * Note that while this adds extra code to the multiplier it
466 * saves time since the carry propagation is removed from the
467 * above nested loop.This has the effect of reducing the work
468 * from N*(N+N*c)==N**2 + c*N**2 to N**2 + N*c where c is the
469 * cost of the shifting. On very small numbers this is slower
470 * but on most cryptographic size numbers it is faster.
471 *
472 * In this particular implementation we feed the carries from
473 * behind which means when the loop terminates we still have one
474 * last digit to copy
475 */
476 tmpc = c->dp; 459 tmpc = c->dp;
477 for (ix = 1; ix < digs; ix++) { 460 for (ix = 0; ix < digs; ix++) {
478 /* forward the carry from the previous temp */
479 W[ix] += (W[ix - 1] >> ((mp_word) DIGIT_BIT));
480
481 /* now extract the previous digit [below the carry] */ 461 /* now extract the previous digit [below the carry] */
482 *tmpc++ = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK)); 462 *tmpc++ = W[ix];
483 } 463 }
484 /* fetch the last digit */
485 *tmpc++ = (mp_digit) (W[digs - 1] & ((mp_word) MP_MASK));
486 464
487 /* clear unused digits [that existed in the old copy of c] */ 465 /* clear unused digits [that existed in the old copy of c] */
488 for (; ix < olduse; ix++) { 466 for (; ix < olduse; ix++) {
489 *tmpc++ = 0; 467 *tmpc++ = 0;
490 } 468 }
491 } 469 }
492 mp_clamp (c); 470 mp_clamp (c);
493 return MP_OKAY; 471 return MP_OKAY;
494 } 472 }
473 #endif
495 474
496 /* End: bn_fast_s_mp_mul_digs.c */ 475 /* End: bn_fast_s_mp_mul_digs.c */
497 476
498 /* Start: bn_fast_s_mp_mul_high_digs.c */ 477 /* Start: bn_fast_s_mp_mul_high_digs.c */
499 /* LibTomMath, multiple-precision integer library -- Tom St Denis 478 #include <tommath.h>
500 * 479 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C
501 * LibTomMath is a library that provides multiple-precision 480 /* LibTomMath, multiple-precision integer library -- Tom St Denis
502 * integer arithmetic as well as number theoretic functionality. 481 *
503 * 482 * LibTomMath is a library that provides multiple-precision
504 * The library was designed directly after the MPI library by 483 * integer arithmetic as well as number theoretic functionality.
505 * Michael Fromberger but has been written from scratch with 484 *
506 * additional optimizations in place. 485 * The library was designed directly after the MPI library by
507 * 486 * Michael Fromberger but has been written from scratch with
508 * The library is free for all purposes without any express 487 * additional optimizations in place.
509 * guarantee it works. 488 *
510 * 489 * The library is free for all purposes without any express
511 * Tom St Denis, [email protected], http://math.libtomcrypt.org 490 * guarantee it works.
512 */ 491 *
513 #include <tommath.h> 492 * Tom St Denis, [email protected], http://math.libtomcrypt.org
514 493 */
515 /* this is a modified version of fast_s_mp_mul_digs that only produces 494
516 * output digits *above* digs. See the comments for fast_s_mp_mul_digs 495 /* this is a modified version of fast_s_mul_digs that only produces
496 * output digits *above* digs. See the comments for fast_s_mul_digs
517 * to see how it works. 497 * to see how it works.
518 * 498 *
519 * This is used in the Barrett reduction since for one of the multiplications 499 * This is used in the Barrett reduction since for one of the multiplications
520 * only the higher digits were needed. This essentially halves the work. 500 * only the higher digits were needed. This essentially halves the work.
521 * 501 *
522 * Based on Algorithm 14.12 on pp.595 of HAC. 502 * Based on Algorithm 14.12 on pp.595 of HAC.
523 */ 503 */
524 int 504 int
525 fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs) 505 fast_s_mp_mul_high_digs (mp_int * a, mp_int * b, mp_int * c, int digs)
526 { 506 {
527 int oldused, newused, res, pa, pb, ix; 507 int olduse, res, pa, ix, iz;
528 mp_word W[MP_WARRAY]; 508 mp_digit W[MP_WARRAY];
529 509 mp_word _W;
530 /* calculate size of product and allocate more space if required */ 510
531 newused = a->used + b->used + 1; 511 /* grow the destination as required */
532 if (c->alloc < newused) { 512 pa = a->used + b->used;
533 if ((res = mp_grow (c, newused)) != MP_OKAY) { 513 if (c->alloc < pa) {
514 if ((res = mp_grow (c, pa)) != MP_OKAY) {
534 return res; 515 return res;
535 } 516 }
536 } 517 }
537 518
538 /* like the other comba method we compute the columns first */ 519 /* number of output digits to produce */
539 pa = a->used; 520 pa = a->used + b->used;
540 pb = b->used; 521 _W = 0;
541 memset (W + digs, 0, (pa + pb + 1 - digs) * sizeof (mp_word)); 522 for (ix = digs; ix <= pa; ix++) {
542 for (ix = 0; ix < pa; ix++) { 523 int tx, ty, iy;
543 { 524 mp_digit *tmpx, *tmpy;
544 register mp_digit tmpx, *tmpy; 525
545 register int iy; 526 /* get offsets into the two bignums */
546 register mp_word *_W; 527 ty = MIN(b->used-1, ix);
547 528 tx = ix - ty;
548 /* work todo, that is we only calculate digits that are at "digs" or above */ 529
549 iy = digs - ix; 530 /* setup temp aliases */
550 531 tmpx = a->dp + tx;
551 /* copy of word on the left of A[ix] * B[iy] */ 532 tmpy = b->dp + ty;
552 tmpx = a->dp[ix]; 533
553 534 /* this is the number of times the loop will iterrate, essentially its
554 /* alias for right side */ 535 while (tx++ < a->used && ty-- >= 0) { ... }
555 tmpy = b->dp + iy;
556
557 /* alias for the columns of output. Offset to be equal to or above the
558 * smallest digit place requested
559 */ 536 */
560 _W = W + digs; 537 iy = MIN(a->used-tx, ty+1);
561 538
562 /* skip cases below zero where ix > digs */ 539 /* execute loop */
563 if (iy < 0) { 540 for (iz = 0; iz < iy; iz++) {
564 iy = abs(iy); 541 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
565 tmpy += iy;
566 _W += iy;
567 iy = 0;
568 } 542 }
569 543
570 /* compute column products for digits above the minimum */ 544 /* store term */
571 for (; iy < pb; iy++) { 545 W[ix] = ((mp_digit)_W) & MP_MASK;
572 *_W++ += ((mp_word) tmpx) * ((mp_word)*tmpy++); 546
573 } 547 /* make next carry */
574 } 548 _W = _W >> ((mp_word)DIGIT_BIT);
575 } 549 }
576 550
577 /* setup dest */ 551 /* setup dest */
578 oldused = c->used; 552 olduse = c->used;
579 c->used = newused; 553 c->used = pa;
580 554
581 /* now convert the array W downto what we need 555 {
582 * 556 register mp_digit *tmpc;
583 * See comments in bn_fast_s_mp_mul_digs.c 557
584 */ 558 tmpc = c->dp + digs;
585 for (ix = digs + 1; ix < newused; ix++) { 559 for (ix = digs; ix <= pa; ix++) {
586 W[ix] += (W[ix - 1] >> ((mp_word) DIGIT_BIT)); 560 /* now extract the previous digit [below the carry] */
587 c->dp[ix - 1] = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK)); 561 *tmpc++ = W[ix];
588 } 562 }
589 c->dp[newused - 1] = (mp_digit) (W[newused - 1] & ((mp_word) MP_MASK)); 563
590 564 /* clear unused digits [that existed in the old copy of c] */
591 for (; ix < oldused; ix++) { 565 for (; ix < olduse; ix++) {
592 c->dp[ix] = 0; 566 *tmpc++ = 0;
567 }
593 } 568 }
594 mp_clamp (c); 569 mp_clamp (c);
595 return MP_OKAY; 570 return MP_OKAY;
596 } 571 }
572 #endif
597 573
598 /* End: bn_fast_s_mp_mul_high_digs.c */ 574 /* End: bn_fast_s_mp_mul_high_digs.c */
599 575
600 /* Start: bn_fast_s_mp_sqr.c */ 576 /* Start: bn_fast_s_mp_sqr.c */
601 /* LibTomMath, multiple-precision integer library -- Tom St Denis 577 #include <tommath.h>
602 * 578 #ifdef BN_FAST_S_MP_SQR_C
603 * LibTomMath is a library that provides multiple-precision 579 /* LibTomMath, multiple-precision integer library -- Tom St Denis
604 * integer arithmetic as well as number theoretic functionality. 580 *
605 * 581 * LibTomMath is a library that provides multiple-precision
606 * The library was designed directly after the MPI library by 582 * integer arithmetic as well as number theoretic functionality.
607 * Michael Fromberger but has been written from scratch with 583 *
608 * additional optimizations in place. 584 * The library was designed directly after the MPI library by
609 * 585 * Michael Fromberger but has been written from scratch with
610 * The library is free for all purposes without any express 586 * additional optimizations in place.
611 * guarantee it works. 587 *
612 * 588 * The library is free for all purposes without any express
613 * Tom St Denis, [email protected], http://math.libtomcrypt.org 589 * guarantee it works.
614 */ 590 *
615 #include <tommath.h> 591 * Tom St Denis, [email protected], http://math.libtomcrypt.org
592 */
616 593
617 /* fast squaring 594 /* fast squaring
618 * 595 *
619 * This is the comba method where the columns of the product 596 * This is the comba method where the columns of the product
620 * are computed first then the carries are computed. This 597 * are computed first then the carries are computed. This
629 * because 64-bit shifts are slow! 606 * because 64-bit shifts are slow!
630 * 607 *
631 * Based on Algorithm 14.16 on pp.597 of HAC. 608 * Based on Algorithm 14.16 on pp.597 of HAC.
632 * 609 *
633 */ 610 */
611 /* the jist of squaring...
612
613 you do like mult except the offset of the tmpx [one that starts closer to zero]
614 can't equal the offset of tmpy. So basically you set up iy like before then you min it with
615 (ty-tx) so that it never happens. You double all those you add in the inner loop
616
617 After that loop you do the squares and add them in.
618
619 Remove W2 and don't memset W
620
621 */
622
634 int fast_s_mp_sqr (mp_int * a, mp_int * b) 623 int fast_s_mp_sqr (mp_int * a, mp_int * b)
635 { 624 {
636 int olduse, newused, res, ix, pa; 625 int olduse, res, pa, ix, iz;
637 mp_word W2[MP_WARRAY], W[MP_WARRAY]; 626 mp_digit W[MP_WARRAY], *tmpx;
638 627 mp_word W1;
639 /* calculate size of product and allocate as required */ 628
640 pa = a->used; 629 /* grow the destination as required */
641 newused = pa + pa + 1; 630 pa = a->used + a->used;
642 if (b->alloc < newused) { 631 if (b->alloc < pa) {
643 if ((res = mp_grow (b, newused)) != MP_OKAY) { 632 if ((res = mp_grow (b, pa)) != MP_OKAY) {
644 return res; 633 return res;
645 } 634 }
646 } 635 }
647 636
648 /* zero temp buffer (columns) 637 /* number of output digits to produce */
649 * Note that there are two buffers. Since squaring requires 638 W1 = 0;
650 * a outer and inner product and the inner product requires 639 for (ix = 0; ix <= pa; ix++) {
651 * computing a product and doubling it (a relatively expensive 640 int tx, ty, iy;
652 * op to perform n**2 times if you don't have to) the inner and 641 mp_word _W;
653 * outer products are computed in different buffers. This way 642 mp_digit *tmpy;
654 * the inner product can be doubled using n doublings instead of 643
655 * n**2 644 /* clear counter */
656 */ 645 _W = 0;
657 memset (W, 0, newused * sizeof (mp_word)); 646
658 memset (W2, 0, newused * sizeof (mp_word)); 647 /* get offsets into the two bignums */
659 648 ty = MIN(a->used-1, ix);
660 /* This computes the inner product. To simplify the inner N**2 loop 649 tx = ix - ty;
661 * the multiplication by two is done afterwards in the N loop. 650
662 */ 651 /* setup temp aliases */
663 for (ix = 0; ix < pa; ix++) { 652 tmpx = a->dp + tx;
664 /* compute the outer product 653 tmpy = a->dp + ty;
665 * 654
666 * Note that every outer product is computed 655 /* this is the number of times the loop will iterrate, essentially its
667 * for a particular column only once which means that 656 while (tx++ < a->used && ty-- >= 0) { ... }
668 * there is no need todo a double precision addition 657 */
669 * into the W2[] array. 658 iy = MIN(a->used-tx, ty+1);
670 */ 659
671 W2[ix + ix] = ((mp_word)a->dp[ix]) * ((mp_word)a->dp[ix]); 660 /* now for squaring tx can never equal ty
672 661 * we halve the distance since they approach at a rate of 2x
673 { 662 * and we have to round because odd cases need to be executed
674 register mp_digit tmpx, *tmpy; 663 */
675 register mp_word *_W; 664 iy = MIN(iy, (ty-tx+1)>>1);
676 register int iy; 665
677 666 /* execute loop */
678 /* copy of left side */ 667 for (iz = 0; iz < iy; iz++) {
679 tmpx = a->dp[ix]; 668 _W += ((mp_word)*tmpx++)*((mp_word)*tmpy--);
680
681 /* alias for right side */
682 tmpy = a->dp + (ix + 1);
683
684 /* the column to store the result in */
685 _W = W + (ix + ix + 1);
686
687 /* inner products */
688 for (iy = ix + 1; iy < pa; iy++) {
689 *_W++ += ((mp_word)tmpx) * ((mp_word)*tmpy++);
690 } 669 }
691 } 670
671 /* double the inner product and add carry */
672 _W = _W + _W + W1;
673
674 /* even columns have the square term in them */
675 if ((ix&1) == 0) {
676 _W += ((mp_word)a->dp[ix>>1])*((mp_word)a->dp[ix>>1]);
677 }
678
679 /* store it */
680 W[ix] = _W;
681
682 /* make next carry */
683 W1 = _W >> ((mp_word)DIGIT_BIT);
692 } 684 }
693 685
694 /* setup dest */ 686 /* setup dest */
695 olduse = b->used; 687 olduse = b->used;
696 b->used = newused; 688 b->used = a->used+a->used;
697 689
698 /* now compute digits
699 *
700 * We have to double the inner product sums, add in the
701 * outer product sums, propagate carries and convert
702 * to single precision.
703 */
704 { 690 {
705 register mp_digit *tmpb; 691 mp_digit *tmpb;
706
707 /* double first value, since the inner products are
708 * half of what they should be
709 */
710 W[0] += W[0] + W2[0];
711
712 tmpb = b->dp; 692 tmpb = b->dp;
713 for (ix = 1; ix < newused; ix++) { 693 for (ix = 0; ix < pa; ix++) {
714 /* double/add next digit */ 694 *tmpb++ = W[ix] & MP_MASK;
715 W[ix] += W[ix] + W2[ix]; 695 }
716 696
717 /* propagate carry forwards [from the previous digit] */ 697 /* clear unused digits [that existed in the old copy of c] */
718 W[ix] = W[ix] + (W[ix - 1] >> ((mp_word) DIGIT_BIT));
719
720 /* store the current digit now that the carry isn't
721 * needed
722 */
723 *tmpb++ = (mp_digit) (W[ix - 1] & ((mp_word) MP_MASK));
724 }
725 /* set the last value. Note even if the carry is zero
726 * this is required since the next step will not zero
727 * it if b originally had a value at b->dp[2*a.used]
728 */
729 *tmpb++ = (mp_digit) (W[(newused) - 1] & ((mp_word) MP_MASK));
730
731 /* clear high digits of b if there were any originally */
732 for (; ix < olduse; ix++) { 698 for (; ix < olduse; ix++) {
733 *tmpb++ = 0; 699 *tmpb++ = 0;
734 } 700 }
735 } 701 }
736
737 mp_clamp (b); 702 mp_clamp (b);
738 return MP_OKAY; 703 return MP_OKAY;
739 } 704 }
705 #endif
740 706
741 /* End: bn_fast_s_mp_sqr.c */ 707 /* End: bn_fast_s_mp_sqr.c */
742 708
743 /* Start: bn_mp_2expt.c */ 709 /* Start: bn_mp_2expt.c */
744 /* LibTomMath, multiple-precision integer library -- Tom St Denis 710 #include <tommath.h>
745 * 711 #ifdef BN_MP_2EXPT_C
746 * LibTomMath is a library that provides multiple-precision 712 /* LibTomMath, multiple-precision integer library -- Tom St Denis
747 * integer arithmetic as well as number theoretic functionality. 713 *
748 * 714 * LibTomMath is a library that provides multiple-precision
749 * The library was designed directly after the MPI library by 715 * integer arithmetic as well as number theoretic functionality.
750 * Michael Fromberger but has been written from scratch with 716 *
751 * additional optimizations in place. 717 * The library was designed directly after the MPI library by
752 * 718 * Michael Fromberger but has been written from scratch with
753 * The library is free for all purposes without any express 719 * additional optimizations in place.
754 * guarantee it works. 720 *
755 * 721 * The library is free for all purposes without any express
756 * Tom St Denis, [email protected], http://math.libtomcrypt.org 722 * guarantee it works.
757 */ 723 *
758 #include <tommath.h> 724 * Tom St Denis, [email protected], http://math.libtomcrypt.org
725 */
759 726
760 /* computes a = 2**b 727 /* computes a = 2**b
761 * 728 *
762 * Simple algorithm which zeroes the int, grows it then just sets one bit 729 * Simple algorithm which zeroes the int, grows it then just sets one bit
763 * as required. 730 * as required.
777 744
778 /* set the used count of where the bit will go */ 745 /* set the used count of where the bit will go */
779 a->used = b / DIGIT_BIT + 1; 746 a->used = b / DIGIT_BIT + 1;
780 747
781 /* put the single bit in its place */ 748 /* put the single bit in its place */
782 a->dp[b / DIGIT_BIT] = 1 << (b % DIGIT_BIT); 749 a->dp[b / DIGIT_BIT] = ((mp_digit)1) << (b % DIGIT_BIT);
783 750
784 return MP_OKAY; 751 return MP_OKAY;
785 } 752 }
753 #endif
786 754
787 /* End: bn_mp_2expt.c */ 755 /* End: bn_mp_2expt.c */
788 756
789 /* Start: bn_mp_abs.c */ 757 /* Start: bn_mp_abs.c */
790 /* LibTomMath, multiple-precision integer library -- Tom St Denis 758 #include <tommath.h>
791 * 759 #ifdef BN_MP_ABS_C
792 * LibTomMath is a library that provides multiple-precision 760 /* LibTomMath, multiple-precision integer library -- Tom St Denis
793 * integer arithmetic as well as number theoretic functionality. 761 *
794 * 762 * LibTomMath is a library that provides multiple-precision
795 * The library was designed directly after the MPI library by 763 * integer arithmetic as well as number theoretic functionality.
796 * Michael Fromberger but has been written from scratch with 764 *
797 * additional optimizations in place. 765 * The library was designed directly after the MPI library by
798 * 766 * Michael Fromberger but has been written from scratch with
799 * The library is free for all purposes without any express 767 * additional optimizations in place.
800 * guarantee it works. 768 *
801 * 769 * The library is free for all purposes without any express
802 * Tom St Denis, [email protected], http://math.libtomcrypt.org 770 * guarantee it works.
803 */ 771 *
804 #include <tommath.h> 772 * Tom St Denis, [email protected], http://math.libtomcrypt.org
773 */
805 774
806 /* b = |a| 775 /* b = |a|
807 * 776 *
808 * Simple function copies the input and fixes the sign to positive 777 * Simple function copies the input and fixes the sign to positive
809 */ 778 */
822 /* force the sign of b to positive */ 791 /* force the sign of b to positive */
823 b->sign = MP_ZPOS; 792 b->sign = MP_ZPOS;
824 793
825 return MP_OKAY; 794 return MP_OKAY;
826 } 795 }
796 #endif
827 797
828 /* End: bn_mp_abs.c */ 798 /* End: bn_mp_abs.c */
829 799
830 /* Start: bn_mp_add.c */ 800 /* Start: bn_mp_add.c */
831 /* LibTomMath, multiple-precision integer library -- Tom St Denis 801 #include <tommath.h>
832 * 802 #ifdef BN_MP_ADD_C
833 * LibTomMath is a library that provides multiple-precision 803 /* LibTomMath, multiple-precision integer library -- Tom St Denis
834 * integer arithmetic as well as number theoretic functionality. 804 *
835 * 805 * LibTomMath is a library that provides multiple-precision
836 * The library was designed directly after the MPI library by 806 * integer arithmetic as well as number theoretic functionality.
837 * Michael Fromberger but has been written from scratch with 807 *
838 * additional optimizations in place. 808 * The library was designed directly after the MPI library by
839 * 809 * Michael Fromberger but has been written from scratch with
840 * The library is free for all purposes without any express 810 * additional optimizations in place.
841 * guarantee it works. 811 *
842 * 812 * The library is free for all purposes without any express
843 * Tom St Denis, [email protected], http://math.libtomcrypt.org 813 * guarantee it works.
844 */ 814 *
845 #include <tommath.h> 815 * Tom St Denis, [email protected], http://math.libtomcrypt.org
816 */
846 817
847 /* high level addition (handles signs) */ 818 /* high level addition (handles signs) */
848 int mp_add (mp_int * a, mp_int * b, mp_int * c) 819 int mp_add (mp_int * a, mp_int * b, mp_int * c)
849 { 820 {
850 int sa, sb, res; 821 int sa, sb, res;
873 } 844 }
874 } 845 }
875 return res; 846 return res;
876 } 847 }
877 848
849 #endif
878 850
879 /* End: bn_mp_add.c */ 851 /* End: bn_mp_add.c */
880 852
881 /* Start: bn_mp_add_d.c */ 853 /* Start: bn_mp_add_d.c */
882 /* LibTomMath, multiple-precision integer library -- Tom St Denis 854 #include <tommath.h>
883 * 855 #ifdef BN_MP_ADD_D_C
884 * LibTomMath is a library that provides multiple-precision 856 /* LibTomMath, multiple-precision integer library -- Tom St Denis
885 * integer arithmetic as well as number theoretic functionality. 857 *
886 * 858 * LibTomMath is a library that provides multiple-precision
887 * The library was designed directly after the MPI library by 859 * integer arithmetic as well as number theoretic functionality.
888 * Michael Fromberger but has been written from scratch with 860 *
889 * additional optimizations in place. 861 * The library was designed directly after the MPI library by
890 * 862 * Michael Fromberger but has been written from scratch with
891 * The library is free for all purposes without any express 863 * additional optimizations in place.
892 * guarantee it works. 864 *
893 * 865 * The library is free for all purposes without any express
894 * Tom St Denis, [email protected], http://math.libtomcrypt.org 866 * guarantee it works.
895 */ 867 *
896 #include <tommath.h> 868 * Tom St Denis, [email protected], http://math.libtomcrypt.org
869 */
897 870
898 /* single digit addition */ 871 /* single digit addition */
899 int 872 int
900 mp_add_d (mp_int * a, mp_digit b, mp_int * c) 873 mp_add_d (mp_int * a, mp_digit b, mp_int * c)
901 { 874 {
980 mp_clamp(c); 953 mp_clamp(c);
981 954
982 return MP_OKAY; 955 return MP_OKAY;
983 } 956 }
984 957
958 #endif
985 959
986 /* End: bn_mp_add_d.c */ 960 /* End: bn_mp_add_d.c */
987 961
988 /* Start: bn_mp_addmod.c */ 962 /* Start: bn_mp_addmod.c */
989 /* LibTomMath, multiple-precision integer library -- Tom St Denis 963 #include <tommath.h>
990 * 964 #ifdef BN_MP_ADDMOD_C
991 * LibTomMath is a library that provides multiple-precision 965 /* LibTomMath, multiple-precision integer library -- Tom St Denis
992 * integer arithmetic as well as number theoretic functionality. 966 *
993 * 967 * LibTomMath is a library that provides multiple-precision
994 * The library was designed directly after the MPI library by 968 * integer arithmetic as well as number theoretic functionality.
995 * Michael Fromberger but has been written from scratch with 969 *
996 * additional optimizations in place. 970 * The library was designed directly after the MPI library by
997 * 971 * Michael Fromberger but has been written from scratch with
998 * The library is free for all purposes without any express 972 * additional optimizations in place.
999 * guarantee it works. 973 *
1000 * 974 * The library is free for all purposes without any express
1001 * Tom St Denis, [email protected], http://math.libtomcrypt.org 975 * guarantee it works.
1002 */ 976 *
1003 #include <tommath.h> 977 * Tom St Denis, [email protected], http://math.libtomcrypt.org
978 */
1004 979
1005 /* d = a + b (mod c) */ 980 /* d = a + b (mod c) */
1006 int 981 int
1007 mp_addmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d) 982 mp_addmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
1008 { 983 {
1019 } 994 }
1020 res = mp_mod (&t, c, d); 995 res = mp_mod (&t, c, d);
1021 mp_clear (&t); 996 mp_clear (&t);
1022 return res; 997 return res;
1023 } 998 }
999 #endif
1024 1000
1025 /* End: bn_mp_addmod.c */ 1001 /* End: bn_mp_addmod.c */
1026 1002
1027 /* Start: bn_mp_and.c */ 1003 /* Start: bn_mp_and.c */
1028 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1004 #include <tommath.h>
1029 * 1005 #ifdef BN_MP_AND_C
1030 * LibTomMath is a library that provides multiple-precision 1006 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1031 * integer arithmetic as well as number theoretic functionality. 1007 *
1032 * 1008 * LibTomMath is a library that provides multiple-precision
1033 * The library was designed directly after the MPI library by 1009 * integer arithmetic as well as number theoretic functionality.
1034 * Michael Fromberger but has been written from scratch with 1010 *
1035 * additional optimizations in place. 1011 * The library was designed directly after the MPI library by
1036 * 1012 * Michael Fromberger but has been written from scratch with
1037 * The library is free for all purposes without any express 1013 * additional optimizations in place.
1038 * guarantee it works. 1014 *
1039 * 1015 * The library is free for all purposes without any express
1040 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1016 * guarantee it works.
1041 */ 1017 *
1042 #include <tommath.h> 1018 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1019 */
1043 1020
1044 /* AND two ints together */ 1021 /* AND two ints together */
1045 int 1022 int
1046 mp_and (mp_int * a, mp_int * b, mp_int * c) 1023 mp_and (mp_int * a, mp_int * b, mp_int * c)
1047 { 1024 {
1074 mp_clamp (&t); 1051 mp_clamp (&t);
1075 mp_exch (c, &t); 1052 mp_exch (c, &t);
1076 mp_clear (&t); 1053 mp_clear (&t);
1077 return MP_OKAY; 1054 return MP_OKAY;
1078 } 1055 }
1056 #endif
1079 1057
1080 /* End: bn_mp_and.c */ 1058 /* End: bn_mp_and.c */
1081 1059
1082 /* Start: bn_mp_clamp.c */ 1060 /* Start: bn_mp_clamp.c */
1083 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1061 #include <tommath.h>
1084 * 1062 #ifdef BN_MP_CLAMP_C
1085 * LibTomMath is a library that provides multiple-precision 1063 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1086 * integer arithmetic as well as number theoretic functionality. 1064 *
1087 * 1065 * LibTomMath is a library that provides multiple-precision
1088 * The library was designed directly after the MPI library by 1066 * integer arithmetic as well as number theoretic functionality.
1089 * Michael Fromberger but has been written from scratch with 1067 *
1090 * additional optimizations in place. 1068 * The library was designed directly after the MPI library by
1091 * 1069 * Michael Fromberger but has been written from scratch with
1092 * The library is free for all purposes without any express 1070 * additional optimizations in place.
1093 * guarantee it works. 1071 *
1094 * 1072 * The library is free for all purposes without any express
1095 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1073 * guarantee it works.
1096 */ 1074 *
1097 #include <tommath.h> 1075 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1076 */
1098 1077
1099 /* trim unused digits 1078 /* trim unused digits
1100 * 1079 *
1101 * This is used to ensure that leading zero digits are 1080 * This is used to ensure that leading zero digits are
1102 * trimed and the leading "used" digit will be non-zero 1081 * trimed and the leading "used" digit will be non-zero
1116 /* reset the sign flag if used == 0 */ 1095 /* reset the sign flag if used == 0 */
1117 if (a->used == 0) { 1096 if (a->used == 0) {
1118 a->sign = MP_ZPOS; 1097 a->sign = MP_ZPOS;
1119 } 1098 }
1120 } 1099 }
1100 #endif
1121 1101
1122 /* End: bn_mp_clamp.c */ 1102 /* End: bn_mp_clamp.c */
1123 1103
1124 /* Start: bn_mp_clear.c */ 1104 /* Start: bn_mp_clear.c */
1125 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1105 #include <tommath.h>
1126 * 1106 #ifdef BN_MP_CLEAR_C
1127 * LibTomMath is a library that provides multiple-precision 1107 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1128 * integer arithmetic as well as number theoretic functionality. 1108 *
1129 * 1109 * LibTomMath is a library that provides multiple-precision
1130 * The library was designed directly after the MPI library by 1110 * integer arithmetic as well as number theoretic functionality.
1131 * Michael Fromberger but has been written from scratch with 1111 *
1132 * additional optimizations in place. 1112 * The library was designed directly after the MPI library by
1133 * 1113 * Michael Fromberger but has been written from scratch with
1134 * The library is free for all purposes without any express 1114 * additional optimizations in place.
1135 * guarantee it works. 1115 *
1136 * 1116 * The library is free for all purposes without any express
1137 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1117 * guarantee it works.
1138 */ 1118 *
1139 #include <tommath.h> 1119 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1120 */
1140 1121
1141 /* clear one (frees) */ 1122 /* clear one (frees) */
1142 void 1123 void
1143 mp_clear (mp_int * a) 1124 mp_clear (mp_int * a)
1144 { 1125 {
1126 int i;
1127
1145 /* only do anything if a hasn't been freed previously */ 1128 /* only do anything if a hasn't been freed previously */
1146 if (a->dp != NULL) { 1129 if (a->dp != NULL) {
1147 /* first zero the digits */ 1130 /* first zero the digits */
1148 memset (a->dp, 0, sizeof (mp_digit) * a->used); 1131 for (i = 0; i < a->used; i++) {
1132 a->dp[i] = 0;
1133 }
1149 1134
1150 /* free ram */ 1135 /* free ram */
1151 XFREE(a->dp); 1136 XFREE(a->dp);
1152 1137
1153 /* reset members to make debugging easier */ 1138 /* reset members to make debugging easier */
1154 a->dp = NULL; 1139 a->dp = NULL;
1155 a->alloc = a->used = 0; 1140 a->alloc = a->used = 0;
1156 a->sign = MP_ZPOS; 1141 a->sign = MP_ZPOS;
1157 } 1142 }
1158 } 1143 }
1144 #endif
1159 1145
1160 /* End: bn_mp_clear.c */ 1146 /* End: bn_mp_clear.c */
1161 1147
1162 /* Start: bn_mp_clear_multi.c */ 1148 /* Start: bn_mp_clear_multi.c */
1163 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1149 #include <tommath.h>
1164 * 1150 #ifdef BN_MP_CLEAR_MULTI_C
1165 * LibTomMath is a library that provides multiple-precision 1151 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1166 * integer arithmetic as well as number theoretic functionality. 1152 *
1167 * 1153 * LibTomMath is a library that provides multiple-precision
1168 * The library was designed directly after the MPI library by 1154 * integer arithmetic as well as number theoretic functionality.
1169 * Michael Fromberger but has been written from scratch with 1155 *
1170 * additional optimizations in place. 1156 * The library was designed directly after the MPI library by
1171 * 1157 * Michael Fromberger but has been written from scratch with
1172 * The library is free for all purposes without any express 1158 * additional optimizations in place.
1173 * guarantee it works. 1159 *
1174 * 1160 * The library is free for all purposes without any express
1175 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1161 * guarantee it works.
1176 */ 1162 *
1177 #include <tommath.h> 1163 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1164 */
1178 #include <stdarg.h> 1165 #include <stdarg.h>
1179 1166
1180 void mp_clear_multi(mp_int *mp, ...) 1167 void mp_clear_multi(mp_int *mp, ...)
1181 { 1168 {
1182 mp_int* next_mp = mp; 1169 mp_int* next_mp = mp;
1186 mp_clear(next_mp); 1173 mp_clear(next_mp);
1187 next_mp = va_arg(args, mp_int*); 1174 next_mp = va_arg(args, mp_int*);
1188 } 1175 }
1189 va_end(args); 1176 va_end(args);
1190 } 1177 }
1178 #endif
1191 1179
1192 /* End: bn_mp_clear_multi.c */ 1180 /* End: bn_mp_clear_multi.c */
1193 1181
1194 /* Start: bn_mp_cmp.c */ 1182 /* Start: bn_mp_cmp.c */
1195 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1183 #include <tommath.h>
1196 * 1184 #ifdef BN_MP_CMP_C
1197 * LibTomMath is a library that provides multiple-precision 1185 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1198 * integer arithmetic as well as number theoretic functionality. 1186 *
1199 * 1187 * LibTomMath is a library that provides multiple-precision
1200 * The library was designed directly after the MPI library by 1188 * integer arithmetic as well as number theoretic functionality.
1201 * Michael Fromberger but has been written from scratch with 1189 *
1202 * additional optimizations in place. 1190 * The library was designed directly after the MPI library by
1203 * 1191 * Michael Fromberger but has been written from scratch with
1204 * The library is free for all purposes without any express 1192 * additional optimizations in place.
1205 * guarantee it works. 1193 *
1206 * 1194 * The library is free for all purposes without any express
1207 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1195 * guarantee it works.
1208 */ 1196 *
1209 #include <tommath.h> 1197 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1198 */
1210 1199
1211 /* compare two ints (signed)*/ 1200 /* compare two ints (signed)*/
1212 int 1201 int
1213 mp_cmp (mp_int * a, mp_int * b) 1202 mp_cmp (mp_int * a, mp_int * b)
1214 { 1203 {
1227 return mp_cmp_mag(b, a); 1216 return mp_cmp_mag(b, a);
1228 } else { 1217 } else {
1229 return mp_cmp_mag(a, b); 1218 return mp_cmp_mag(a, b);
1230 } 1219 }
1231 } 1220 }
1221 #endif
1232 1222
1233 /* End: bn_mp_cmp.c */ 1223 /* End: bn_mp_cmp.c */
1234 1224
1235 /* Start: bn_mp_cmp_d.c */ 1225 /* Start: bn_mp_cmp_d.c */
1236 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1226 #include <tommath.h>
1237 * 1227 #ifdef BN_MP_CMP_D_C
1238 * LibTomMath is a library that provides multiple-precision 1228 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1239 * integer arithmetic as well as number theoretic functionality. 1229 *
1240 * 1230 * LibTomMath is a library that provides multiple-precision
1241 * The library was designed directly after the MPI library by 1231 * integer arithmetic as well as number theoretic functionality.
1242 * Michael Fromberger but has been written from scratch with 1232 *
1243 * additional optimizations in place. 1233 * The library was designed directly after the MPI library by
1244 * 1234 * Michael Fromberger but has been written from scratch with
1245 * The library is free for all purposes without any express 1235 * additional optimizations in place.
1246 * guarantee it works. 1236 *
1247 * 1237 * The library is free for all purposes without any express
1248 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1238 * guarantee it works.
1249 */ 1239 *
1250 #include <tommath.h> 1240 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1241 */
1251 1242
1252 /* compare a digit */ 1243 /* compare a digit */
1253 int mp_cmp_d(mp_int * a, mp_digit b) 1244 int mp_cmp_d(mp_int * a, mp_digit b)
1254 { 1245 {
1255 /* compare based on sign */ 1246 /* compare based on sign */
1269 return MP_LT; 1260 return MP_LT;
1270 } else { 1261 } else {
1271 return MP_EQ; 1262 return MP_EQ;
1272 } 1263 }
1273 } 1264 }
1265 #endif
1274 1266
1275 /* End: bn_mp_cmp_d.c */ 1267 /* End: bn_mp_cmp_d.c */
1276 1268
1277 /* Start: bn_mp_cmp_mag.c */ 1269 /* Start: bn_mp_cmp_mag.c */
1278 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1270 #include <tommath.h>
1279 * 1271 #ifdef BN_MP_CMP_MAG_C
1280 * LibTomMath is a library that provides multiple-precision 1272 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1281 * integer arithmetic as well as number theoretic functionality. 1273 *
1282 * 1274 * LibTomMath is a library that provides multiple-precision
1283 * The library was designed directly after the MPI library by 1275 * integer arithmetic as well as number theoretic functionality.
1284 * Michael Fromberger but has been written from scratch with 1276 *
1285 * additional optimizations in place. 1277 * The library was designed directly after the MPI library by
1286 * 1278 * Michael Fromberger but has been written from scratch with
1287 * The library is free for all purposes without any express 1279 * additional optimizations in place.
1288 * guarantee it works. 1280 *
1289 * 1281 * The library is free for all purposes without any express
1290 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1282 * guarantee it works.
1291 */ 1283 *
1292 #include <tommath.h> 1284 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1285 */
1293 1286
1294 /* compare maginitude of two ints (unsigned) */ 1287 /* compare maginitude of two ints (unsigned) */
1295 int mp_cmp_mag (mp_int * a, mp_int * b) 1288 int mp_cmp_mag (mp_int * a, mp_int * b)
1296 { 1289 {
1297 int n; 1290 int n;
1322 return MP_LT; 1315 return MP_LT;
1323 } 1316 }
1324 } 1317 }
1325 return MP_EQ; 1318 return MP_EQ;
1326 } 1319 }
1320 #endif
1327 1321
1328 /* End: bn_mp_cmp_mag.c */ 1322 /* End: bn_mp_cmp_mag.c */
1329 1323
1330 /* Start: bn_mp_cnt_lsb.c */ 1324 /* Start: bn_mp_cnt_lsb.c */
1331 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1325 #include <tommath.h>
1332 * 1326 #ifdef BN_MP_CNT_LSB_C
1333 * LibTomMath is a library that provides multiple-precision 1327 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1334 * integer arithmetic as well as number theoretic functionality. 1328 *
1335 * 1329 * LibTomMath is a library that provides multiple-precision
1336 * The library was designed directly after the MPI library by 1330 * integer arithmetic as well as number theoretic functionality.
1337 * Michael Fromberger but has been written from scratch with 1331 *
1338 * additional optimizations in place. 1332 * The library was designed directly after the MPI library by
1339 * 1333 * Michael Fromberger but has been written from scratch with
1340 * The library is free for all purposes without any express 1334 * additional optimizations in place.
1341 * guarantee it works. 1335 *
1342 * 1336 * The library is free for all purposes without any express
1343 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1337 * guarantee it works.
1344 */ 1338 *
1345 #include <tommath.h> 1339 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1340 */
1346 1341
1347 static const int lnz[16] = { 1342 static const int lnz[16] = {
1348 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0 1343 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
1349 }; 1344 };
1350 1345
1373 } while (qq == 0); 1368 } while (qq == 0);
1374 } 1369 }
1375 return x; 1370 return x;
1376 } 1371 }
1377 1372
1373 #endif
1378 1374
1379 /* End: bn_mp_cnt_lsb.c */ 1375 /* End: bn_mp_cnt_lsb.c */
1380 1376
1381 /* Start: bn_mp_copy.c */ 1377 /* Start: bn_mp_copy.c */
1382 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1378 #include <tommath.h>
1383 * 1379 #ifdef BN_MP_COPY_C
1384 * LibTomMath is a library that provides multiple-precision 1380 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1385 * integer arithmetic as well as number theoretic functionality. 1381 *
1386 * 1382 * LibTomMath is a library that provides multiple-precision
1387 * The library was designed directly after the MPI library by 1383 * integer arithmetic as well as number theoretic functionality.
1388 * Michael Fromberger but has been written from scratch with 1384 *
1389 * additional optimizations in place. 1385 * The library was designed directly after the MPI library by
1390 * 1386 * Michael Fromberger but has been written from scratch with
1391 * The library is free for all purposes without any express 1387 * additional optimizations in place.
1392 * guarantee it works. 1388 *
1393 * 1389 * The library is free for all purposes without any express
1394 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1390 * guarantee it works.
1395 */ 1391 *
1396 #include <tommath.h> 1392 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1393 */
1397 1394
1398 /* copy, b = a */ 1395 /* copy, b = a */
1399 int 1396 int
1400 mp_copy (mp_int * a, mp_int * b) 1397 mp_copy (mp_int * a, mp_int * b)
1401 { 1398 {
1439 /* copy used count and sign */ 1436 /* copy used count and sign */
1440 b->used = a->used; 1437 b->used = a->used;
1441 b->sign = a->sign; 1438 b->sign = a->sign;
1442 return MP_OKAY; 1439 return MP_OKAY;
1443 } 1440 }
1441 #endif
1444 1442
1445 /* End: bn_mp_copy.c */ 1443 /* End: bn_mp_copy.c */
1446 1444
1447 /* Start: bn_mp_count_bits.c */ 1445 /* Start: bn_mp_count_bits.c */
1448 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1446 #include <tommath.h>
1449 * 1447 #ifdef BN_MP_COUNT_BITS_C
1450 * LibTomMath is a library that provides multiple-precision 1448 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1451 * integer arithmetic as well as number theoretic functionality. 1449 *
1452 * 1450 * LibTomMath is a library that provides multiple-precision
1453 * The library was designed directly after the MPI library by 1451 * integer arithmetic as well as number theoretic functionality.
1454 * Michael Fromberger but has been written from scratch with 1452 *
1455 * additional optimizations in place. 1453 * The library was designed directly after the MPI library by
1456 * 1454 * Michael Fromberger but has been written from scratch with
1457 * The library is free for all purposes without any express 1455 * additional optimizations in place.
1458 * guarantee it works. 1456 *
1459 * 1457 * The library is free for all purposes without any express
1460 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1458 * guarantee it works.
1461 */ 1459 *
1462 #include <tommath.h> 1460 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1461 */
1463 1462
1464 /* returns the number of bits in an int */ 1463 /* returns the number of bits in an int */
1465 int 1464 int
1466 mp_count_bits (mp_int * a) 1465 mp_count_bits (mp_int * a)
1467 { 1466 {
1482 ++r; 1481 ++r;
1483 q >>= ((mp_digit) 1); 1482 q >>= ((mp_digit) 1);
1484 } 1483 }
1485 return r; 1484 return r;
1486 } 1485 }
1486 #endif
1487 1487
1488 /* End: bn_mp_count_bits.c */ 1488 /* End: bn_mp_count_bits.c */
1489 1489
1490 /* Start: bn_mp_div.c */ 1490 /* Start: bn_mp_div.c */
1491 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1491 #include <tommath.h>
1492 * 1492 #ifdef BN_MP_DIV_C
1493 * LibTomMath is a library that provides multiple-precision 1493 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1494 * integer arithmetic as well as number theoretic functionality. 1494 *
1495 * 1495 * LibTomMath is a library that provides multiple-precision
1496 * The library was designed directly after the MPI library by 1496 * integer arithmetic as well as number theoretic functionality.
1497 * Michael Fromberger but has been written from scratch with 1497 *
1498 * additional optimizations in place. 1498 * The library was designed directly after the MPI library by
1499 * 1499 * Michael Fromberger but has been written from scratch with
1500 * The library is free for all purposes without any express 1500 * additional optimizations in place.
1501 * guarantee it works. 1501 *
1502 * 1502 * The library is free for all purposes without any express
1503 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1503 * guarantee it works.
1504 */ 1504 *
1505 #include <tommath.h> 1505 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1506 */
1507
1508 #ifdef BN_MP_DIV_SMALL
1509
1510 /* slower bit-bang division... also smaller */
1511 int mp_div(mp_int * a, mp_int * b, mp_int * c, mp_int * d)
1512 {
1513 mp_int ta, tb, tq, q;
1514 int res, n, n2;
1515
1516 /* is divisor zero ? */
1517 if (mp_iszero (b) == 1) {
1518 return MP_VAL;
1519 }
1520
1521 /* if a < b then q=0, r = a */
1522 if (mp_cmp_mag (a, b) == MP_LT) {
1523 if (d != NULL) {
1524 res = mp_copy (a, d);
1525 } else {
1526 res = MP_OKAY;
1527 }
1528 if (c != NULL) {
1529 mp_zero (c);
1530 }
1531 return res;
1532 }
1533
1534 /* init our temps */
1535 if ((res = mp_init_multi(&ta, &tb, &tq, &q, NULL) != MP_OKAY)) {
1536 return res;
1537 }
1538
1539
1540 mp_set(&tq, 1);
1541 n = mp_count_bits(a) - mp_count_bits(b);
1542 if (((res = mp_copy(a, &ta)) != MP_OKAY) ||
1543 ((res = mp_copy(b, &tb)) != MP_OKAY) ||
1544 ((res = mp_mul_2d(&tb, n, &tb)) != MP_OKAY) ||
1545 ((res = mp_mul_2d(&tq, n, &tq)) != MP_OKAY)) {
1546 goto __ERR;
1547 }
1548
1549 while (n-- >= 0) {
1550 if (mp_cmp(&tb, &ta) != MP_GT) {
1551 if (((res = mp_sub(&ta, &tb, &ta)) != MP_OKAY) ||
1552 ((res = mp_add(&q, &tq, &q)) != MP_OKAY)) {
1553 goto __ERR;
1554 }
1555 }
1556 if (((res = mp_div_2d(&tb, 1, &tb, NULL)) != MP_OKAY) ||
1557 ((res = mp_div_2d(&tq, 1, &tq, NULL)) != MP_OKAY)) {
1558 goto __ERR;
1559 }
1560 }
1561
1562 /* now q == quotient and ta == remainder */
1563 n = a->sign;
1564 n2 = (a->sign == b->sign ? MP_ZPOS : MP_NEG);
1565 if (c != NULL) {
1566 mp_exch(c, &q);
1567 c->sign = n2;
1568 }
1569 if (d != NULL) {
1570 mp_exch(d, &ta);
1571 d->sign = n;
1572 }
1573 __ERR:
1574 mp_clear_multi(&ta, &tb, &tq, &q, NULL);
1575 return res;
1576 }
1577
1578 #else
1506 1579
1507 /* integer signed division. 1580 /* integer signed division.
1508 * c*b + d == a [e.g. a/b, c=quotient, d=remainder] 1581 * c*b + d == a [e.g. a/b, c=quotient, d=remainder]
1509 * HAC pp.598 Algorithm 14.20 1582 * HAC pp.598 Algorithm 14.20
1510 * 1583 *
1675 /* now q is the quotient and x is the remainder 1748 /* now q is the quotient and x is the remainder
1676 * [which we have to normalize] 1749 * [which we have to normalize]
1677 */ 1750 */
1678 1751
1679 /* get sign before writing to c */ 1752 /* get sign before writing to c */
1680 x.sign = a->sign; 1753 x.sign = x.used == 0 ? MP_ZPOS : a->sign;
1681 1754
1682 if (c != NULL) { 1755 if (c != NULL) {
1683 mp_clamp (&q); 1756 mp_clamp (&q);
1684 mp_exch (&q, c); 1757 mp_exch (&q, c);
1685 c->sign = neg; 1758 c->sign = neg;
1698 __T1:mp_clear (&t1); 1771 __T1:mp_clear (&t1);
1699 __Q:mp_clear (&q); 1772 __Q:mp_clear (&q);
1700 return res; 1773 return res;
1701 } 1774 }
1702 1775
1776 #endif
1777
1778 #endif
1779
1703 /* End: bn_mp_div.c */ 1780 /* End: bn_mp_div.c */
1704 1781
1705 /* Start: bn_mp_div_2.c */ 1782 /* Start: bn_mp_div_2.c */
1706 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1783 #include <tommath.h>
1707 * 1784 #ifdef BN_MP_DIV_2_C
1708 * LibTomMath is a library that provides multiple-precision 1785 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1709 * integer arithmetic as well as number theoretic functionality. 1786 *
1710 * 1787 * LibTomMath is a library that provides multiple-precision
1711 * The library was designed directly after the MPI library by 1788 * integer arithmetic as well as number theoretic functionality.
1712 * Michael Fromberger but has been written from scratch with 1789 *
1713 * additional optimizations in place. 1790 * The library was designed directly after the MPI library by
1714 * 1791 * Michael Fromberger but has been written from scratch with
1715 * The library is free for all purposes without any express 1792 * additional optimizations in place.
1716 * guarantee it works. 1793 *
1717 * 1794 * The library is free for all purposes without any express
1718 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1795 * guarantee it works.
1719 */ 1796 *
1720 #include <tommath.h> 1797 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1798 */
1721 1799
1722 /* b = a/2 */ 1800 /* b = a/2 */
1723 int mp_div_2(mp_int * a, mp_int * b) 1801 int mp_div_2(mp_int * a, mp_int * b)
1724 { 1802 {
1725 int x, res, oldused; 1803 int x, res, oldused;
1763 } 1841 }
1764 b->sign = a->sign; 1842 b->sign = a->sign;
1765 mp_clamp (b); 1843 mp_clamp (b);
1766 return MP_OKAY; 1844 return MP_OKAY;
1767 } 1845 }
1846 #endif
1768 1847
1769 /* End: bn_mp_div_2.c */ 1848 /* End: bn_mp_div_2.c */
1770 1849
1771 /* Start: bn_mp_div_2d.c */ 1850 /* Start: bn_mp_div_2d.c */
1772 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1851 #include <tommath.h>
1773 * 1852 #ifdef BN_MP_DIV_2D_C
1774 * LibTomMath is a library that provides multiple-precision 1853 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1775 * integer arithmetic as well as number theoretic functionality. 1854 *
1776 * 1855 * LibTomMath is a library that provides multiple-precision
1777 * The library was designed directly after the MPI library by 1856 * integer arithmetic as well as number theoretic functionality.
1778 * Michael Fromberger but has been written from scratch with 1857 *
1779 * additional optimizations in place. 1858 * The library was designed directly after the MPI library by
1780 * 1859 * Michael Fromberger but has been written from scratch with
1781 * The library is free for all purposes without any express 1860 * additional optimizations in place.
1782 * guarantee it works. 1861 *
1783 * 1862 * The library is free for all purposes without any express
1784 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1863 * guarantee it works.
1785 */ 1864 *
1786 #include <tommath.h> 1865 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1866 */
1787 1867
1788 /* shift right by a certain bit count (store quotient in c, optional remainder in d) */ 1868 /* shift right by a certain bit count (store quotient in c, optional remainder in d) */
1789 int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d) 1869 int mp_div_2d (mp_int * a, int b, mp_int * c, mp_int * d)
1790 { 1870 {
1791 mp_digit D, r, rr; 1871 mp_digit D, r, rr;
1858 mp_exch (&t, d); 1938 mp_exch (&t, d);
1859 } 1939 }
1860 mp_clear (&t); 1940 mp_clear (&t);
1861 return MP_OKAY; 1941 return MP_OKAY;
1862 } 1942 }
1943 #endif
1863 1944
1864 /* End: bn_mp_div_2d.c */ 1945 /* End: bn_mp_div_2d.c */
1865 1946
1866 /* Start: bn_mp_div_3.c */ 1947 /* Start: bn_mp_div_3.c */
1867 /* LibTomMath, multiple-precision integer library -- Tom St Denis 1948 #include <tommath.h>
1868 * 1949 #ifdef BN_MP_DIV_3_C
1869 * LibTomMath is a library that provides multiple-precision 1950 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1870 * integer arithmetic as well as number theoretic functionality. 1951 *
1871 * 1952 * LibTomMath is a library that provides multiple-precision
1872 * The library was designed directly after the MPI library by 1953 * integer arithmetic as well as number theoretic functionality.
1873 * Michael Fromberger but has been written from scratch with 1954 *
1874 * additional optimizations in place. 1955 * The library was designed directly after the MPI library by
1875 * 1956 * Michael Fromberger but has been written from scratch with
1876 * The library is free for all purposes without any express 1957 * additional optimizations in place.
1877 * guarantee it works. 1958 *
1878 * 1959 * The library is free for all purposes without any express
1879 * Tom St Denis, [email protected], http://math.libtomcrypt.org 1960 * guarantee it works.
1880 */ 1961 *
1881 #include <tommath.h> 1962 * Tom St Denis, [email protected], http://math.libtomcrypt.org
1963 */
1882 1964
1883 /* divide by three (based on routine from MPI and the GMP manual) */ 1965 /* divide by three (based on routine from MPI and the GMP manual) */
1884 int 1966 int
1885 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d) 1967 mp_div_3 (mp_int * a, mp_int *c, mp_digit * d)
1886 { 1968 {
1935 mp_clear(&q); 2017 mp_clear(&q);
1936 2018
1937 return res; 2019 return res;
1938 } 2020 }
1939 2021
2022 #endif
1940 2023
1941 /* End: bn_mp_div_3.c */ 2024 /* End: bn_mp_div_3.c */
1942 2025
1943 /* Start: bn_mp_div_d.c */ 2026 /* Start: bn_mp_div_d.c */
1944 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2027 #include <tommath.h>
1945 * 2028 #ifdef BN_MP_DIV_D_C
1946 * LibTomMath is a library that provides multiple-precision 2029 /* LibTomMath, multiple-precision integer library -- Tom St Denis
1947 * integer arithmetic as well as number theoretic functionality. 2030 *
1948 * 2031 * LibTomMath is a library that provides multiple-precision
1949 * The library was designed directly after the MPI library by 2032 * integer arithmetic as well as number theoretic functionality.
1950 * Michael Fromberger but has been written from scratch with 2033 *
1951 * additional optimizations in place. 2034 * The library was designed directly after the MPI library by
1952 * 2035 * Michael Fromberger but has been written from scratch with
1953 * The library is free for all purposes without any express 2036 * additional optimizations in place.
1954 * guarantee it works. 2037 *
1955 * 2038 * The library is free for all purposes without any express
1956 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2039 * guarantee it works.
1957 */ 2040 *
1958 #include <tommath.h> 2041 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2042 */
1959 2043
1960 static int s_is_power_of_two(mp_digit b, int *p) 2044 static int s_is_power_of_two(mp_digit b, int *p)
1961 { 2045 {
1962 int x; 2046 int x;
1963 2047
1995 } 2079 }
1996 2080
1997 /* power of two ? */ 2081 /* power of two ? */
1998 if (s_is_power_of_two(b, &ix) == 1) { 2082 if (s_is_power_of_two(b, &ix) == 1) {
1999 if (d != NULL) { 2083 if (d != NULL) {
2000 *d = a->dp[0] & ((1<<ix) - 1); 2084 *d = a->dp[0] & ((((mp_digit)1)<<ix) - 1);
2001 } 2085 }
2002 if (c != NULL) { 2086 if (c != NULL) {
2003 return mp_div_2d(a, ix, c, NULL); 2087 return mp_div_2d(a, ix, c, NULL);
2004 } 2088 }
2005 return MP_OKAY; 2089 return MP_OKAY;
2006 } 2090 }
2007 2091
2092 #ifdef BN_MP_DIV_3_C
2008 /* three? */ 2093 /* three? */
2009 if (b == 3) { 2094 if (b == 3) {
2010 return mp_div_3(a, c, d); 2095 return mp_div_3(a, c, d);
2011 } 2096 }
2097 #endif
2012 2098
2013 /* no easy answer [c'est la vie]. Just division */ 2099 /* no easy answer [c'est la vie]. Just division */
2014 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) { 2100 if ((res = mp_init_size(&q, a->used)) != MP_OKAY) {
2015 return res; 2101 return res;
2016 } 2102 }
2041 mp_clear(&q); 2127 mp_clear(&q);
2042 2128
2043 return res; 2129 return res;
2044 } 2130 }
2045 2131
2132 #endif
2046 2133
2047 /* End: bn_mp_div_d.c */ 2134 /* End: bn_mp_div_d.c */
2048 2135
2049 /* Start: bn_mp_dr_is_modulus.c */ 2136 /* Start: bn_mp_dr_is_modulus.c */
2050 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2137 #include <tommath.h>
2051 * 2138 #ifdef BN_MP_DR_IS_MODULUS_C
2052 * LibTomMath is a library that provides multiple-precision 2139 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2053 * integer arithmetic as well as number theoretic functionality. 2140 *
2054 * 2141 * LibTomMath is a library that provides multiple-precision
2055 * The library was designed directly after the MPI library by 2142 * integer arithmetic as well as number theoretic functionality.
2056 * Michael Fromberger but has been written from scratch with 2143 *
2057 * additional optimizations in place. 2144 * The library was designed directly after the MPI library by
2058 * 2145 * Michael Fromberger but has been written from scratch with
2059 * The library is free for all purposes without any express 2146 * additional optimizations in place.
2060 * guarantee it works. 2147 *
2061 * 2148 * The library is free for all purposes without any express
2062 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2149 * guarantee it works.
2063 */ 2150 *
2064 #include <tommath.h> 2151 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2152 */
2065 2153
2066 /* determines if a number is a valid DR modulus */ 2154 /* determines if a number is a valid DR modulus */
2067 int mp_dr_is_modulus(mp_int *a) 2155 int mp_dr_is_modulus(mp_int *a)
2068 { 2156 {
2069 int ix; 2157 int ix;
2082 } 2170 }
2083 } 2171 }
2084 return 1; 2172 return 1;
2085 } 2173 }
2086 2174
2175 #endif
2087 2176
2088 /* End: bn_mp_dr_is_modulus.c */ 2177 /* End: bn_mp_dr_is_modulus.c */
2089 2178
2090 /* Start: bn_mp_dr_reduce.c */ 2179 /* Start: bn_mp_dr_reduce.c */
2091 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2180 #include <tommath.h>
2092 * 2181 #ifdef BN_MP_DR_REDUCE_C
2093 * LibTomMath is a library that provides multiple-precision 2182 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2094 * integer arithmetic as well as number theoretic functionality. 2183 *
2095 * 2184 * LibTomMath is a library that provides multiple-precision
2096 * The library was designed directly after the MPI library by 2185 * integer arithmetic as well as number theoretic functionality.
2097 * Michael Fromberger but has been written from scratch with 2186 *
2098 * additional optimizations in place. 2187 * The library was designed directly after the MPI library by
2099 * 2188 * Michael Fromberger but has been written from scratch with
2100 * The library is free for all purposes without any express 2189 * additional optimizations in place.
2101 * guarantee it works. 2190 *
2102 * 2191 * The library is free for all purposes without any express
2103 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2192 * guarantee it works.
2104 */ 2193 *
2105 #include <tommath.h> 2194 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2195 */
2106 2196
2107 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm. 2197 /* reduce "x" in place modulo "n" using the Diminished Radix algorithm.
2108 * 2198 *
2109 * Based on algorithm from the paper 2199 * Based on algorithm from the paper
2110 * 2200 *
2174 s_mp_sub(x, n, x); 2264 s_mp_sub(x, n, x);
2175 goto top; 2265 goto top;
2176 } 2266 }
2177 return MP_OKAY; 2267 return MP_OKAY;
2178 } 2268 }
2269 #endif
2179 2270
2180 /* End: bn_mp_dr_reduce.c */ 2271 /* End: bn_mp_dr_reduce.c */
2181 2272
2182 /* Start: bn_mp_dr_setup.c */ 2273 /* Start: bn_mp_dr_setup.c */
2183 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2274 #include <tommath.h>
2184 * 2275 #ifdef BN_MP_DR_SETUP_C
2185 * LibTomMath is a library that provides multiple-precision 2276 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2186 * integer arithmetic as well as number theoretic functionality. 2277 *
2187 * 2278 * LibTomMath is a library that provides multiple-precision
2188 * The library was designed directly after the MPI library by 2279 * integer arithmetic as well as number theoretic functionality.
2189 * Michael Fromberger but has been written from scratch with 2280 *
2190 * additional optimizations in place. 2281 * The library was designed directly after the MPI library by
2191 * 2282 * Michael Fromberger but has been written from scratch with
2192 * The library is free for all purposes without any express 2283 * additional optimizations in place.
2193 * guarantee it works. 2284 *
2194 * 2285 * The library is free for all purposes without any express
2195 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2286 * guarantee it works.
2196 */ 2287 *
2197 #include <tommath.h> 2288 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2289 */
2198 2290
2199 /* determines the setup value */ 2291 /* determines the setup value */
2200 void mp_dr_setup(mp_int *a, mp_digit *d) 2292 void mp_dr_setup(mp_int *a, mp_digit *d)
2201 { 2293 {
2202 /* the casts are required if DIGIT_BIT is one less than 2294 /* the casts are required if DIGIT_BIT is one less than
2204 */ 2296 */
2205 *d = (mp_digit)((((mp_word)1) << ((mp_word)DIGIT_BIT)) - 2297 *d = (mp_digit)((((mp_word)1) << ((mp_word)DIGIT_BIT)) -
2206 ((mp_word)a->dp[0])); 2298 ((mp_word)a->dp[0]));
2207 } 2299 }
2208 2300
2301 #endif
2209 2302
2210 /* End: bn_mp_dr_setup.c */ 2303 /* End: bn_mp_dr_setup.c */
2211 2304
2212 /* Start: bn_mp_exch.c */ 2305 /* Start: bn_mp_exch.c */
2213 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2306 #include <tommath.h>
2214 * 2307 #ifdef BN_MP_EXCH_C
2215 * LibTomMath is a library that provides multiple-precision 2308 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2216 * integer arithmetic as well as number theoretic functionality. 2309 *
2217 * 2310 * LibTomMath is a library that provides multiple-precision
2218 * The library was designed directly after the MPI library by 2311 * integer arithmetic as well as number theoretic functionality.
2219 * Michael Fromberger but has been written from scratch with 2312 *
2220 * additional optimizations in place. 2313 * The library was designed directly after the MPI library by
2221 * 2314 * Michael Fromberger but has been written from scratch with
2222 * The library is free for all purposes without any express 2315 * additional optimizations in place.
2223 * guarantee it works. 2316 *
2224 * 2317 * The library is free for all purposes without any express
2225 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2318 * guarantee it works.
2226 */ 2319 *
2227 #include <tommath.h> 2320 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2321 */
2228 2322
2229 /* swap the elements of two integers, for cases where you can't simply swap the 2323 /* swap the elements of two integers, for cases where you can't simply swap the
2230 * mp_int pointers around 2324 * mp_int pointers around
2231 */ 2325 */
2232 void 2326 void
2236 2330
2237 t = *a; 2331 t = *a;
2238 *a = *b; 2332 *a = *b;
2239 *b = t; 2333 *b = t;
2240 } 2334 }
2335 #endif
2241 2336
2242 /* End: bn_mp_exch.c */ 2337 /* End: bn_mp_exch.c */
2243 2338
2244 /* Start: bn_mp_expt_d.c */ 2339 /* Start: bn_mp_expt_d.c */
2245 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2340 #include <tommath.h>
2246 * 2341 #ifdef BN_MP_EXPT_D_C
2247 * LibTomMath is a library that provides multiple-precision 2342 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2248 * integer arithmetic as well as number theoretic functionality. 2343 *
2249 * 2344 * LibTomMath is a library that provides multiple-precision
2250 * The library was designed directly after the MPI library by 2345 * integer arithmetic as well as number theoretic functionality.
2251 * Michael Fromberger but has been written from scratch with 2346 *
2252 * additional optimizations in place. 2347 * The library was designed directly after the MPI library by
2253 * 2348 * Michael Fromberger but has been written from scratch with
2254 * The library is free for all purposes without any express 2349 * additional optimizations in place.
2255 * guarantee it works. 2350 *
2256 * 2351 * The library is free for all purposes without any express
2257 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2352 * guarantee it works.
2258 */ 2353 *
2259 #include <tommath.h> 2354 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2355 */
2260 2356
2261 /* calculate c = a**b using a square-multiply algorithm */ 2357 /* calculate c = a**b using a square-multiply algorithm */
2262 int mp_expt_d (mp_int * a, mp_digit b, mp_int * c) 2358 int mp_expt_d (mp_int * a, mp_digit b, mp_int * c)
2263 { 2359 {
2264 int res, x; 2360 int res, x;
2291 } 2387 }
2292 2388
2293 mp_clear (&g); 2389 mp_clear (&g);
2294 return MP_OKAY; 2390 return MP_OKAY;
2295 } 2391 }
2392 #endif
2296 2393
2297 /* End: bn_mp_expt_d.c */ 2394 /* End: bn_mp_expt_d.c */
2298 2395
2299 /* Start: bn_mp_exptmod.c */ 2396 /* Start: bn_mp_exptmod.c */
2300 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2397 #include <tommath.h>
2301 * 2398 #ifdef BN_MP_EXPTMOD_C
2302 * LibTomMath is a library that provides multiple-precision 2399 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2303 * integer arithmetic as well as number theoretic functionality. 2400 *
2304 * 2401 * LibTomMath is a library that provides multiple-precision
2305 * The library was designed directly after the MPI library by 2402 * integer arithmetic as well as number theoretic functionality.
2306 * Michael Fromberger but has been written from scratch with 2403 *
2307 * additional optimizations in place. 2404 * The library was designed directly after the MPI library by
2308 * 2405 * Michael Fromberger but has been written from scratch with
2309 * The library is free for all purposes without any express 2406 * additional optimizations in place.
2310 * guarantee it works. 2407 *
2311 * 2408 * The library is free for all purposes without any express
2312 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2409 * guarantee it works.
2313 */ 2410 *
2314 #include <tommath.h> 2411 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2412 */
2315 2413
2316 2414
2317 /* this is a shell function that calls either the normal or Montgomery 2415 /* this is a shell function that calls either the normal or Montgomery
2318 * exptmod functions. Originally the call to the montgomery code was 2416 * exptmod functions. Originally the call to the montgomery code was
2319 * embedded in the normal function but that wasted alot of stack space 2417 * embedded in the normal function but that wasted alot of stack space
2328 return MP_VAL; 2426 return MP_VAL;
2329 } 2427 }
2330 2428
2331 /* if exponent X is negative we have to recurse */ 2429 /* if exponent X is negative we have to recurse */
2332 if (X->sign == MP_NEG) { 2430 if (X->sign == MP_NEG) {
2431 #ifdef BN_MP_INVMOD_C
2333 mp_int tmpG, tmpX; 2432 mp_int tmpG, tmpX;
2334 int err; 2433 int err;
2335 2434
2336 /* first compute 1/G mod P */ 2435 /* first compute 1/G mod P */
2337 if ((err = mp_init(&tmpG)) != MP_OKAY) { 2436 if ((err = mp_init(&tmpG)) != MP_OKAY) {
2354 2453
2355 /* and now compute (1/G)**|X| instead of G**X [X < 0] */ 2454 /* and now compute (1/G)**|X| instead of G**X [X < 0] */
2356 err = mp_exptmod(&tmpG, &tmpX, P, Y); 2455 err = mp_exptmod(&tmpG, &tmpX, P, Y);
2357 mp_clear_multi(&tmpG, &tmpX, NULL); 2456 mp_clear_multi(&tmpG, &tmpX, NULL);
2358 return err; 2457 return err;
2359 } 2458 #else
2360 2459 /* no invmod */
2460 return MP_VAL
2461 #endif
2462 }
2463
2464 #ifdef BN_MP_DR_IS_MODULUS_C
2361 /* is it a DR modulus? */ 2465 /* is it a DR modulus? */
2362 dr = mp_dr_is_modulus(P); 2466 dr = mp_dr_is_modulus(P);
2363 2467 #else
2468 dr = 0;
2469 #endif
2470
2471 #ifdef BN_MP_REDUCE_IS_2K_C
2364 /* if not, is it a uDR modulus? */ 2472 /* if not, is it a uDR modulus? */
2365 if (dr == 0) { 2473 if (dr == 0) {
2366 dr = mp_reduce_is_2k(P) << 1; 2474 dr = mp_reduce_is_2k(P) << 1;
2367 } 2475 }
2476 #endif
2368 2477
2369 /* if the modulus is odd or dr != 0 use the fast method */ 2478 /* if the modulus is odd or dr != 0 use the fast method */
2479 #ifdef BN_MP_EXPTMOD_FAST_C
2370 if (mp_isodd (P) == 1 || dr != 0) { 2480 if (mp_isodd (P) == 1 || dr != 0) {
2371 return mp_exptmod_fast (G, X, P, Y, dr); 2481 return mp_exptmod_fast (G, X, P, Y, dr);
2372 } else { 2482 } else {
2483 #endif
2484 #ifdef BN_S_MP_EXPTMOD_C
2373 /* otherwise use the generic Barrett reduction technique */ 2485 /* otherwise use the generic Barrett reduction technique */
2374 return s_mp_exptmod (G, X, P, Y); 2486 return s_mp_exptmod (G, X, P, Y);
2375 } 2487 #else
2376 } 2488 /* no exptmod for evens */
2377 2489 return MP_VAL;
2490 #endif
2491 #ifdef BN_MP_EXPTMOD_FAST_C
2492 }
2493 #endif
2494 }
2495
2496 #endif
2378 2497
2379 /* End: bn_mp_exptmod.c */ 2498 /* End: bn_mp_exptmod.c */
2380 2499
2381 /* Start: bn_mp_exptmod_fast.c */ 2500 /* Start: bn_mp_exptmod_fast.c */
2382 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2501 #include <tommath.h>
2383 * 2502 #ifdef BN_MP_EXPTMOD_FAST_C
2384 * LibTomMath is a library that provides multiple-precision 2503 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2385 * integer arithmetic as well as number theoretic functionality. 2504 *
2386 * 2505 * LibTomMath is a library that provides multiple-precision
2387 * The library was designed directly after the MPI library by 2506 * integer arithmetic as well as number theoretic functionality.
2388 * Michael Fromberger but has been written from scratch with 2507 *
2389 * additional optimizations in place. 2508 * The library was designed directly after the MPI library by
2390 * 2509 * Michael Fromberger but has been written from scratch with
2391 * The library is free for all purposes without any express 2510 * additional optimizations in place.
2392 * guarantee it works. 2511 *
2393 * 2512 * The library is free for all purposes without any express
2394 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2513 * guarantee it works.
2395 */ 2514 *
2396 #include <tommath.h> 2515 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2516 */
2397 2517
2398 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85 2518 /* computes Y == G**X mod P, HAC pp.616, Algorithm 14.85
2399 * 2519 *
2400 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation. 2520 * Uses a left-to-right k-ary sliding window to compute the modular exponentiation.
2401 * The value of k changes based on the size of the exponent. 2521 * The value of k changes based on the size of the exponent.
2463 } 2583 }
2464 } 2584 }
2465 2585
2466 /* determine and setup reduction code */ 2586 /* determine and setup reduction code */
2467 if (redmode == 0) { 2587 if (redmode == 0) {
2588 #ifdef BN_MP_MONTGOMERY_SETUP_C
2468 /* now setup montgomery */ 2589 /* now setup montgomery */
2469 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) { 2590 if ((err = mp_montgomery_setup (P, &mp)) != MP_OKAY) {
2470 goto __M; 2591 goto __M;
2471 } 2592 }
2593 #else
2594 err = MP_VAL;
2595 goto __M;
2596 #endif
2472 2597
2473 /* automatically pick the comba one if available (saves quite a few calls/ifs) */ 2598 /* automatically pick the comba one if available (saves quite a few calls/ifs) */
2599 #ifdef BN_FAST_MP_MONTGOMERY_REDUCE_C
2474 if (((P->used * 2 + 1) < MP_WARRAY) && 2600 if (((P->used * 2 + 1) < MP_WARRAY) &&
2475 P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 2601 P->used < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
2476 redux = fast_mp_montgomery_reduce; 2602 redux = fast_mp_montgomery_reduce;
2477 } else { 2603 } else
2604 #endif
2605 {
2606 #ifdef BN_MP_MONTGOMERY_REDUCE_C
2478 /* use slower baseline Montgomery method */ 2607 /* use slower baseline Montgomery method */
2479 redux = mp_montgomery_reduce; 2608 redux = mp_montgomery_reduce;
2609 #else
2610 err = MP_VAL;
2611 goto __M;
2612 #endif
2480 } 2613 }
2481 } else if (redmode == 1) { 2614 } else if (redmode == 1) {
2615 #if defined(BN_MP_DR_SETUP_C) && defined(BN_MP_DR_REDUCE_C)
2482 /* setup DR reduction for moduli of the form B**k - b */ 2616 /* setup DR reduction for moduli of the form B**k - b */
2483 mp_dr_setup(P, &mp); 2617 mp_dr_setup(P, &mp);
2484 redux = mp_dr_reduce; 2618 redux = mp_dr_reduce;
2619 #else
2620 err = MP_VAL;
2621 goto __M;
2622 #endif
2485 } else { 2623 } else {
2624 #if defined(BN_MP_REDUCE_2K_SETUP_C) && defined(BN_MP_REDUCE_2K_C)
2486 /* setup DR reduction for moduli of the form 2**k - b */ 2625 /* setup DR reduction for moduli of the form 2**k - b */
2487 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) { 2626 if ((err = mp_reduce_2k_setup(P, &mp)) != MP_OKAY) {
2488 goto __M; 2627 goto __M;
2489 } 2628 }
2490 redux = mp_reduce_2k; 2629 redux = mp_reduce_2k;
2630 #else
2631 err = MP_VAL;
2632 goto __M;
2633 #endif
2491 } 2634 }
2492 2635
2493 /* setup result */ 2636 /* setup result */
2494 if ((err = mp_init (&res)) != MP_OKAY) { 2637 if ((err = mp_init (&res)) != MP_OKAY) {
2495 goto __M; 2638 goto __M;
2496 } 2639 }
2497 2640
2498 /* create M table 2641 /* create M table
2499 * 2642 *
2500 * The M table contains powers of the input base, e.g. M[x] = G^x mod P 2643
2501 * 2644 *
2502 * The first half of the table is not computed though accept for M[0] and M[1] 2645 * The first half of the table is not computed though accept for M[0] and M[1]
2503 */ 2646 */
2504 2647
2505 if (redmode == 0) { 2648 if (redmode == 0) {
2649 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
2506 /* now we need R mod m */ 2650 /* now we need R mod m */
2507 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) { 2651 if ((err = mp_montgomery_calc_normalization (&res, P)) != MP_OKAY) {
2508 goto __RES; 2652 goto __RES;
2509 } 2653 }
2654 #else
2655 err = MP_VAL;
2656 goto __RES;
2657 #endif
2510 2658
2511 /* now set M[1] to G * R mod m */ 2659 /* now set M[1] to G * R mod m */
2512 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) { 2660 if ((err = mp_mulmod (G, &res, P, &M[1])) != MP_OKAY) {
2513 goto __RES; 2661 goto __RES;
2514 } 2662 }
2648 * recall that any value in a Montgomery system is 2796 * recall that any value in a Montgomery system is
2649 * actually multiplied by R mod n. So we have 2797 * actually multiplied by R mod n. So we have
2650 * to reduce one more time to cancel out the factor 2798 * to reduce one more time to cancel out the factor
2651 * of R. 2799 * of R.
2652 */ 2800 */
2653 if ((err = mp_montgomery_reduce (&res, P, mp)) != MP_OKAY) { 2801 if ((err = redux(&res, P, mp)) != MP_OKAY) {
2654 goto __RES; 2802 goto __RES;
2655 } 2803 }
2656 } 2804 }
2657 2805
2658 /* swap res with Y */ 2806 /* swap res with Y */
2664 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 2812 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
2665 mp_clear (&M[x]); 2813 mp_clear (&M[x]);
2666 } 2814 }
2667 return err; 2815 return err;
2668 } 2816 }
2817 #endif
2818
2669 2819
2670 /* End: bn_mp_exptmod_fast.c */ 2820 /* End: bn_mp_exptmod_fast.c */
2671 2821
2672 /* Start: bn_mp_exteuclid.c */ 2822 /* Start: bn_mp_exteuclid.c */
2673 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2823 #include <tommath.h>
2674 * 2824 #ifdef BN_MP_EXTEUCLID_C
2675 * LibTomMath is a library that provides multiple-precision 2825 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2676 * integer arithmetic as well as number theoretic functionality. 2826 *
2677 * 2827 * LibTomMath is a library that provides multiple-precision
2678 * The library was designed directly after the MPI library by 2828 * integer arithmetic as well as number theoretic functionality.
2679 * Michael Fromberger but has been written from scratch with 2829 *
2680 * additional optimizations in place. 2830 * The library was designed directly after the MPI library by
2681 * 2831 * Michael Fromberger but has been written from scratch with
2682 * The library is free for all purposes without any express 2832 * additional optimizations in place.
2683 * guarantee it works. 2833 *
2684 * 2834 * The library is free for all purposes without any express
2685 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2835 * guarantee it works.
2686 */ 2836 *
2687 #include <tommath.h> 2837 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2838 */
2688 2839
2689 /* Extended euclidean algorithm of (a, b) produces 2840 /* Extended euclidean algorithm of (a, b) produces
2690 a*u1 + b*u2 = u3 2841 a*u1 + b*u2 = u3
2691 */ 2842 */
2692 int mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3) 2843 int mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3)
2737 2888
2738 err = MP_OKAY; 2889 err = MP_OKAY;
2739 _ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL); 2890 _ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL);
2740 return err; 2891 return err;
2741 } 2892 }
2893 #endif
2742 2894
2743 /* End: bn_mp_exteuclid.c */ 2895 /* End: bn_mp_exteuclid.c */
2744 2896
2745 /* Start: bn_mp_fread.c */ 2897 /* Start: bn_mp_fread.c */
2746 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2898 #include <tommath.h>
2747 * 2899 #ifdef BN_MP_FREAD_C
2748 * LibTomMath is a library that provides multiple-precision 2900 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2749 * integer arithmetic as well as number theoretic functionality. 2901 *
2750 * 2902 * LibTomMath is a library that provides multiple-precision
2751 * The library was designed directly after the MPI library by 2903 * integer arithmetic as well as number theoretic functionality.
2752 * Michael Fromberger but has been written from scratch with 2904 *
2753 * additional optimizations in place. 2905 * The library was designed directly after the MPI library by
2754 * 2906 * Michael Fromberger but has been written from scratch with
2755 * The library is free for all purposes without any express 2907 * additional optimizations in place.
2756 * guarantee it works. 2908 *
2757 * 2909 * The library is free for all purposes without any express
2758 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2910 * guarantee it works.
2759 */ 2911 *
2760 #include <tommath.h> 2912 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2913 */
2761 2914
2762 /* read a bigint from a file stream in ASCII */ 2915 /* read a bigint from a file stream in ASCII */
2763 int mp_fread(mp_int *a, int radix, FILE *stream) 2916 int mp_fread(mp_int *a, int radix, FILE *stream)
2764 { 2917 {
2765 int err, ch, neg, y; 2918 int err, ch, neg, y;
2802 } 2955 }
2803 2956
2804 return MP_OKAY; 2957 return MP_OKAY;
2805 } 2958 }
2806 2959
2960 #endif
2807 2961
2808 /* End: bn_mp_fread.c */ 2962 /* End: bn_mp_fread.c */
2809 2963
2810 /* Start: bn_mp_fwrite.c */ 2964 /* Start: bn_mp_fwrite.c */
2811 /* LibTomMath, multiple-precision integer library -- Tom St Denis 2965 #include <tommath.h>
2812 * 2966 #ifdef BN_MP_FWRITE_C
2813 * LibTomMath is a library that provides multiple-precision 2967 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2814 * integer arithmetic as well as number theoretic functionality. 2968 *
2815 * 2969 * LibTomMath is a library that provides multiple-precision
2816 * The library was designed directly after the MPI library by 2970 * integer arithmetic as well as number theoretic functionality.
2817 * Michael Fromberger but has been written from scratch with 2971 *
2818 * additional optimizations in place. 2972 * The library was designed directly after the MPI library by
2819 * 2973 * Michael Fromberger but has been written from scratch with
2820 * The library is free for all purposes without any express 2974 * additional optimizations in place.
2821 * guarantee it works. 2975 *
2822 * 2976 * The library is free for all purposes without any express
2823 * Tom St Denis, [email protected], http://math.libtomcrypt.org 2977 * guarantee it works.
2824 */ 2978 *
2825 #include <tommath.h> 2979 * Tom St Denis, [email protected], http://math.libtomcrypt.org
2980 */
2826 2981
2827 int mp_fwrite(mp_int *a, int radix, FILE *stream) 2982 int mp_fwrite(mp_int *a, int radix, FILE *stream)
2828 { 2983 {
2829 char *buf; 2984 char *buf;
2830 int err, len, x; 2985 int err, len, x;
2852 3007
2853 XFREE (buf); 3008 XFREE (buf);
2854 return MP_OKAY; 3009 return MP_OKAY;
2855 } 3010 }
2856 3011
3012 #endif
2857 3013
2858 /* End: bn_mp_fwrite.c */ 3014 /* End: bn_mp_fwrite.c */
2859 3015
2860 /* Start: bn_mp_gcd.c */ 3016 /* Start: bn_mp_gcd.c */
2861 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3017 #include <tommath.h>
2862 * 3018 #ifdef BN_MP_GCD_C
2863 * LibTomMath is a library that provides multiple-precision 3019 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2864 * integer arithmetic as well as number theoretic functionality. 3020 *
2865 * 3021 * LibTomMath is a library that provides multiple-precision
2866 * The library was designed directly after the MPI library by 3022 * integer arithmetic as well as number theoretic functionality.
2867 * Michael Fromberger but has been written from scratch with 3023 *
2868 * additional optimizations in place. 3024 * The library was designed directly after the MPI library by
2869 * 3025 * Michael Fromberger but has been written from scratch with
2870 * The library is free for all purposes without any express 3026 * additional optimizations in place.
2871 * guarantee it works. 3027 *
2872 * 3028 * The library is free for all purposes without any express
2873 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3029 * guarantee it works.
2874 */ 3030 *
2875 #include <tommath.h> 3031 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3032 */
2876 3033
2877 /* Greatest Common Divisor using the binary method */ 3034 /* Greatest Common Divisor using the binary method */
2878 int mp_gcd (mp_int * a, mp_int * b, mp_int * c) 3035 int mp_gcd (mp_int * a, mp_int * b, mp_int * c)
2879 { 3036 {
2880 mp_int u, v; 3037 mp_int u, v;
2963 res = MP_OKAY; 3120 res = MP_OKAY;
2964 __V:mp_clear (&u); 3121 __V:mp_clear (&u);
2965 __U:mp_clear (&v); 3122 __U:mp_clear (&v);
2966 return res; 3123 return res;
2967 } 3124 }
3125 #endif
2968 3126
2969 /* End: bn_mp_gcd.c */ 3127 /* End: bn_mp_gcd.c */
2970 3128
2971 /* Start: bn_mp_get_int.c */ 3129 /* Start: bn_mp_get_int.c */
2972 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3130 #include <tommath.h>
2973 * 3131 #ifdef BN_MP_GET_INT_C
2974 * LibTomMath is a library that provides multiple-precision 3132 /* LibTomMath, multiple-precision integer library -- Tom St Denis
2975 * integer arithmetic as well as number theoretic functionality. 3133 *
2976 * 3134 * LibTomMath is a library that provides multiple-precision
2977 * The library was designed directly after the MPI library by 3135 * integer arithmetic as well as number theoretic functionality.
2978 * Michael Fromberger but has been written from scratch with 3136 *
2979 * additional optimizations in place. 3137 * The library was designed directly after the MPI library by
2980 * 3138 * Michael Fromberger but has been written from scratch with
2981 * The library is free for all purposes without any express 3139 * additional optimizations in place.
2982 * guarantee it works. 3140 *
2983 * 3141 * The library is free for all purposes without any express
2984 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3142 * guarantee it works.
2985 */ 3143 *
2986 #include <tommath.h> 3144 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3145 */
2987 3146
2988 /* get the lower 32-bits of an mp_int */ 3147 /* get the lower 32-bits of an mp_int */
2989 unsigned long mp_get_int(mp_int * a) 3148 unsigned long mp_get_int(mp_int * a)
2990 { 3149 {
2991 int i; 3150 int i;
3006 } 3165 }
3007 3166
3008 /* force result to 32-bits always so it is consistent on non 32-bit platforms */ 3167 /* force result to 32-bits always so it is consistent on non 32-bit platforms */
3009 return res & 0xFFFFFFFFUL; 3168 return res & 0xFFFFFFFFUL;
3010 } 3169 }
3170 #endif
3011 3171
3012 /* End: bn_mp_get_int.c */ 3172 /* End: bn_mp_get_int.c */
3013 3173
3014 /* Start: bn_mp_grow.c */ 3174 /* Start: bn_mp_grow.c */
3015 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3175 #include <tommath.h>
3016 * 3176 #ifdef BN_MP_GROW_C
3017 * LibTomMath is a library that provides multiple-precision 3177 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3018 * integer arithmetic as well as number theoretic functionality. 3178 *
3019 * 3179 * LibTomMath is a library that provides multiple-precision
3020 * The library was designed directly after the MPI library by 3180 * integer arithmetic as well as number theoretic functionality.
3021 * Michael Fromberger but has been written from scratch with 3181 *
3022 * additional optimizations in place. 3182 * The library was designed directly after the MPI library by
3023 * 3183 * Michael Fromberger but has been written from scratch with
3024 * The library is free for all purposes without any express 3184 * additional optimizations in place.
3025 * guarantee it works. 3185 *
3026 * 3186 * The library is free for all purposes without any express
3027 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3187 * guarantee it works.
3028 */ 3188 *
3029 #include <tommath.h> 3189 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3190 */
3030 3191
3031 /* grow as required */ 3192 /* grow as required */
3032 int mp_grow (mp_int * a, int size) 3193 int mp_grow (mp_int * a, int size)
3033 { 3194 {
3034 int i; 3195 int i;
3061 a->dp[i] = 0; 3222 a->dp[i] = 0;
3062 } 3223 }
3063 } 3224 }
3064 return MP_OKAY; 3225 return MP_OKAY;
3065 } 3226 }
3227 #endif
3066 3228
3067 /* End: bn_mp_grow.c */ 3229 /* End: bn_mp_grow.c */
3068 3230
3069 /* Start: bn_mp_init.c */ 3231 /* Start: bn_mp_init.c */
3070 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3232 #include <tommath.h>
3071 * 3233 #ifdef BN_MP_INIT_C
3072 * LibTomMath is a library that provides multiple-precision 3234 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3073 * integer arithmetic as well as number theoretic functionality. 3235 *
3074 * 3236 * LibTomMath is a library that provides multiple-precision
3075 * The library was designed directly after the MPI library by 3237 * integer arithmetic as well as number theoretic functionality.
3076 * Michael Fromberger but has been written from scratch with 3238 *
3077 * additional optimizations in place. 3239 * The library was designed directly after the MPI library by
3078 * 3240 * Michael Fromberger but has been written from scratch with
3079 * The library is free for all purposes without any express 3241 * additional optimizations in place.
3080 * guarantee it works. 3242 *
3081 * 3243 * The library is free for all purposes without any express
3082 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3244 * guarantee it works.
3083 */ 3245 *
3084 #include <tommath.h> 3246 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3085 3247 */
3086 /* init a new bigint */ 3248
3249 /* init a new mp_int */
3087 int mp_init (mp_int * a) 3250 int mp_init (mp_int * a)
3088 { 3251 {
3252 int i;
3253
3089 /* allocate memory required and clear it */ 3254 /* allocate memory required and clear it */
3090 a->dp = OPT_CAST(mp_digit) XCALLOC (sizeof (mp_digit), MP_PREC); 3255 a->dp = OPT_CAST(mp_digit) XMALLOC (sizeof (mp_digit) * MP_PREC);
3091 if (a->dp == NULL) { 3256 if (a->dp == NULL) {
3092 return MP_MEM; 3257 return MP_MEM;
3258 }
3259
3260 /* set the digits to zero */
3261 for (i = 0; i < MP_PREC; i++) {
3262 a->dp[i] = 0;
3093 } 3263 }
3094 3264
3095 /* set the used to zero, allocated digits to the default precision 3265 /* set the used to zero, allocated digits to the default precision
3096 * and sign to positive */ 3266 * and sign to positive */
3097 a->used = 0; 3267 a->used = 0;
3098 a->alloc = MP_PREC; 3268 a->alloc = MP_PREC;
3099 a->sign = MP_ZPOS; 3269 a->sign = MP_ZPOS;
3100 3270
3101 return MP_OKAY; 3271 return MP_OKAY;
3102 } 3272 }
3273 #endif
3103 3274
3104 /* End: bn_mp_init.c */ 3275 /* End: bn_mp_init.c */
3105 3276
3106 /* Start: bn_mp_init_copy.c */ 3277 /* Start: bn_mp_init_copy.c */
3107 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3278 #include <tommath.h>
3108 * 3279 #ifdef BN_MP_INIT_COPY_C
3109 * LibTomMath is a library that provides multiple-precision 3280 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3110 * integer arithmetic as well as number theoretic functionality. 3281 *
3111 * 3282 * LibTomMath is a library that provides multiple-precision
3112 * The library was designed directly after the MPI library by 3283 * integer arithmetic as well as number theoretic functionality.
3113 * Michael Fromberger but has been written from scratch with 3284 *
3114 * additional optimizations in place. 3285 * The library was designed directly after the MPI library by
3115 * 3286 * Michael Fromberger but has been written from scratch with
3116 * The library is free for all purposes without any express 3287 * additional optimizations in place.
3117 * guarantee it works. 3288 *
3118 * 3289 * The library is free for all purposes without any express
3119 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3290 * guarantee it works.
3120 */ 3291 *
3121 #include <tommath.h> 3292 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3293 */
3122 3294
3123 /* creates "a" then copies b into it */ 3295 /* creates "a" then copies b into it */
3124 int mp_init_copy (mp_int * a, mp_int * b) 3296 int mp_init_copy (mp_int * a, mp_int * b)
3125 { 3297 {
3126 int res; 3298 int res;
3128 if ((res = mp_init (a)) != MP_OKAY) { 3300 if ((res = mp_init (a)) != MP_OKAY) {
3129 return res; 3301 return res;
3130 } 3302 }
3131 return mp_copy (b, a); 3303 return mp_copy (b, a);
3132 } 3304 }
3305 #endif
3133 3306
3134 /* End: bn_mp_init_copy.c */ 3307 /* End: bn_mp_init_copy.c */
3135 3308
3136 /* Start: bn_mp_init_multi.c */ 3309 /* Start: bn_mp_init_multi.c */
3137 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3310 #include <tommath.h>
3138 * 3311 #ifdef BN_MP_INIT_MULTI_C
3139 * LibTomMath is a library that provides multiple-precision 3312 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3140 * integer arithmetic as well as number theoretic functionality. 3313 *
3141 * 3314 * LibTomMath is a library that provides multiple-precision
3142 * The library was designed directly after the MPI library by 3315 * integer arithmetic as well as number theoretic functionality.
3143 * Michael Fromberger but has been written from scratch with 3316 *
3144 * additional optimizations in place. 3317 * The library was designed directly after the MPI library by
3145 * 3318 * Michael Fromberger but has been written from scratch with
3146 * The library is free for all purposes without any express 3319 * additional optimizations in place.
3147 * guarantee it works. 3320 *
3148 * 3321 * The library is free for all purposes without any express
3149 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3322 * guarantee it works.
3150 */ 3323 *
3151 #include <tommath.h> 3324 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3325 */
3152 #include <stdarg.h> 3326 #include <stdarg.h>
3153 3327
3154 int mp_init_multi(mp_int *mp, ...) 3328 int mp_init_multi(mp_int *mp, ...)
3155 { 3329 {
3156 mp_err res = MP_OKAY; /* Assume ok until proven otherwise */ 3330 mp_err res = MP_OKAY; /* Assume ok until proven otherwise */
3185 } 3359 }
3186 va_end(args); 3360 va_end(args);
3187 return res; /* Assumed ok, if error flagged above. */ 3361 return res; /* Assumed ok, if error flagged above. */
3188 } 3362 }
3189 3363
3364 #endif
3190 3365
3191 /* End: bn_mp_init_multi.c */ 3366 /* End: bn_mp_init_multi.c */
3192 3367
3193 /* Start: bn_mp_init_set.c */ 3368 /* Start: bn_mp_init_set.c */
3194 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3369 #include <tommath.h>
3195 * 3370 #ifdef BN_MP_INIT_SET_C
3196 * LibTomMath is a library that provides multiple-precision 3371 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3197 * integer arithmetic as well as number theoretic functionality. 3372 *
3198 * 3373 * LibTomMath is a library that provides multiple-precision
3199 * The library was designed directly after the MPI library by 3374 * integer arithmetic as well as number theoretic functionality.
3200 * Michael Fromberger but has been written from scratch with 3375 *
3201 * additional optimizations in place. 3376 * The library was designed directly after the MPI library by
3202 * 3377 * Michael Fromberger but has been written from scratch with
3203 * The library is free for all purposes without any express 3378 * additional optimizations in place.
3204 * guarantee it works. 3379 *
3205 * 3380 * The library is free for all purposes without any express
3206 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3381 * guarantee it works.
3207 */ 3382 *
3208 #include <tommath.h> 3383 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3384 */
3209 3385
3210 /* initialize and set a digit */ 3386 /* initialize and set a digit */
3211 int mp_init_set (mp_int * a, mp_digit b) 3387 int mp_init_set (mp_int * a, mp_digit b)
3212 { 3388 {
3213 int err; 3389 int err;
3215 return err; 3391 return err;
3216 } 3392 }
3217 mp_set(a, b); 3393 mp_set(a, b);
3218 return err; 3394 return err;
3219 } 3395 }
3396 #endif
3220 3397
3221 /* End: bn_mp_init_set.c */ 3398 /* End: bn_mp_init_set.c */
3222 3399
3223 /* Start: bn_mp_init_set_int.c */ 3400 /* Start: bn_mp_init_set_int.c */
3224 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3401 #include <tommath.h>
3225 * 3402 #ifdef BN_MP_INIT_SET_INT_C
3226 * LibTomMath is a library that provides multiple-precision 3403 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3227 * integer arithmetic as well as number theoretic functionality. 3404 *
3228 * 3405 * LibTomMath is a library that provides multiple-precision
3229 * The library was designed directly after the MPI library by 3406 * integer arithmetic as well as number theoretic functionality.
3230 * Michael Fromberger but has been written from scratch with 3407 *
3231 * additional optimizations in place. 3408 * The library was designed directly after the MPI library by
3232 * 3409 * Michael Fromberger but has been written from scratch with
3233 * The library is free for all purposes without any express 3410 * additional optimizations in place.
3234 * guarantee it works. 3411 *
3235 * 3412 * The library is free for all purposes without any express
3236 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3413 * guarantee it works.
3237 */ 3414 *
3238 #include <tommath.h> 3415 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3416 */
3239 3417
3240 /* initialize and set a digit */ 3418 /* initialize and set a digit */
3241 int mp_init_set_int (mp_int * a, unsigned long b) 3419 int mp_init_set_int (mp_int * a, unsigned long b)
3242 { 3420 {
3243 int err; 3421 int err;
3244 if ((err = mp_init(a)) != MP_OKAY) { 3422 if ((err = mp_init(a)) != MP_OKAY) {
3245 return err; 3423 return err;
3246 } 3424 }
3247 return mp_set_int(a, b); 3425 return mp_set_int(a, b);
3248 } 3426 }
3427 #endif
3249 3428
3250 /* End: bn_mp_init_set_int.c */ 3429 /* End: bn_mp_init_set_int.c */
3251 3430
3252 /* Start: bn_mp_init_size.c */ 3431 /* Start: bn_mp_init_size.c */
3253 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3432 #include <tommath.h>
3254 * 3433 #ifdef BN_MP_INIT_SIZE_C
3255 * LibTomMath is a library that provides multiple-precision 3434 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3256 * integer arithmetic as well as number theoretic functionality. 3435 *
3257 * 3436 * LibTomMath is a library that provides multiple-precision
3258 * The library was designed directly after the MPI library by 3437 * integer arithmetic as well as number theoretic functionality.
3259 * Michael Fromberger but has been written from scratch with 3438 *
3260 * additional optimizations in place. 3439 * The library was designed directly after the MPI library by
3261 * 3440 * Michael Fromberger but has been written from scratch with
3262 * The library is free for all purposes without any express 3441 * additional optimizations in place.
3263 * guarantee it works. 3442 *
3264 * 3443 * The library is free for all purposes without any express
3265 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3444 * guarantee it works.
3266 */ 3445 *
3267 #include <tommath.h> 3446 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3447 */
3268 3448
3269 /* init an mp_init for a given size */ 3449 /* init an mp_init for a given size */
3270 int mp_init_size (mp_int * a, int size) 3450 int mp_init_size (mp_int * a, int size)
3271 { 3451 {
3452 int x;
3453
3272 /* pad size so there are always extra digits */ 3454 /* pad size so there are always extra digits */
3273 size += (MP_PREC * 2) - (size % MP_PREC); 3455 size += (MP_PREC * 2) - (size % MP_PREC);
3274 3456
3275 /* alloc mem */ 3457 /* alloc mem */
3276 a->dp = OPT_CAST(mp_digit) XCALLOC (sizeof (mp_digit), size); 3458 a->dp = OPT_CAST(mp_digit) XMALLOC (sizeof (mp_digit) * size);
3277 if (a->dp == NULL) { 3459 if (a->dp == NULL) {
3278 return MP_MEM; 3460 return MP_MEM;
3279 } 3461 }
3462
3463 /* set the members */
3280 a->used = 0; 3464 a->used = 0;
3281 a->alloc = size; 3465 a->alloc = size;
3282 a->sign = MP_ZPOS; 3466 a->sign = MP_ZPOS;
3283 3467
3468 /* zero the digits */
3469 for (x = 0; x < size; x++) {
3470 a->dp[x] = 0;
3471 }
3472
3284 return MP_OKAY; 3473 return MP_OKAY;
3285 } 3474 }
3475 #endif
3286 3476
3287 /* End: bn_mp_init_size.c */ 3477 /* End: bn_mp_init_size.c */
3288 3478
3289 /* Start: bn_mp_invmod.c */ 3479 /* Start: bn_mp_invmod.c */
3290 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3480 #include <tommath.h>
3291 * 3481 #ifdef BN_MP_INVMOD_C
3292 * LibTomMath is a library that provides multiple-precision 3482 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3293 * integer arithmetic as well as number theoretic functionality. 3483 *
3294 * 3484 * LibTomMath is a library that provides multiple-precision
3295 * The library was designed directly after the MPI library by 3485 * integer arithmetic as well as number theoretic functionality.
3296 * Michael Fromberger but has been written from scratch with 3486 *
3297 * additional optimizations in place. 3487 * The library was designed directly after the MPI library by
3298 * 3488 * Michael Fromberger but has been written from scratch with
3299 * The library is free for all purposes without any express 3489 * additional optimizations in place.
3300 * guarantee it works. 3490 *
3301 * 3491 * The library is free for all purposes without any express
3302 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3492 * guarantee it works.
3303 */ 3493 *
3304 #include <tommath.h> 3494 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3495 */
3305 3496
3306 /* hac 14.61, pp608 */ 3497 /* hac 14.61, pp608 */
3307 int mp_invmod (mp_int * a, mp_int * b, mp_int * c) 3498 int mp_invmod (mp_int * a, mp_int * b, mp_int * c)
3308 { 3499 {
3309 mp_int x, y, u, v, A, B, C, D;
3310 int res;
3311
3312 /* b cannot be negative */ 3500 /* b cannot be negative */
3313 if (b->sign == MP_NEG || mp_iszero(b) == 1) { 3501 if (b->sign == MP_NEG || mp_iszero(b) == 1) {
3314 return MP_VAL; 3502 return MP_VAL;
3315 } 3503 }
3316 3504
3505 #ifdef BN_FAST_MP_INVMOD_C
3317 /* if the modulus is odd we can use a faster routine instead */ 3506 /* if the modulus is odd we can use a faster routine instead */
3318 if (mp_isodd (b) == 1) { 3507 if (mp_isodd (b) == 1) {
3319 return fast_mp_invmod (a, b, c); 3508 return fast_mp_invmod (a, b, c);
3320 } 3509 }
3321 3510 #endif
3511
3512 #ifdef BN_MP_INVMOD_SLOW_C
3513 return mp_invmod_slow(a, b, c);
3514 #endif
3515
3516 return MP_VAL;
3517 }
3518 #endif
3519
3520 /* End: bn_mp_invmod.c */
3521
3522 /* Start: bn_mp_invmod_slow.c */
3523 #include <tommath.h>
3524 #ifdef BN_MP_INVMOD_SLOW_C
3525 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3526 *
3527 * LibTomMath is a library that provides multiple-precision
3528 * integer arithmetic as well as number theoretic functionality.
3529 *
3530 * The library was designed directly after the MPI library by
3531 * Michael Fromberger but has been written from scratch with
3532 * additional optimizations in place.
3533 *
3534 * The library is free for all purposes without any express
3535 * guarantee it works.
3536 *
3537 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3538 */
3539
3540 /* hac 14.61, pp608 */
3541 int mp_invmod_slow (mp_int * a, mp_int * b, mp_int * c)
3542 {
3543 mp_int x, y, u, v, A, B, C, D;
3544 int res;
3545
3546 /* b cannot be negative */
3547 if (b->sign == MP_NEG || mp_iszero(b) == 1) {
3548 return MP_VAL;
3549 }
3550
3322 /* init temps */ 3551 /* init temps */
3323 if ((res = mp_init_multi(&x, &y, &u, &v, 3552 if ((res = mp_init_multi(&x, &y, &u, &v,
3324 &A, &B, &C, &D, NULL)) != MP_OKAY) { 3553 &A, &B, &C, &D, NULL)) != MP_OKAY) {
3325 return res; 3554 return res;
3326 } 3555 }
3459 mp_exch (&C, c); 3688 mp_exch (&C, c);
3460 res = MP_OKAY; 3689 res = MP_OKAY;
3461 __ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL); 3690 __ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
3462 return res; 3691 return res;
3463 } 3692 }
3464 3693 #endif
3465 /* End: bn_mp_invmod.c */ 3694
3695 /* End: bn_mp_invmod_slow.c */
3466 3696
3467 /* Start: bn_mp_is_square.c */ 3697 /* Start: bn_mp_is_square.c */
3468 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3698 #include <tommath.h>
3469 * 3699 #ifdef BN_MP_IS_SQUARE_C
3470 * LibTomMath is a library that provides multiple-precision 3700 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3471 * integer arithmetic as well as number theoretic functionality. 3701 *
3472 * 3702 * LibTomMath is a library that provides multiple-precision
3473 * The library was designed directly after the MPI library by 3703 * integer arithmetic as well as number theoretic functionality.
3474 * Michael Fromberger but has been written from scratch with 3704 *
3475 * additional optimizations in place. 3705 * The library was designed directly after the MPI library by
3476 * 3706 * Michael Fromberger but has been written from scratch with
3477 * The library is free for all purposes without any express 3707 * additional optimizations in place.
3478 * guarantee it works. 3708 *
3479 * 3709 * The library is free for all purposes without any express
3480 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3710 * guarantee it works.
3481 */ 3711 *
3482 #include <tommath.h> 3712 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3713 */
3483 3714
3484 /* Check if remainders are possible squares - fast exclude non-squares */ 3715 /* Check if remainders are possible squares - fast exclude non-squares */
3485 static const char rem_128[128] = { 3716 static const char rem_128[128] = {
3486 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 3717 0, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
3487 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 3718 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,
3534 } 3765 }
3535 if (rem_105[c] == 1) { 3766 if (rem_105[c] == 1) {
3536 return MP_OKAY; 3767 return MP_OKAY;
3537 } 3768 }
3538 3769
3539 /* product of primes less than 2^31 */ 3770
3540 if ((res = mp_init_set_int(&t,11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) { 3771 if ((res = mp_init_set_int(&t,11L*13L*17L*19L*23L*29L*31L)) != MP_OKAY) {
3541 return res; 3772 return res;
3542 } 3773 }
3543 if ((res = mp_mod(arg,&t,&t)) != MP_OKAY) { 3774 if ((res = mp_mod(arg,&t,&t)) != MP_OKAY) {
3544 goto ERR; 3775 goto ERR;
3566 3797
3567 *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO; 3798 *ret = (mp_cmp_mag(&t,arg) == MP_EQ) ? MP_YES : MP_NO;
3568 ERR:mp_clear(&t); 3799 ERR:mp_clear(&t);
3569 return res; 3800 return res;
3570 } 3801 }
3802 #endif
3571 3803
3572 /* End: bn_mp_is_square.c */ 3804 /* End: bn_mp_is_square.c */
3573 3805
3574 /* Start: bn_mp_jacobi.c */ 3806 /* Start: bn_mp_jacobi.c */
3575 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3807 #include <tommath.h>
3576 * 3808 #ifdef BN_MP_JACOBI_C
3577 * LibTomMath is a library that provides multiple-precision 3809 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3578 * integer arithmetic as well as number theoretic functionality. 3810 *
3579 * 3811 * LibTomMath is a library that provides multiple-precision
3580 * The library was designed directly after the MPI library by 3812 * integer arithmetic as well as number theoretic functionality.
3581 * Michael Fromberger but has been written from scratch with 3813 *
3582 * additional optimizations in place. 3814 * The library was designed directly after the MPI library by
3583 * 3815 * Michael Fromberger but has been written from scratch with
3584 * The library is free for all purposes without any express 3816 * additional optimizations in place.
3585 * guarantee it works. 3817 *
3586 * 3818 * The library is free for all purposes without any express
3587 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3819 * guarantee it works.
3588 */ 3820 *
3589 #include <tommath.h> 3821 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3822 */
3590 3823
3591 /* computes the jacobi c = (a | n) (or Legendre if n is prime) 3824 /* computes the jacobi c = (a | n) (or Legendre if n is prime)
3592 * HAC pp. 73 Algorithm 2.149 3825 * HAC pp. 73 Algorithm 2.149
3593 */ 3826 */
3594 int mp_jacobi (mp_int * a, mp_int * p, int *c) 3827 int mp_jacobi (mp_int * a, mp_int * p, int *c)
3669 res = MP_OKAY; 3902 res = MP_OKAY;
3670 __P1:mp_clear (&p1); 3903 __P1:mp_clear (&p1);
3671 __A1:mp_clear (&a1); 3904 __A1:mp_clear (&a1);
3672 return res; 3905 return res;
3673 } 3906 }
3907 #endif
3674 3908
3675 /* End: bn_mp_jacobi.c */ 3909 /* End: bn_mp_jacobi.c */
3676 3910
3677 /* Start: bn_mp_karatsuba_mul.c */ 3911 /* Start: bn_mp_karatsuba_mul.c */
3678 /* LibTomMath, multiple-precision integer library -- Tom St Denis 3912 #include <tommath.h>
3679 * 3913 #ifdef BN_MP_KARATSUBA_MUL_C
3680 * LibTomMath is a library that provides multiple-precision 3914 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3681 * integer arithmetic as well as number theoretic functionality. 3915 *
3682 * 3916 * LibTomMath is a library that provides multiple-precision
3683 * The library was designed directly after the MPI library by 3917 * integer arithmetic as well as number theoretic functionality.
3684 * Michael Fromberger but has been written from scratch with 3918 *
3685 * additional optimizations in place. 3919 * The library was designed directly after the MPI library by
3686 * 3920 * Michael Fromberger but has been written from scratch with
3687 * The library is free for all purposes without any express 3921 * additional optimizations in place.
3688 * guarantee it works. 3922 *
3689 * 3923 * The library is free for all purposes without any express
3690 * Tom St Denis, [email protected], http://math.libtomcrypt.org 3924 * guarantee it works.
3691 */ 3925 *
3692 #include <tommath.h> 3926 * Tom St Denis, [email protected], http://math.libtomcrypt.org
3927 */
3693 3928
3694 /* c = |a| * |b| using Karatsuba Multiplication using 3929 /* c = |a| * |b| using Karatsuba Multiplication using
3695 * three half size multiplications 3930 * three half size multiplications
3696 * 3931 *
3697 * Let B represent the radix [e.g. 2**DIGIT_BIT] and 3932 * Let B represent the radix [e.g. 2**DIGIT_BIT] and
3751 goto T1; 3986 goto T1;
3752 if (mp_init_size (&x1y1, B * 2) != MP_OKAY) 3987 if (mp_init_size (&x1y1, B * 2) != MP_OKAY)
3753 goto X0Y0; 3988 goto X0Y0;
3754 3989
3755 /* now shift the digits */ 3990 /* now shift the digits */
3756 x0.sign = x1.sign = a->sign;
3757 y0.sign = y1.sign = b->sign;
3758
3759 x0.used = y0.used = B; 3991 x0.used = y0.used = B;
3760 x1.used = a->used - B; 3992 x1.used = a->used - B;
3761 y1.used = b->used - B; 3993 y1.used = b->used - B;
3762 3994
3763 { 3995 {
3837 X1:mp_clear (&x1); 4069 X1:mp_clear (&x1);
3838 X0:mp_clear (&x0); 4070 X0:mp_clear (&x0);
3839 ERR: 4071 ERR:
3840 return err; 4072 return err;
3841 } 4073 }
4074 #endif
3842 4075
3843 /* End: bn_mp_karatsuba_mul.c */ 4076 /* End: bn_mp_karatsuba_mul.c */
3844 4077
3845 /* Start: bn_mp_karatsuba_sqr.c */ 4078 /* Start: bn_mp_karatsuba_sqr.c */
3846 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4079 #include <tommath.h>
3847 * 4080 #ifdef BN_MP_KARATSUBA_SQR_C
3848 * LibTomMath is a library that provides multiple-precision 4081 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3849 * integer arithmetic as well as number theoretic functionality. 4082 *
3850 * 4083 * LibTomMath is a library that provides multiple-precision
3851 * The library was designed directly after the MPI library by 4084 * integer arithmetic as well as number theoretic functionality.
3852 * Michael Fromberger but has been written from scratch with 4085 *
3853 * additional optimizations in place. 4086 * The library was designed directly after the MPI library by
3854 * 4087 * Michael Fromberger but has been written from scratch with
3855 * The library is free for all purposes without any express 4088 * additional optimizations in place.
3856 * guarantee it works. 4089 *
3857 * 4090 * The library is free for all purposes without any express
3858 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4091 * guarantee it works.
3859 */ 4092 *
3860 #include <tommath.h> 4093 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4094 */
3861 4095
3862 /* Karatsuba squaring, computes b = a*a using three 4096 /* Karatsuba squaring, computes b = a*a using three
3863 * half size squarings 4097 * half size squarings
3864 * 4098 *
3865 * See comments of mp_karatsuba_mul for details. It 4099 * See comments of karatsuba_mul for details. It
3866 * is essentially the same algorithm but merely 4100 * is essentially the same algorithm but merely
3867 * tuned to perform recursive squarings. 4101 * tuned to perform recursive squarings.
3868 */ 4102 */
3869 int mp_karatsuba_sqr (mp_int * a, mp_int * b) 4103 int mp_karatsuba_sqr (mp_int * a, mp_int * b)
3870 { 4104 {
3956 X1:mp_clear (&x1); 4190 X1:mp_clear (&x1);
3957 X0:mp_clear (&x0); 4191 X0:mp_clear (&x0);
3958 ERR: 4192 ERR:
3959 return err; 4193 return err;
3960 } 4194 }
4195 #endif
3961 4196
3962 /* End: bn_mp_karatsuba_sqr.c */ 4197 /* End: bn_mp_karatsuba_sqr.c */
3963 4198
3964 /* Start: bn_mp_lcm.c */ 4199 /* Start: bn_mp_lcm.c */
3965 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4200 #include <tommath.h>
3966 * 4201 #ifdef BN_MP_LCM_C
3967 * LibTomMath is a library that provides multiple-precision 4202 /* LibTomMath, multiple-precision integer library -- Tom St Denis
3968 * integer arithmetic as well as number theoretic functionality. 4203 *
3969 * 4204 * LibTomMath is a library that provides multiple-precision
3970 * The library was designed directly after the MPI library by 4205 * integer arithmetic as well as number theoretic functionality.
3971 * Michael Fromberger but has been written from scratch with 4206 *
3972 * additional optimizations in place. 4207 * The library was designed directly after the MPI library by
3973 * 4208 * Michael Fromberger but has been written from scratch with
3974 * The library is free for all purposes without any express 4209 * additional optimizations in place.
3975 * guarantee it works. 4210 *
3976 * 4211 * The library is free for all purposes without any express
3977 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4212 * guarantee it works.
3978 */ 4213 *
3979 #include <tommath.h> 4214 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4215 */
3980 4216
3981 /* computes least common multiple as |a*b|/(a, b) */ 4217 /* computes least common multiple as |a*b|/(a, b) */
3982 int mp_lcm (mp_int * a, mp_int * b, mp_int * c) 4218 int mp_lcm (mp_int * a, mp_int * b, mp_int * c)
3983 { 4219 {
3984 int res; 4220 int res;
4014 4250
4015 __T: 4251 __T:
4016 mp_clear_multi (&t1, &t2, NULL); 4252 mp_clear_multi (&t1, &t2, NULL);
4017 return res; 4253 return res;
4018 } 4254 }
4255 #endif
4019 4256
4020 /* End: bn_mp_lcm.c */ 4257 /* End: bn_mp_lcm.c */
4021 4258
4022 /* Start: bn_mp_lshd.c */ 4259 /* Start: bn_mp_lshd.c */
4023 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4260 #include <tommath.h>
4024 * 4261 #ifdef BN_MP_LSHD_C
4025 * LibTomMath is a library that provides multiple-precision 4262 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4026 * integer arithmetic as well as number theoretic functionality. 4263 *
4027 * 4264 * LibTomMath is a library that provides multiple-precision
4028 * The library was designed directly after the MPI library by 4265 * integer arithmetic as well as number theoretic functionality.
4029 * Michael Fromberger but has been written from scratch with 4266 *
4030 * additional optimizations in place. 4267 * The library was designed directly after the MPI library by
4031 * 4268 * Michael Fromberger but has been written from scratch with
4032 * The library is free for all purposes without any express 4269 * additional optimizations in place.
4033 * guarantee it works. 4270 *
4034 * 4271 * The library is free for all purposes without any express
4035 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4272 * guarantee it works.
4036 */ 4273 *
4037 #include <tommath.h> 4274 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4275 */
4038 4276
4039 /* shift left a certain amount of digits */ 4277 /* shift left a certain amount of digits */
4040 int mp_lshd (mp_int * a, int b) 4278 int mp_lshd (mp_int * a, int b)
4041 { 4279 {
4042 int x, res; 4280 int x, res;
4079 *top++ = 0; 4317 *top++ = 0;
4080 } 4318 }
4081 } 4319 }
4082 return MP_OKAY; 4320 return MP_OKAY;
4083 } 4321 }
4322 #endif
4084 4323
4085 /* End: bn_mp_lshd.c */ 4324 /* End: bn_mp_lshd.c */
4086 4325
4087 /* Start: bn_mp_mod.c */ 4326 /* Start: bn_mp_mod.c */
4088 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4327 #include <tommath.h>
4089 * 4328 #ifdef BN_MP_MOD_C
4090 * LibTomMath is a library that provides multiple-precision 4329 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4091 * integer arithmetic as well as number theoretic functionality. 4330 *
4092 * 4331 * LibTomMath is a library that provides multiple-precision
4093 * The library was designed directly after the MPI library by 4332 * integer arithmetic as well as number theoretic functionality.
4094 * Michael Fromberger but has been written from scratch with 4333 *
4095 * additional optimizations in place. 4334 * The library was designed directly after the MPI library by
4096 * 4335 * Michael Fromberger but has been written from scratch with
4097 * The library is free for all purposes without any express 4336 * additional optimizations in place.
4098 * guarantee it works. 4337 *
4099 * 4338 * The library is free for all purposes without any express
4100 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4339 * guarantee it works.
4101 */ 4340 *
4102 #include <tommath.h> 4341 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4342 */
4103 4343
4104 /* c = a mod b, 0 <= c < b */ 4344 /* c = a mod b, 0 <= c < b */
4105 int 4345 int
4106 mp_mod (mp_int * a, mp_int * b, mp_int * c) 4346 mp_mod (mp_int * a, mp_int * b, mp_int * c)
4107 { 4347 {
4125 } 4365 }
4126 4366
4127 mp_clear (&t); 4367 mp_clear (&t);
4128 return res; 4368 return res;
4129 } 4369 }
4370 #endif
4130 4371
4131 /* End: bn_mp_mod.c */ 4372 /* End: bn_mp_mod.c */
4132 4373
4133 /* Start: bn_mp_mod_2d.c */ 4374 /* Start: bn_mp_mod_2d.c */
4134 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4375 #include <tommath.h>
4135 * 4376 #ifdef BN_MP_MOD_2D_C
4136 * LibTomMath is a library that provides multiple-precision 4377 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4137 * integer arithmetic as well as number theoretic functionality. 4378 *
4138 * 4379 * LibTomMath is a library that provides multiple-precision
4139 * The library was designed directly after the MPI library by 4380 * integer arithmetic as well as number theoretic functionality.
4140 * Michael Fromberger but has been written from scratch with 4381 *
4141 * additional optimizations in place. 4382 * The library was designed directly after the MPI library by
4142 * 4383 * Michael Fromberger but has been written from scratch with
4143 * The library is free for all purposes without any express 4384 * additional optimizations in place.
4144 * guarantee it works. 4385 *
4145 * 4386 * The library is free for all purposes without any express
4146 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4387 * guarantee it works.
4147 */ 4388 *
4148 #include <tommath.h> 4389 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4390 */
4149 4391
4150 /* calc a value mod 2**b */ 4392 /* calc a value mod 2**b */
4151 int 4393 int
4152 mp_mod_2d (mp_int * a, int b, mp_int * c) 4394 mp_mod_2d (mp_int * a, int b, mp_int * c)
4153 { 4395 {
4178 c->dp[b / DIGIT_BIT] &= 4420 c->dp[b / DIGIT_BIT] &=
4179 (mp_digit) ((((mp_digit) 1) << (((mp_digit) b) % DIGIT_BIT)) - ((mp_digit) 1)); 4421 (mp_digit) ((((mp_digit) 1) << (((mp_digit) b) % DIGIT_BIT)) - ((mp_digit) 1));
4180 mp_clamp (c); 4422 mp_clamp (c);
4181 return MP_OKAY; 4423 return MP_OKAY;
4182 } 4424 }
4425 #endif
4183 4426
4184 /* End: bn_mp_mod_2d.c */ 4427 /* End: bn_mp_mod_2d.c */
4185 4428
4186 /* Start: bn_mp_mod_d.c */ 4429 /* Start: bn_mp_mod_d.c */
4187 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4430 #include <tommath.h>
4188 * 4431 #ifdef BN_MP_MOD_D_C
4189 * LibTomMath is a library that provides multiple-precision 4432 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4190 * integer arithmetic as well as number theoretic functionality. 4433 *
4191 * 4434 * LibTomMath is a library that provides multiple-precision
4192 * The library was designed directly after the MPI library by 4435 * integer arithmetic as well as number theoretic functionality.
4193 * Michael Fromberger but has been written from scratch with 4436 *
4194 * additional optimizations in place. 4437 * The library was designed directly after the MPI library by
4195 * 4438 * Michael Fromberger but has been written from scratch with
4196 * The library is free for all purposes without any express 4439 * additional optimizations in place.
4197 * guarantee it works. 4440 *
4198 * 4441 * The library is free for all purposes without any express
4199 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4442 * guarantee it works.
4200 */ 4443 *
4201 #include <tommath.h> 4444 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4445 */
4202 4446
4203 int 4447 int
4204 mp_mod_d (mp_int * a, mp_digit b, mp_digit * c) 4448 mp_mod_d (mp_int * a, mp_digit b, mp_digit * c)
4205 { 4449 {
4206 return mp_div_d(a, b, NULL, c); 4450 return mp_div_d(a, b, NULL, c);
4207 } 4451 }
4452 #endif
4208 4453
4209 /* End: bn_mp_mod_d.c */ 4454 /* End: bn_mp_mod_d.c */
4210 4455
4211 /* Start: bn_mp_montgomery_calc_normalization.c */ 4456 /* Start: bn_mp_montgomery_calc_normalization.c */
4212 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4457 #include <tommath.h>
4213 * 4458 #ifdef BN_MP_MONTGOMERY_CALC_NORMALIZATION_C
4214 * LibTomMath is a library that provides multiple-precision 4459 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4215 * integer arithmetic as well as number theoretic functionality. 4460 *
4216 * 4461 * LibTomMath is a library that provides multiple-precision
4217 * The library was designed directly after the MPI library by 4462 * integer arithmetic as well as number theoretic functionality.
4218 * Michael Fromberger but has been written from scratch with 4463 *
4219 * additional optimizations in place. 4464 * The library was designed directly after the MPI library by
4220 * 4465 * Michael Fromberger but has been written from scratch with
4221 * The library is free for all purposes without any express 4466 * additional optimizations in place.
4222 * guarantee it works. 4467 *
4223 * 4468 * The library is free for all purposes without any express
4224 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4469 * guarantee it works.
4225 */ 4470 *
4226 #include <tommath.h> 4471 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4227 4472 */
4228 /* calculates a = B^n mod b for Montgomery reduction 4473
4229 * Where B is the base [e.g. 2^DIGIT_BIT]. 4474 /*
4230 * B^n mod b is computed by first computing
4231 * A = B^(n-1) which doesn't require a reduction but a simple OR.
4232 * then C = A * B = B^n is computed by performing upto DIGIT_BIT
4233 * shifts with subtractions when the result is greater than b. 4475 * shifts with subtractions when the result is greater than b.
4234 * 4476 *
4235 * The method is slightly modified to shift B unconditionally upto just under 4477 * The method is slightly modified to shift B unconditionally upto just under
4236 * the leading bit of b. This saves alot of multiple precision shifting. 4478 * the leading bit of b. This saves alot of multiple precision shifting.
4237 */ 4479 */
4238 int 4480 int mp_montgomery_calc_normalization (mp_int * a, mp_int * b)
4239 mp_montgomery_calc_normalization (mp_int * a, mp_int * b)
4240 { 4481 {
4241 int x, bits, res; 4482 int x, bits, res;
4242 4483
4243 /* how many bits of last digit does b use */ 4484 /* how many bits of last digit does b use */
4244 bits = mp_count_bits (b) % DIGIT_BIT; 4485 bits = mp_count_bits (b) % DIGIT_BIT;
4245 4486
4246 /* compute A = B^(n-1) * 2^(bits-1) */ 4487
4247 if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) { 4488 if (b->used > 1) {
4248 return res; 4489 if ((res = mp_2expt (a, (b->used - 1) * DIGIT_BIT + bits - 1)) != MP_OKAY) {
4249 } 4490 return res;
4491 }
4492 } else {
4493 mp_set(a, 1);
4494 bits = 1;
4495 }
4496
4250 4497
4251 /* now compute C = A * B mod b */ 4498 /* now compute C = A * B mod b */
4252 for (x = bits - 1; x < (int)DIGIT_BIT; x++) { 4499 for (x = bits - 1; x < (int)DIGIT_BIT; x++) {
4253 if ((res = mp_mul_2 (a, a)) != MP_OKAY) { 4500 if ((res = mp_mul_2 (a, a)) != MP_OKAY) {
4254 return res; 4501 return res;
4260 } 4507 }
4261 } 4508 }
4262 4509
4263 return MP_OKAY; 4510 return MP_OKAY;
4264 } 4511 }
4512 #endif
4265 4513
4266 /* End: bn_mp_montgomery_calc_normalization.c */ 4514 /* End: bn_mp_montgomery_calc_normalization.c */
4267 4515
4268 /* Start: bn_mp_montgomery_reduce.c */ 4516 /* Start: bn_mp_montgomery_reduce.c */
4269 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4517 #include <tommath.h>
4270 * 4518 #ifdef BN_MP_MONTGOMERY_REDUCE_C
4271 * LibTomMath is a library that provides multiple-precision 4519 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4272 * integer arithmetic as well as number theoretic functionality. 4520 *
4273 * 4521 * LibTomMath is a library that provides multiple-precision
4274 * The library was designed directly after the MPI library by 4522 * integer arithmetic as well as number theoretic functionality.
4275 * Michael Fromberger but has been written from scratch with 4523 *
4276 * additional optimizations in place. 4524 * The library was designed directly after the MPI library by
4277 * 4525 * Michael Fromberger but has been written from scratch with
4278 * The library is free for all purposes without any express 4526 * additional optimizations in place.
4279 * guarantee it works. 4527 *
4280 * 4528 * The library is free for all purposes without any express
4281 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4529 * guarantee it works.
4282 */ 4530 *
4283 #include <tommath.h> 4531 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4532 */
4284 4533
4285 /* computes xR**-1 == x (mod N) via Montgomery Reduction */ 4534 /* computes xR**-1 == x (mod N) via Montgomery Reduction */
4286 int 4535 int
4287 mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho) 4536 mp_montgomery_reduce (mp_int * x, mp_int * n, mp_digit rho)
4288 { 4537 {
4289 int ix, res, digs; 4538 int ix, res, digs;
4290 mp_digit mu; 4539 mp_digit mu;
4291 4540
4292 /* can the fast reduction [comba] method be used? 4541 /* can the fast reduction [comba] method be used?
4293 * 4542 *
4294 * Note that unlike in mp_mul you're safely allowed *less* 4543 * Note that unlike in mul you're safely allowed *less*
4295 * than the available columns [255 per default] since carries 4544 * than the available columns [255 per default] since carries
4296 * are fixed up in the inner loop. 4545 * are fixed up in the inner loop.
4297 */ 4546 */
4298 digs = n->used * 2 + 1; 4547 digs = n->used * 2 + 1;
4299 if ((digs < MP_WARRAY) && 4548 if ((digs < MP_WARRAY) &&
4312 4561
4313 for (ix = 0; ix < n->used; ix++) { 4562 for (ix = 0; ix < n->used; ix++) {
4314 /* mu = ai * rho mod b 4563 /* mu = ai * rho mod b
4315 * 4564 *
4316 * The value of rho must be precalculated via 4565 * The value of rho must be precalculated via
4317 * bn_mp_montgomery_setup() such that 4566 * montgomery_setup() such that
4318 * it equals -1/n0 mod b this allows the 4567 * it equals -1/n0 mod b this allows the
4319 * following inner loop to reduce the 4568 * following inner loop to reduce the
4320 * input one digit at a time 4569 * input one digit at a time
4321 */ 4570 */
4322 mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK); 4571 mu = (mp_digit) (((mp_word)x->dp[ix]) * ((mp_word)rho) & MP_MASK);
4376 return s_mp_sub (x, n, x); 4625 return s_mp_sub (x, n, x);
4377 } 4626 }
4378 4627
4379 return MP_OKAY; 4628 return MP_OKAY;
4380 } 4629 }
4630 #endif
4381 4631
4382 /* End: bn_mp_montgomery_reduce.c */ 4632 /* End: bn_mp_montgomery_reduce.c */
4383 4633
4384 /* Start: bn_mp_montgomery_setup.c */ 4634 /* Start: bn_mp_montgomery_setup.c */
4385 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4635 #include <tommath.h>
4386 * 4636 #ifdef BN_MP_MONTGOMERY_SETUP_C
4387 * LibTomMath is a library that provides multiple-precision 4637 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4388 * integer arithmetic as well as number theoretic functionality. 4638 *
4389 * 4639 * LibTomMath is a library that provides multiple-precision
4390 * The library was designed directly after the MPI library by 4640 * integer arithmetic as well as number theoretic functionality.
4391 * Michael Fromberger but has been written from scratch with 4641 *
4392 * additional optimizations in place. 4642 * The library was designed directly after the MPI library by
4393 * 4643 * Michael Fromberger but has been written from scratch with
4394 * The library is free for all purposes without any express 4644 * additional optimizations in place.
4395 * guarantee it works. 4645 *
4396 * 4646 * The library is free for all purposes without any express
4397 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4647 * guarantee it works.
4398 */ 4648 *
4399 #include <tommath.h> 4649 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4650 */
4400 4651
4401 /* setups the montgomery reduction stuff */ 4652 /* setups the montgomery reduction stuff */
4402 int 4653 int
4403 mp_montgomery_setup (mp_int * n, mp_digit * rho) 4654 mp_montgomery_setup (mp_int * n, mp_digit * rho)
4404 { 4655 {
4429 #ifdef MP_64BIT 4680 #ifdef MP_64BIT
4430 x *= 2 - b * x; /* here x*a==1 mod 2**64 */ 4681 x *= 2 - b * x; /* here x*a==1 mod 2**64 */
4431 #endif 4682 #endif
4432 4683
4433 /* rho = -1/m mod b */ 4684 /* rho = -1/m mod b */
4434 *rho = (((mp_digit) 1 << ((mp_digit) DIGIT_BIT)) - x) & MP_MASK; 4685 *rho = (((mp_word)1 << ((mp_word) DIGIT_BIT)) - x) & MP_MASK;
4435 4686
4436 return MP_OKAY; 4687 return MP_OKAY;
4437 } 4688 }
4689 #endif
4438 4690
4439 /* End: bn_mp_montgomery_setup.c */ 4691 /* End: bn_mp_montgomery_setup.c */
4440 4692
4441 /* Start: bn_mp_mul.c */ 4693 /* Start: bn_mp_mul.c */
4442 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4694 #include <tommath.h>
4443 * 4695 #ifdef BN_MP_MUL_C
4444 * LibTomMath is a library that provides multiple-precision 4696 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4445 * integer arithmetic as well as number theoretic functionality. 4697 *
4446 * 4698 * LibTomMath is a library that provides multiple-precision
4447 * The library was designed directly after the MPI library by 4699 * integer arithmetic as well as number theoretic functionality.
4448 * Michael Fromberger but has been written from scratch with 4700 *
4449 * additional optimizations in place. 4701 * The library was designed directly after the MPI library by
4450 * 4702 * Michael Fromberger but has been written from scratch with
4451 * The library is free for all purposes without any express 4703 * additional optimizations in place.
4452 * guarantee it works. 4704 *
4453 * 4705 * The library is free for all purposes without any express
4454 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4706 * guarantee it works.
4455 */ 4707 *
4456 #include <tommath.h> 4708 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4709 */
4457 4710
4458 /* high level multiplication (handles sign) */ 4711 /* high level multiplication (handles sign) */
4459 int mp_mul (mp_int * a, mp_int * b, mp_int * c) 4712 int mp_mul (mp_int * a, mp_int * b, mp_int * c)
4460 { 4713 {
4461 int res, neg; 4714 int res, neg;
4462 neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG; 4715 neg = (a->sign == b->sign) ? MP_ZPOS : MP_NEG;
4463 4716
4464 /* use Toom-Cook? */ 4717 /* use Toom-Cook? */
4718 #ifdef BN_MP_TOOM_MUL_C
4465 if (MIN (a->used, b->used) >= TOOM_MUL_CUTOFF) { 4719 if (MIN (a->used, b->used) >= TOOM_MUL_CUTOFF) {
4466 res = mp_toom_mul(a, b, c); 4720 res = mp_toom_mul(a, b, c);
4721 } else
4722 #endif
4723 #ifdef BN_MP_KARATSUBA_MUL_C
4467 /* use Karatsuba? */ 4724 /* use Karatsuba? */
4468 } else if (MIN (a->used, b->used) >= KARATSUBA_MUL_CUTOFF) { 4725 if (MIN (a->used, b->used) >= KARATSUBA_MUL_CUTOFF) {
4469 res = mp_karatsuba_mul (a, b, c); 4726 res = mp_karatsuba_mul (a, b, c);
4470 } else { 4727 } else
4728 #endif
4729 {
4471 /* can we use the fast multiplier? 4730 /* can we use the fast multiplier?
4472 * 4731 *
4473 * The fast multiplier can be used if the output will 4732 * The fast multiplier can be used if the output will
4474 * have less than MP_WARRAY digits and the number of 4733 * have less than MP_WARRAY digits and the number of
4475 * digits won't affect carry propagation 4734 * digits won't affect carry propagation
4476 */ 4735 */
4477 int digs = a->used + b->used + 1; 4736 int digs = a->used + b->used + 1;
4478 4737
4738 #ifdef BN_FAST_S_MP_MUL_DIGS_C
4479 if ((digs < MP_WARRAY) && 4739 if ((digs < MP_WARRAY) &&
4480 MIN(a->used, b->used) <= 4740 MIN(a->used, b->used) <=
4481 (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 4741 (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
4482 res = fast_s_mp_mul_digs (a, b, c, digs); 4742 res = fast_s_mp_mul_digs (a, b, c, digs);
4483 } else { 4743 } else
4484 res = s_mp_mul (a, b, c); 4744 #endif
4485 } 4745 #ifdef BN_S_MP_MUL_DIGS_C
4486 } 4746 res = s_mp_mul (a, b, c); /* uses s_mp_mul_digs */
4487 c->sign = neg; 4747 #else
4748 res = MP_VAL;
4749 #endif
4750
4751 }
4752 c->sign = (c->used > 0) ? neg : MP_ZPOS;
4488 return res; 4753 return res;
4489 } 4754 }
4755 #endif
4490 4756
4491 /* End: bn_mp_mul.c */ 4757 /* End: bn_mp_mul.c */
4492 4758
4493 /* Start: bn_mp_mul_2.c */ 4759 /* Start: bn_mp_mul_2.c */
4494 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4760 #include <tommath.h>
4495 * 4761 #ifdef BN_MP_MUL_2_C
4496 * LibTomMath is a library that provides multiple-precision 4762 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4497 * integer arithmetic as well as number theoretic functionality. 4763 *
4498 * 4764 * LibTomMath is a library that provides multiple-precision
4499 * The library was designed directly after the MPI library by 4765 * integer arithmetic as well as number theoretic functionality.
4500 * Michael Fromberger but has been written from scratch with 4766 *
4501 * additional optimizations in place. 4767 * The library was designed directly after the MPI library by
4502 * 4768 * Michael Fromberger but has been written from scratch with
4503 * The library is free for all purposes without any express 4769 * additional optimizations in place.
4504 * guarantee it works. 4770 *
4505 * 4771 * The library is free for all purposes without any express
4506 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4772 * guarantee it works.
4507 */ 4773 *
4508 #include <tommath.h> 4774 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4775 */
4509 4776
4510 /* b = a*2 */ 4777 /* b = a*2 */
4511 int mp_mul_2(mp_int * a, mp_int * b) 4778 int mp_mul_2(mp_int * a, mp_int * b)
4512 { 4779 {
4513 int x, res, oldused; 4780 int x, res, oldused;
4565 } 4832 }
4566 } 4833 }
4567 b->sign = a->sign; 4834 b->sign = a->sign;
4568 return MP_OKAY; 4835 return MP_OKAY;
4569 } 4836 }
4837 #endif
4570 4838
4571 /* End: bn_mp_mul_2.c */ 4839 /* End: bn_mp_mul_2.c */
4572 4840
4573 /* Start: bn_mp_mul_2d.c */ 4841 /* Start: bn_mp_mul_2d.c */
4574 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4842 #include <tommath.h>
4575 * 4843 #ifdef BN_MP_MUL_2D_C
4576 * LibTomMath is a library that provides multiple-precision 4844 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4577 * integer arithmetic as well as number theoretic functionality. 4845 *
4578 * 4846 * LibTomMath is a library that provides multiple-precision
4579 * The library was designed directly after the MPI library by 4847 * integer arithmetic as well as number theoretic functionality.
4580 * Michael Fromberger but has been written from scratch with 4848 *
4581 * additional optimizations in place. 4849 * The library was designed directly after the MPI library by
4582 * 4850 * Michael Fromberger but has been written from scratch with
4583 * The library is free for all purposes without any express 4851 * additional optimizations in place.
4584 * guarantee it works. 4852 *
4585 * 4853 * The library is free for all purposes without any express
4586 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4854 * guarantee it works.
4587 */ 4855 *
4588 #include <tommath.h> 4856 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4857 */
4589 4858
4590 /* shift left by a certain bit count */ 4859 /* shift left by a certain bit count */
4591 int mp_mul_2d (mp_int * a, int b, mp_int * c) 4860 int mp_mul_2d (mp_int * a, int b, mp_int * c)
4592 { 4861 {
4593 mp_digit d; 4862 mp_digit d;
4648 } 4917 }
4649 } 4918 }
4650 mp_clamp (c); 4919 mp_clamp (c);
4651 return MP_OKAY; 4920 return MP_OKAY;
4652 } 4921 }
4922 #endif
4653 4923
4654 /* End: bn_mp_mul_2d.c */ 4924 /* End: bn_mp_mul_2d.c */
4655 4925
4656 /* Start: bn_mp_mul_d.c */ 4926 /* Start: bn_mp_mul_d.c */
4657 /* LibTomMath, multiple-precision integer library -- Tom St Denis 4927 #include <tommath.h>
4658 * 4928 #ifdef BN_MP_MUL_D_C
4659 * LibTomMath is a library that provides multiple-precision 4929 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4660 * integer arithmetic as well as number theoretic functionality. 4930 *
4661 * 4931 * LibTomMath is a library that provides multiple-precision
4662 * The library was designed directly after the MPI library by 4932 * integer arithmetic as well as number theoretic functionality.
4663 * Michael Fromberger but has been written from scratch with 4933 *
4664 * additional optimizations in place. 4934 * The library was designed directly after the MPI library by
4665 * 4935 * Michael Fromberger but has been written from scratch with
4666 * The library is free for all purposes without any express 4936 * additional optimizations in place.
4667 * guarantee it works. 4937 *
4668 * 4938 * The library is free for all purposes without any express
4669 * Tom St Denis, [email protected], http://math.libtomcrypt.org 4939 * guarantee it works.
4670 */ 4940 *
4671 #include <tommath.h> 4941 * Tom St Denis, [email protected], http://math.libtomcrypt.org
4942 */
4672 4943
4673 /* multiply by a digit */ 4944 /* multiply by a digit */
4674 int 4945 int
4675 mp_mul_d (mp_int * a, mp_digit b, mp_int * c) 4946 mp_mul_d (mp_int * a, mp_digit b, mp_int * c)
4676 { 4947 {
4724 c->used = a->used + 1; 4995 c->used = a->used + 1;
4725 mp_clamp(c); 4996 mp_clamp(c);
4726 4997
4727 return MP_OKAY; 4998 return MP_OKAY;
4728 } 4999 }
5000 #endif
4729 5001
4730 /* End: bn_mp_mul_d.c */ 5002 /* End: bn_mp_mul_d.c */
4731 5003
4732 /* Start: bn_mp_mulmod.c */ 5004 /* Start: bn_mp_mulmod.c */
4733 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5005 #include <tommath.h>
4734 * 5006 #ifdef BN_MP_MULMOD_C
4735 * LibTomMath is a library that provides multiple-precision 5007 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4736 * integer arithmetic as well as number theoretic functionality. 5008 *
4737 * 5009 * LibTomMath is a library that provides multiple-precision
4738 * The library was designed directly after the MPI library by 5010 * integer arithmetic as well as number theoretic functionality.
4739 * Michael Fromberger but has been written from scratch with 5011 *
4740 * additional optimizations in place. 5012 * The library was designed directly after the MPI library by
4741 * 5013 * Michael Fromberger but has been written from scratch with
4742 * The library is free for all purposes without any express 5014 * additional optimizations in place.
4743 * guarantee it works. 5015 *
4744 * 5016 * The library is free for all purposes without any express
4745 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5017 * guarantee it works.
4746 */ 5018 *
4747 #include <tommath.h> 5019 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5020 */
4748 5021
4749 /* d = a * b (mod c) */ 5022 /* d = a * b (mod c) */
4750 int 5023 int
4751 mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d) 5024 mp_mulmod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
4752 { 5025 {
4763 } 5036 }
4764 res = mp_mod (&t, c, d); 5037 res = mp_mod (&t, c, d);
4765 mp_clear (&t); 5038 mp_clear (&t);
4766 return res; 5039 return res;
4767 } 5040 }
5041 #endif
4768 5042
4769 /* End: bn_mp_mulmod.c */ 5043 /* End: bn_mp_mulmod.c */
4770 5044
4771 /* Start: bn_mp_n_root.c */ 5045 /* Start: bn_mp_n_root.c */
4772 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5046 #include <tommath.h>
4773 * 5047 #ifdef BN_MP_N_ROOT_C
4774 * LibTomMath is a library that provides multiple-precision 5048 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4775 * integer arithmetic as well as number theoretic functionality. 5049 *
4776 * 5050 * LibTomMath is a library that provides multiple-precision
4777 * The library was designed directly after the MPI library by 5051 * integer arithmetic as well as number theoretic functionality.
4778 * Michael Fromberger but has been written from scratch with 5052 *
4779 * additional optimizations in place. 5053 * The library was designed directly after the MPI library by
4780 * 5054 * Michael Fromberger but has been written from scratch with
4781 * The library is free for all purposes without any express 5055 * additional optimizations in place.
4782 * guarantee it works. 5056 *
4783 * 5057 * The library is free for all purposes without any express
4784 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5058 * guarantee it works.
4785 */ 5059 *
4786 #include <tommath.h> 5060 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5061 */
4787 5062
4788 /* find the n'th root of an integer 5063 /* find the n'th root of an integer
4789 * 5064 *
4790 * Result found such that (c)**b <= a and (c+1)**b > a 5065 * Result found such that (c)**b <= a and (c+1)**b > a
4791 * 5066 *
4893 __T3:mp_clear (&t3); 5168 __T3:mp_clear (&t3);
4894 __T2:mp_clear (&t2); 5169 __T2:mp_clear (&t2);
4895 __T1:mp_clear (&t1); 5170 __T1:mp_clear (&t1);
4896 return res; 5171 return res;
4897 } 5172 }
5173 #endif
4898 5174
4899 /* End: bn_mp_n_root.c */ 5175 /* End: bn_mp_n_root.c */
4900 5176
4901 /* Start: bn_mp_neg.c */ 5177 /* Start: bn_mp_neg.c */
4902 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5178 #include <tommath.h>
4903 * 5179 #ifdef BN_MP_NEG_C
4904 * LibTomMath is a library that provides multiple-precision 5180 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4905 * integer arithmetic as well as number theoretic functionality. 5181 *
4906 * 5182 * LibTomMath is a library that provides multiple-precision
4907 * The library was designed directly after the MPI library by 5183 * integer arithmetic as well as number theoretic functionality.
4908 * Michael Fromberger but has been written from scratch with 5184 *
4909 * additional optimizations in place. 5185 * The library was designed directly after the MPI library by
4910 * 5186 * Michael Fromberger but has been written from scratch with
4911 * The library is free for all purposes without any express 5187 * additional optimizations in place.
4912 * guarantee it works. 5188 *
4913 * 5189 * The library is free for all purposes without any express
4914 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5190 * guarantee it works.
4915 */ 5191 *
4916 #include <tommath.h> 5192 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5193 */
4917 5194
4918 /* b = -a */ 5195 /* b = -a */
4919 int mp_neg (mp_int * a, mp_int * b) 5196 int mp_neg (mp_int * a, mp_int * b)
4920 { 5197 {
4921 int res; 5198 int res;
4925 if (mp_iszero(b) != MP_YES) { 5202 if (mp_iszero(b) != MP_YES) {
4926 b->sign = (a->sign == MP_ZPOS) ? MP_NEG : MP_ZPOS; 5203 b->sign = (a->sign == MP_ZPOS) ? MP_NEG : MP_ZPOS;
4927 } 5204 }
4928 return MP_OKAY; 5205 return MP_OKAY;
4929 } 5206 }
5207 #endif
4930 5208
4931 /* End: bn_mp_neg.c */ 5209 /* End: bn_mp_neg.c */
4932 5210
4933 /* Start: bn_mp_or.c */ 5211 /* Start: bn_mp_or.c */
4934 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5212 #include <tommath.h>
4935 * 5213 #ifdef BN_MP_OR_C
4936 * LibTomMath is a library that provides multiple-precision 5214 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4937 * integer arithmetic as well as number theoretic functionality. 5215 *
4938 * 5216 * LibTomMath is a library that provides multiple-precision
4939 * The library was designed directly after the MPI library by 5217 * integer arithmetic as well as number theoretic functionality.
4940 * Michael Fromberger but has been written from scratch with 5218 *
4941 * additional optimizations in place. 5219 * The library was designed directly after the MPI library by
4942 * 5220 * Michael Fromberger but has been written from scratch with
4943 * The library is free for all purposes without any express 5221 * additional optimizations in place.
4944 * guarantee it works. 5222 *
4945 * 5223 * The library is free for all purposes without any express
4946 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5224 * guarantee it works.
4947 */ 5225 *
4948 #include <tommath.h> 5226 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5227 */
4949 5228
4950 /* OR two ints together */ 5229 /* OR two ints together */
4951 int mp_or (mp_int * a, mp_int * b, mp_int * c) 5230 int mp_or (mp_int * a, mp_int * b, mp_int * c)
4952 { 5231 {
4953 int res, ix, px; 5232 int res, ix, px;
4973 mp_clamp (&t); 5252 mp_clamp (&t);
4974 mp_exch (c, &t); 5253 mp_exch (c, &t);
4975 mp_clear (&t); 5254 mp_clear (&t);
4976 return MP_OKAY; 5255 return MP_OKAY;
4977 } 5256 }
5257 #endif
4978 5258
4979 /* End: bn_mp_or.c */ 5259 /* End: bn_mp_or.c */
4980 5260
4981 /* Start: bn_mp_prime_fermat.c */ 5261 /* Start: bn_mp_prime_fermat.c */
4982 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5262 #include <tommath.h>
4983 * 5263 #ifdef BN_MP_PRIME_FERMAT_C
4984 * LibTomMath is a library that provides multiple-precision 5264 /* LibTomMath, multiple-precision integer library -- Tom St Denis
4985 * integer arithmetic as well as number theoretic functionality. 5265 *
4986 * 5266 * LibTomMath is a library that provides multiple-precision
4987 * The library was designed directly after the MPI library by 5267 * integer arithmetic as well as number theoretic functionality.
4988 * Michael Fromberger but has been written from scratch with 5268 *
4989 * additional optimizations in place. 5269 * The library was designed directly after the MPI library by
4990 * 5270 * Michael Fromberger but has been written from scratch with
4991 * The library is free for all purposes without any express 5271 * additional optimizations in place.
4992 * guarantee it works. 5272 *
4993 * 5273 * The library is free for all purposes without any express
4994 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5274 * guarantee it works.
4995 */ 5275 *
4996 #include <tommath.h> 5276 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5277 */
4997 5278
4998 /* performs one Fermat test. 5279 /* performs one Fermat test.
4999 * 5280 *
5000 * If "a" were prime then b**a == b (mod a) since the order of 5281 * If "a" were prime then b**a == b (mod a) since the order of
5001 * the multiplicative sub-group would be phi(a) = a-1. That means 5282 * the multiplicative sub-group would be phi(a) = a-1. That means
5033 5314
5034 err = MP_OKAY; 5315 err = MP_OKAY;
5035 __T:mp_clear (&t); 5316 __T:mp_clear (&t);
5036 return err; 5317 return err;
5037 } 5318 }
5319 #endif
5038 5320
5039 /* End: bn_mp_prime_fermat.c */ 5321 /* End: bn_mp_prime_fermat.c */
5040 5322
5041 /* Start: bn_mp_prime_is_divisible.c */ 5323 /* Start: bn_mp_prime_is_divisible.c */
5042 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5324 #include <tommath.h>
5043 * 5325 #ifdef BN_MP_PRIME_IS_DIVISIBLE_C
5044 * LibTomMath is a library that provides multiple-precision 5326 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5045 * integer arithmetic as well as number theoretic functionality. 5327 *
5046 * 5328 * LibTomMath is a library that provides multiple-precision
5047 * The library was designed directly after the MPI library by 5329 * integer arithmetic as well as number theoretic functionality.
5048 * Michael Fromberger but has been written from scratch with 5330 *
5049 * additional optimizations in place. 5331 * The library was designed directly after the MPI library by
5050 * 5332 * Michael Fromberger but has been written from scratch with
5051 * The library is free for all purposes without any express 5333 * additional optimizations in place.
5052 * guarantee it works. 5334 *
5053 * 5335 * The library is free for all purposes without any express
5054 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5336 * guarantee it works.
5055 */ 5337 *
5056 #include <tommath.h> 5338 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5339 */
5057 5340
5058 /* determines if an integers is divisible by one 5341 /* determines if an integers is divisible by one
5059 * of the first PRIME_SIZE primes or not 5342 * of the first PRIME_SIZE primes or not
5060 * 5343 *
5061 * sets result to 0 if not, 1 if yes 5344 * sets result to 0 if not, 1 if yes
5081 } 5364 }
5082 } 5365 }
5083 5366
5084 return MP_OKAY; 5367 return MP_OKAY;
5085 } 5368 }
5369 #endif
5086 5370
5087 /* End: bn_mp_prime_is_divisible.c */ 5371 /* End: bn_mp_prime_is_divisible.c */
5088 5372
5089 /* Start: bn_mp_prime_is_prime.c */ 5373 /* Start: bn_mp_prime_is_prime.c */
5090 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5374 #include <tommath.h>
5091 * 5375 #ifdef BN_MP_PRIME_IS_PRIME_C
5092 * LibTomMath is a library that provides multiple-precision 5376 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5093 * integer arithmetic as well as number theoretic functionality. 5377 *
5094 * 5378 * LibTomMath is a library that provides multiple-precision
5095 * The library was designed directly after the MPI library by 5379 * integer arithmetic as well as number theoretic functionality.
5096 * Michael Fromberger but has been written from scratch with 5380 *
5097 * additional optimizations in place. 5381 * The library was designed directly after the MPI library by
5098 * 5382 * Michael Fromberger but has been written from scratch with
5099 * The library is free for all purposes without any express 5383 * additional optimizations in place.
5100 * guarantee it works. 5384 *
5101 * 5385 * The library is free for all purposes without any express
5102 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5386 * guarantee it works.
5103 */ 5387 *
5104 #include <tommath.h> 5388 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5389 */
5105 5390
5106 /* performs a variable number of rounds of Miller-Rabin 5391 /* performs a variable number of rounds of Miller-Rabin
5107 * 5392 *
5108 * Probability of error after t rounds is no more than 5393 * Probability of error after t rounds is no more than
5109 * (1/4)^t when 1 <= t <= PRIME_SIZE 5394
5110 * 5395 *
5111 * Sets result to 1 if probably prime, 0 otherwise 5396 * Sets result to 1 if probably prime, 0 otherwise
5112 */ 5397 */
5113 int mp_prime_is_prime (mp_int * a, int t, int *result) 5398 int mp_prime_is_prime (mp_int * a, int t, int *result)
5114 { 5399 {
5162 /* passed the test */ 5447 /* passed the test */
5163 *result = MP_YES; 5448 *result = MP_YES;
5164 __B:mp_clear (&b); 5449 __B:mp_clear (&b);
5165 return err; 5450 return err;
5166 } 5451 }
5452 #endif
5167 5453
5168 /* End: bn_mp_prime_is_prime.c */ 5454 /* End: bn_mp_prime_is_prime.c */
5169 5455
5170 /* Start: bn_mp_prime_miller_rabin.c */ 5456 /* Start: bn_mp_prime_miller_rabin.c */
5171 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5457 #include <tommath.h>
5172 * 5458 #ifdef BN_MP_PRIME_MILLER_RABIN_C
5173 * LibTomMath is a library that provides multiple-precision 5459 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5174 * integer arithmetic as well as number theoretic functionality. 5460 *
5175 * 5461 * LibTomMath is a library that provides multiple-precision
5176 * The library was designed directly after the MPI library by 5462 * integer arithmetic as well as number theoretic functionality.
5177 * Michael Fromberger but has been written from scratch with 5463 *
5178 * additional optimizations in place. 5464 * The library was designed directly after the MPI library by
5179 * 5465 * Michael Fromberger but has been written from scratch with
5180 * The library is free for all purposes without any express 5466 * additional optimizations in place.
5181 * guarantee it works. 5467 *
5182 * 5468 * The library is free for all purposes without any express
5183 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5469 * guarantee it works.
5184 */ 5470 *
5185 #include <tommath.h> 5471 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5472 */
5186 5473
5187 /* Miller-Rabin test of "a" to the base of "b" as described in 5474 /* Miller-Rabin test of "a" to the base of "b" as described in
5188 * HAC pp. 139 Algorithm 4.24 5475 * HAC pp. 139 Algorithm 4.24
5189 * 5476 *
5190 * Sets result to 0 if definitely composite or 1 if probably prime. 5477 * Sets result to 0 if definitely composite or 1 if probably prime.
5263 __Y:mp_clear (&y); 5550 __Y:mp_clear (&y);
5264 __R:mp_clear (&r); 5551 __R:mp_clear (&r);
5265 __N1:mp_clear (&n1); 5552 __N1:mp_clear (&n1);
5266 return err; 5553 return err;
5267 } 5554 }
5555 #endif
5268 5556
5269 /* End: bn_mp_prime_miller_rabin.c */ 5557 /* End: bn_mp_prime_miller_rabin.c */
5270 5558
5271 /* Start: bn_mp_prime_next_prime.c */ 5559 /* Start: bn_mp_prime_next_prime.c */
5272 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5560 #include <tommath.h>
5273 * 5561 #ifdef BN_MP_PRIME_NEXT_PRIME_C
5274 * LibTomMath is a library that provides multiple-precision 5562 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5275 * integer arithmetic as well as number theoretic functionality. 5563 *
5276 * 5564 * LibTomMath is a library that provides multiple-precision
5277 * The library was designed directly after the MPI library by 5565 * integer arithmetic as well as number theoretic functionality.
5278 * Michael Fromberger but has been written from scratch with 5566 *
5279 * additional optimizations in place. 5567 * The library was designed directly after the MPI library by
5280 * 5568 * Michael Fromberger but has been written from scratch with
5281 * The library is free for all purposes without any express 5569 * additional optimizations in place.
5282 * guarantee it works. 5570 *
5283 * 5571 * The library is free for all purposes without any express
5284 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5572 * guarantee it works.
5285 */ 5573 *
5286 #include <tommath.h> 5574 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5575 */
5287 5576
5288 /* finds the next prime after the number "a" using "t" trials 5577 /* finds the next prime after the number "a" using "t" trials
5289 * of Miller-Rabin. 5578 * of Miller-Rabin.
5290 * 5579 *
5291 * bbs_style = 1 means the prime must be congruent to 3 mod 4 5580 * bbs_style = 1 means the prime must be congruent to 3 mod 4
5431 __ERR: 5720 __ERR:
5432 mp_clear(&b); 5721 mp_clear(&b);
5433 return err; 5722 return err;
5434 } 5723 }
5435 5724
5725 #endif
5436 5726
5437 /* End: bn_mp_prime_next_prime.c */ 5727 /* End: bn_mp_prime_next_prime.c */
5438 5728
5729 /* Start: bn_mp_prime_rabin_miller_trials.c */
5730 #include <tommath.h>
5731 #ifdef BN_MP_PRIME_RABIN_MILLER_TRIALS_C
5732 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5733 *
5734 * LibTomMath is a library that provides multiple-precision
5735 * integer arithmetic as well as number theoretic functionality.
5736 *
5737 * The library was designed directly after the MPI library by
5738 * Michael Fromberger but has been written from scratch with
5739 * additional optimizations in place.
5740 *
5741 * The library is free for all purposes without any express
5742 * guarantee it works.
5743 *
5744 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5745 */
5746
5747
5748 static const struct {
5749 int k, t;
5750 } sizes[] = {
5751 { 128, 28 },
5752 { 256, 16 },
5753 { 384, 10 },
5754 { 512, 7 },
5755 { 640, 6 },
5756 { 768, 5 },
5757 { 896, 4 },
5758 { 1024, 4 }
5759 };
5760
5761 /* returns # of RM trials required for a given bit size */
5762 int mp_prime_rabin_miller_trials(int size)
5763 {
5764 int x;
5765
5766 for (x = 0; x < (int)(sizeof(sizes)/(sizeof(sizes[0]))); x++) {
5767 if (sizes[x].k == size) {
5768 return sizes[x].t;
5769 } else if (sizes[x].k > size) {
5770 return (x == 0) ? sizes[0].t : sizes[x - 1].t;
5771 }
5772 }
5773 return sizes[x-1].t + 1;
5774 }
5775
5776
5777 #endif
5778
5779 /* End: bn_mp_prime_rabin_miller_trials.c */
5780
5439 /* Start: bn_mp_prime_random_ex.c */ 5781 /* Start: bn_mp_prime_random_ex.c */
5440 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5782 #include <tommath.h>
5441 * 5783 #ifdef BN_MP_PRIME_RANDOM_EX_C
5442 * LibTomMath is a library that provides multiple-precision 5784 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5443 * integer arithmetic as well as number theoretic functionality. 5785 *
5444 * 5786 * LibTomMath is a library that provides multiple-precision
5445 * The library was designed directly after the MPI library by 5787 * integer arithmetic as well as number theoretic functionality.
5446 * Michael Fromberger but has been written from scratch with 5788 *
5447 * additional optimizations in place. 5789 * The library was designed directly after the MPI library by
5448 * 5790 * Michael Fromberger but has been written from scratch with
5449 * The library is free for all purposes without any express 5791 * additional optimizations in place.
5450 * guarantee it works. 5792 *
5451 * 5793 * The library is free for all purposes without any express
5452 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5794 * guarantee it works.
5453 */ 5795 *
5454 #include <tommath.h> 5796 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5797 */
5455 5798
5456 /* makes a truly random prime of a given size (bits), 5799 /* makes a truly random prime of a given size (bits),
5457 * 5800 *
5458 * Flags are as follows: 5801 * Flags are as follows:
5459 * 5802 *
5529 /* read it in */ 5872 /* read it in */
5530 if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) { goto error; } 5873 if ((err = mp_read_unsigned_bin(a, tmp, bsize)) != MP_OKAY) { goto error; }
5531 5874
5532 /* is it prime? */ 5875 /* is it prime? */
5533 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; } 5876 if ((err = mp_prime_is_prime(a, t, &res)) != MP_OKAY) { goto error; }
5877 if (res == MP_NO) {
5878 continue;
5879 }
5534 5880
5535 if (flags & LTM_PRIME_SAFE) { 5881 if (flags & LTM_PRIME_SAFE) {
5536 /* see if (a-1)/2 is prime */ 5882 /* see if (a-1)/2 is prime */
5537 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { goto error; } 5883 if ((err = mp_sub_d(a, 1, a)) != MP_OKAY) { goto error; }
5538 if ((err = mp_div_2(a, a)) != MP_OKAY) { goto error; } 5884 if ((err = mp_div_2(a, a)) != MP_OKAY) { goto error; }
5553 XFREE(tmp); 5899 XFREE(tmp);
5554 return err; 5900 return err;
5555 } 5901 }
5556 5902
5557 5903
5904 #endif
5558 5905
5559 /* End: bn_mp_prime_random_ex.c */ 5906 /* End: bn_mp_prime_random_ex.c */
5560 5907
5561 /* Start: bn_mp_radix_size.c */ 5908 /* Start: bn_mp_radix_size.c */
5562 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5909 #include <tommath.h>
5563 * 5910 #ifdef BN_MP_RADIX_SIZE_C
5564 * LibTomMath is a library that provides multiple-precision 5911 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5565 * integer arithmetic as well as number theoretic functionality. 5912 *
5566 * 5913 * LibTomMath is a library that provides multiple-precision
5567 * The library was designed directly after the MPI library by 5914 * integer arithmetic as well as number theoretic functionality.
5568 * Michael Fromberger but has been written from scratch with 5915 *
5569 * additional optimizations in place. 5916 * The library was designed directly after the MPI library by
5570 * 5917 * Michael Fromberger but has been written from scratch with
5571 * The library is free for all purposes without any express 5918 * additional optimizations in place.
5572 * guarantee it works. 5919 *
5573 * 5920 * The library is free for all purposes without any express
5574 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5921 * guarantee it works.
5575 */ 5922 *
5576 #include <tommath.h> 5923 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5924 */
5577 5925
5578 /* returns size of ASCII reprensentation */ 5926 /* returns size of ASCII reprensentation */
5579 int mp_radix_size (mp_int * a, int radix, int *size) 5927 int mp_radix_size (mp_int * a, int radix, int *size)
5580 { 5928 {
5581 int res, digs; 5929 int res, digs;
5622 /* return digs + 1, the 1 is for the NULL byte that would be required. */ 5970 /* return digs + 1, the 1 is for the NULL byte that would be required. */
5623 *size = digs + 1; 5971 *size = digs + 1;
5624 return MP_OKAY; 5972 return MP_OKAY;
5625 } 5973 }
5626 5974
5975 #endif
5627 5976
5628 /* End: bn_mp_radix_size.c */ 5977 /* End: bn_mp_radix_size.c */
5629 5978
5630 /* Start: bn_mp_radix_smap.c */ 5979 /* Start: bn_mp_radix_smap.c */
5631 /* LibTomMath, multiple-precision integer library -- Tom St Denis 5980 #include <tommath.h>
5632 * 5981 #ifdef BN_MP_RADIX_SMAP_C
5633 * LibTomMath is a library that provides multiple-precision 5982 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5634 * integer arithmetic as well as number theoretic functionality. 5983 *
5635 * 5984 * LibTomMath is a library that provides multiple-precision
5636 * The library was designed directly after the MPI library by 5985 * integer arithmetic as well as number theoretic functionality.
5637 * Michael Fromberger but has been written from scratch with 5986 *
5638 * additional optimizations in place. 5987 * The library was designed directly after the MPI library by
5639 * 5988 * Michael Fromberger but has been written from scratch with
5640 * The library is free for all purposes without any express 5989 * additional optimizations in place.
5641 * guarantee it works. 5990 *
5642 * 5991 * The library is free for all purposes without any express
5643 * Tom St Denis, [email protected], http://math.libtomcrypt.org 5992 * guarantee it works.
5644 */ 5993 *
5645 #include <tommath.h> 5994 * Tom St Denis, [email protected], http://math.libtomcrypt.org
5995 */
5646 5996
5647 /* chars used in radix conversions */ 5997 /* chars used in radix conversions */
5648 const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/"; 5998 const char *mp_s_rmap = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";
5999 #endif
5649 6000
5650 /* End: bn_mp_radix_smap.c */ 6001 /* End: bn_mp_radix_smap.c */
5651 6002
5652 /* Start: bn_mp_rand.c */ 6003 /* Start: bn_mp_rand.c */
5653 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6004 #include <tommath.h>
5654 * 6005 #ifdef BN_MP_RAND_C
5655 * LibTomMath is a library that provides multiple-precision 6006 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5656 * integer arithmetic as well as number theoretic functionality. 6007 *
5657 * 6008 * LibTomMath is a library that provides multiple-precision
5658 * The library was designed directly after the MPI library by 6009 * integer arithmetic as well as number theoretic functionality.
5659 * Michael Fromberger but has been written from scratch with 6010 *
5660 * additional optimizations in place. 6011 * The library was designed directly after the MPI library by
5661 * 6012 * Michael Fromberger but has been written from scratch with
5662 * The library is free for all purposes without any express 6013 * additional optimizations in place.
5663 * guarantee it works. 6014 *
5664 * 6015 * The library is free for all purposes without any express
5665 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6016 * guarantee it works.
5666 */ 6017 *
5667 #include <tommath.h> 6018 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6019 */
5668 6020
5669 /* makes a pseudo-random int of a given size */ 6021 /* makes a pseudo-random int of a given size */
5670 int 6022 int
5671 mp_rand (mp_int * a, int digits) 6023 mp_rand (mp_int * a, int digits)
5672 { 6024 {
5697 } 6049 }
5698 } 6050 }
5699 6051
5700 return MP_OKAY; 6052 return MP_OKAY;
5701 } 6053 }
6054 #endif
5702 6055
5703 /* End: bn_mp_rand.c */ 6056 /* End: bn_mp_rand.c */
5704 6057
5705 /* Start: bn_mp_read_radix.c */ 6058 /* Start: bn_mp_read_radix.c */
5706 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6059 #include <tommath.h>
5707 * 6060 #ifdef BN_MP_READ_RADIX_C
5708 * LibTomMath is a library that provides multiple-precision 6061 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5709 * integer arithmetic as well as number theoretic functionality. 6062 *
5710 * 6063 * LibTomMath is a library that provides multiple-precision
5711 * The library was designed directly after the MPI library by 6064 * integer arithmetic as well as number theoretic functionality.
5712 * Michael Fromberger but has been written from scratch with 6065 *
5713 * additional optimizations in place. 6066 * The library was designed directly after the MPI library by
5714 * 6067 * Michael Fromberger but has been written from scratch with
5715 * The library is free for all purposes without any express 6068 * additional optimizations in place.
5716 * guarantee it works. 6069 *
5717 * 6070 * The library is free for all purposes without any express
5718 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6071 * guarantee it works.
5719 */ 6072 *
5720 #include <tommath.h> 6073 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6074 */
5721 6075
5722 /* read a string [ASCII] in a given radix */ 6076 /* read a string [ASCII] in a given radix */
5723 int mp_read_radix (mp_int * a, char *str, int radix) 6077 int mp_read_radix (mp_int * a, char *str, int radix)
5724 { 6078 {
5725 int y, res, neg; 6079 int y, res, neg;
5777 if (mp_iszero(a) != 1) { 6131 if (mp_iszero(a) != 1) {
5778 a->sign = neg; 6132 a->sign = neg;
5779 } 6133 }
5780 return MP_OKAY; 6134 return MP_OKAY;
5781 } 6135 }
6136 #endif
5782 6137
5783 /* End: bn_mp_read_radix.c */ 6138 /* End: bn_mp_read_radix.c */
5784 6139
5785 /* Start: bn_mp_read_signed_bin.c */ 6140 /* Start: bn_mp_read_signed_bin.c */
5786 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6141 #include <tommath.h>
5787 * 6142 #ifdef BN_MP_READ_SIGNED_BIN_C
5788 * LibTomMath is a library that provides multiple-precision 6143 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5789 * integer arithmetic as well as number theoretic functionality. 6144 *
5790 * 6145 * LibTomMath is a library that provides multiple-precision
5791 * The library was designed directly after the MPI library by 6146 * integer arithmetic as well as number theoretic functionality.
5792 * Michael Fromberger but has been written from scratch with 6147 *
5793 * additional optimizations in place. 6148 * The library was designed directly after the MPI library by
5794 * 6149 * Michael Fromberger but has been written from scratch with
5795 * The library is free for all purposes without any express 6150 * additional optimizations in place.
5796 * guarantee it works. 6151 *
5797 * 6152 * The library is free for all purposes without any express
5798 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6153 * guarantee it works.
5799 */ 6154 *
5800 #include <tommath.h> 6155 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6156 */
5801 6157
5802 /* read signed bin, big endian, first byte is 0==positive or 1==negative */ 6158 /* read signed bin, big endian, first byte is 0==positive or 1==negative */
5803 int 6159 int
5804 mp_read_signed_bin (mp_int * a, unsigned char *b, int c) 6160 mp_read_signed_bin (mp_int * a, unsigned char *b, int c)
5805 { 6161 {
5817 a->sign = MP_NEG; 6173 a->sign = MP_NEG;
5818 } 6174 }
5819 6175
5820 return MP_OKAY; 6176 return MP_OKAY;
5821 } 6177 }
6178 #endif
5822 6179
5823 /* End: bn_mp_read_signed_bin.c */ 6180 /* End: bn_mp_read_signed_bin.c */
5824 6181
5825 /* Start: bn_mp_read_unsigned_bin.c */ 6182 /* Start: bn_mp_read_unsigned_bin.c */
5826 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6183 #include <tommath.h>
5827 * 6184 #ifdef BN_MP_READ_UNSIGNED_BIN_C
5828 * LibTomMath is a library that provides multiple-precision 6185 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5829 * integer arithmetic as well as number theoretic functionality. 6186 *
5830 * 6187 * LibTomMath is a library that provides multiple-precision
5831 * The library was designed directly after the MPI library by 6188 * integer arithmetic as well as number theoretic functionality.
5832 * Michael Fromberger but has been written from scratch with 6189 *
5833 * additional optimizations in place. 6190 * The library was designed directly after the MPI library by
5834 * 6191 * Michael Fromberger but has been written from scratch with
5835 * The library is free for all purposes without any express 6192 * additional optimizations in place.
5836 * guarantee it works. 6193 *
5837 * 6194 * The library is free for all purposes without any express
5838 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6195 * guarantee it works.
5839 */ 6196 *
5840 #include <tommath.h> 6197 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6198 */
5841 6199
5842 /* reads a unsigned char array, assumes the msb is stored first [big endian] */ 6200 /* reads a unsigned char array, assumes the msb is stored first [big endian] */
5843 int 6201 int
5844 mp_read_unsigned_bin (mp_int * a, unsigned char *b, int c) 6202 mp_read_unsigned_bin (mp_int * a, unsigned char *b, int c)
5845 { 6203 {
5871 #endif 6229 #endif
5872 } 6230 }
5873 mp_clamp (a); 6231 mp_clamp (a);
5874 return MP_OKAY; 6232 return MP_OKAY;
5875 } 6233 }
6234 #endif
5876 6235
5877 /* End: bn_mp_read_unsigned_bin.c */ 6236 /* End: bn_mp_read_unsigned_bin.c */
5878 6237
5879 /* Start: bn_mp_reduce.c */ 6238 /* Start: bn_mp_reduce.c */
5880 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6239 #include <tommath.h>
5881 * 6240 #ifdef BN_MP_REDUCE_C
5882 * LibTomMath is a library that provides multiple-precision 6241 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5883 * integer arithmetic as well as number theoretic functionality. 6242 *
5884 * 6243 * LibTomMath is a library that provides multiple-precision
5885 * The library was designed directly after the MPI library by 6244 * integer arithmetic as well as number theoretic functionality.
5886 * Michael Fromberger but has been written from scratch with 6245 *
5887 * additional optimizations in place. 6246 * The library was designed directly after the MPI library by
5888 * 6247 * Michael Fromberger but has been written from scratch with
5889 * The library is free for all purposes without any express 6248 * additional optimizations in place.
5890 * guarantee it works. 6249 *
5891 * 6250 * The library is free for all purposes without any express
5892 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6251 * guarantee it works.
5893 */ 6252 *
5894 #include <tommath.h> 6253 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6254 */
5895 6255
5896 /* reduces x mod m, assumes 0 < x < m**2, mu is 6256 /* reduces x mod m, assumes 0 < x < m**2, mu is
5897 * precomputed via mp_reduce_setup. 6257 * precomputed via mp_reduce_setup.
5898 * From HAC pp.604 Algorithm 14.42 6258 * From HAC pp.604 Algorithm 14.42
5899 */ 6259 */
5915 if (((unsigned long) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) { 6275 if (((unsigned long) um) > (((mp_digit)1) << (DIGIT_BIT - 1))) {
5916 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) { 6276 if ((res = mp_mul (&q, mu, &q)) != MP_OKAY) {
5917 goto CLEANUP; 6277 goto CLEANUP;
5918 } 6278 }
5919 } else { 6279 } else {
6280 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
5920 if ((res = s_mp_mul_high_digs (&q, mu, &q, um - 1)) != MP_OKAY) { 6281 if ((res = s_mp_mul_high_digs (&q, mu, &q, um - 1)) != MP_OKAY) {
5921 goto CLEANUP; 6282 goto CLEANUP;
5922 } 6283 }
6284 #elif defined(BN_FAST_S_MP_MUL_HIGH_DIGS_C)
6285 if ((res = fast_s_mp_mul_high_digs (&q, mu, &q, um - 1)) != MP_OKAY) {
6286 goto CLEANUP;
6287 }
6288 #else
6289 {
6290 res = MP_VAL;
6291 goto CLEANUP;
6292 }
6293 #endif
5923 } 6294 }
5924 6295
5925 /* q3 = q2 / b**(k+1) */ 6296 /* q3 = q2 / b**(k+1) */
5926 mp_rshd (&q, um + 1); 6297 mp_rshd (&q, um + 1);
5927 6298
5959 CLEANUP: 6330 CLEANUP:
5960 mp_clear (&q); 6331 mp_clear (&q);
5961 6332
5962 return res; 6333 return res;
5963 } 6334 }
6335 #endif
5964 6336
5965 /* End: bn_mp_reduce.c */ 6337 /* End: bn_mp_reduce.c */
5966 6338
5967 /* Start: bn_mp_reduce_2k.c */ 6339 /* Start: bn_mp_reduce_2k.c */
5968 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6340 #include <tommath.h>
5969 * 6341 #ifdef BN_MP_REDUCE_2K_C
5970 * LibTomMath is a library that provides multiple-precision 6342 /* LibTomMath, multiple-precision integer library -- Tom St Denis
5971 * integer arithmetic as well as number theoretic functionality. 6343 *
5972 * 6344 * LibTomMath is a library that provides multiple-precision
5973 * The library was designed directly after the MPI library by 6345 * integer arithmetic as well as number theoretic functionality.
5974 * Michael Fromberger but has been written from scratch with 6346 *
5975 * additional optimizations in place. 6347 * The library was designed directly after the MPI library by
5976 * 6348 * Michael Fromberger but has been written from scratch with
5977 * The library is free for all purposes without any express 6349 * additional optimizations in place.
5978 * guarantee it works. 6350 *
5979 * 6351 * The library is free for all purposes without any express
5980 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6352 * guarantee it works.
5981 */ 6353 *
5982 #include <tommath.h> 6354 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6355 */
5983 6356
5984 /* reduces a modulo n where n is of the form 2**p - d */ 6357 /* reduces a modulo n where n is of the form 2**p - d */
5985 int 6358 int
5986 mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d) 6359 mp_reduce_2k(mp_int *a, mp_int *n, mp_digit d)
5987 { 6360 {
6019 ERR: 6392 ERR:
6020 mp_clear(&q); 6393 mp_clear(&q);
6021 return res; 6394 return res;
6022 } 6395 }
6023 6396
6397 #endif
6024 6398
6025 /* End: bn_mp_reduce_2k.c */ 6399 /* End: bn_mp_reduce_2k.c */
6026 6400
6027 /* Start: bn_mp_reduce_2k_setup.c */ 6401 /* Start: bn_mp_reduce_2k_setup.c */
6028 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6402 #include <tommath.h>
6029 * 6403 #ifdef BN_MP_REDUCE_2K_SETUP_C
6030 * LibTomMath is a library that provides multiple-precision 6404 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6031 * integer arithmetic as well as number theoretic functionality. 6405 *
6032 * 6406 * LibTomMath is a library that provides multiple-precision
6033 * The library was designed directly after the MPI library by 6407 * integer arithmetic as well as number theoretic functionality.
6034 * Michael Fromberger but has been written from scratch with 6408 *
6035 * additional optimizations in place. 6409 * The library was designed directly after the MPI library by
6036 * 6410 * Michael Fromberger but has been written from scratch with
6037 * The library is free for all purposes without any express 6411 * additional optimizations in place.
6038 * guarantee it works. 6412 *
6039 * 6413 * The library is free for all purposes without any express
6040 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6414 * guarantee it works.
6041 */ 6415 *
6042 #include <tommath.h> 6416 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6417 */
6043 6418
6044 /* determines the setup value */ 6419 /* determines the setup value */
6045 int 6420 int
6046 mp_reduce_2k_setup(mp_int *a, mp_digit *d) 6421 mp_reduce_2k_setup(mp_int *a, mp_digit *d)
6047 { 6422 {
6065 6440
6066 *d = tmp.dp[0]; 6441 *d = tmp.dp[0];
6067 mp_clear(&tmp); 6442 mp_clear(&tmp);
6068 return MP_OKAY; 6443 return MP_OKAY;
6069 } 6444 }
6445 #endif
6070 6446
6071 /* End: bn_mp_reduce_2k_setup.c */ 6447 /* End: bn_mp_reduce_2k_setup.c */
6072 6448
6073 /* Start: bn_mp_reduce_is_2k.c */ 6449 /* Start: bn_mp_reduce_is_2k.c */
6074 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6450 #include <tommath.h>
6075 * 6451 #ifdef BN_MP_REDUCE_IS_2K_C
6076 * LibTomMath is a library that provides multiple-precision 6452 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6077 * integer arithmetic as well as number theoretic functionality. 6453 *
6078 * 6454 * LibTomMath is a library that provides multiple-precision
6079 * The library was designed directly after the MPI library by 6455 * integer arithmetic as well as number theoretic functionality.
6080 * Michael Fromberger but has been written from scratch with 6456 *
6081 * additional optimizations in place. 6457 * The library was designed directly after the MPI library by
6082 * 6458 * Michael Fromberger but has been written from scratch with
6083 * The library is free for all purposes without any express 6459 * additional optimizations in place.
6084 * guarantee it works. 6460 *
6085 * 6461 * The library is free for all purposes without any express
6086 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6462 * guarantee it works.
6087 */ 6463 *
6088 #include <tommath.h> 6464 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6465 */
6089 6466
6090 /* determines if mp_reduce_2k can be used */ 6467 /* determines if mp_reduce_2k can be used */
6091 int mp_reduce_is_2k(mp_int *a) 6468 int mp_reduce_is_2k(mp_int *a)
6092 { 6469 {
6093 int ix, iy, iz, iw; 6470 int ix, iy, iw;
6471 mp_digit iz;
6094 6472
6095 if (a->used == 0) { 6473 if (a->used == 0) {
6096 return 0; 6474 return 0;
6097 } else if (a->used == 1) { 6475 } else if (a->used == 1) {
6098 return 1; 6476 return 1;
6105 for (ix = DIGIT_BIT; ix < iy; ix++) { 6483 for (ix = DIGIT_BIT; ix < iy; ix++) {
6106 if ((a->dp[iw] & iz) == 0) { 6484 if ((a->dp[iw] & iz) == 0) {
6107 return 0; 6485 return 0;
6108 } 6486 }
6109 iz <<= 1; 6487 iz <<= 1;
6110 if (iz > (int)MP_MASK) { 6488 if (iz > (mp_digit)MP_MASK) {
6111 ++iw; 6489 ++iw;
6112 iz = 1; 6490 iz = 1;
6113 } 6491 }
6114 } 6492 }
6115 } 6493 }
6116 return 1; 6494 return 1;
6117 } 6495 }
6118 6496
6497 #endif
6119 6498
6120 /* End: bn_mp_reduce_is_2k.c */ 6499 /* End: bn_mp_reduce_is_2k.c */
6121 6500
6122 /* Start: bn_mp_reduce_setup.c */ 6501 /* Start: bn_mp_reduce_setup.c */
6123 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6502 #include <tommath.h>
6124 * 6503 #ifdef BN_MP_REDUCE_SETUP_C
6125 * LibTomMath is a library that provides multiple-precision 6504 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6126 * integer arithmetic as well as number theoretic functionality. 6505 *
6127 * 6506 * LibTomMath is a library that provides multiple-precision
6128 * The library was designed directly after the MPI library by 6507 * integer arithmetic as well as number theoretic functionality.
6129 * Michael Fromberger but has been written from scratch with 6508 *
6130 * additional optimizations in place. 6509 * The library was designed directly after the MPI library by
6131 * 6510 * Michael Fromberger but has been written from scratch with
6132 * The library is free for all purposes without any express 6511 * additional optimizations in place.
6133 * guarantee it works. 6512 *
6134 * 6513 * The library is free for all purposes without any express
6135 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6514 * guarantee it works.
6136 */ 6515 *
6137 #include <tommath.h> 6516 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6517 */
6138 6518
6139 /* pre-calculate the value required for Barrett reduction 6519 /* pre-calculate the value required for Barrett reduction
6140 * For a given modulus "b" it calulates the value required in "a" 6520 * For a given modulus "b" it calulates the value required in "a"
6141 */ 6521 */
6142 int 6522 int mp_reduce_setup (mp_int * a, mp_int * b)
6143 mp_reduce_setup (mp_int * a, mp_int * b)
6144 { 6523 {
6145 int res; 6524 int res;
6146 6525
6147 if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) { 6526 if ((res = mp_2expt (a, b->used * 2 * DIGIT_BIT)) != MP_OKAY) {
6148 return res; 6527 return res;
6149 } 6528 }
6150 return mp_div (a, b, a, NULL); 6529 return mp_div (a, b, a, NULL);
6151 } 6530 }
6531 #endif
6152 6532
6153 /* End: bn_mp_reduce_setup.c */ 6533 /* End: bn_mp_reduce_setup.c */
6154 6534
6155 /* Start: bn_mp_rshd.c */ 6535 /* Start: bn_mp_rshd.c */
6156 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6536 #include <tommath.h>
6157 * 6537 #ifdef BN_MP_RSHD_C
6158 * LibTomMath is a library that provides multiple-precision 6538 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6159 * integer arithmetic as well as number theoretic functionality. 6539 *
6160 * 6540 * LibTomMath is a library that provides multiple-precision
6161 * The library was designed directly after the MPI library by 6541 * integer arithmetic as well as number theoretic functionality.
6162 * Michael Fromberger but has been written from scratch with 6542 *
6163 * additional optimizations in place. 6543 * The library was designed directly after the MPI library by
6164 * 6544 * Michael Fromberger but has been written from scratch with
6165 * The library is free for all purposes without any express 6545 * additional optimizations in place.
6166 * guarantee it works. 6546 *
6167 * 6547 * The library is free for all purposes without any express
6168 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6548 * guarantee it works.
6169 */ 6549 *
6170 #include <tommath.h> 6550 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6551 */
6171 6552
6172 /* shift right a certain amount of digits */ 6553 /* shift right a certain amount of digits */
6173 void mp_rshd (mp_int * a, int b) 6554 void mp_rshd (mp_int * a, int b)
6174 { 6555 {
6175 int x; 6556 int x;
6217 } 6598 }
6218 6599
6219 /* remove excess digits */ 6600 /* remove excess digits */
6220 a->used -= b; 6601 a->used -= b;
6221 } 6602 }
6603 #endif
6222 6604
6223 /* End: bn_mp_rshd.c */ 6605 /* End: bn_mp_rshd.c */
6224 6606
6225 /* Start: bn_mp_set.c */ 6607 /* Start: bn_mp_set.c */
6226 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6608 #include <tommath.h>
6227 * 6609 #ifdef BN_MP_SET_C
6228 * LibTomMath is a library that provides multiple-precision 6610 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6229 * integer arithmetic as well as number theoretic functionality. 6611 *
6230 * 6612 * LibTomMath is a library that provides multiple-precision
6231 * The library was designed directly after the MPI library by 6613 * integer arithmetic as well as number theoretic functionality.
6232 * Michael Fromberger but has been written from scratch with 6614 *
6233 * additional optimizations in place. 6615 * The library was designed directly after the MPI library by
6234 * 6616 * Michael Fromberger but has been written from scratch with
6235 * The library is free for all purposes without any express 6617 * additional optimizations in place.
6236 * guarantee it works. 6618 *
6237 * 6619 * The library is free for all purposes without any express
6238 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6620 * guarantee it works.
6239 */ 6621 *
6240 #include <tommath.h> 6622 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6623 */
6241 6624
6242 /* set to a digit */ 6625 /* set to a digit */
6243 void mp_set (mp_int * a, mp_digit b) 6626 void mp_set (mp_int * a, mp_digit b)
6244 { 6627 {
6245 mp_zero (a); 6628 mp_zero (a);
6246 a->dp[0] = b & MP_MASK; 6629 a->dp[0] = b & MP_MASK;
6247 a->used = (a->dp[0] != 0) ? 1 : 0; 6630 a->used = (a->dp[0] != 0) ? 1 : 0;
6248 } 6631 }
6632 #endif
6249 6633
6250 /* End: bn_mp_set.c */ 6634 /* End: bn_mp_set.c */
6251 6635
6252 /* Start: bn_mp_set_int.c */ 6636 /* Start: bn_mp_set_int.c */
6253 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6637 #include <tommath.h>
6254 * 6638 #ifdef BN_MP_SET_INT_C
6255 * LibTomMath is a library that provides multiple-precision 6639 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6256 * integer arithmetic as well as number theoretic functionality. 6640 *
6257 * 6641 * LibTomMath is a library that provides multiple-precision
6258 * The library was designed directly after the MPI library by 6642 * integer arithmetic as well as number theoretic functionality.
6259 * Michael Fromberger but has been written from scratch with 6643 *
6260 * additional optimizations in place. 6644 * The library was designed directly after the MPI library by
6261 * 6645 * Michael Fromberger but has been written from scratch with
6262 * The library is free for all purposes without any express 6646 * additional optimizations in place.
6263 * guarantee it works. 6647 *
6264 * 6648 * The library is free for all purposes without any express
6265 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6649 * guarantee it works.
6266 */ 6650 *
6267 #include <tommath.h> 6651 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6652 */
6268 6653
6269 /* set a 32-bit const */ 6654 /* set a 32-bit const */
6270 int mp_set_int (mp_int * a, unsigned long b) 6655 int mp_set_int (mp_int * a, unsigned long b)
6271 { 6656 {
6272 int x, res; 6657 int x, res;
6290 a->used += 1; 6675 a->used += 1;
6291 } 6676 }
6292 mp_clamp (a); 6677 mp_clamp (a);
6293 return MP_OKAY; 6678 return MP_OKAY;
6294 } 6679 }
6680 #endif
6295 6681
6296 /* End: bn_mp_set_int.c */ 6682 /* End: bn_mp_set_int.c */
6297 6683
6298 /* Start: bn_mp_shrink.c */ 6684 /* Start: bn_mp_shrink.c */
6299 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6685 #include <tommath.h>
6300 * 6686 #ifdef BN_MP_SHRINK_C
6301 * LibTomMath is a library that provides multiple-precision 6687 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6302 * integer arithmetic as well as number theoretic functionality. 6688 *
6303 * 6689 * LibTomMath is a library that provides multiple-precision
6304 * The library was designed directly after the MPI library by 6690 * integer arithmetic as well as number theoretic functionality.
6305 * Michael Fromberger but has been written from scratch with 6691 *
6306 * additional optimizations in place. 6692 * The library was designed directly after the MPI library by
6307 * 6693 * Michael Fromberger but has been written from scratch with
6308 * The library is free for all purposes without any express 6694 * additional optimizations in place.
6309 * guarantee it works. 6695 *
6310 * 6696 * The library is free for all purposes without any express
6311 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6697 * guarantee it works.
6312 */ 6698 *
6313 #include <tommath.h> 6699 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6700 */
6314 6701
6315 /* shrink a bignum */ 6702 /* shrink a bignum */
6316 int mp_shrink (mp_int * a) 6703 int mp_shrink (mp_int * a)
6317 { 6704 {
6318 mp_digit *tmp; 6705 mp_digit *tmp;
6323 a->dp = tmp; 6710 a->dp = tmp;
6324 a->alloc = a->used; 6711 a->alloc = a->used;
6325 } 6712 }
6326 return MP_OKAY; 6713 return MP_OKAY;
6327 } 6714 }
6715 #endif
6328 6716
6329 /* End: bn_mp_shrink.c */ 6717 /* End: bn_mp_shrink.c */
6330 6718
6331 /* Start: bn_mp_signed_bin_size.c */ 6719 /* Start: bn_mp_signed_bin_size.c */
6332 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6720 #include <tommath.h>
6333 * 6721 #ifdef BN_MP_SIGNED_BIN_SIZE_C
6334 * LibTomMath is a library that provides multiple-precision 6722 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6335 * integer arithmetic as well as number theoretic functionality. 6723 *
6336 * 6724 * LibTomMath is a library that provides multiple-precision
6337 * The library was designed directly after the MPI library by 6725 * integer arithmetic as well as number theoretic functionality.
6338 * Michael Fromberger but has been written from scratch with 6726 *
6339 * additional optimizations in place. 6727 * The library was designed directly after the MPI library by
6340 * 6728 * Michael Fromberger but has been written from scratch with
6341 * The library is free for all purposes without any express 6729 * additional optimizations in place.
6342 * guarantee it works. 6730 *
6343 * 6731 * The library is free for all purposes without any express
6344 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6732 * guarantee it works.
6345 */ 6733 *
6346 #include <tommath.h> 6734 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6735 */
6347 6736
6348 /* get the size for an signed equivalent */ 6737 /* get the size for an signed equivalent */
6349 int mp_signed_bin_size (mp_int * a) 6738 int mp_signed_bin_size (mp_int * a)
6350 { 6739 {
6351 return 1 + mp_unsigned_bin_size (a); 6740 return 1 + mp_unsigned_bin_size (a);
6352 } 6741 }
6742 #endif
6353 6743
6354 /* End: bn_mp_signed_bin_size.c */ 6744 /* End: bn_mp_signed_bin_size.c */
6355 6745
6356 /* Start: bn_mp_sqr.c */ 6746 /* Start: bn_mp_sqr.c */
6357 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6747 #include <tommath.h>
6358 * 6748 #ifdef BN_MP_SQR_C
6359 * LibTomMath is a library that provides multiple-precision 6749 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6360 * integer arithmetic as well as number theoretic functionality. 6750 *
6361 * 6751 * LibTomMath is a library that provides multiple-precision
6362 * The library was designed directly after the MPI library by 6752 * integer arithmetic as well as number theoretic functionality.
6363 * Michael Fromberger but has been written from scratch with 6753 *
6364 * additional optimizations in place. 6754 * The library was designed directly after the MPI library by
6365 * 6755 * Michael Fromberger but has been written from scratch with
6366 * The library is free for all purposes without any express 6756 * additional optimizations in place.
6367 * guarantee it works. 6757 *
6368 * 6758 * The library is free for all purposes without any express
6369 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6759 * guarantee it works.
6370 */ 6760 *
6371 #include <tommath.h> 6761 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6762 */
6372 6763
6373 /* computes b = a*a */ 6764 /* computes b = a*a */
6374 int 6765 int
6375 mp_sqr (mp_int * a, mp_int * b) 6766 mp_sqr (mp_int * a, mp_int * b)
6376 { 6767 {
6377 int res; 6768 int res;
6378 6769
6770 #ifdef BN_MP_TOOM_SQR_C
6379 /* use Toom-Cook? */ 6771 /* use Toom-Cook? */
6380 if (a->used >= TOOM_SQR_CUTOFF) { 6772 if (a->used >= TOOM_SQR_CUTOFF) {
6381 res = mp_toom_sqr(a, b); 6773 res = mp_toom_sqr(a, b);
6382 /* Karatsuba? */ 6774 /* Karatsuba? */
6383 } else if (a->used >= KARATSUBA_SQR_CUTOFF) { 6775 } else
6776 #endif
6777 #ifdef BN_MP_KARATSUBA_SQR_C
6778 if (a->used >= KARATSUBA_SQR_CUTOFF) {
6384 res = mp_karatsuba_sqr (a, b); 6779 res = mp_karatsuba_sqr (a, b);
6385 } else { 6780 } else
6781 #endif
6782 {
6783 #ifdef BN_FAST_S_MP_SQR_C
6386 /* can we use the fast comba multiplier? */ 6784 /* can we use the fast comba multiplier? */
6387 if ((a->used * 2 + 1) < MP_WARRAY && 6785 if ((a->used * 2 + 1) < MP_WARRAY &&
6388 a->used < 6786 a->used <
6389 (1 << (sizeof(mp_word) * CHAR_BIT - 2*DIGIT_BIT - 1))) { 6787 (1 << (sizeof(mp_word) * CHAR_BIT - 2*DIGIT_BIT - 1))) {
6390 res = fast_s_mp_sqr (a, b); 6788 res = fast_s_mp_sqr (a, b);
6391 } else { 6789 } else
6790 #endif
6791 #ifdef BN_S_MP_SQR_C
6392 res = s_mp_sqr (a, b); 6792 res = s_mp_sqr (a, b);
6393 } 6793 #else
6794 res = MP_VAL;
6795 #endif
6394 } 6796 }
6395 b->sign = MP_ZPOS; 6797 b->sign = MP_ZPOS;
6396 return res; 6798 return res;
6397 } 6799 }
6800 #endif
6398 6801
6399 /* End: bn_mp_sqr.c */ 6802 /* End: bn_mp_sqr.c */
6400 6803
6401 /* Start: bn_mp_sqrmod.c */ 6804 /* Start: bn_mp_sqrmod.c */
6402 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6805 #include <tommath.h>
6403 * 6806 #ifdef BN_MP_SQRMOD_C
6404 * LibTomMath is a library that provides multiple-precision 6807 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6405 * integer arithmetic as well as number theoretic functionality. 6808 *
6406 * 6809 * LibTomMath is a library that provides multiple-precision
6407 * The library was designed directly after the MPI library by 6810 * integer arithmetic as well as number theoretic functionality.
6408 * Michael Fromberger but has been written from scratch with 6811 *
6409 * additional optimizations in place. 6812 * The library was designed directly after the MPI library by
6410 * 6813 * Michael Fromberger but has been written from scratch with
6411 * The library is free for all purposes without any express 6814 * additional optimizations in place.
6412 * guarantee it works. 6815 *
6413 * 6816 * The library is free for all purposes without any express
6414 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6817 * guarantee it works.
6415 */ 6818 *
6416 #include <tommath.h> 6819 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6820 */
6417 6821
6418 /* c = a * a (mod b) */ 6822 /* c = a * a (mod b) */
6419 int 6823 int
6420 mp_sqrmod (mp_int * a, mp_int * b, mp_int * c) 6824 mp_sqrmod (mp_int * a, mp_int * b, mp_int * c)
6421 { 6825 {
6432 } 6836 }
6433 res = mp_mod (&t, b, c); 6837 res = mp_mod (&t, b, c);
6434 mp_clear (&t); 6838 mp_clear (&t);
6435 return res; 6839 return res;
6436 } 6840 }
6841 #endif
6437 6842
6438 /* End: bn_mp_sqrmod.c */ 6843 /* End: bn_mp_sqrmod.c */
6439 6844
6440 /* Start: bn_mp_sqrt.c */ 6845 /* Start: bn_mp_sqrt.c */
6441 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6846 #include <tommath.h>
6442 * 6847 #ifdef BN_MP_SQRT_C
6443 * LibTomMath is a library that provides multiple-precision 6848 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6444 * integer arithmetic as well as number theoretic functionality. 6849 *
6445 * 6850 * LibTomMath is a library that provides multiple-precision
6446 * The library was designed directly after the MPI library by 6851 * integer arithmetic as well as number theoretic functionality.
6447 * Michael Fromberger but has been written from scratch with 6852 *
6448 * additional optimizations in place. 6853 * The library was designed directly after the MPI library by
6449 * 6854 * Michael Fromberger but has been written from scratch with
6450 * The library is free for all purposes without any express 6855 * additional optimizations in place.
6451 * guarantee it works. 6856 *
6452 * 6857 * The library is free for all purposes without any express
6453 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6858 * guarantee it works.
6454 */ 6859 *
6455 #include <tommath.h> 6860 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6861 */
6456 6862
6457 /* this function is less generic than mp_n_root, simpler and faster */ 6863 /* this function is less generic than mp_n_root, simpler and faster */
6458 int mp_sqrt(mp_int *arg, mp_int *ret) 6864 int mp_sqrt(mp_int *arg, mp_int *ret)
6459 { 6865 {
6460 int res; 6866 int res;
6511 E1: mp_clear(&t2); 6917 E1: mp_clear(&t2);
6512 E2: mp_clear(&t1); 6918 E2: mp_clear(&t1);
6513 return res; 6919 return res;
6514 } 6920 }
6515 6921
6922 #endif
6516 6923
6517 /* End: bn_mp_sqrt.c */ 6924 /* End: bn_mp_sqrt.c */
6518 6925
6519 /* Start: bn_mp_sub.c */ 6926 /* Start: bn_mp_sub.c */
6520 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6927 #include <tommath.h>
6521 * 6928 #ifdef BN_MP_SUB_C
6522 * LibTomMath is a library that provides multiple-precision 6929 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6523 * integer arithmetic as well as number theoretic functionality. 6930 *
6524 * 6931 * LibTomMath is a library that provides multiple-precision
6525 * The library was designed directly after the MPI library by 6932 * integer arithmetic as well as number theoretic functionality.
6526 * Michael Fromberger but has been written from scratch with 6933 *
6527 * additional optimizations in place. 6934 * The library was designed directly after the MPI library by
6528 * 6935 * Michael Fromberger but has been written from scratch with
6529 * The library is free for all purposes without any express 6936 * additional optimizations in place.
6530 * guarantee it works. 6937 *
6531 * 6938 * The library is free for all purposes without any express
6532 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6939 * guarantee it works.
6533 */ 6940 *
6534 #include <tommath.h> 6941 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6942 */
6535 6943
6536 /* high level subtraction (handles signs) */ 6944 /* high level subtraction (handles signs) */
6537 int 6945 int
6538 mp_sub (mp_int * a, mp_int * b, mp_int * c) 6946 mp_sub (mp_int * a, mp_int * b, mp_int * c)
6539 { 6947 {
6568 } 6976 }
6569 } 6977 }
6570 return res; 6978 return res;
6571 } 6979 }
6572 6980
6981 #endif
6573 6982
6574 /* End: bn_mp_sub.c */ 6983 /* End: bn_mp_sub.c */
6575 6984
6576 /* Start: bn_mp_sub_d.c */ 6985 /* Start: bn_mp_sub_d.c */
6577 /* LibTomMath, multiple-precision integer library -- Tom St Denis 6986 #include <tommath.h>
6578 * 6987 #ifdef BN_MP_SUB_D_C
6579 * LibTomMath is a library that provides multiple-precision 6988 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6580 * integer arithmetic as well as number theoretic functionality. 6989 *
6581 * 6990 * LibTomMath is a library that provides multiple-precision
6582 * The library was designed directly after the MPI library by 6991 * integer arithmetic as well as number theoretic functionality.
6583 * Michael Fromberger but has been written from scratch with 6992 *
6584 * additional optimizations in place. 6993 * The library was designed directly after the MPI library by
6585 * 6994 * Michael Fromberger but has been written from scratch with
6586 * The library is free for all purposes without any express 6995 * additional optimizations in place.
6587 * guarantee it works. 6996 *
6588 * 6997 * The library is free for all purposes without any express
6589 * Tom St Denis, [email protected], http://math.libtomcrypt.org 6998 * guarantee it works.
6590 */ 6999 *
6591 #include <tommath.h> 7000 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7001 */
6592 7002
6593 /* single digit subtraction */ 7003 /* single digit subtraction */
6594 int 7004 int
6595 mp_sub_d (mp_int * a, mp_digit b, mp_int * c) 7005 mp_sub_d (mp_int * a, mp_digit b, mp_int * c)
6596 { 7006 {
6655 } 7065 }
6656 mp_clamp(c); 7066 mp_clamp(c);
6657 return MP_OKAY; 7067 return MP_OKAY;
6658 } 7068 }
6659 7069
7070 #endif
6660 7071
6661 /* End: bn_mp_sub_d.c */ 7072 /* End: bn_mp_sub_d.c */
6662 7073
6663 /* Start: bn_mp_submod.c */ 7074 /* Start: bn_mp_submod.c */
6664 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7075 #include <tommath.h>
6665 * 7076 #ifdef BN_MP_SUBMOD_C
6666 * LibTomMath is a library that provides multiple-precision 7077 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6667 * integer arithmetic as well as number theoretic functionality. 7078 *
6668 * 7079 * LibTomMath is a library that provides multiple-precision
6669 * The library was designed directly after the MPI library by 7080 * integer arithmetic as well as number theoretic functionality.
6670 * Michael Fromberger but has been written from scratch with 7081 *
6671 * additional optimizations in place. 7082 * The library was designed directly after the MPI library by
6672 * 7083 * Michael Fromberger but has been written from scratch with
6673 * The library is free for all purposes without any express 7084 * additional optimizations in place.
6674 * guarantee it works. 7085 *
6675 * 7086 * The library is free for all purposes without any express
6676 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7087 * guarantee it works.
6677 */ 7088 *
6678 #include <tommath.h> 7089 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7090 */
6679 7091
6680 /* d = a - b (mod c) */ 7092 /* d = a - b (mod c) */
6681 int 7093 int
6682 mp_submod (mp_int * a, mp_int * b, mp_int * c, mp_int * d) 7094 mp_submod (mp_int * a, mp_int * b, mp_int * c, mp_int * d)
6683 { 7095 {
6695 } 7107 }
6696 res = mp_mod (&t, c, d); 7108 res = mp_mod (&t, c, d);
6697 mp_clear (&t); 7109 mp_clear (&t);
6698 return res; 7110 return res;
6699 } 7111 }
7112 #endif
6700 7113
6701 /* End: bn_mp_submod.c */ 7114 /* End: bn_mp_submod.c */
6702 7115
6703 /* Start: bn_mp_to_signed_bin.c */ 7116 /* Start: bn_mp_to_signed_bin.c */
6704 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7117 #include <tommath.h>
6705 * 7118 #ifdef BN_MP_TO_SIGNED_BIN_C
6706 * LibTomMath is a library that provides multiple-precision 7119 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6707 * integer arithmetic as well as number theoretic functionality. 7120 *
6708 * 7121 * LibTomMath is a library that provides multiple-precision
6709 * The library was designed directly after the MPI library by 7122 * integer arithmetic as well as number theoretic functionality.
6710 * Michael Fromberger but has been written from scratch with 7123 *
6711 * additional optimizations in place. 7124 * The library was designed directly after the MPI library by
6712 * 7125 * Michael Fromberger but has been written from scratch with
6713 * The library is free for all purposes without any express 7126 * additional optimizations in place.
6714 * guarantee it works. 7127 *
6715 * 7128 * The library is free for all purposes without any express
6716 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7129 * guarantee it works.
6717 */ 7130 *
6718 #include <tommath.h> 7131 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7132 */
6719 7133
6720 /* store in signed [big endian] format */ 7134 /* store in signed [big endian] format */
6721 int 7135 int
6722 mp_to_signed_bin (mp_int * a, unsigned char *b) 7136 mp_to_signed_bin (mp_int * a, unsigned char *b)
6723 { 7137 {
6727 return res; 7141 return res;
6728 } 7142 }
6729 b[0] = (unsigned char) ((a->sign == MP_ZPOS) ? 0 : 1); 7143 b[0] = (unsigned char) ((a->sign == MP_ZPOS) ? 0 : 1);
6730 return MP_OKAY; 7144 return MP_OKAY;
6731 } 7145 }
7146 #endif
6732 7147
6733 /* End: bn_mp_to_signed_bin.c */ 7148 /* End: bn_mp_to_signed_bin.c */
6734 7149
6735 /* Start: bn_mp_to_unsigned_bin.c */ 7150 /* Start: bn_mp_to_unsigned_bin.c */
6736 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7151 #include <tommath.h>
6737 * 7152 #ifdef BN_MP_TO_UNSIGNED_BIN_C
6738 * LibTomMath is a library that provides multiple-precision 7153 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6739 * integer arithmetic as well as number theoretic functionality. 7154 *
6740 * 7155 * LibTomMath is a library that provides multiple-precision
6741 * The library was designed directly after the MPI library by 7156 * integer arithmetic as well as number theoretic functionality.
6742 * Michael Fromberger but has been written from scratch with 7157 *
6743 * additional optimizations in place. 7158 * The library was designed directly after the MPI library by
6744 * 7159 * Michael Fromberger but has been written from scratch with
6745 * The library is free for all purposes without any express 7160 * additional optimizations in place.
6746 * guarantee it works. 7161 *
6747 * 7162 * The library is free for all purposes without any express
6748 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7163 * guarantee it works.
6749 */ 7164 *
6750 #include <tommath.h> 7165 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7166 */
6751 7167
6752 /* store in unsigned [big endian] format */ 7168 /* store in unsigned [big endian] format */
6753 int 7169 int
6754 mp_to_unsigned_bin (mp_int * a, unsigned char *b) 7170 mp_to_unsigned_bin (mp_int * a, unsigned char *b)
6755 { 7171 {
6774 } 7190 }
6775 bn_reverse (b, x); 7191 bn_reverse (b, x);
6776 mp_clear (&t); 7192 mp_clear (&t);
6777 return MP_OKAY; 7193 return MP_OKAY;
6778 } 7194 }
7195 #endif
6779 7196
6780 /* End: bn_mp_to_unsigned_bin.c */ 7197 /* End: bn_mp_to_unsigned_bin.c */
6781 7198
6782 /* Start: bn_mp_toom_mul.c */ 7199 /* Start: bn_mp_toom_mul.c */
6783 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7200 #include <tommath.h>
6784 * 7201 #ifdef BN_MP_TOOM_MUL_C
6785 * LibTomMath is a library that provides multiple-precision 7202 /* LibTomMath, multiple-precision integer library -- Tom St Denis
6786 * integer arithmetic as well as number theoretic functionality. 7203 *
6787 * 7204 * LibTomMath is a library that provides multiple-precision
6788 * The library was designed directly after the MPI library by 7205 * integer arithmetic as well as number theoretic functionality.
6789 * Michael Fromberger but has been written from scratch with 7206 *
6790 * additional optimizations in place. 7207 * The library was designed directly after the MPI library by
6791 * 7208 * Michael Fromberger but has been written from scratch with
6792 * The library is free for all purposes without any express 7209 * additional optimizations in place.
6793 * guarantee it works. 7210 *
6794 * 7211 * The library is free for all purposes without any express
6795 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7212 * guarantee it works.
6796 */ 7213 *
6797 #include <tommath.h> 7214 * Tom St Denis, [email protected], http://math.libtomcrypt.org
6798 7215 */
6799 /* multiplication using the Toom-Cook 3-way algorithm */ 7216
7217 /* multiplication using the Toom-Cook 3-way algorithm
7218 *
7219 * Much more complicated than Karatsuba but has a lower asymptotic running time of
7220 * O(N**1.464). This algorithm is only particularly useful on VERY large
7221 * inputs (we're talking 1000s of digits here...).
7222 */
6800 int mp_toom_mul(mp_int *a, mp_int *b, mp_int *c) 7223 int mp_toom_mul(mp_int *a, mp_int *b, mp_int *c)
6801 { 7224 {
6802 mp_int w0, w1, w2, w3, w4, tmp1, tmp2, a0, a1, a2, b0, b1, b2; 7225 mp_int w0, w1, w2, w3, w4, tmp1, tmp2, a0, a1, a2, b0, b1, b2;
6803 int res, B; 7226 int res, B;
6804 7227
7050 &a0, &a1, &a2, &b0, &b1, 7473 &a0, &a1, &a2, &b0, &b1,
7051 &b2, &tmp1, &tmp2, NULL); 7474 &b2, &tmp1, &tmp2, NULL);
7052 return res; 7475 return res;
7053 } 7476 }
7054 7477
7478 #endif
7055 7479
7056 /* End: bn_mp_toom_mul.c */ 7480 /* End: bn_mp_toom_mul.c */
7057 7481
7058 /* Start: bn_mp_toom_sqr.c */ 7482 /* Start: bn_mp_toom_sqr.c */
7059 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7483 #include <tommath.h>
7060 * 7484 #ifdef BN_MP_TOOM_SQR_C
7061 * LibTomMath is a library that provides multiple-precision 7485 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7062 * integer arithmetic as well as number theoretic functionality. 7486 *
7063 * 7487 * LibTomMath is a library that provides multiple-precision
7064 * The library was designed directly after the MPI library by 7488 * integer arithmetic as well as number theoretic functionality.
7065 * Michael Fromberger but has been written from scratch with 7489 *
7066 * additional optimizations in place. 7490 * The library was designed directly after the MPI library by
7067 * 7491 * Michael Fromberger but has been written from scratch with
7068 * The library is free for all purposes without any express 7492 * additional optimizations in place.
7069 * guarantee it works. 7493 *
7070 * 7494 * The library is free for all purposes without any express
7071 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7495 * guarantee it works.
7072 */ 7496 *
7073 #include <tommath.h> 7497 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7498 */
7074 7499
7075 /* squaring using Toom-Cook 3-way algorithm */ 7500 /* squaring using Toom-Cook 3-way algorithm */
7076 int 7501 int
7077 mp_toom_sqr(mp_int *a, mp_int *b) 7502 mp_toom_sqr(mp_int *a, mp_int *b)
7078 { 7503 {
7274 ERR: 7699 ERR:
7275 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL); 7700 mp_clear_multi(&w0, &w1, &w2, &w3, &w4, &a0, &a1, &a2, &tmp1, NULL);
7276 return res; 7701 return res;
7277 } 7702 }
7278 7703
7704 #endif
7279 7705
7280 /* End: bn_mp_toom_sqr.c */ 7706 /* End: bn_mp_toom_sqr.c */
7281 7707
7282 /* Start: bn_mp_toradix.c */ 7708 /* Start: bn_mp_toradix.c */
7283 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7709 #include <tommath.h>
7284 * 7710 #ifdef BN_MP_TORADIX_C
7285 * LibTomMath is a library that provides multiple-precision 7711 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7286 * integer arithmetic as well as number theoretic functionality. 7712 *
7287 * 7713 * LibTomMath is a library that provides multiple-precision
7288 * The library was designed directly after the MPI library by 7714 * integer arithmetic as well as number theoretic functionality.
7289 * Michael Fromberger but has been written from scratch with 7715 *
7290 * additional optimizations in place. 7716 * The library was designed directly after the MPI library by
7291 * 7717 * Michael Fromberger but has been written from scratch with
7292 * The library is free for all purposes without any express 7718 * additional optimizations in place.
7293 * guarantee it works. 7719 *
7294 * 7720 * The library is free for all purposes without any express
7295 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7721 * guarantee it works.
7296 */ 7722 *
7297 #include <tommath.h> 7723 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7724 */
7298 7725
7299 /* stores a bignum as a ASCII string in a given radix (2..64) */ 7726 /* stores a bignum as a ASCII string in a given radix (2..64) */
7300 int mp_toradix (mp_int * a, char *str, int radix) 7727 int mp_toradix (mp_int * a, char *str, int radix)
7301 { 7728 {
7302 int res, digs; 7729 int res, digs;
7347 7774
7348 mp_clear (&t); 7775 mp_clear (&t);
7349 return MP_OKAY; 7776 return MP_OKAY;
7350 } 7777 }
7351 7778
7779 #endif
7352 7780
7353 /* End: bn_mp_toradix.c */ 7781 /* End: bn_mp_toradix.c */
7354 7782
7355 /* Start: bn_mp_toradix_n.c */ 7783 /* Start: bn_mp_toradix_n.c */
7356 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7784 #include <tommath.h>
7357 * 7785 #ifdef BN_MP_TORADIX_N_C
7358 * LibTomMath is a library that provides multiple-precision 7786 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7359 * integer arithmetic as well as number theoretic functionality. 7787 *
7360 * 7788 * LibTomMath is a library that provides multiple-precision
7361 * The library was designed directly after the MPI library by 7789 * integer arithmetic as well as number theoretic functionality.
7362 * Michael Fromberger but has been written from scratch with 7790 *
7363 * additional optimizations in place. 7791 * The library was designed directly after the MPI library by
7364 * 7792 * Michael Fromberger but has been written from scratch with
7365 * The library is free for all purposes without any express 7793 * additional optimizations in place.
7366 * guarantee it works. 7794 *
7367 * 7795 * The library is free for all purposes without any express
7368 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7796 * guarantee it works.
7369 */ 7797 *
7370 #include <tommath.h> 7798 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7799 */
7371 7800
7372 /* stores a bignum as a ASCII string in a given radix (2..64) 7801 /* stores a bignum as a ASCII string in a given radix (2..64)
7373 * 7802 *
7374 * Stores upto maxlen-1 chars and always a NULL byte 7803 * Stores upto maxlen-1 chars and always a NULL byte
7375 */ 7804 */
7434 7863
7435 mp_clear (&t); 7864 mp_clear (&t);
7436 return MP_OKAY; 7865 return MP_OKAY;
7437 } 7866 }
7438 7867
7868 #endif
7439 7869
7440 /* End: bn_mp_toradix_n.c */ 7870 /* End: bn_mp_toradix_n.c */
7441 7871
7442 /* Start: bn_mp_unsigned_bin_size.c */ 7872 /* Start: bn_mp_unsigned_bin_size.c */
7443 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7873 #include <tommath.h>
7444 * 7874 #ifdef BN_MP_UNSIGNED_BIN_SIZE_C
7445 * LibTomMath is a library that provides multiple-precision 7875 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7446 * integer arithmetic as well as number theoretic functionality. 7876 *
7447 * 7877 * LibTomMath is a library that provides multiple-precision
7448 * The library was designed directly after the MPI library by 7878 * integer arithmetic as well as number theoretic functionality.
7449 * Michael Fromberger but has been written from scratch with 7879 *
7450 * additional optimizations in place. 7880 * The library was designed directly after the MPI library by
7451 * 7881 * Michael Fromberger but has been written from scratch with
7452 * The library is free for all purposes without any express 7882 * additional optimizations in place.
7453 * guarantee it works. 7883 *
7454 * 7884 * The library is free for all purposes without any express
7455 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7885 * guarantee it works.
7456 */ 7886 *
7457 #include <tommath.h> 7887 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7888 */
7458 7889
7459 /* get the size for an unsigned equivalent */ 7890 /* get the size for an unsigned equivalent */
7460 int 7891 int
7461 mp_unsigned_bin_size (mp_int * a) 7892 mp_unsigned_bin_size (mp_int * a)
7462 { 7893 {
7463 int size = mp_count_bits (a); 7894 int size = mp_count_bits (a);
7464 return (size / 8 + ((size & 7) != 0 ? 1 : 0)); 7895 return (size / 8 + ((size & 7) != 0 ? 1 : 0));
7465 } 7896 }
7897 #endif
7466 7898
7467 /* End: bn_mp_unsigned_bin_size.c */ 7899 /* End: bn_mp_unsigned_bin_size.c */
7468 7900
7469 /* Start: bn_mp_xor.c */ 7901 /* Start: bn_mp_xor.c */
7470 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7902 #include <tommath.h>
7471 * 7903 #ifdef BN_MP_XOR_C
7472 * LibTomMath is a library that provides multiple-precision 7904 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7473 * integer arithmetic as well as number theoretic functionality. 7905 *
7474 * 7906 * LibTomMath is a library that provides multiple-precision
7475 * The library was designed directly after the MPI library by 7907 * integer arithmetic as well as number theoretic functionality.
7476 * Michael Fromberger but has been written from scratch with 7908 *
7477 * additional optimizations in place. 7909 * The library was designed directly after the MPI library by
7478 * 7910 * Michael Fromberger but has been written from scratch with
7479 * The library is free for all purposes without any express 7911 * additional optimizations in place.
7480 * guarantee it works. 7912 *
7481 * 7913 * The library is free for all purposes without any express
7482 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7914 * guarantee it works.
7483 */ 7915 *
7484 #include <tommath.h> 7916 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7917 */
7485 7918
7486 /* XOR two ints together */ 7919 /* XOR two ints together */
7487 int 7920 int
7488 mp_xor (mp_int * a, mp_int * b, mp_int * c) 7921 mp_xor (mp_int * a, mp_int * b, mp_int * c)
7489 { 7922 {
7503 px = a->used; 7936 px = a->used;
7504 x = a; 7937 x = a;
7505 } 7938 }
7506 7939
7507 for (ix = 0; ix < px; ix++) { 7940 for (ix = 0; ix < px; ix++) {
7508 t.dp[ix] ^= x->dp[ix]; 7941
7509 } 7942 }
7510 mp_clamp (&t); 7943 mp_clamp (&t);
7511 mp_exch (c, &t); 7944 mp_exch (c, &t);
7512 mp_clear (&t); 7945 mp_clear (&t);
7513 return MP_OKAY; 7946 return MP_OKAY;
7514 } 7947 }
7948 #endif
7515 7949
7516 /* End: bn_mp_xor.c */ 7950 /* End: bn_mp_xor.c */
7517 7951
7518 /* Start: bn_mp_zero.c */ 7952 /* Start: bn_mp_zero.c */
7519 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7953 #include <tommath.h>
7520 * 7954 #ifdef BN_MP_ZERO_C
7521 * LibTomMath is a library that provides multiple-precision 7955 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7522 * integer arithmetic as well as number theoretic functionality. 7956 *
7523 * 7957 * LibTomMath is a library that provides multiple-precision
7524 * The library was designed directly after the MPI library by 7958 * integer arithmetic as well as number theoretic functionality.
7525 * Michael Fromberger but has been written from scratch with 7959 *
7526 * additional optimizations in place. 7960 * The library was designed directly after the MPI library by
7527 * 7961 * Michael Fromberger but has been written from scratch with
7528 * The library is free for all purposes without any express 7962 * additional optimizations in place.
7529 * guarantee it works. 7963 *
7530 * 7964 * The library is free for all purposes without any express
7531 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7965 * guarantee it works.
7532 */ 7966 *
7533 #include <tommath.h> 7967 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7968 */
7534 7969
7535 /* set to zero */ 7970 /* set to zero */
7536 void 7971 void
7537 mp_zero (mp_int * a) 7972 mp_zero (mp_int * a)
7538 { 7973 {
7539 a->sign = MP_ZPOS; 7974 a->sign = MP_ZPOS;
7540 a->used = 0; 7975 a->used = 0;
7541 memset (a->dp, 0, sizeof (mp_digit) * a->alloc); 7976 memset (a->dp, 0, sizeof (mp_digit) * a->alloc);
7542 } 7977 }
7978 #endif
7543 7979
7544 /* End: bn_mp_zero.c */ 7980 /* End: bn_mp_zero.c */
7545 7981
7546 /* Start: bn_prime_sizes_tab.c */
7547 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7548 *
7549 * LibTomMath is a library that provides multiple-precision
7550 * integer arithmetic as well as number theoretic functionality.
7551 *
7552 * The library was designed directly after the MPI library by
7553 * Michael Fromberger but has been written from scratch with
7554 * additional optimizations in place.
7555 *
7556 * The library is free for all purposes without any express
7557 * guarantee it works.
7558 *
7559 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7560 */
7561 #include <tommath.h>
7562
7563 /* this table gives the # of rabin miller trials for a prob of failure lower than 2^-96 */
7564 static const struct {
7565 int k, t;
7566 } sizes[] = {
7567 { 128, 28 },
7568 { 256, 16 },
7569 { 384, 10 },
7570 { 512, 7 },
7571 { 640, 6 },
7572 { 768, 5 },
7573 { 896, 4 },
7574 { 1024, 4 },
7575 { 1152, 3 },
7576 { 1280, 3 },
7577 { 1408, 3 },
7578 { 1536, 3 },
7579 { 1664, 3 },
7580 { 1792, 2 } };
7581
7582 /* returns # of RM trials required for a given bit size */
7583 int mp_prime_rabin_miller_trials(int size)
7584 {
7585 int x;
7586
7587 for (x = 0; x < (int)(sizeof(sizes)/(sizeof(sizes[0]))); x++) {
7588 if (sizes[x].k == size) {
7589 return sizes[x].t;
7590 } else if (sizes[x].k > size) {
7591 return (x == 0) ? sizes[0].t : sizes[x - 1].t;
7592 }
7593 }
7594 return 1;
7595 }
7596
7597
7598
7599 /* End: bn_prime_sizes_tab.c */
7600
7601 /* Start: bn_prime_tab.c */ 7982 /* Start: bn_prime_tab.c */
7602 /* LibTomMath, multiple-precision integer library -- Tom St Denis 7983 #include <tommath.h>
7603 * 7984 #ifdef BN_PRIME_TAB_C
7604 * LibTomMath is a library that provides multiple-precision 7985 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7605 * integer arithmetic as well as number theoretic functionality. 7986 *
7606 * 7987 * LibTomMath is a library that provides multiple-precision
7607 * The library was designed directly after the MPI library by 7988 * integer arithmetic as well as number theoretic functionality.
7608 * Michael Fromberger but has been written from scratch with 7989 *
7609 * additional optimizations in place. 7990 * The library was designed directly after the MPI library by
7610 * 7991 * Michael Fromberger but has been written from scratch with
7611 * The library is free for all purposes without any express 7992 * additional optimizations in place.
7612 * guarantee it works. 7993 *
7613 * 7994 * The library is free for all purposes without any express
7614 * Tom St Denis, [email protected], http://math.libtomcrypt.org 7995 * guarantee it works.
7615 */ 7996 *
7616 #include <tommath.h> 7997 * Tom St Denis, [email protected], http://math.libtomcrypt.org
7998 */
7617 const mp_digit __prime_tab[] = { 7999 const mp_digit __prime_tab[] = {
7618 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013, 8000 0x0002, 0x0003, 0x0005, 0x0007, 0x000B, 0x000D, 0x0011, 0x0013,
7619 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035, 8001 0x0017, 0x001D, 0x001F, 0x0025, 0x0029, 0x002B, 0x002F, 0x0035,
7620 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059, 8002 0x003B, 0x003D, 0x0043, 0x0047, 0x0049, 0x004F, 0x0053, 0x0059,
7621 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F, 8003 0x0061, 0x0065, 0x0067, 0x006B, 0x006D, 0x0071, 0x007F,
7652 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7, 8034 0x05BF, 0x05C9, 0x05CB, 0x05CF, 0x05D1, 0x05D5, 0x05DB, 0x05E7,
7653 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623, 8035 0x05F3, 0x05FB, 0x0607, 0x060D, 0x0611, 0x0617, 0x061F, 0x0623,
7654 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653 8036 0x062B, 0x062F, 0x063D, 0x0641, 0x0647, 0x0649, 0x064D, 0x0653
7655 #endif 8037 #endif
7656 }; 8038 };
8039 #endif
7657 8040
7658 /* End: bn_prime_tab.c */ 8041 /* End: bn_prime_tab.c */
7659 8042
7660 /* Start: bn_reverse.c */ 8043 /* Start: bn_reverse.c */
7661 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8044 #include <tommath.h>
7662 * 8045 #ifdef BN_REVERSE_C
7663 * LibTomMath is a library that provides multiple-precision 8046 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7664 * integer arithmetic as well as number theoretic functionality. 8047 *
7665 * 8048 * LibTomMath is a library that provides multiple-precision
7666 * The library was designed directly after the MPI library by 8049 * integer arithmetic as well as number theoretic functionality.
7667 * Michael Fromberger but has been written from scratch with 8050 *
7668 * additional optimizations in place. 8051 * The library was designed directly after the MPI library by
7669 * 8052 * Michael Fromberger but has been written from scratch with
7670 * The library is free for all purposes without any express 8053 * additional optimizations in place.
7671 * guarantee it works. 8054 *
7672 * 8055 * The library is free for all purposes without any express
7673 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8056 * guarantee it works.
7674 */ 8057 *
7675 #include <tommath.h> 8058 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8059 */
7676 8060
7677 /* reverse an array, used for radix code */ 8061 /* reverse an array, used for radix code */
7678 void 8062 void
7679 bn_reverse (unsigned char *s, int len) 8063 bn_reverse (unsigned char *s, int len)
7680 { 8064 {
7689 s[iy] = t; 8073 s[iy] = t;
7690 ++ix; 8074 ++ix;
7691 --iy; 8075 --iy;
7692 } 8076 }
7693 } 8077 }
8078 #endif
7694 8079
7695 /* End: bn_reverse.c */ 8080 /* End: bn_reverse.c */
7696 8081
7697 /* Start: bn_s_mp_add.c */ 8082 /* Start: bn_s_mp_add.c */
7698 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8083 #include <tommath.h>
7699 * 8084 #ifdef BN_S_MP_ADD_C
7700 * LibTomMath is a library that provides multiple-precision 8085 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7701 * integer arithmetic as well as number theoretic functionality. 8086 *
7702 * 8087 * LibTomMath is a library that provides multiple-precision
7703 * The library was designed directly after the MPI library by 8088 * integer arithmetic as well as number theoretic functionality.
7704 * Michael Fromberger but has been written from scratch with 8089 *
7705 * additional optimizations in place. 8090 * The library was designed directly after the MPI library by
7706 * 8091 * Michael Fromberger but has been written from scratch with
7707 * The library is free for all purposes without any express 8092 * additional optimizations in place.
7708 * guarantee it works. 8093 *
7709 * 8094 * The library is free for all purposes without any express
7710 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8095 * guarantee it works.
7711 */ 8096 *
7712 #include <tommath.h> 8097 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8098 */
7713 8099
7714 /* low level addition, based on HAC pp.594, Algorithm 14.7 */ 8100 /* low level addition, based on HAC pp.594, Algorithm 14.7 */
7715 int 8101 int
7716 s_mp_add (mp_int * a, mp_int * b, mp_int * c) 8102 s_mp_add (mp_int * a, mp_int * b, mp_int * c)
7717 { 8103 {
7796 } 8182 }
7797 8183
7798 mp_clamp (c); 8184 mp_clamp (c);
7799 return MP_OKAY; 8185 return MP_OKAY;
7800 } 8186 }
8187 #endif
7801 8188
7802 /* End: bn_s_mp_add.c */ 8189 /* End: bn_s_mp_add.c */
7803 8190
7804 /* Start: bn_s_mp_exptmod.c */ 8191 /* Start: bn_s_mp_exptmod.c */
7805 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8192 #include <tommath.h>
7806 * 8193 #ifdef BN_S_MP_EXPTMOD_C
7807 * LibTomMath is a library that provides multiple-precision 8194 /* LibTomMath, multiple-precision integer library -- Tom St Denis
7808 * integer arithmetic as well as number theoretic functionality. 8195 *
7809 * 8196 * LibTomMath is a library that provides multiple-precision
7810 * The library was designed directly after the MPI library by 8197 * integer arithmetic as well as number theoretic functionality.
7811 * Michael Fromberger but has been written from scratch with 8198 *
7812 * additional optimizations in place. 8199 * The library was designed directly after the MPI library by
7813 * 8200 * Michael Fromberger but has been written from scratch with
7814 * The library is free for all purposes without any express 8201 * additional optimizations in place.
7815 * guarantee it works. 8202 *
7816 * 8203 * The library is free for all purposes without any express
7817 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8204 * guarantee it works.
7818 */ 8205 *
7819 #include <tommath.h> 8206 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8207 */
7820 8208
7821 #ifdef MP_LOW_MEM 8209 #ifdef MP_LOW_MEM
7822 #define TAB_SIZE 32 8210 #define TAB_SIZE 32
7823 #else 8211 #else
7824 #define TAB_SIZE 256 8212 #define TAB_SIZE 256
8034 for (x = 1<<(winsize-1); x < (1 << winsize); x++) { 8422 for (x = 1<<(winsize-1); x < (1 << winsize); x++) {
8035 mp_clear (&M[x]); 8423 mp_clear (&M[x]);
8036 } 8424 }
8037 return err; 8425 return err;
8038 } 8426 }
8427 #endif
8039 8428
8040 /* End: bn_s_mp_exptmod.c */ 8429 /* End: bn_s_mp_exptmod.c */
8041 8430
8042 /* Start: bn_s_mp_mul_digs.c */ 8431 /* Start: bn_s_mp_mul_digs.c */
8043 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8432 #include <tommath.h>
8044 * 8433 #ifdef BN_S_MP_MUL_DIGS_C
8045 * LibTomMath is a library that provides multiple-precision 8434 /* LibTomMath, multiple-precision integer library -- Tom St Denis
8046 * integer arithmetic as well as number theoretic functionality. 8435 *
8047 * 8436 * LibTomMath is a library that provides multiple-precision
8048 * The library was designed directly after the MPI library by 8437 * integer arithmetic as well as number theoretic functionality.
8049 * Michael Fromberger but has been written from scratch with 8438 *
8050 * additional optimizations in place. 8439 * The library was designed directly after the MPI library by
8051 * 8440 * Michael Fromberger but has been written from scratch with
8052 * The library is free for all purposes without any express 8441 * additional optimizations in place.
8053 * guarantee it works. 8442 *
8054 * 8443 * The library is free for all purposes without any express
8055 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8444 * guarantee it works.
8056 */ 8445 *
8057 #include <tommath.h> 8446 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8447 */
8058 8448
8059 /* multiplies |a| * |b| and only computes upto digs digits of result 8449 /* multiplies |a| * |b| and only computes upto digs digits of result
8060 * HAC pp. 595, Algorithm 14.12 Modified so you can control how 8450 * HAC pp. 595, Algorithm 14.12 Modified so you can control how
8061 * many digits of output are created. 8451 * many digits of output are created.
8062 */ 8452 */
8123 mp_exch (&t, c); 8513 mp_exch (&t, c);
8124 8514
8125 mp_clear (&t); 8515 mp_clear (&t);
8126 return MP_OKAY; 8516 return MP_OKAY;
8127 } 8517 }
8518 #endif
8128 8519
8129 /* End: bn_s_mp_mul_digs.c */ 8520 /* End: bn_s_mp_mul_digs.c */
8130 8521
8131 /* Start: bn_s_mp_mul_high_digs.c */ 8522 /* Start: bn_s_mp_mul_high_digs.c */
8132 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8523 #include <tommath.h>
8133 * 8524 #ifdef BN_S_MP_MUL_HIGH_DIGS_C
8134 * LibTomMath is a library that provides multiple-precision 8525 /* LibTomMath, multiple-precision integer library -- Tom St Denis
8135 * integer arithmetic as well as number theoretic functionality. 8526 *
8136 * 8527 * LibTomMath is a library that provides multiple-precision
8137 * The library was designed directly after the MPI library by 8528 * integer arithmetic as well as number theoretic functionality.
8138 * Michael Fromberger but has been written from scratch with 8529 *
8139 * additional optimizations in place. 8530 * The library was designed directly after the MPI library by
8140 * 8531 * Michael Fromberger but has been written from scratch with
8141 * The library is free for all purposes without any express 8532 * additional optimizations in place.
8142 * guarantee it works. 8533 *
8143 * 8534 * The library is free for all purposes without any express
8144 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8535 * guarantee it works.
8145 */ 8536 *
8146 #include <tommath.h> 8537 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8538 */
8147 8539
8148 /* multiplies |a| * |b| and does not compute the lower digs digits 8540 /* multiplies |a| * |b| and does not compute the lower digs digits
8149 * [meant to get the higher part of the product] 8541 * [meant to get the higher part of the product]
8150 */ 8542 */
8151 int 8543 int
8156 mp_digit u; 8548 mp_digit u;
8157 mp_word r; 8549 mp_word r;
8158 mp_digit tmpx, *tmpt, *tmpy; 8550 mp_digit tmpx, *tmpt, *tmpy;
8159 8551
8160 /* can we use the fast multiplier? */ 8552 /* can we use the fast multiplier? */
8553 #ifdef BN_FAST_S_MP_MUL_HIGH_DIGS_C
8161 if (((a->used + b->used + 1) < MP_WARRAY) 8554 if (((a->used + b->used + 1) < MP_WARRAY)
8162 && MIN (a->used, b->used) < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) { 8555 && MIN (a->used, b->used) < (1 << ((CHAR_BIT * sizeof (mp_word)) - (2 * DIGIT_BIT)))) {
8163 return fast_s_mp_mul_high_digs (a, b, c, digs); 8556 return fast_s_mp_mul_high_digs (a, b, c, digs);
8164 } 8557 }
8558 #endif
8165 8559
8166 if ((res = mp_init_size (&t, a->used + b->used + 1)) != MP_OKAY) { 8560 if ((res = mp_init_size (&t, a->used + b->used + 1)) != MP_OKAY) {
8167 return res; 8561 return res;
8168 } 8562 }
8169 t.used = a->used + b->used + 1; 8563 t.used = a->used + b->used + 1;
8200 mp_clamp (&t); 8594 mp_clamp (&t);
8201 mp_exch (&t, c); 8595 mp_exch (&t, c);
8202 mp_clear (&t); 8596 mp_clear (&t);
8203 return MP_OKAY; 8597 return MP_OKAY;
8204 } 8598 }
8599 #endif
8205 8600
8206 /* End: bn_s_mp_mul_high_digs.c */ 8601 /* End: bn_s_mp_mul_high_digs.c */
8207 8602
8208 /* Start: bn_s_mp_sqr.c */ 8603 /* Start: bn_s_mp_sqr.c */
8209 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8604 #include <tommath.h>
8210 * 8605 #ifdef BN_S_MP_SQR_C
8211 * LibTomMath is a library that provides multiple-precision 8606 /* LibTomMath, multiple-precision integer library -- Tom St Denis
8212 * integer arithmetic as well as number theoretic functionality. 8607 *
8213 * 8608 * LibTomMath is a library that provides multiple-precision
8214 * The library was designed directly after the MPI library by 8609 * integer arithmetic as well as number theoretic functionality.
8215 * Michael Fromberger but has been written from scratch with 8610 *
8216 * additional optimizations in place. 8611 * The library was designed directly after the MPI library by
8217 * 8612 * Michael Fromberger but has been written from scratch with
8218 * The library is free for all purposes without any express 8613 * additional optimizations in place.
8219 * guarantee it works. 8614 *
8220 * 8615 * The library is free for all purposes without any express
8221 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8616 * guarantee it works.
8222 */ 8617 *
8223 #include <tommath.h> 8618 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8619 */
8224 8620
8225 /* low level squaring, b = a*a, HAC pp.596-597, Algorithm 14.16 */ 8621 /* low level squaring, b = a*a, HAC pp.596-597, Algorithm 14.16 */
8226 int 8622 int
8227 s_mp_sqr (mp_int * a, mp_int * b) 8623 s_mp_sqr (mp_int * a, mp_int * b)
8228 { 8624 {
8283 mp_clamp (&t); 8679 mp_clamp (&t);
8284 mp_exch (&t, b); 8680 mp_exch (&t, b);
8285 mp_clear (&t); 8681 mp_clear (&t);
8286 return MP_OKAY; 8682 return MP_OKAY;
8287 } 8683 }
8684 #endif
8288 8685
8289 /* End: bn_s_mp_sqr.c */ 8686 /* End: bn_s_mp_sqr.c */
8290 8687
8291 /* Start: bn_s_mp_sub.c */ 8688 /* Start: bn_s_mp_sub.c */
8292 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8689 #include <tommath.h>
8293 * 8690 #ifdef BN_S_MP_SUB_C
8294 * LibTomMath is a library that provides multiple-precision 8691 /* LibTomMath, multiple-precision integer library -- Tom St Denis
8295 * integer arithmetic as well as number theoretic functionality. 8692 *
8296 * 8693 * LibTomMath is a library that provides multiple-precision
8297 * The library was designed directly after the MPI library by 8694 * integer arithmetic as well as number theoretic functionality.
8298 * Michael Fromberger but has been written from scratch with 8695 *
8299 * additional optimizations in place. 8696 * The library was designed directly after the MPI library by
8300 * 8697 * Michael Fromberger but has been written from scratch with
8301 * The library is free for all purposes without any express 8698 * additional optimizations in place.
8302 * guarantee it works. 8699 *
8303 * 8700 * The library is free for all purposes without any express
8304 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8701 * guarantee it works.
8305 */ 8702 *
8306 #include <tommath.h> 8703 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8704 */
8307 8705
8308 /* low level subtraction (assumes |a| > |b|), HAC pp.595 Algorithm 14.9 */ 8706 /* low level subtraction (assumes |a| > |b|), HAC pp.595 Algorithm 14.9 */
8309 int 8707 int
8310 s_mp_sub (mp_int * a, mp_int * b, mp_int * c) 8708 s_mp_sub (mp_int * a, mp_int * b, mp_int * c)
8311 { 8709 {
8370 8768
8371 mp_clamp (c); 8769 mp_clamp (c);
8372 return MP_OKAY; 8770 return MP_OKAY;
8373 } 8771 }
8374 8772
8773 #endif
8375 8774
8376 /* End: bn_s_mp_sub.c */ 8775 /* End: bn_s_mp_sub.c */
8377 8776
8378 /* Start: bncore.c */ 8777 /* Start: bncore.c */
8379 /* LibTomMath, multiple-precision integer library -- Tom St Denis 8778 #include <tommath.h>
8380 * 8779 #ifdef BNCORE_C
8381 * LibTomMath is a library that provides multiple-precision 8780 /* LibTomMath, multiple-precision integer library -- Tom St Denis
8382 * integer arithmetic as well as number theoretic functionality. 8781 *
8383 * 8782 * LibTomMath is a library that provides multiple-precision
8384 * The library was designed directly after the MPI library by 8783 * integer arithmetic as well as number theoretic functionality.
8385 * Michael Fromberger but has been written from scratch with 8784 *
8386 * additional optimizations in place. 8785 * The library was designed directly after the MPI library by
8387 * 8786 * Michael Fromberger but has been written from scratch with
8388 * The library is free for all purposes without any express 8787 * additional optimizations in place.
8389 * guarantee it works. 8788 *
8390 * 8789 * The library is free for all purposes without any express
8391 * Tom St Denis, [email protected], http://math.libtomcrypt.org 8790 * guarantee it works.
8392 */ 8791 *
8393 #include <tommath.h> 8792 * Tom St Denis, [email protected], http://math.libtomcrypt.org
8793 */
8394 8794
8395 /* Known optimal configurations 8795 /* Known optimal configurations
8396 8796
8397 CPU /Compiler /MUL CUTOFF/SQR CUTOFF 8797 CPU /Compiler /MUL CUTOFF/SQR CUTOFF
8398 ------------------------------------------------------------- 8798 -------------------------------------------------------------
8399 Intel P4 /GCC v3.2 / 70/ 108 8799 Intel P4 Northwood /GCC v3.4.1 / 88/ 128/LTM 0.32 ;-)
8400 AMD Athlon XP /GCC v3.2 / 109/ 127 8800
8401
8402 */ 8801 */
8403 8802
8404 /* configured for a AMD XP Thoroughbred core with etc/tune.c */ 8803 int KARATSUBA_MUL_CUTOFF = 88, /* Min. number of digits before Karatsuba multiplication is used. */
8405 int KARATSUBA_MUL_CUTOFF = 109, /* Min. number of digits before Karatsuba multiplication is used. */ 8804 KARATSUBA_SQR_CUTOFF = 128, /* Min. number of digits before Karatsuba squaring is used. */
8406 KARATSUBA_SQR_CUTOFF = 127, /* Min. number of digits before Karatsuba squaring is used. */
8407 8805
8408 TOOM_MUL_CUTOFF = 350, /* no optimal values of these are known yet so set em high */ 8806 TOOM_MUL_CUTOFF = 350, /* no optimal values of these are known yet so set em high */
8409 TOOM_SQR_CUTOFF = 400; 8807 TOOM_SQR_CUTOFF = 400;
8808 #endif
8410 8809
8411 /* End: bncore.c */ 8810 /* End: bncore.c */
8412 8811
8413 8812
8414 /* EOF */ 8813 /* EOF */