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