Merge branch 'for-linus' of git://selinuxproject.org/~jmorris/linux-security
[linux-3.10.git] / lib / mpi / mpi-mpow.c
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
24 static 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  */
41 int 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;
126 nomem:
127         /* cleanup */
128         mpi_free(tmp);
129         for (i = 0; i < (1 << k); i++)
130                 mpi_free(G[i]);
131         kfree(G);
132 err_out:
133         return rc;
134 }