raw
smg_comms_c_wrappers    1 /* mpi-inv.c  -  MPI functions
smg_comms_c_wrappers    2  * Modified by No Such Labs. (C) 2015. See README.
smg_comms_c_wrappers    3  *
smg_comms_c_wrappers    4  * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
smg_comms_c_wrappers    5  * SHA256(gnupg-1.4.10.tar.gz):
smg_comms_c_wrappers    6  *        0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
smg_comms_c_wrappers    7  * (C) 1994-2005 Free Software Foundation, Inc.
smg_comms_c_wrappers    8  *
smg_comms_c_wrappers    9  * This program is free software: you can redistribute it and/or modify
smg_comms_c_wrappers   10  * it under the terms of the GNU General Public License as published by
smg_comms_c_wrappers   11  * the Free Software Foundation, either version 3 of the License, or
smg_comms_c_wrappers   12  * (at your option) any later version.
smg_comms_c_wrappers   13  *
smg_comms_c_wrappers   14  * This program is distributed in the hope that it will be useful,
smg_comms_c_wrappers   15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
smg_comms_c_wrappers   16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
smg_comms_c_wrappers   17  * GNU General Public License for more details.
smg_comms_c_wrappers   18  *
smg_comms_c_wrappers   19  * You should have received a copy of the GNU General Public License
smg_comms_c_wrappers   20  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
smg_comms_c_wrappers   21  */
smg_comms_c_wrappers   22 
smg_comms_c_wrappers   23 #include <stdio.h>
smg_comms_c_wrappers   24 #include <stdlib.h>
smg_comms_c_wrappers   25 
smg_comms_c_wrappers   26 #include "knobs.h"
smg_comms_c_wrappers   27 #include "mpi-internal.h"
smg_comms_c_wrappers   28 
smg_comms_c_wrappers   29 
smg_comms_c_wrappers   30 /****************
smg_comms_c_wrappers   31  * Calculate the multiplicative inverse X of A mod N
smg_comms_c_wrappers   32  * That is: Find the solution x for
smg_comms_c_wrappers   33  *		1 = (a*x) mod n
smg_comms_c_wrappers   34  */
smg_comms_c_wrappers   35 void
smg_comms_c_wrappers   36 mpi_invm( MPI x, MPI a, MPI n )
smg_comms_c_wrappers   37 {
smg_comms_c_wrappers   38 #if 0
smg_comms_c_wrappers   39     MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
smg_comms_c_wrappers   40     MPI ta, tb, tc;
smg_comms_c_wrappers   41 
smg_comms_c_wrappers   42     u = mpi_copy(a);
smg_comms_c_wrappers   43     v = mpi_copy(n);
smg_comms_c_wrappers   44     u1 = mpi_alloc_set_ui(1);
smg_comms_c_wrappers   45     u2 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers   46     u3 = mpi_copy(u);
smg_comms_c_wrappers   47     v1 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers   48     v2 = mpi_alloc_set_ui(1);
smg_comms_c_wrappers   49     v3 = mpi_copy(v);
smg_comms_c_wrappers   50     q  = mpi_alloc( mpi_get_nlimbs(u)+1 );
smg_comms_c_wrappers   51     t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
smg_comms_c_wrappers   52     t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
smg_comms_c_wrappers   53     t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
smg_comms_c_wrappers   54     while( mpi_cmp_ui( v3, 0 ) ) {
smg_comms_c_wrappers   55 	mpi_fdiv_q( q, u3, v3 );
smg_comms_c_wrappers   56 	mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
smg_comms_c_wrappers   57 	mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
smg_comms_c_wrappers   58 	mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
smg_comms_c_wrappers   59 	mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
smg_comms_c_wrappers   60     }
smg_comms_c_wrappers   61     /*	log_debug("result:\n");
smg_comms_c_wrappers   62 	log_mpidump("q =", q );
smg_comms_c_wrappers   63 	log_mpidump("u1=", u1);
smg_comms_c_wrappers   64 	log_mpidump("u2=", u2);
smg_comms_c_wrappers   65 	log_mpidump("u3=", u3);
smg_comms_c_wrappers   66 	log_mpidump("v1=", v1);
smg_comms_c_wrappers   67 	log_mpidump("v2=", v2); */
smg_comms_c_wrappers   68     mpi_set(x, u1);
smg_comms_c_wrappers   69 
smg_comms_c_wrappers   70     mpi_free(u1);
smg_comms_c_wrappers   71     mpi_free(u2);
smg_comms_c_wrappers   72     mpi_free(u3);
smg_comms_c_wrappers   73     mpi_free(v1);
smg_comms_c_wrappers   74     mpi_free(v2);
smg_comms_c_wrappers   75     mpi_free(v3);
smg_comms_c_wrappers   76     mpi_free(q);
smg_comms_c_wrappers   77     mpi_free(t1);
smg_comms_c_wrappers   78     mpi_free(t2);
smg_comms_c_wrappers   79     mpi_free(t3);
smg_comms_c_wrappers   80     mpi_free(u);
smg_comms_c_wrappers   81     mpi_free(v);
smg_comms_c_wrappers   82 #elif 0
smg_comms_c_wrappers   83     /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
smg_comms_c_wrappers   84      * modified according to Michael Penk's solution for Exercice 35 */
smg_comms_c_wrappers   85 
smg_comms_c_wrappers   86     /* FIXME: we can simplify this in most cases (see Knuth) */
smg_comms_c_wrappers   87     MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
smg_comms_c_wrappers   88     unsigned k;
smg_comms_c_wrappers   89     int sign;
smg_comms_c_wrappers   90 
smg_comms_c_wrappers   91     u = mpi_copy(a);
smg_comms_c_wrappers   92     v = mpi_copy(n);
smg_comms_c_wrappers   93     for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
smg_comms_c_wrappers   94 	mpi_rshift(u, u, 1);
smg_comms_c_wrappers   95 	mpi_rshift(v, v, 1);
smg_comms_c_wrappers   96     }
smg_comms_c_wrappers   97 
smg_comms_c_wrappers   98 
smg_comms_c_wrappers   99     u1 = mpi_alloc_set_ui(1);
smg_comms_c_wrappers  100     u2 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers  101     u3 = mpi_copy(u);
smg_comms_c_wrappers  102     v1 = mpi_copy(v);				   /* !-- used as const 1 */
smg_comms_c_wrappers  103     v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
smg_comms_c_wrappers  104     v3 = mpi_copy(v);
smg_comms_c_wrappers  105     if( mpi_test_bit(u, 0) ) { /* u is odd */
smg_comms_c_wrappers  106 	t1 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers  107 	t2 = mpi_alloc_set_ui(1); t2->sign = 1;
smg_comms_c_wrappers  108 	t3 = mpi_copy(v); t3->sign = !t3->sign;
smg_comms_c_wrappers  109 	goto Y4;
smg_comms_c_wrappers  110     }
smg_comms_c_wrappers  111     else {
smg_comms_c_wrappers  112 	t1 = mpi_alloc_set_ui(1);
smg_comms_c_wrappers  113 	t2 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers  114 	t3 = mpi_copy(u);
smg_comms_c_wrappers  115     }
smg_comms_c_wrappers  116     do {
smg_comms_c_wrappers  117 	do {
smg_comms_c_wrappers  118 	    if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
smg_comms_c_wrappers  119 		mpi_add(t1, t1, v);
smg_comms_c_wrappers  120 		mpi_sub(t2, t2, u);
smg_comms_c_wrappers  121 	    }
smg_comms_c_wrappers  122 	    mpi_rshift(t1, t1, 1);
smg_comms_c_wrappers  123 	    mpi_rshift(t2, t2, 1);
smg_comms_c_wrappers  124 	    mpi_rshift(t3, t3, 1);
smg_comms_c_wrappers  125 	  Y4:
smg_comms_c_wrappers  126 	    ;
smg_comms_c_wrappers  127 	} while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
smg_comms_c_wrappers  128 
smg_comms_c_wrappers  129 	if( !t3->sign ) {
smg_comms_c_wrappers  130 	    mpi_set(u1, t1);
smg_comms_c_wrappers  131 	    mpi_set(u2, t2);
smg_comms_c_wrappers  132 	    mpi_set(u3, t3);
smg_comms_c_wrappers  133 	}
smg_comms_c_wrappers  134 	else {
smg_comms_c_wrappers  135 	    mpi_sub(v1, v, t1);
smg_comms_c_wrappers  136 	    sign = u->sign; u->sign = !u->sign;
smg_comms_c_wrappers  137 	    mpi_sub(v2, u, t2);
smg_comms_c_wrappers  138 	    u->sign = sign;
smg_comms_c_wrappers  139 	    sign = t3->sign; t3->sign = !t3->sign;
smg_comms_c_wrappers  140 	    mpi_set(v3, t3);
smg_comms_c_wrappers  141 	    t3->sign = sign;
smg_comms_c_wrappers  142 	}
smg_comms_c_wrappers  143 	mpi_sub(t1, u1, v1);
smg_comms_c_wrappers  144 	mpi_sub(t2, u2, v2);
smg_comms_c_wrappers  145 	mpi_sub(t3, u3, v3);
smg_comms_c_wrappers  146 	if( t1->sign ) {
smg_comms_c_wrappers  147 	    mpi_add(t1, t1, v);
smg_comms_c_wrappers  148 	    mpi_sub(t2, t2, u);
smg_comms_c_wrappers  149 	}
smg_comms_c_wrappers  150     } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
smg_comms_c_wrappers  151     /* mpi_lshift( u3, k ); */
smg_comms_c_wrappers  152     mpi_set(x, u1);
smg_comms_c_wrappers  153 
smg_comms_c_wrappers  154     mpi_free(u1);
smg_comms_c_wrappers  155     mpi_free(u2);
smg_comms_c_wrappers  156     mpi_free(u3);
smg_comms_c_wrappers  157     mpi_free(v1);
smg_comms_c_wrappers  158     mpi_free(v2);
smg_comms_c_wrappers  159     mpi_free(v3);
smg_comms_c_wrappers  160     mpi_free(t1);
smg_comms_c_wrappers  161     mpi_free(t2);
smg_comms_c_wrappers  162     mpi_free(t3);
smg_comms_c_wrappers  163 #else
smg_comms_c_wrappers  164     /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
smg_comms_c_wrappers  165      * modified according to Michael Penk's solution for Exercice 35
smg_comms_c_wrappers  166      * with further enhancement */
smg_comms_c_wrappers  167     MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
smg_comms_c_wrappers  168     unsigned k;
smg_comms_c_wrappers  169     int sign;
smg_comms_c_wrappers  170     int odd ;
smg_comms_c_wrappers  171 
smg_comms_c_wrappers  172     u = mpi_copy(a);
smg_comms_c_wrappers  173     v = mpi_copy(n);
smg_comms_c_wrappers  174 
smg_comms_c_wrappers  175     for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
smg_comms_c_wrappers  176 	mpi_rshift(u, u, 1);
smg_comms_c_wrappers  177 	mpi_rshift(v, v, 1);
smg_comms_c_wrappers  178     }
smg_comms_c_wrappers  179     odd = mpi_test_bit(v,0);
smg_comms_c_wrappers  180 
smg_comms_c_wrappers  181     u1 = mpi_alloc_set_ui(1);
smg_comms_c_wrappers  182     if( !odd )
smg_comms_c_wrappers  183 	u2 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers  184     u3 = mpi_copy(u);
smg_comms_c_wrappers  185     v1 = mpi_copy(v);
smg_comms_c_wrappers  186     if( !odd ) {
smg_comms_c_wrappers  187 	v2 = mpi_alloc( mpi_get_nlimbs(u) );
smg_comms_c_wrappers  188 	mpi_sub( v2, u1, u ); /* U is used as const 1 */
smg_comms_c_wrappers  189     }
smg_comms_c_wrappers  190     v3 = mpi_copy(v);
smg_comms_c_wrappers  191     if( mpi_test_bit(u, 0) ) { /* u is odd */
smg_comms_c_wrappers  192 	t1 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers  193 	if( !odd ) {
smg_comms_c_wrappers  194 	    t2 = mpi_alloc_set_ui(1); t2->sign = 1;
smg_comms_c_wrappers  195 	}
smg_comms_c_wrappers  196 	t3 = mpi_copy(v); t3->sign = !t3->sign;
smg_comms_c_wrappers  197 	goto Y4;
smg_comms_c_wrappers  198     }
smg_comms_c_wrappers  199     else {
smg_comms_c_wrappers  200 	t1 = mpi_alloc_set_ui(1);
smg_comms_c_wrappers  201 	if( !odd )
smg_comms_c_wrappers  202 	    t2 = mpi_alloc_set_ui(0);
smg_comms_c_wrappers  203 	t3 = mpi_copy(u);
smg_comms_c_wrappers  204     }
smg_comms_c_wrappers  205     do {
smg_comms_c_wrappers  206 	do {
smg_comms_c_wrappers  207 	    if( !odd ) {
smg_comms_c_wrappers  208 		if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
smg_comms_c_wrappers  209 		    mpi_add(t1, t1, v);
smg_comms_c_wrappers  210 		    mpi_sub(t2, t2, u);
smg_comms_c_wrappers  211 		}
smg_comms_c_wrappers  212 		mpi_rshift(t1, t1, 1);
smg_comms_c_wrappers  213 		mpi_rshift(t2, t2, 1);
smg_comms_c_wrappers  214 		mpi_rshift(t3, t3, 1);
smg_comms_c_wrappers  215 	    }
smg_comms_c_wrappers  216 	    else {
smg_comms_c_wrappers  217 		if( mpi_test_bit(t1, 0) )
smg_comms_c_wrappers  218 		    mpi_add(t1, t1, v);
smg_comms_c_wrappers  219 		mpi_rshift(t1, t1, 1);
smg_comms_c_wrappers  220 		mpi_rshift(t3, t3, 1);
smg_comms_c_wrappers  221 	    }
smg_comms_c_wrappers  222 	  Y4:
smg_comms_c_wrappers  223 	    ;
smg_comms_c_wrappers  224 	} while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
smg_comms_c_wrappers  225 
smg_comms_c_wrappers  226 	if( !t3->sign ) {
smg_comms_c_wrappers  227 	    mpi_set(u1, t1);
smg_comms_c_wrappers  228 	    if( !odd )
smg_comms_c_wrappers  229 		mpi_set(u2, t2);
smg_comms_c_wrappers  230 	    mpi_set(u3, t3);
smg_comms_c_wrappers  231 	}
smg_comms_c_wrappers  232 	else {
smg_comms_c_wrappers  233 	    mpi_sub(v1, v, t1);
smg_comms_c_wrappers  234 	    sign = u->sign; u->sign = !u->sign;
smg_comms_c_wrappers  235 	    if( !odd )
smg_comms_c_wrappers  236 		mpi_sub(v2, u, t2);
smg_comms_c_wrappers  237 	    u->sign = sign;
smg_comms_c_wrappers  238 	    sign = t3->sign; t3->sign = !t3->sign;
smg_comms_c_wrappers  239 	    mpi_set(v3, t3);
smg_comms_c_wrappers  240 	    t3->sign = sign;
smg_comms_c_wrappers  241 	}
smg_comms_c_wrappers  242 	mpi_sub(t1, u1, v1);
smg_comms_c_wrappers  243 	if( !odd )
smg_comms_c_wrappers  244 	    mpi_sub(t2, u2, v2);
smg_comms_c_wrappers  245 	mpi_sub(t3, u3, v3);
smg_comms_c_wrappers  246 	if( t1->sign ) {
smg_comms_c_wrappers  247 	    mpi_add(t1, t1, v);
smg_comms_c_wrappers  248 	    if( !odd )
smg_comms_c_wrappers  249 		mpi_sub(t2, t2, u);
smg_comms_c_wrappers  250 	}
smg_comms_c_wrappers  251     } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
smg_comms_c_wrappers  252     /* mpi_lshift( u3, k ); */
smg_comms_c_wrappers  253     mpi_set(x, u1);
smg_comms_c_wrappers  254 
smg_comms_c_wrappers  255     mpi_free(u1);
smg_comms_c_wrappers  256     mpi_free(v1);
smg_comms_c_wrappers  257     mpi_free(t1);
smg_comms_c_wrappers  258     if( !odd ) {
smg_comms_c_wrappers  259 	mpi_free(u2);
smg_comms_c_wrappers  260 	mpi_free(v2);
smg_comms_c_wrappers  261 	mpi_free(t2);
smg_comms_c_wrappers  262     }
smg_comms_c_wrappers  263     mpi_free(u3);
smg_comms_c_wrappers  264     mpi_free(v3);
smg_comms_c_wrappers  265     mpi_free(t3);
smg_comms_c_wrappers  266 
smg_comms_c_wrappers  267     mpi_free(u);
smg_comms_c_wrappers  268     mpi_free(v);
smg_comms_c_wrappers  269 #endif
smg_comms_c_wrappers  270 }