1/* mpi-mpow.c  -  MPI functions
  2 * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
  3 *
  4 * This file is part of GnuPG.
  5 *
  6 * GnuPG is free software; you can redistribute it and/or modify
  7 * it under the terms of the GNU General Public License as published by
  8 * the Free Software Foundation; either version 2 of the License, or
  9 * (at your option) any later version.
 10 *
 11 * GnuPG is distributed in the hope that it will be useful,
 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 14 * GNU General Public License for more details.
 15 *
 16 * You should have received a copy of the GNU General Public License
 17 * along with this program; if not, write to the Free Software
 18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
 19 */
 20
 21#include "mpi-internal.h"
 22#include "longlong.h"
 23
 24static int build_index(const MPI *exparray, int k, int i, int t)
 25{
 26	int j, bitno;
 27	int index = 0;
 28
 29	bitno = t - i;
 30	for (j = k - 1; j >= 0; j--) {
 31		index <<= 1;
 32		if (mpi_test_bit(exparray[j], bitno))
 33			index |= 1;
 34	}
 35	return index;
 36}
 37
 38/****************
 39 * RES = (BASE[0] ^ EXP[0]) *  (BASE[1] ^ EXP[1]) * ... * mod M
 40 */
 41int mpi_mulpowm(MPI res, MPI *basearray, MPI *exparray, MPI m)
 42{
 43	int rc = -ENOMEM;
 44	int k;			/* number of elements */
 45	int t;			/* bit size of largest exponent */
 46	int i, j, idx;
 47	MPI *G = NULL;		/* table with precomputed values of size 2^k */
 48	MPI tmp = NULL;
 49
 50	for (k = 0; basearray[k]; k++)
 51		;
 52	if (!k) {
 53		pr_emerg("mpi_mulpowm: assert(k) failed\n");
 54		BUG();
 55	}
 56	for (t = 0, i = 0; (tmp = exparray[i]); i++) {
 57		j = mpi_get_nbits(tmp);
 58		if (j > t)
 59			t = j;
 60	}
 61	if (i != k) {
 62		pr_emerg("mpi_mulpowm: assert(i==k) failed\n");
 63		BUG();
 64	}
 65	if (!t) {
 66		pr_emerg("mpi_mulpowm: assert(t) failed\n");
 67		BUG();
 68	}
 69	if (k >= 10) {
 70		pr_emerg("mpi_mulpowm: assert(k<10) failed\n");
 71		BUG();
 72	}
 73
 74	G = kzalloc((1 << k) * sizeof *G, GFP_KERNEL);
 75	if (!G)
 76		goto err_out;
 77
 78	/* and calculate */
 79	tmp = mpi_alloc(mpi_get_nlimbs(m) + 1);
 80	if (!tmp)
 81		goto nomem;
 82	if (mpi_set_ui(res, 1) < 0)
 83		goto nomem;
 84	for (i = 1; i <= t; i++) {
 85		if (mpi_mulm(tmp, res, res, m) < 0)
 86			goto nomem;
 87		idx = build_index(exparray, k, i, t);
 88		if (!(idx >= 0 && idx < (1 << k))) {
 89			pr_emerg("mpi_mulpowm: assert(idx >= 0 && idx < (1<<k)) failed\n");
 90			BUG();
 91		}
 92		if (!G[idx]) {
 93			if (!idx) {
 94				G[0] = mpi_alloc_set_ui(1);
 95				if (!G[0])
 96					goto nomem;
 97			} else {
 98				for (j = 0; j < k; j++) {
 99					if ((idx & (1 << j))) {
100						if (!G[idx]) {
101							if (mpi_copy
102							    (&G[idx],
103							     basearray[j]) < 0)
104								goto nomem;
105						} else {
106							if (mpi_mulm
107							    (G[idx], G[idx],
108							     basearray[j],
109							     m) < 0)
110								goto nomem;
111						}
112					}
113				}
114				if (!G[idx]) {
115					G[idx] = mpi_alloc(0);
116					if (!G[idx])
117						goto nomem;
118				}
119			}
120		}
121		if (mpi_mulm(res, tmp, G[idx], m) < 0)
122			goto nomem;
123	}
124
125	rc = 0;
126nomem:
127	/* cleanup */
128	mpi_free(tmp);
129	for (i = 0; i < (1 << k); i++)
130		mpi_free(G[i]);
131	kfree(G);
132err_out:
133	return rc;
134}