-
+ BD7B8BD954F2DDD627A55179B48C589DEE37155BA3A2984C0E7AD6CC32C1C4A53DD0E9BE5BD9A1EC1B6EE9C04E98DD40ADFB2FEC78BD2F24FF4E6EC6F723CB55smg_comms/mpi/mpi-inv.c(0 . 0)(1 . 270)
4453 /* mpi-inv.c - MPI functions
4454 * Modified by No Such Labs. (C) 2015. See README.
4455 *
4456 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
4457 * SHA256(gnupg-1.4.10.tar.gz):
4458 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
4459 * (C) 1994-2005 Free Software Foundation, Inc.
4460 *
4461 * This program is free software: you can redistribute it and/or modify
4462 * it under the terms of the GNU General Public License as published by
4463 * the Free Software Foundation, either version 3 of the License, or
4464 * (at your option) any later version.
4465 *
4466 * This program is distributed in the hope that it will be useful,
4467 * but WITHOUT ANY WARRANTY; without even the implied warranty of
4468 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4469 * GNU General Public License for more details.
4470 *
4471 * You should have received a copy of the GNU General Public License
4472 * along with this program. If not, see <http://www.gnu.org/licenses/>.
4473 */
4474
4475 #include <stdio.h>
4476 #include <stdlib.h>
4477
4478 #include "knobs.h"
4479 #include "mpi-internal.h"
4480
4481
4482 /****************
4483 * Calculate the multiplicative inverse X of A mod N
4484 * That is: Find the solution x for
4485 * 1 = (a*x) mod n
4486 */
4487 void
4488 mpi_invm( MPI x, MPI a, MPI n )
4489 {
4490 #if 0
4491 MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
4492 MPI ta, tb, tc;
4493
4494 u = mpi_copy(a);
4495 v = mpi_copy(n);
4496 u1 = mpi_alloc_set_ui(1);
4497 u2 = mpi_alloc_set_ui(0);
4498 u3 = mpi_copy(u);
4499 v1 = mpi_alloc_set_ui(0);
4500 v2 = mpi_alloc_set_ui(1);
4501 v3 = mpi_copy(v);
4502 q = mpi_alloc( mpi_get_nlimbs(u)+1 );
4503 t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
4504 t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
4505 t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
4506 while( mpi_cmp_ui( v3, 0 ) ) {
4507 mpi_fdiv_q( q, u3, v3 );
4508 mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
4509 mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
4510 mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
4511 mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
4512 }
4513 /* log_debug("result:\n");
4514 log_mpidump("q =", q );
4515 log_mpidump("u1=", u1);
4516 log_mpidump("u2=", u2);
4517 log_mpidump("u3=", u3);
4518 log_mpidump("v1=", v1);
4519 log_mpidump("v2=", v2); */
4520 mpi_set(x, u1);
4521
4522 mpi_free(u1);
4523 mpi_free(u2);
4524 mpi_free(u3);
4525 mpi_free(v1);
4526 mpi_free(v2);
4527 mpi_free(v3);
4528 mpi_free(q);
4529 mpi_free(t1);
4530 mpi_free(t2);
4531 mpi_free(t3);
4532 mpi_free(u);
4533 mpi_free(v);
4534 #elif 0
4535 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
4536 * modified according to Michael Penk's solution for Exercice 35 */
4537
4538 /* FIXME: we can simplify this in most cases (see Knuth) */
4539 MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
4540 unsigned k;
4541 int sign;
4542
4543 u = mpi_copy(a);
4544 v = mpi_copy(n);
4545 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
4546 mpi_rshift(u, u, 1);
4547 mpi_rshift(v, v, 1);
4548 }
4549
4550
4551 u1 = mpi_alloc_set_ui(1);
4552 u2 = mpi_alloc_set_ui(0);
4553 u3 = mpi_copy(u);
4554 v1 = mpi_copy(v); /* !-- used as const 1 */
4555 v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
4556 v3 = mpi_copy(v);
4557 if( mpi_test_bit(u, 0) ) { /* u is odd */
4558 t1 = mpi_alloc_set_ui(0);
4559 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
4560 t3 = mpi_copy(v); t3->sign = !t3->sign;
4561 goto Y4;
4562 }
4563 else {
4564 t1 = mpi_alloc_set_ui(1);
4565 t2 = mpi_alloc_set_ui(0);
4566 t3 = mpi_copy(u);
4567 }
4568 do {
4569 do {
4570 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
4571 mpi_add(t1, t1, v);
4572 mpi_sub(t2, t2, u);
4573 }
4574 mpi_rshift(t1, t1, 1);
4575 mpi_rshift(t2, t2, 1);
4576 mpi_rshift(t3, t3, 1);
4577 Y4:
4578 ;
4579 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
4580
4581 if( !t3->sign ) {
4582 mpi_set(u1, t1);
4583 mpi_set(u2, t2);
4584 mpi_set(u3, t3);
4585 }
4586 else {
4587 mpi_sub(v1, v, t1);
4588 sign = u->sign; u->sign = !u->sign;
4589 mpi_sub(v2, u, t2);
4590 u->sign = sign;
4591 sign = t3->sign; t3->sign = !t3->sign;
4592 mpi_set(v3, t3);
4593 t3->sign = sign;
4594 }
4595 mpi_sub(t1, u1, v1);
4596 mpi_sub(t2, u2, v2);
4597 mpi_sub(t3, u3, v3);
4598 if( t1->sign ) {
4599 mpi_add(t1, t1, v);
4600 mpi_sub(t2, t2, u);
4601 }
4602 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
4603 /* mpi_lshift( u3, k ); */
4604 mpi_set(x, u1);
4605
4606 mpi_free(u1);
4607 mpi_free(u2);
4608 mpi_free(u3);
4609 mpi_free(v1);
4610 mpi_free(v2);
4611 mpi_free(v3);
4612 mpi_free(t1);
4613 mpi_free(t2);
4614 mpi_free(t3);
4615 #else
4616 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
4617 * modified according to Michael Penk's solution for Exercice 35
4618 * with further enhancement */
4619 MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
4620 unsigned k;
4621 int sign;
4622 int odd ;
4623
4624 u = mpi_copy(a);
4625 v = mpi_copy(n);
4626
4627 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
4628 mpi_rshift(u, u, 1);
4629 mpi_rshift(v, v, 1);
4630 }
4631 odd = mpi_test_bit(v,0);
4632
4633 u1 = mpi_alloc_set_ui(1);
4634 if( !odd )
4635 u2 = mpi_alloc_set_ui(0);
4636 u3 = mpi_copy(u);
4637 v1 = mpi_copy(v);
4638 if( !odd ) {
4639 v2 = mpi_alloc( mpi_get_nlimbs(u) );
4640 mpi_sub( v2, u1, u ); /* U is used as const 1 */
4641 }
4642 v3 = mpi_copy(v);
4643 if( mpi_test_bit(u, 0) ) { /* u is odd */
4644 t1 = mpi_alloc_set_ui(0);
4645 if( !odd ) {
4646 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
4647 }
4648 t3 = mpi_copy(v); t3->sign = !t3->sign;
4649 goto Y4;
4650 }
4651 else {
4652 t1 = mpi_alloc_set_ui(1);
4653 if( !odd )
4654 t2 = mpi_alloc_set_ui(0);
4655 t3 = mpi_copy(u);
4656 }
4657 do {
4658 do {
4659 if( !odd ) {
4660 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
4661 mpi_add(t1, t1, v);
4662 mpi_sub(t2, t2, u);
4663 }
4664 mpi_rshift(t1, t1, 1);
4665 mpi_rshift(t2, t2, 1);
4666 mpi_rshift(t3, t3, 1);
4667 }
4668 else {
4669 if( mpi_test_bit(t1, 0) )
4670 mpi_add(t1, t1, v);
4671 mpi_rshift(t1, t1, 1);
4672 mpi_rshift(t3, t3, 1);
4673 }
4674 Y4:
4675 ;
4676 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
4677
4678 if( !t3->sign ) {
4679 mpi_set(u1, t1);
4680 if( !odd )
4681 mpi_set(u2, t2);
4682 mpi_set(u3, t3);
4683 }
4684 else {
4685 mpi_sub(v1, v, t1);
4686 sign = u->sign; u->sign = !u->sign;
4687 if( !odd )
4688 mpi_sub(v2, u, t2);
4689 u->sign = sign;
4690 sign = t3->sign; t3->sign = !t3->sign;
4691 mpi_set(v3, t3);
4692 t3->sign = sign;
4693 }
4694 mpi_sub(t1, u1, v1);
4695 if( !odd )
4696 mpi_sub(t2, u2, v2);
4697 mpi_sub(t3, u3, v3);
4698 if( t1->sign ) {
4699 mpi_add(t1, t1, v);
4700 if( !odd )
4701 mpi_sub(t2, t2, u);
4702 }
4703 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
4704 /* mpi_lshift( u3, k ); */
4705 mpi_set(x, u1);
4706
4707 mpi_free(u1);
4708 mpi_free(v1);
4709 mpi_free(t1);
4710 if( !odd ) {
4711 mpi_free(u2);
4712 mpi_free(v2);
4713 mpi_free(t2);
4714 }
4715 mpi_free(u3);
4716 mpi_free(v3);
4717 mpi_free(t3);
4718
4719 mpi_free(u);
4720 mpi_free(v);
4721 #endif
4722 }