raw
ch1_mpi                 1 /* mpi-mul.c  -  MPI functions
ch1_mpi                 2  * Modified by No Such Labs. (C) 2015. See README.
ch1_mpi                 3  *
ch1_mpi                 4  * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
ch1_mpi                 5  * SHA256(gnupg-1.4.10.tar.gz):
ch1_mpi                 6  *        0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
ch1_mpi                 7  * (C) 1994-2005 Free Software Foundation, Inc.
ch1_mpi                 8  *
ch1_mpi                 9  * This program is free software: you can redistribute it and/or modify
ch1_mpi                10  * it under the terms of the GNU General Public License as published by
ch1_mpi                11  * the Free Software Foundation, either version 3 of the License, or
ch1_mpi                12  * (at your option) any later version.
ch1_mpi                13  *
ch1_mpi                14  * This program is distributed in the hope that it will be useful,
ch1_mpi                15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
ch1_mpi                16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
ch1_mpi                17  * GNU General Public License for more details.
ch1_mpi                18  *
ch1_mpi                19  * You should have received a copy of the GNU General Public License
ch1_mpi                20  * along with this program.  If not, see <http://www.gnu.org/licenses/>.
ch1_mpi                21  */
ch1_mpi                22 
ch1_mpi                23 #include <stdio.h>
ch1_mpi                24 #include <stdlib.h>
ch1_mpi                25 
ch1_mpi                26 #include "knobs.h"
ch1_mpi                27 #include "mpi-internal.h"
ch1_mpi                28 
ch1_mpi                29 
ch1_mpi                30 void
ch1_mpi                31 mpi_mul_ui( MPI prod, MPI mult, unsigned long small_mult )
ch1_mpi                32 {
ch1_mpi                33     mpi_size_t size, prod_size;
ch1_mpi                34     mpi_ptr_t  prod_ptr;
ch1_mpi                35     mpi_limb_t cy;
ch1_mpi                36     int sign;
ch1_mpi                37 
ch1_mpi                38     size = mult->nlimbs;
ch1_mpi                39     sign = mult->sign;
ch1_mpi                40 
ch1_mpi                41     if( !size || !small_mult ) {
ch1_mpi                42 	prod->nlimbs = 0;
ch1_mpi                43 	prod->sign = 0;
ch1_mpi                44 	return;
ch1_mpi                45     }
ch1_mpi                46 
ch1_mpi                47     prod_size = size + 1;
ch1_mpi                48     if( prod->alloced < prod_size )
ch1_mpi                49 	mpi_resize( prod, prod_size );
ch1_mpi                50     prod_ptr = prod->d;
ch1_mpi                51 
ch1_mpi                52     cy = mpihelp_mul_1( prod_ptr, mult->d, size, (mpi_limb_t)small_mult );
ch1_mpi                53     if( cy )
ch1_mpi                54 	prod_ptr[size++] = cy;
ch1_mpi                55     prod->nlimbs = size;
ch1_mpi                56     prod->sign = sign;
ch1_mpi                57 }
ch1_mpi                58 
ch1_mpi                59 
ch1_mpi                60 void
ch1_mpi                61 mpi_mul_2exp( MPI w, MPI u, unsigned long cnt)
ch1_mpi                62 {
ch1_mpi                63     mpi_size_t usize, wsize, limb_cnt;
ch1_mpi                64     mpi_ptr_t wp;
ch1_mpi                65     mpi_limb_t wlimb;
ch1_mpi                66     int usign, wsign;
ch1_mpi                67 
ch1_mpi                68     usize = u->nlimbs;
ch1_mpi                69     usign = u->sign;
ch1_mpi                70 
ch1_mpi                71     if( !usize ) {
ch1_mpi                72 	w->nlimbs = 0;
ch1_mpi                73 	w->sign = 0;
ch1_mpi                74 	return;
ch1_mpi                75     }
ch1_mpi                76 
ch1_mpi                77     limb_cnt = cnt / BITS_PER_MPI_LIMB;
ch1_mpi                78     wsize = usize + limb_cnt + 1;
ch1_mpi                79     if( w->alloced < wsize )
ch1_mpi                80 	mpi_resize(w, wsize );
ch1_mpi                81     wp = w->d;
ch1_mpi                82     wsize = usize + limb_cnt;
ch1_mpi                83     wsign = usign;
ch1_mpi                84 
ch1_mpi                85     cnt %= BITS_PER_MPI_LIMB;
ch1_mpi                86     if( cnt ) {
ch1_mpi                87 	wlimb = mpihelp_lshift( wp + limb_cnt, u->d, usize, cnt );
ch1_mpi                88 	if( wlimb ) {
ch1_mpi                89 	    wp[wsize] = wlimb;
ch1_mpi                90 	    wsize++;
ch1_mpi                91 	}
ch1_mpi                92     }
ch1_mpi                93     else {
ch1_mpi                94 	MPN_COPY_DECR( wp + limb_cnt, u->d, usize );
ch1_mpi                95     }
ch1_mpi                96 
ch1_mpi                97     /* Zero all whole limbs at low end.  Do it here and not before calling
ch1_mpi                98      * mpn_lshift, not to lose for U == W.  */
ch1_mpi                99     MPN_ZERO( wp, limb_cnt );
ch1_mpi               100 
ch1_mpi               101     w->nlimbs = wsize;
ch1_mpi               102     w->sign = wsign;
ch1_mpi               103 }
ch1_mpi               104 
ch1_mpi               105 
ch1_mpi               106 
ch1_mpi               107 void
ch1_mpi               108 mpi_mul( MPI w, MPI u, MPI v)
ch1_mpi               109 {
ch1_mpi               110     mpi_size_t usize, vsize, wsize;
ch1_mpi               111     mpi_ptr_t up, vp, wp;
ch1_mpi               112     mpi_limb_t cy;
ch1_mpi               113     int usign, vsign, usecure, vsecure, sign_product;
ch1_mpi               114     int assign_wp=0;
ch1_mpi               115     mpi_ptr_t tmp_limb=NULL;
ch1_mpi               116 
ch1_mpi               117 
ch1_mpi               118     if( u->nlimbs < v->nlimbs ) { /* Swap U and V. */
ch1_mpi               119 	usize = v->nlimbs;
ch1_mpi               120 	usign = v->sign;
ch1_mpi               121 	usecure = mpi_is_secure(v);
ch1_mpi               122 	up    = v->d;
ch1_mpi               123 	vsize = u->nlimbs;
ch1_mpi               124 	vsign = u->sign;
ch1_mpi               125 	vsecure = mpi_is_secure(u);
ch1_mpi               126 	vp    = u->d;
ch1_mpi               127     }
ch1_mpi               128     else {
ch1_mpi               129 	usize = u->nlimbs;
ch1_mpi               130 	usign = u->sign;
ch1_mpi               131 	usecure = mpi_is_secure(u);
ch1_mpi               132 	up    = u->d;
ch1_mpi               133 	vsize = v->nlimbs;
ch1_mpi               134 	vsign = v->sign;
ch1_mpi               135 	vsecure = mpi_is_secure(v);
ch1_mpi               136 	vp    = v->d;
ch1_mpi               137     }
ch1_mpi               138     sign_product = usign ^ vsign;
ch1_mpi               139     wp = w->d;
ch1_mpi               140 
ch1_mpi               141     /* Ensure W has space enough to store the result.  */
ch1_mpi               142     wsize = usize + vsize;
ch1_mpi               143     if ( !mpi_is_secure (w) && (mpi_is_secure (u) || mpi_is_secure (v)) ) {
ch1_mpi               144         /* w is not allocated in secure space but u or v is.  To make sure
ch1_mpi               145          * that no temporray results are stored in w, we temporary use 
ch1_mpi               146          * a newly allocated limb space for w */
ch1_mpi               147         wp = mpi_alloc_limb_space( wsize, 1 );
ch1_mpi               148         assign_wp = 2; /* mark it as 2 so that we can later copy it back to
ch1_mpi               149                         * mormal memory */
ch1_mpi               150     }
ch1_mpi               151     else if( w->alloced < wsize ) {
ch1_mpi               152 	if( wp == up || wp == vp ) {
ch1_mpi               153 	    wp = mpi_alloc_limb_space( wsize, mpi_is_secure(w) );
ch1_mpi               154 	    assign_wp = 1;
ch1_mpi               155 	}
ch1_mpi               156 	else {
ch1_mpi               157 	    mpi_resize(w, wsize );
ch1_mpi               158 	    wp = w->d;
ch1_mpi               159 	}
ch1_mpi               160     }
ch1_mpi               161     else { /* Make U and V not overlap with W.	*/
ch1_mpi               162 	if( wp == up ) {
ch1_mpi               163 	    /* W and U are identical.  Allocate temporary space for U.	*/
ch1_mpi               164 	    up = tmp_limb = mpi_alloc_limb_space( usize, usecure  );
ch1_mpi               165 	    /* Is V identical too?  Keep it identical with U.  */
ch1_mpi               166 	    if( wp == vp )
ch1_mpi               167 		vp = up;
ch1_mpi               168 	    /* Copy to the temporary space.  */
ch1_mpi               169 	    MPN_COPY( up, wp, usize );
ch1_mpi               170 	}
ch1_mpi               171 	else if( wp == vp ) {
ch1_mpi               172 	    /* W and V are identical.  Allocate temporary space for V.	*/
ch1_mpi               173 	    vp = tmp_limb = mpi_alloc_limb_space( vsize, vsecure );
ch1_mpi               174 	    /* Copy to the temporary space.  */
ch1_mpi               175 	    MPN_COPY( vp, wp, vsize );
ch1_mpi               176 	}
ch1_mpi               177     }
ch1_mpi               178 
ch1_mpi               179     if( !vsize )
ch1_mpi               180 	wsize = 0;
ch1_mpi               181     else {
ch1_mpi               182 	cy = mpihelp_mul( wp, up, usize, vp, vsize );
ch1_mpi               183 	wsize -= cy? 0:1;
ch1_mpi               184     }
ch1_mpi               185 
ch1_mpi               186     if( assign_wp ) {
ch1_mpi               187         if (assign_wp == 2) {
ch1_mpi               188             /* copy the temp wp from secure memory back to normal memory */
ch1_mpi               189 	    mpi_ptr_t tmp_wp = mpi_alloc_limb_space (wsize, 0);
ch1_mpi               190 	    MPN_COPY (tmp_wp, wp, wsize);
ch1_mpi               191             mpi_free_limb_space (wp);
ch1_mpi               192             wp = tmp_wp;
ch1_mpi               193         }
ch1_mpi               194 	mpi_assign_limb_space( w, wp, wsize );
ch1_mpi               195     }
ch1_mpi               196     w->nlimbs = wsize;
ch1_mpi               197     w->sign = sign_product;
ch1_mpi               198     if( tmp_limb )
ch1_mpi               199 	mpi_free_limb_space( tmp_limb );
ch1_mpi               200 }
ch1_mpi               201 
ch1_mpi               202 
ch1_mpi               203 void
ch1_mpi               204 mpi_mulm( MPI w, MPI u, MPI v, MPI m)
ch1_mpi               205 {
ch1_mpi               206     mpi_mul(w, u, v);
ch1_mpi               207     mpi_fdiv_r( w, w, m );
ch1_mpi               208 }
ch1_mpi               209