-
+ 221190B0F2BADE0E8F32E7ABB9A0CDA81A2B15A0ABE6AB54596B4823C41149EBB93338FA4CE7C6C4809618A53A173003F7FEBD510F188509E0D7FDD466596130smg_comms/mpi/mpi-mpow.c(0 . 0)(1 . 103)
4727 /* mpi-mpow.c - MPI functions
4728 * Modified by No Such Labs. (C) 2015. See README.
4729 *
4730 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
4731 * SHA256(gnupg-1.4.10.tar.gz):
4732 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
4733 * (C) 1994-2005 Free Software Foundation, Inc.
4734 *
4735 * This program is free software: you can redistribute it and/or modify
4736 * it under the terms of the GNU General Public License as published by
4737 * the Free Software Foundation, either version 3 of the License, or
4738 * (at your option) any later version.
4739 *
4740 * This program is distributed in the hope that it will be useful,
4741 * but WITHOUT ANY WARRANTY; without even the implied warranty of
4742 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4743 * GNU General Public License for more details.
4744 *
4745 * You should have received a copy of the GNU General Public License
4746 * along with this program. If not, see <http://www.gnu.org/licenses/>.
4747 */
4748
4749 #include <stdio.h>
4750 #include <stdlib.h>
4751 #include <assert.h>
4752
4753 #include "knobs.h"
4754 #include "mpi-internal.h"
4755 #include "longlong.h"
4756
4757
4758 static int
4759 build_index( MPI *exparray, int k, int i, int t )
4760 {
4761 int j, bitno;
4762 int idx = 0;
4763
4764 bitno = t-i;
4765 for(j=k-1; j >= 0; j-- ) {
4766 idx <<= 1;
4767 if( mpi_test_bit( exparray[j], bitno ) )
4768 idx |= 1;
4769 }
4770 return idx;
4771 }
4772
4773 /****************
4774 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
4775 */
4776 void
4777 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
4778 {
4779 int k; /* number of elements */
4780 int t; /* bit size of largest exponent */
4781 int i, j, idx;
4782 MPI *G; /* table with precomputed values of size 2^k */
4783 MPI tmp;
4784
4785 for(k=0; basearray[k]; k++ )
4786 ;
4787 assert(k);
4788 for(t=0, i=0; (tmp=exparray[i]); i++ ) {
4789 j = mpi_get_nbits(tmp);
4790 if( j > t )
4791 t = j;
4792 }
4793 assert(i==k);
4794 assert(t);
4795 assert( k < 10 );
4796
4797 G = xmalloc_clear( (1<<k) * sizeof *G );
4798 /* and calculate */
4799 tmp = mpi_alloc( mpi_get_nlimbs(m)+1 );
4800 mpi_set_ui( res, 1 );
4801 for(i = 1; i <= t; i++ ) {
4802 mpi_mulm(tmp, res, res, m );
4803 idx = build_index( exparray, k, i, t );
4804 assert( idx >= 0 && idx < (1<<k) );
4805 if( !G[idx] ) {
4806 if( !idx )
4807 G[0] = mpi_alloc_set_ui( 1 );
4808 else {
4809 for(j=0; j < k; j++ ) {
4810 if( (idx & (1<<j) ) ) {
4811 if( !G[idx] )
4812 G[idx] = mpi_copy( basearray[j] );
4813 else
4814 mpi_mulm( G[idx], G[idx], basearray[j], m );
4815 }
4816 }
4817 if( !G[idx] )
4818 G[idx] = mpi_alloc(0);
4819 }
4820 }
4821 mpi_mulm(res, tmp, G[idx], m );
4822 }
4823
4824 /* cleanup */
4825 mpi_free(tmp);
4826 for(i=0; i < (1<<k); i++ )
4827 mpi_free(G[i]);
4828 xfree(G);
4829 }