-
+ 221190B0F2BADE0E8F32E7ABB9A0CDA81A2B15A0ABE6AB54596B4823C41149EBB93338FA4CE7C6C4809618A53A173003F7FEBD510F188509E0D7FDD466596130eucrypt/mpi/mpi-mpow.c(0 . 0)(1 . 103)
3988 /* mpi-mpow.c - MPI functions
3989 * Modified by No Such Labs. (C) 2015. See README.
3990 *
3991 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
3992 * SHA256(gnupg-1.4.10.tar.gz):
3993 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
3994 * (C) 1994-2005 Free Software Foundation, Inc.
3995 *
3996 * This program is free software: you can redistribute it and/or modify
3997 * it under the terms of the GNU General Public License as published by
3998 * the Free Software Foundation, either version 3 of the License, or
3999 * (at your option) any later version.
4000 *
4001 * This program is distributed in the hope that it will be useful,
4002 * but WITHOUT ANY WARRANTY; without even the implied warranty of
4003 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4004 * GNU General Public License for more details.
4005 *
4006 * You should have received a copy of the GNU General Public License
4007 * along with this program. If not, see <http://www.gnu.org/licenses/>.
4008 */
4009
4010 #include <stdio.h>
4011 #include <stdlib.h>
4012 #include <assert.h>
4013
4014 #include "knobs.h"
4015 #include "mpi-internal.h"
4016 #include "longlong.h"
4017
4018
4019 static int
4020 build_index( MPI *exparray, int k, int i, int t )
4021 {
4022 int j, bitno;
4023 int idx = 0;
4024
4025 bitno = t-i;
4026 for(j=k-1; j >= 0; j-- ) {
4027 idx <<= 1;
4028 if( mpi_test_bit( exparray[j], bitno ) )
4029 idx |= 1;
4030 }
4031 return idx;
4032 }
4033
4034 /****************
4035 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
4036 */
4037 void
4038 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
4039 {
4040 int k; /* number of elements */
4041 int t; /* bit size of largest exponent */
4042 int i, j, idx;
4043 MPI *G; /* table with precomputed values of size 2^k */
4044 MPI tmp;
4045
4046 for(k=0; basearray[k]; k++ )
4047 ;
4048 assert(k);
4049 for(t=0, i=0; (tmp=exparray[i]); i++ ) {
4050 j = mpi_get_nbits(tmp);
4051 if( j > t )
4052 t = j;
4053 }
4054 assert(i==k);
4055 assert(t);
4056 assert( k < 10 );
4057
4058 G = xmalloc_clear( (1<<k) * sizeof *G );
4059 /* and calculate */
4060 tmp = mpi_alloc( mpi_get_nlimbs(m)+1 );
4061 mpi_set_ui( res, 1 );
4062 for(i = 1; i <= t; i++ ) {
4063 mpi_mulm(tmp, res, res, m );
4064 idx = build_index( exparray, k, i, t );
4065 assert( idx >= 0 && idx < (1<<k) );
4066 if( !G[idx] ) {
4067 if( !idx )
4068 G[0] = mpi_alloc_set_ui( 1 );
4069 else {
4070 for(j=0; j < k; j++ ) {
4071 if( (idx & (1<<j) ) ) {
4072 if( !G[idx] )
4073 G[idx] = mpi_copy( basearray[j] );
4074 else
4075 mpi_mulm( G[idx], G[idx], basearray[j], m );
4076 }
4077 }
4078 if( !G[idx] )
4079 G[idx] = mpi_alloc(0);
4080 }
4081 }
4082 mpi_mulm(res, tmp, G[idx], m );
4083 }
4084
4085 /* cleanup */
4086 mpi_free(tmp);
4087 for(i=0; i < (1<<k); i++ )
4088 mpi_free(G[i]);
4089 xfree(G);
4090 }