-
+ A87EBB2E2397F5903EAA0066A9ADF8F977BF7A67866CD181D0699B6D6A029880D86F349BE9CB9E6901D35B052BD871380E18AB19EFCF319C8A3662A93691856Empi/mpi-mpow.c(0 . 0)(1 . 98)
7337 /* mpi-mpow.c - MPI functions
7338 * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
7339 *
7340 * This file is part of GnuPG.
7341 *
7342 * GnuPG is free software; you can redistribute it and/or modify
7343 * it under the terms of the GNU General Public License as published by
7344 * the Free Software Foundation; either version 3 of the License, or
7345 * (at your option) any later version.
7346 *
7347 * GnuPG is distributed in the hope that it will be useful,
7348 * but WITHOUT ANY WARRANTY; without even the implied warranty of
7349 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
7350 * GNU General Public License for more details.
7351 *
7352 * You should have received a copy of the GNU General Public License
7353 * along with this program; if not, see <http://www.gnu.org/licenses/>.
7354 */
7355
7356 #include <config.h>
7357 #include <stdio.h>
7358 #include <stdlib.h>
7359 #include "mpi-internal.h"
7360 #include "longlong.h"
7361 #include <assert.h>
7362
7363 static int
7364 build_index( MPI *exparray, int k, int i, int t )
7365 {
7366 int j, bitno;
7367 int idx = 0;
7368
7369 bitno = t-i;
7370 for(j=k-1; j >= 0; j-- ) {
7371 idx <<= 1;
7372 if( mpi_test_bit( exparray[j], bitno ) )
7373 idx |= 1;
7374 }
7375 return idx;
7376 }
7377
7378 /****************
7379 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
7380 */
7381 void
7382 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
7383 {
7384 int k; /* number of elements */
7385 int t; /* bit size of largest exponent */
7386 int i, j, idx;
7387 MPI *G; /* table with precomputed values of size 2^k */
7388 MPI tmp;
7389
7390 for(k=0; basearray[k]; k++ )
7391 ;
7392 assert(k);
7393 for(t=0, i=0; (tmp=exparray[i]); i++ ) {
7394 j = mpi_get_nbits(tmp);
7395 if( j > t )
7396 t = j;
7397 }
7398 assert(i==k);
7399 assert(t);
7400 assert( k < 10 );
7401
7402 G = xmalloc_clear( (1<<k) * sizeof *G );
7403 /* and calculate */
7404 tmp = mpi_alloc( mpi_get_nlimbs(m)+1 );
7405 mpi_set_ui( res, 1 );
7406 for(i = 1; i <= t; i++ ) {
7407 mpi_mulm(tmp, res, res, m );
7408 idx = build_index( exparray, k, i, t );
7409 assert( idx >= 0 && idx < (1<<k) );
7410 if( !G[idx] ) {
7411 if( !idx )
7412 G[0] = mpi_alloc_set_ui( 1 );
7413 else {
7414 for(j=0; j < k; j++ ) {
7415 if( (idx & (1<<j) ) ) {
7416 if( !G[idx] )
7417 G[idx] = mpi_copy( basearray[j] );
7418 else
7419 mpi_mulm( G[idx], G[idx], basearray[j], m );
7420 }
7421 }
7422 if( !G[idx] )
7423 G[idx] = mpi_alloc(0);
7424 }
7425 }
7426 mpi_mulm(res, tmp, G[idx], m );
7427 }
7428
7429 /* cleanup */
7430 mpi_free(tmp);
7431 for(i=0; i < (1<<k); i++ )
7432 mpi_free(G[i]);
7433 xfree(G);
7434 }