smg_comms_c_wrappers 1
smg_comms_c_wrappers 2 * Modified by No Such Labs. (C) 2015. See README.
smg_comms_c_wrappers 3 *
smg_comms_c_wrappers 4 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
smg_comms_c_wrappers 5 * SHA256(gnupg-1.4.10.tar.gz):
smg_comms_c_wrappers 6 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
smg_comms_c_wrappers 7 * (C) 1994-2005 Free Software Foundation, Inc.
smg_comms_c_wrappers 8 *
smg_comms_c_wrappers 9 * This program is free software: you can redistribute it and/or modify
smg_comms_c_wrappers 10 * it under the terms of the GNU General Public License as published by
smg_comms_c_wrappers 11 * the Free Software Foundation, either version 3 of the License, or
smg_comms_c_wrappers 12 * (at your option) any later version.
smg_comms_c_wrappers 13 *
smg_comms_c_wrappers 14 * This program is distributed in the hope that it will be useful,
smg_comms_c_wrappers 15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
smg_comms_c_wrappers 16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
smg_comms_c_wrappers 17 * GNU General Public License for more details.
smg_comms_c_wrappers 18 *
smg_comms_c_wrappers 19 * You should have received a copy of the GNU General Public License
smg_comms_c_wrappers 20 * along with this program. If not, see <http:
smg_comms_c_wrappers 21 */
smg_comms_c_wrappers 22
smg_comms_c_wrappers 23 #include <stdio.h>
smg_comms_c_wrappers 24 #include <stdlib.h>
smg_comms_c_wrappers 25 #include <assert.h>
smg_comms_c_wrappers 26
smg_comms_c_wrappers 27 #include "knobs.h"
smg_comms_c_wrappers 28 #include "mpi-internal.h"
smg_comms_c_wrappers 29 #include "longlong.h"
smg_comms_c_wrappers 30
smg_comms_c_wrappers 31
smg_comms_c_wrappers 32 static int
smg_comms_c_wrappers 33 build_index( MPI *exparray, int k, int i, int t )
smg_comms_c_wrappers 34 {
smg_comms_c_wrappers 35 int j, bitno;
smg_comms_c_wrappers 36 int idx = 0;
smg_comms_c_wrappers 37
smg_comms_c_wrappers 38 bitno = t-i;
smg_comms_c_wrappers 39 for(j=k-1; j >= 0; j-- ) {
smg_comms_c_wrappers 40 idx <<= 1;
smg_comms_c_wrappers 41 if( mpi_test_bit( exparray[j], bitno ) )
smg_comms_c_wrappers 42 idx |= 1;
smg_comms_c_wrappers 43 }
smg_comms_c_wrappers 44 return idx;
smg_comms_c_wrappers 45 }
smg_comms_c_wrappers 46
smg_comms_c_wrappers 47
smg_comms_c_wrappers 48 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
smg_comms_c_wrappers 49 */
smg_comms_c_wrappers 50 void
smg_comms_c_wrappers 51 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
smg_comms_c_wrappers 52 {
smg_comms_c_wrappers 53 int k;
smg_comms_c_wrappers 54 int t;
smg_comms_c_wrappers 55 int i, j, idx;
smg_comms_c_wrappers 56 MPI *G;
smg_comms_c_wrappers 57 MPI tmp;
smg_comms_c_wrappers 58
smg_comms_c_wrappers 59 for(k=0; basearray[k]; k++ )
smg_comms_c_wrappers 60 ;
smg_comms_c_wrappers 61 assert(k);
smg_comms_c_wrappers 62 for(t=0, i=0; (tmp=exparray[i]); i++ ) {
smg_comms_c_wrappers 63 j = mpi_get_nbits(tmp);
smg_comms_c_wrappers 64 if( j > t )
smg_comms_c_wrappers 65 t = j;
smg_comms_c_wrappers 66 }
smg_comms_c_wrappers 67 assert(i==k);
smg_comms_c_wrappers 68 assert(t);
smg_comms_c_wrappers 69 assert( k < 10 );
smg_comms_c_wrappers 70
smg_comms_c_wrappers 71 G = xmalloc_clear( (1<<k) * sizeof *G );
smg_comms_c_wrappers 72
smg_comms_c_wrappers 73 tmp = mpi_alloc( mpi_get_nlimbs(m)+1 );
smg_comms_c_wrappers 74 mpi_set_ui( res, 1 );
smg_comms_c_wrappers 75 for(i = 1; i <= t; i++ ) {
smg_comms_c_wrappers 76 mpi_mulm(tmp, res, res, m );
smg_comms_c_wrappers 77 idx = build_index( exparray, k, i, t );
smg_comms_c_wrappers 78 assert( idx >= 0 && idx < (1<<k) );
smg_comms_c_wrappers 79 if( !G[idx] ) {
smg_comms_c_wrappers 80 if( !idx )
smg_comms_c_wrappers 81 G[0] = mpi_alloc_set_ui( 1 );
smg_comms_c_wrappers 82 else {
smg_comms_c_wrappers 83 for(j=0; j < k; j++ ) {
smg_comms_c_wrappers 84 if( (idx & (1<<j) ) ) {
smg_comms_c_wrappers 85 if( !G[idx] )
smg_comms_c_wrappers 86 G[idx] = mpi_copy( basearray[j] );
smg_comms_c_wrappers 87 else
smg_comms_c_wrappers 88 mpi_mulm( G[idx], G[idx], basearray[j], m );
smg_comms_c_wrappers 89 }
smg_comms_c_wrappers 90 }
smg_comms_c_wrappers 91 if( !G[idx] )
smg_comms_c_wrappers 92 G[idx] = mpi_alloc(0);
smg_comms_c_wrappers 93 }
smg_comms_c_wrappers 94 }
smg_comms_c_wrappers 95 mpi_mulm(res, tmp, G[idx], m );
smg_comms_c_wrappers 96 }
smg_comms_c_wrappers 97
smg_comms_c_wrappers 98
smg_comms_c_wrappers 99 mpi_free(tmp);
smg_comms_c_wrappers 100 for(i=0; i < (1<<k); i++ )
smg_comms_c_wrappers 101 mpi_free(G[i]);
smg_comms_c_wrappers 102 xfree(G);
smg_comms_c_wrappers 103 }