raw
smg_comms_c_wrappers    1 /* mpi-pow.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 #include <string.h>
smg_comms_c_wrappers   26 #include <assert.h>
smg_comms_c_wrappers   27 
smg_comms_c_wrappers   28 #include "knobs.h"
smg_comms_c_wrappers   29 #include "mpi-internal.h"
smg_comms_c_wrappers   30 #include "longlong.h"
smg_comms_c_wrappers   31 
smg_comms_c_wrappers   32 
smg_comms_c_wrappers   33 
smg_comms_c_wrappers   34 /****************
smg_comms_c_wrappers   35  * RES = BASE ^ EXP mod MOD
smg_comms_c_wrappers   36  */
smg_comms_c_wrappers   37 void
smg_comms_c_wrappers   38 mpi_powm( MPI res, MPI base, MPI exponent, MPI mod)
smg_comms_c_wrappers   39 {
smg_comms_c_wrappers   40     mpi_ptr_t  rp, ep, mp, bp;
smg_comms_c_wrappers   41     mpi_size_t esize, msize, bsize, rsize;
smg_comms_c_wrappers   42     int        esign, msign, bsign, rsign;
smg_comms_c_wrappers   43     int        esec,  msec,  bsec,  rsec;
smg_comms_c_wrappers   44     mpi_size_t size;
smg_comms_c_wrappers   45     int mod_shift_cnt;
smg_comms_c_wrappers   46     int negative_result;
smg_comms_c_wrappers   47     mpi_ptr_t mp_marker=NULL, bp_marker=NULL, ep_marker=NULL;
smg_comms_c_wrappers   48     mpi_ptr_t xp_marker=NULL;
smg_comms_c_wrappers   49     int assign_rp=0;
smg_comms_c_wrappers   50     mpi_ptr_t tspace = NULL;
smg_comms_c_wrappers   51     mpi_size_t tsize=0;   /* to avoid compiler warning */
smg_comms_c_wrappers   52 			  /* fixme: we should check that the warning is void*/
smg_comms_c_wrappers   53 
smg_comms_c_wrappers   54     esize = exponent->nlimbs;
smg_comms_c_wrappers   55     msize = mod->nlimbs;
smg_comms_c_wrappers   56     size = 2 * msize;
smg_comms_c_wrappers   57     esign = exponent->sign;
smg_comms_c_wrappers   58     msign = mod->sign;
smg_comms_c_wrappers   59 
smg_comms_c_wrappers   60     esec = mpi_is_secure(exponent);
smg_comms_c_wrappers   61     msec = mpi_is_secure(mod);
smg_comms_c_wrappers   62     bsec = mpi_is_secure(base);
smg_comms_c_wrappers   63     rsec = mpi_is_secure(res);
smg_comms_c_wrappers   64 
smg_comms_c_wrappers   65     rp = res->d;
smg_comms_c_wrappers   66     ep = exponent->d;
smg_comms_c_wrappers   67 
smg_comms_c_wrappers   68     if( !msize )
smg_comms_c_wrappers   69 	msize = 1 / msize;	    /* provoke a signal */
smg_comms_c_wrappers   70 
smg_comms_c_wrappers   71     if( !esize ) {
smg_comms_c_wrappers   72 	/* Exponent is zero, result is 1 mod MOD, i.e., 1 or 0
smg_comms_c_wrappers   73 	 * depending on if MOD equals 1.  */
smg_comms_c_wrappers   74 	rp[0] = 1;
smg_comms_c_wrappers   75 	res->nlimbs = (msize == 1 && mod->d[0] == 1) ? 0 : 1;
smg_comms_c_wrappers   76 	res->sign = 0;
smg_comms_c_wrappers   77 	goto leave;
smg_comms_c_wrappers   78     }
smg_comms_c_wrappers   79 
smg_comms_c_wrappers   80     /* Normalize MOD (i.e. make its most significant bit set) as required by
smg_comms_c_wrappers   81      * mpn_divrem.  This will make the intermediate values in the calculation
smg_comms_c_wrappers   82      * slightly larger, but the correct result is obtained after a final
smg_comms_c_wrappers   83      * reduction using the original MOD value.	*/
smg_comms_c_wrappers   84     mp = mp_marker = mpi_alloc_limb_space(msize, msec);
smg_comms_c_wrappers   85     count_leading_zeros( mod_shift_cnt, mod->d[msize-1] );
smg_comms_c_wrappers   86     if( mod_shift_cnt )
smg_comms_c_wrappers   87 	mpihelp_lshift( mp, mod->d, msize, mod_shift_cnt );
smg_comms_c_wrappers   88     else
smg_comms_c_wrappers   89 	MPN_COPY( mp, mod->d, msize );
smg_comms_c_wrappers   90 
smg_comms_c_wrappers   91     bsize = base->nlimbs;
smg_comms_c_wrappers   92     bsign = base->sign;
smg_comms_c_wrappers   93     if( bsize > msize ) { /* The base is larger than the module. Reduce it. */
smg_comms_c_wrappers   94 	/* Allocate (BSIZE + 1) with space for remainder and quotient.
smg_comms_c_wrappers   95 	 * (The quotient is (bsize - msize + 1) limbs.)  */
smg_comms_c_wrappers   96 	bp = bp_marker = mpi_alloc_limb_space( bsize + 1, bsec );
smg_comms_c_wrappers   97 	MPN_COPY( bp, base->d, bsize );
smg_comms_c_wrappers   98 	/* We don't care about the quotient, store it above the remainder,
smg_comms_c_wrappers   99 	 * at BP + MSIZE.  */
smg_comms_c_wrappers  100 	mpihelp_divrem( bp + msize, 0, bp, bsize, mp, msize );
smg_comms_c_wrappers  101 	bsize = msize;
smg_comms_c_wrappers  102 	/* Canonicalize the base, since we are going to multiply with it
smg_comms_c_wrappers  103 	 * quite a few times.  */
smg_comms_c_wrappers  104 	MPN_NORMALIZE( bp, bsize );
smg_comms_c_wrappers  105     }
smg_comms_c_wrappers  106     else
smg_comms_c_wrappers  107 	bp = base->d;
smg_comms_c_wrappers  108 
smg_comms_c_wrappers  109     if( !bsize ) {
smg_comms_c_wrappers  110 	res->nlimbs = 0;
smg_comms_c_wrappers  111 	res->sign = 0;
smg_comms_c_wrappers  112 	goto leave;
smg_comms_c_wrappers  113     }
smg_comms_c_wrappers  114 
smg_comms_c_wrappers  115     if( res->alloced < size ) {
smg_comms_c_wrappers  116 	/* We have to allocate more space for RES.  If any of the input
smg_comms_c_wrappers  117 	 * parameters are identical to RES, defer deallocation of the old
smg_comms_c_wrappers  118 	 * space.  */
smg_comms_c_wrappers  119 	if( rp == ep || rp == mp || rp == bp ) {
smg_comms_c_wrappers  120 	    rp = mpi_alloc_limb_space( size, rsec );
smg_comms_c_wrappers  121 	    assign_rp = 1;
smg_comms_c_wrappers  122 	}
smg_comms_c_wrappers  123 	else {
smg_comms_c_wrappers  124 	    mpi_resize( res, size );
smg_comms_c_wrappers  125 	    rp = res->d;
smg_comms_c_wrappers  126 	}
smg_comms_c_wrappers  127     }
smg_comms_c_wrappers  128     else { /* Make BASE, EXPONENT and MOD not overlap with RES.  */
smg_comms_c_wrappers  129 	if( rp == bp ) {
smg_comms_c_wrappers  130 	    /* RES and BASE are identical.  Allocate temp. space for BASE.  */
smg_comms_c_wrappers  131 	    assert( !bp_marker );
smg_comms_c_wrappers  132 	    bp = bp_marker = mpi_alloc_limb_space( bsize, bsec );
smg_comms_c_wrappers  133 	    MPN_COPY(bp, rp, bsize);
smg_comms_c_wrappers  134 	}
smg_comms_c_wrappers  135 	if( rp == ep ) {
smg_comms_c_wrappers  136 	    /* RES and EXPONENT are identical.  
smg_comms_c_wrappers  137                Allocate temp. space for EXPONENT.  */
smg_comms_c_wrappers  138 	    ep = ep_marker = mpi_alloc_limb_space( esize, esec );
smg_comms_c_wrappers  139 	    MPN_COPY(ep, rp, esize);
smg_comms_c_wrappers  140 	}
smg_comms_c_wrappers  141 	if( rp == mp ) {
smg_comms_c_wrappers  142 	    /* RES and MOD are identical.  Allocate temporary space for MOD.*/
smg_comms_c_wrappers  143 	    assert( !mp_marker );
smg_comms_c_wrappers  144 	    mp = mp_marker = mpi_alloc_limb_space( msize, msec );
smg_comms_c_wrappers  145 	    MPN_COPY(mp, rp, msize);
smg_comms_c_wrappers  146 	}
smg_comms_c_wrappers  147     }
smg_comms_c_wrappers  148 
smg_comms_c_wrappers  149     MPN_COPY( rp, bp, bsize );
smg_comms_c_wrappers  150     rsize = bsize;
smg_comms_c_wrappers  151     rsign = bsign;
smg_comms_c_wrappers  152 
smg_comms_c_wrappers  153     {
smg_comms_c_wrappers  154 	mpi_size_t i;
smg_comms_c_wrappers  155 	mpi_ptr_t xp = xp_marker = mpi_alloc_limb_space( 2 * (msize + 1), msec );
smg_comms_c_wrappers  156 	int c;
smg_comms_c_wrappers  157 	mpi_limb_t e;
smg_comms_c_wrappers  158 	mpi_limb_t carry_limb;
smg_comms_c_wrappers  159 	struct karatsuba_ctx karactx;
smg_comms_c_wrappers  160 
smg_comms_c_wrappers  161 	memset( &karactx, 0, sizeof karactx );
smg_comms_c_wrappers  162 	negative_result = (ep[0] & 1) && base->sign;
smg_comms_c_wrappers  163 
smg_comms_c_wrappers  164 	i = esize - 1;
smg_comms_c_wrappers  165 	e = ep[i];
smg_comms_c_wrappers  166 	count_leading_zeros (c, e);
smg_comms_c_wrappers  167 	e = (e << c) << 1;     /* shift the exp bits to the left, lose msb */
smg_comms_c_wrappers  168 	c = BITS_PER_MPI_LIMB - 1 - c;
smg_comms_c_wrappers  169 
smg_comms_c_wrappers  170 	/* Main loop.
smg_comms_c_wrappers  171 	 *
smg_comms_c_wrappers  172 	 * Make the result be pointed to alternately by XP and RP.  This
smg_comms_c_wrappers  173 	 * helps us avoid block copying, which would otherwise be necessary
smg_comms_c_wrappers  174 	 * with the overlap restrictions of mpihelp_divmod. With 50% probability
smg_comms_c_wrappers  175 	 * the result after this loop will be in the area originally pointed
smg_comms_c_wrappers  176 	 * by RP (==RES->d), and with 50% probability in the area originally
smg_comms_c_wrappers  177 	 * pointed to by XP.
smg_comms_c_wrappers  178 	 */
smg_comms_c_wrappers  179 
smg_comms_c_wrappers  180 	for(;;) {
smg_comms_c_wrappers  181 	    while( c ) {
smg_comms_c_wrappers  182 		mpi_ptr_t tp;
smg_comms_c_wrappers  183 		mpi_size_t xsize;
smg_comms_c_wrappers  184 
smg_comms_c_wrappers  185 		/*mpihelp_mul_n(xp, rp, rp, rsize);*/
smg_comms_c_wrappers  186 		if( rsize < KARATSUBA_THRESHOLD )
smg_comms_c_wrappers  187 		    mpih_sqr_n_basecase( xp, rp, rsize );
smg_comms_c_wrappers  188 		else {
smg_comms_c_wrappers  189 		    if( !tspace ) {
smg_comms_c_wrappers  190 			tsize = 2 * rsize;
smg_comms_c_wrappers  191 			tspace = mpi_alloc_limb_space( tsize, 0 );
smg_comms_c_wrappers  192 		    }
smg_comms_c_wrappers  193 		    else if( tsize < (2*rsize) ) {
smg_comms_c_wrappers  194 			mpi_free_limb_space( tspace );
smg_comms_c_wrappers  195 			tsize = 2 * rsize;
smg_comms_c_wrappers  196 			tspace = mpi_alloc_limb_space( tsize, 0 );
smg_comms_c_wrappers  197 		    }
smg_comms_c_wrappers  198 		    mpih_sqr_n( xp, rp, rsize, tspace );
smg_comms_c_wrappers  199 		}
smg_comms_c_wrappers  200 
smg_comms_c_wrappers  201 		xsize = 2 * rsize;
smg_comms_c_wrappers  202 		if( xsize > msize ) {
smg_comms_c_wrappers  203 		    mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize);
smg_comms_c_wrappers  204 		    xsize = msize;
smg_comms_c_wrappers  205 		}
smg_comms_c_wrappers  206 
smg_comms_c_wrappers  207 		tp = rp; rp = xp; xp = tp;
smg_comms_c_wrappers  208 		rsize = xsize;
smg_comms_c_wrappers  209 
smg_comms_c_wrappers  210 		if( (mpi_limb_signed_t)e < 0 ) {
smg_comms_c_wrappers  211 		    /*mpihelp_mul( xp, rp, rsize, bp, bsize );*/
smg_comms_c_wrappers  212 		    if( bsize < KARATSUBA_THRESHOLD ) {
smg_comms_c_wrappers  213 			mpihelp_mul( xp, rp, rsize, bp, bsize );
smg_comms_c_wrappers  214 		    }
smg_comms_c_wrappers  215 		    else {
smg_comms_c_wrappers  216 			mpihelp_mul_karatsuba_case(
smg_comms_c_wrappers  217 				     xp, rp, rsize, bp, bsize, &karactx );
smg_comms_c_wrappers  218 		    }
smg_comms_c_wrappers  219 
smg_comms_c_wrappers  220 		    xsize = rsize + bsize;
smg_comms_c_wrappers  221 		    if( xsize > msize ) {
smg_comms_c_wrappers  222 			mpihelp_divrem(xp + msize, 0, xp, xsize, mp, msize);
smg_comms_c_wrappers  223 			xsize = msize;
smg_comms_c_wrappers  224 		    }
smg_comms_c_wrappers  225 
smg_comms_c_wrappers  226 		    tp = rp; rp = xp; xp = tp;
smg_comms_c_wrappers  227 		    rsize = xsize;
smg_comms_c_wrappers  228 		}
smg_comms_c_wrappers  229 		e <<= 1;
smg_comms_c_wrappers  230 		c--;
smg_comms_c_wrappers  231 	    }
smg_comms_c_wrappers  232 
smg_comms_c_wrappers  233 	    i--;
smg_comms_c_wrappers  234 	    if( i < 0 )
smg_comms_c_wrappers  235 		break;
smg_comms_c_wrappers  236 	    e = ep[i];
smg_comms_c_wrappers  237 	    c = BITS_PER_MPI_LIMB;
smg_comms_c_wrappers  238 	}
smg_comms_c_wrappers  239 
smg_comms_c_wrappers  240 	/* We shifted MOD, the modulo reduction argument, left MOD_SHIFT_CNT
smg_comms_c_wrappers  241 	 * steps.  Adjust the result by reducing it with the original MOD.
smg_comms_c_wrappers  242 	 *
smg_comms_c_wrappers  243 	 * Also make sure the result is put in RES->d (where it already
smg_comms_c_wrappers  244 	 * might be, see above).
smg_comms_c_wrappers  245 	 */
smg_comms_c_wrappers  246 	if( mod_shift_cnt ) {
smg_comms_c_wrappers  247 	    carry_limb = mpihelp_lshift( res->d, rp, rsize, mod_shift_cnt);
smg_comms_c_wrappers  248 	    rp = res->d;
smg_comms_c_wrappers  249 	    if( carry_limb ) {
smg_comms_c_wrappers  250 		rp[rsize] = carry_limb;
smg_comms_c_wrappers  251 		rsize++;
smg_comms_c_wrappers  252 	    }
smg_comms_c_wrappers  253 	}
smg_comms_c_wrappers  254 	else {
smg_comms_c_wrappers  255 	    MPN_COPY( res->d, rp, rsize);
smg_comms_c_wrappers  256 	    rp = res->d;
smg_comms_c_wrappers  257 	}
smg_comms_c_wrappers  258 
smg_comms_c_wrappers  259 	if( rsize >= msize ) {
smg_comms_c_wrappers  260 	    mpihelp_divrem(rp + msize, 0, rp, rsize, mp, msize);
smg_comms_c_wrappers  261 	    rsize = msize;
smg_comms_c_wrappers  262 	}
smg_comms_c_wrappers  263 
smg_comms_c_wrappers  264 	/* Remove any leading zero words from the result.  */
smg_comms_c_wrappers  265 	if( mod_shift_cnt )
smg_comms_c_wrappers  266 	    mpihelp_rshift( rp, rp, rsize, mod_shift_cnt);
smg_comms_c_wrappers  267 	MPN_NORMALIZE (rp, rsize);
smg_comms_c_wrappers  268 
smg_comms_c_wrappers  269 	mpihelp_release_karatsuba_ctx( &karactx );
smg_comms_c_wrappers  270     }
smg_comms_c_wrappers  271 
smg_comms_c_wrappers  272     if( negative_result && rsize ) {
smg_comms_c_wrappers  273 	if( mod_shift_cnt )
smg_comms_c_wrappers  274 	    mpihelp_rshift( mp, mp, msize, mod_shift_cnt);
smg_comms_c_wrappers  275 	mpihelp_sub( rp, mp, msize, rp, rsize);
smg_comms_c_wrappers  276 	rsize = msize;
smg_comms_c_wrappers  277 	rsign = msign;
smg_comms_c_wrappers  278 	MPN_NORMALIZE(rp, rsize);
smg_comms_c_wrappers  279     }
smg_comms_c_wrappers  280     res->nlimbs = rsize;
smg_comms_c_wrappers  281     res->sign = rsign;
smg_comms_c_wrappers  282 
smg_comms_c_wrappers  283   leave:
smg_comms_c_wrappers  284     if( assign_rp ) mpi_assign_limb_space( res, rp, size );
smg_comms_c_wrappers  285     if( mp_marker ) mpi_free_limb_space( mp_marker );
smg_comms_c_wrappers  286     if( bp_marker ) mpi_free_limb_space( bp_marker );
smg_comms_c_wrappers  287     if( ep_marker ) mpi_free_limb_space( ep_marker );
smg_comms_c_wrappers  288     if( xp_marker ) mpi_free_limb_space( xp_marker );
smg_comms_c_wrappers  289     if( tspace )    mpi_free_limb_space( tspace );
smg_comms_c_wrappers  290 }
smg_comms_c_wrappers  291