diff options
author | Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> | 2012-01-27 11:14:02 -0500 |
---|---|---|
committer | Konrad Rzeszutek Wilk <konrad.wilk@oracle.com> | 2012-01-27 11:14:02 -0500 |
commit | 6c02b7b1610f873888af20f291c07730889ff0f9 (patch) | |
tree | 1b33e6642cc81605b8d37c0bda0abff0ba64fa2d /lib/mpi/mpi-mpow.c | |
parent | 7a7546b377bdaa25ac77f33d9433c59f259b9688 (diff) | |
parent | dcd6c92267155e70a94b3927bce681ce74b80d1f (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.c | 134 |
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 | |||
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 | } | ||