-
+ BD7B8BD954F2DDD627A55179B48C589DEE37155BA3A2984C0E7AD6CC32C1C4A53DD0E9BE5BD9A1EC1B6EE9C04E98DD40ADFB2FEC78BD2F24FF4E6EC6F723CB55eucrypt/mpi/mpi-inv.c(0 . 0)(1 . 270)
3714 /* mpi-inv.c - MPI functions
3715 * Modified by No Such Labs. (C) 2015. See README.
3716 *
3717 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
3718 * SHA256(gnupg-1.4.10.tar.gz):
3719 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
3720 * (C) 1994-2005 Free Software Foundation, Inc.
3721 *
3722 * This program is free software: you can redistribute it and/or modify
3723 * it under the terms of the GNU General Public License as published by
3724 * the Free Software Foundation, either version 3 of the License, or
3725 * (at your option) any later version.
3726 *
3727 * This program is distributed in the hope that it will be useful,
3728 * but WITHOUT ANY WARRANTY; without even the implied warranty of
3729 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3730 * GNU General Public License for more details.
3731 *
3732 * You should have received a copy of the GNU General Public License
3733 * along with this program. If not, see <http://www.gnu.org/licenses/>.
3734 */
3735
3736 #include <stdio.h>
3737 #include <stdlib.h>
3738
3739 #include "knobs.h"
3740 #include "mpi-internal.h"
3741
3742
3743 /****************
3744 * Calculate the multiplicative inverse X of A mod N
3745 * That is: Find the solution x for
3746 * 1 = (a*x) mod n
3747 */
3748 void
3749 mpi_invm( MPI x, MPI a, MPI n )
3750 {
3751 #if 0
3752 MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
3753 MPI ta, tb, tc;
3754
3755 u = mpi_copy(a);
3756 v = mpi_copy(n);
3757 u1 = mpi_alloc_set_ui(1);
3758 u2 = mpi_alloc_set_ui(0);
3759 u3 = mpi_copy(u);
3760 v1 = mpi_alloc_set_ui(0);
3761 v2 = mpi_alloc_set_ui(1);
3762 v3 = mpi_copy(v);
3763 q = mpi_alloc( mpi_get_nlimbs(u)+1 );
3764 t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
3765 t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
3766 t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
3767 while( mpi_cmp_ui( v3, 0 ) ) {
3768 mpi_fdiv_q( q, u3, v3 );
3769 mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
3770 mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
3771 mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
3772 mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
3773 }
3774 /* log_debug("result:\n");
3775 log_mpidump("q =", q );
3776 log_mpidump("u1=", u1);
3777 log_mpidump("u2=", u2);
3778 log_mpidump("u3=", u3);
3779 log_mpidump("v1=", v1);
3780 log_mpidump("v2=", v2); */
3781 mpi_set(x, u1);
3782
3783 mpi_free(u1);
3784 mpi_free(u2);
3785 mpi_free(u3);
3786 mpi_free(v1);
3787 mpi_free(v2);
3788 mpi_free(v3);
3789 mpi_free(q);
3790 mpi_free(t1);
3791 mpi_free(t2);
3792 mpi_free(t3);
3793 mpi_free(u);
3794 mpi_free(v);
3795 #elif 0
3796 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
3797 * modified according to Michael Penk's solution for Exercice 35 */
3798
3799 /* FIXME: we can simplify this in most cases (see Knuth) */
3800 MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
3801 unsigned k;
3802 int sign;
3803
3804 u = mpi_copy(a);
3805 v = mpi_copy(n);
3806 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
3807 mpi_rshift(u, u, 1);
3808 mpi_rshift(v, v, 1);
3809 }
3810
3811
3812 u1 = mpi_alloc_set_ui(1);
3813 u2 = mpi_alloc_set_ui(0);
3814 u3 = mpi_copy(u);
3815 v1 = mpi_copy(v); /* !-- used as const 1 */
3816 v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
3817 v3 = mpi_copy(v);
3818 if( mpi_test_bit(u, 0) ) { /* u is odd */
3819 t1 = mpi_alloc_set_ui(0);
3820 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
3821 t3 = mpi_copy(v); t3->sign = !t3->sign;
3822 goto Y4;
3823 }
3824 else {
3825 t1 = mpi_alloc_set_ui(1);
3826 t2 = mpi_alloc_set_ui(0);
3827 t3 = mpi_copy(u);
3828 }
3829 do {
3830 do {
3831 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
3832 mpi_add(t1, t1, v);
3833 mpi_sub(t2, t2, u);
3834 }
3835 mpi_rshift(t1, t1, 1);
3836 mpi_rshift(t2, t2, 1);
3837 mpi_rshift(t3, t3, 1);
3838 Y4:
3839 ;
3840 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
3841
3842 if( !t3->sign ) {
3843 mpi_set(u1, t1);
3844 mpi_set(u2, t2);
3845 mpi_set(u3, t3);
3846 }
3847 else {
3848 mpi_sub(v1, v, t1);
3849 sign = u->sign; u->sign = !u->sign;
3850 mpi_sub(v2, u, t2);
3851 u->sign = sign;
3852 sign = t3->sign; t3->sign = !t3->sign;
3853 mpi_set(v3, t3);
3854 t3->sign = sign;
3855 }
3856 mpi_sub(t1, u1, v1);
3857 mpi_sub(t2, u2, v2);
3858 mpi_sub(t3, u3, v3);
3859 if( t1->sign ) {
3860 mpi_add(t1, t1, v);
3861 mpi_sub(t2, t2, u);
3862 }
3863 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
3864 /* mpi_lshift( u3, k ); */
3865 mpi_set(x, u1);
3866
3867 mpi_free(u1);
3868 mpi_free(u2);
3869 mpi_free(u3);
3870 mpi_free(v1);
3871 mpi_free(v2);
3872 mpi_free(v3);
3873 mpi_free(t1);
3874 mpi_free(t2);
3875 mpi_free(t3);
3876 #else
3877 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
3878 * modified according to Michael Penk's solution for Exercice 35
3879 * with further enhancement */
3880 MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
3881 unsigned k;
3882 int sign;
3883 int odd ;
3884
3885 u = mpi_copy(a);
3886 v = mpi_copy(n);
3887
3888 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
3889 mpi_rshift(u, u, 1);
3890 mpi_rshift(v, v, 1);
3891 }
3892 odd = mpi_test_bit(v,0);
3893
3894 u1 = mpi_alloc_set_ui(1);
3895 if( !odd )
3896 u2 = mpi_alloc_set_ui(0);
3897 u3 = mpi_copy(u);
3898 v1 = mpi_copy(v);
3899 if( !odd ) {
3900 v2 = mpi_alloc( mpi_get_nlimbs(u) );
3901 mpi_sub( v2, u1, u ); /* U is used as const 1 */
3902 }
3903 v3 = mpi_copy(v);
3904 if( mpi_test_bit(u, 0) ) { /* u is odd */
3905 t1 = mpi_alloc_set_ui(0);
3906 if( !odd ) {
3907 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
3908 }
3909 t3 = mpi_copy(v); t3->sign = !t3->sign;
3910 goto Y4;
3911 }
3912 else {
3913 t1 = mpi_alloc_set_ui(1);
3914 if( !odd )
3915 t2 = mpi_alloc_set_ui(0);
3916 t3 = mpi_copy(u);
3917 }
3918 do {
3919 do {
3920 if( !odd ) {
3921 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
3922 mpi_add(t1, t1, v);
3923 mpi_sub(t2, t2, u);
3924 }
3925 mpi_rshift(t1, t1, 1);
3926 mpi_rshift(t2, t2, 1);
3927 mpi_rshift(t3, t3, 1);
3928 }
3929 else {
3930 if( mpi_test_bit(t1, 0) )
3931 mpi_add(t1, t1, v);
3932 mpi_rshift(t1, t1, 1);
3933 mpi_rshift(t3, t3, 1);
3934 }
3935 Y4:
3936 ;
3937 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
3938
3939 if( !t3->sign ) {
3940 mpi_set(u1, t1);
3941 if( !odd )
3942 mpi_set(u2, t2);
3943 mpi_set(u3, t3);
3944 }
3945 else {
3946 mpi_sub(v1, v, t1);
3947 sign = u->sign; u->sign = !u->sign;
3948 if( !odd )
3949 mpi_sub(v2, u, t2);
3950 u->sign = sign;
3951 sign = t3->sign; t3->sign = !t3->sign;
3952 mpi_set(v3, t3);
3953 t3->sign = sign;
3954 }
3955 mpi_sub(t1, u1, v1);
3956 if( !odd )
3957 mpi_sub(t2, u2, v2);
3958 mpi_sub(t3, u3, v3);
3959 if( t1->sign ) {
3960 mpi_add(t1, t1, v);
3961 if( !odd )
3962 mpi_sub(t2, t2, u);
3963 }
3964 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
3965 /* mpi_lshift( u3, k ); */
3966 mpi_set(x, u1);
3967
3968 mpi_free(u1);
3969 mpi_free(v1);
3970 mpi_free(t1);
3971 if( !odd ) {
3972 mpi_free(u2);
3973 mpi_free(v2);
3974 mpi_free(t2);
3975 }
3976 mpi_free(u3);
3977 mpi_free(v3);
3978 mpi_free(t3);
3979
3980 mpi_free(u);
3981 mpi_free(v);
3982 #endif
3983 }