-
+ A87EBB2E2397F5903EAA0066A9ADF8F977BF7A67866CD181D0699B6D6A029880D86F349BE9CB9E6901D35B052BD871380E18AB19EFCF319C8A3662A93691856Empi/mpi-mpow.c(0 . 0)(1 . 98)
9354 /* mpi-mpow.c - MPI functions
9355 * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
9356 *
9357 * This file is part of GnuPG.
9358 *
9359 * GnuPG is free software; you can redistribute it and/or modify
9360 * it under the terms of the GNU General Public License as published by
9361 * the Free Software Foundation; either version 3 of the License, or
9362 * (at your option) any later version.
9363 *
9364 * GnuPG is distributed in the hope that it will be useful,
9365 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9366 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9367 * GNU General Public License for more details.
9368 *
9369 * You should have received a copy of the GNU General Public License
9370 * along with this program; if not, see <http://www.gnu.org/licenses/>.
9371 */
9372
9373 #include <config.h>
9374 #include <stdio.h>
9375 #include <stdlib.h>
9376 #include "mpi-internal.h"
9377 #include "longlong.h"
9378 #include <assert.h>
9379
9380 static int
9381 build_index( MPI *exparray, int k, int i, int t )
9382 {
9383 int j, bitno;
9384 int idx = 0;
9385
9386 bitno = t-i;
9387 for(j=k-1; j >= 0; j-- ) {
9388 idx <<= 1;
9389 if( mpi_test_bit( exparray[j], bitno ) )
9390 idx |= 1;
9391 }
9392 return idx;
9393 }
9394
9395 /****************
9396 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
9397 */
9398 void
9399 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
9400 {
9401 int k; /* number of elements */
9402 int t; /* bit size of largest exponent */
9403 int i, j, idx;
9404 MPI *G; /* table with precomputed values of size 2^k */
9405 MPI tmp;
9406
9407 for(k=0; basearray[k]; k++ )
9408 ;
9409 assert(k);
9410 for(t=0, i=0; (tmp=exparray[i]); i++ ) {
9411 j = mpi_get_nbits(tmp);
9412 if( j > t )
9413 t = j;
9414 }
9415 assert(i==k);
9416 assert(t);
9417 assert( k < 10 );
9418
9419 G = xmalloc_clear( (1<<k) * sizeof *G );
9420 /* and calculate */
9421 tmp = mpi_alloc( mpi_get_nlimbs(m)+1 );
9422 mpi_set_ui( res, 1 );
9423 for(i = 1; i <= t; i++ ) {
9424 mpi_mulm(tmp, res, res, m );
9425 idx = build_index( exparray, k, i, t );
9426 assert( idx >= 0 && idx < (1<<k) );
9427 if( !G[idx] ) {
9428 if( !idx )
9429 G[0] = mpi_alloc_set_ui( 1 );
9430 else {
9431 for(j=0; j < k; j++ ) {
9432 if( (idx & (1<<j) ) ) {
9433 if( !G[idx] )
9434 G[idx] = mpi_copy( basearray[j] );
9435 else
9436 mpi_mulm( G[idx], G[idx], basearray[j], m );
9437 }
9438 }
9439 if( !G[idx] )
9440 G[idx] = mpi_alloc(0);
9441 }
9442 }
9443 mpi_mulm(res, tmp, G[idx], m );
9444 }
9445
9446 /* cleanup */
9447 mpi_free(tmp);
9448 for(i=0; i < (1<<k); i++ )
9449 mpi_free(G[i]);
9450 xfree(G);
9451 }