aboutsummaryrefslogtreecommitdiffstats
path: root/lib/mpi/mpi-mpow.c
diff options
context:
space:
mode:
authorKonrad Rzeszutek Wilk <konrad.wilk@oracle.com>2012-01-27 11:14:02 -0500
committerKonrad Rzeszutek Wilk <konrad.wilk@oracle.com>2012-01-27 11:14:02 -0500
commit6c02b7b1610f873888af20f291c07730889ff0f9 (patch)
tree1b33e6642cc81605b8d37c0bda0abff0ba64fa2d /lib/mpi/mpi-mpow.c
parent7a7546b377bdaa25ac77f33d9433c59f259b9688 (diff)
parentdcd6c92267155e70a94b3927bce681ce74b80d1f (diff)
Merge commit 'v3.3-rc1' into stable/for-linus-fixes-3.3
* commit 'v3.3-rc1': (9775 commits) Linux 3.3-rc1 x86, syscall: Need __ARCH_WANT_SYS_IPC for 32 bits qnx4: don't leak ->BitMap on late failure exits qnx4: reduce the insane nesting in qnx4_checkroot() qnx4: di_fname is an array, for crying out loud... KEYS: Permit key_serial() to be called with a const key pointer keys: fix user_defined key sparse messages ima: fix cred sparse warning uml: fix compile for x86-64 MPILIB: Add a missing ENOMEM check tpm: fix (ACPI S3) suspend regression nvme: fix merge error due to change of 'make_request_fn' fn type xen: using EXPORT_SYMBOL requires including export.h gpio: tps65910: Use correct offset for gpio initialization acpi/apei/einj: Add extensions to EINJ from rev 5.0 of acpi spec intel_idle: Split up and provide per CPU initialization func ACPI processor: Remove unneeded variable passed by acpi_processor_hotadd_init V2 tg3: Fix single-vector MSI-X code openvswitch: Fix multipart datapath dumps. ipv6: fix per device IP snmp counters ...
Diffstat (limited to 'lib/mpi/mpi-mpow.c')
-rw-r--r--lib/mpi/mpi-mpow.c134
1 files changed, 134 insertions, 0 deletions
diff --git a/lib/mpi/mpi-mpow.c b/lib/mpi/mpi-mpow.c
new file mode 100644
index 000000000000..7328d0d6c748
--- /dev/null
+++ b/lib/mpi/mpi-mpow.c
@@ -0,0 +1,134 @@
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}