diff options
author | Dmitry Kasatkin <dmitry.kasatkin@intel.com> | 2011-11-07 08:16:37 -0500 |
---|---|---|
committer | Dmitry Kasatkin <dmitry.kasatkin@intel.com> | 2011-11-09 04:47:26 -0500 |
commit | 7e8dec918ef8e0f68b4937c3c50fa57002077a4d (patch) | |
tree | a17d33fa54fcb18c335b36c4550b889b206015f4 /lib/mpi | |
parent | d9c46b184fcfd33c85a7dc48a653435a08e21f56 (diff) |
crypto: GnuPG based MPI lib - additional sources (part 4)
Adds the multi-precision-integer maths library which was originally taken
from GnuPG and ported to the kernel by (among others) David Howells.
This version is taken from Fedora kernel 2.6.32-71.14.1.el6.
The difference is that checkpatch reported errors and warnings have been fixed.
This library is used to implemenet RSA digital signature verification
used in IMA/EVM integrity protection subsystem.
Due to patch size limitation, the patch is divided into 4 parts.
This code is unnecessary for RSA digital signature verification,
but for completeness it is included here and can be compiled,
if CONFIG_MPILIB_EXTRA is enabled.
Signed-off-by: Dmitry Kasatkin <dmitry.kasatkin@intel.com>
Diffstat (limited to 'lib/mpi')
-rw-r--r-- | lib/mpi/Makefile | 11 | ||||
-rw-r--r-- | lib/mpi/generic_mpi-asm-defs.h | 4 | ||||
-rw-r--r-- | lib/mpi/mpi-add.c | 234 | ||||
-rw-r--r-- | lib/mpi/mpi-cmp.c | 68 | ||||
-rw-r--r-- | lib/mpi/mpi-div.c | 333 | ||||
-rw-r--r-- | lib/mpi/mpi-gcd.c | 59 | ||||
-rw-r--r-- | lib/mpi/mpi-inline.c | 31 | ||||
-rw-r--r-- | lib/mpi/mpi-inv.c | 187 | ||||
-rw-r--r-- | lib/mpi/mpi-mpow.c | 133 | ||||
-rw-r--r-- | lib/mpi/mpi-mul.c | 194 | ||||
-rw-r--r-- | lib/mpi/mpi-scan.c | 136 |
11 files changed, 1390 insertions, 0 deletions
diff --git a/lib/mpi/Makefile b/lib/mpi/Makefile index 45ca90a8639c..567d52e74d77 100644 --- a/lib/mpi/Makefile +++ b/lib/mpi/Makefile | |||
@@ -19,3 +19,14 @@ mpi-y = \ | |||
19 | mpih-mul.o \ | 19 | mpih-mul.o \ |
20 | mpi-pow.o \ | 20 | mpi-pow.o \ |
21 | mpiutil.o | 21 | mpiutil.o |
22 | |||
23 | mpi-$(CONFIG_MPILIB_EXTRA) += \ | ||
24 | mpi-add.o \ | ||
25 | mpi-div.o \ | ||
26 | mpi-cmp.o \ | ||
27 | mpi-gcd.o \ | ||
28 | mpi-inline.o \ | ||
29 | mpi-inv.o \ | ||
30 | mpi-mpow.o \ | ||
31 | mpi-mul.o \ | ||
32 | mpi-scan.o | ||
diff --git a/lib/mpi/generic_mpi-asm-defs.h b/lib/mpi/generic_mpi-asm-defs.h new file mode 100644 index 000000000000..047d1f5a7249 --- /dev/null +++ b/lib/mpi/generic_mpi-asm-defs.h | |||
@@ -0,0 +1,4 @@ | |||
1 | /* This file defines some basic constants for the MPI machinery. We | ||
2 | * need to define the types on a per-CPU basis, so it is done with | ||
3 | * this file here. */ | ||
4 | #define BYTES_PER_MPI_LIMB (SIZEOF_UNSIGNED_LONG) | ||
diff --git a/lib/mpi/mpi-add.c b/lib/mpi/mpi-add.c new file mode 100644 index 000000000000..f56b9ba295e6 --- /dev/null +++ b/lib/mpi/mpi-add.c | |||
@@ -0,0 +1,234 @@ | |||
1 | /* mpi-add.c - MPI functions | ||
2 | * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. | ||
3 | * Copyright (C) 1994, 1996 Free Software Foundation, Inc. | ||
4 | * | ||
5 | * This file is part of GnuPG. | ||
6 | * | ||
7 | * GnuPG is free software; you can redistribute it and/or modify | ||
8 | * it under the terms of the GNU General Public License as published by | ||
9 | * the Free Software Foundation; either version 2 of the License, or | ||
10 | * (at your option) any later version. | ||
11 | * | ||
12 | * GnuPG is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
15 | * GNU General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU General Public License | ||
18 | * along with this program; if not, write to the Free Software | ||
19 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA | ||
20 | * | ||
21 | * Note: This code is heavily based on the GNU MP Library. | ||
22 | * Actually it's the same code with only minor changes in the | ||
23 | * way the data is stored; this is to support the abstraction | ||
24 | * of an optional secure memory allocation which may be used | ||
25 | * to avoid revealing of sensitive data due to paging etc. | ||
26 | * The GNU MP Library itself is published under the LGPL; | ||
27 | * however I decided to publish this code under the plain GPL. | ||
28 | */ | ||
29 | |||
30 | #include "mpi-internal.h" | ||
31 | |||
32 | /**************** | ||
33 | * Add the unsigned integer V to the mpi-integer U and store the | ||
34 | * result in W. U and V may be the same. | ||
35 | */ | ||
36 | int mpi_add_ui(MPI w, const MPI u, unsigned long v) | ||
37 | { | ||
38 | mpi_ptr_t wp, up; | ||
39 | mpi_size_t usize, wsize; | ||
40 | int usign, wsign; | ||
41 | |||
42 | usize = u->nlimbs; | ||
43 | usign = u->sign; | ||
44 | wsign = 0; | ||
45 | |||
46 | /* If not space for W (and possible carry), increase space. */ | ||
47 | wsize = usize + 1; | ||
48 | if (w->alloced < wsize) | ||
49 | if (mpi_resize(w, wsize) < 0) | ||
50 | return -ENOMEM; | ||
51 | |||
52 | /* These must be after realloc (U may be the same as W). */ | ||
53 | up = u->d; | ||
54 | wp = w->d; | ||
55 | |||
56 | if (!usize) { /* simple */ | ||
57 | wp[0] = v; | ||
58 | wsize = v ? 1 : 0; | ||
59 | } else if (!usign) { /* mpi is not negative */ | ||
60 | mpi_limb_t cy; | ||
61 | cy = mpihelp_add_1(wp, up, usize, v); | ||
62 | wp[usize] = cy; | ||
63 | wsize = usize + cy; | ||
64 | } else { /* The signs are different. Need exact comparison to determine | ||
65 | * which operand to subtract from which. */ | ||
66 | if (usize == 1 && up[0] < v) { | ||
67 | wp[0] = v - up[0]; | ||
68 | wsize = 1; | ||
69 | } else { | ||
70 | mpihelp_sub_1(wp, up, usize, v); | ||
71 | /* Size can decrease with at most one limb. */ | ||
72 | wsize = usize - (wp[usize - 1] == 0); | ||
73 | wsign = 1; | ||
74 | } | ||
75 | } | ||
76 | |||
77 | w->nlimbs = wsize; | ||
78 | w->sign = wsign; | ||
79 | return 0; | ||
80 | } | ||
81 | |||
82 | int mpi_add(MPI w, MPI u, MPI v) | ||
83 | { | ||
84 | mpi_ptr_t wp, up, vp; | ||
85 | mpi_size_t usize, vsize, wsize; | ||
86 | int usign, vsign, wsign; | ||
87 | |||
88 | if (u->nlimbs < v->nlimbs) { /* Swap U and V. */ | ||
89 | usize = v->nlimbs; | ||
90 | usign = v->sign; | ||
91 | vsize = u->nlimbs; | ||
92 | vsign = u->sign; | ||
93 | wsize = usize + 1; | ||
94 | if (RESIZE_IF_NEEDED(w, wsize) < 0) | ||
95 | return -ENOMEM; | ||
96 | /* These must be after realloc (u or v may be the same as w). */ | ||
97 | up = v->d; | ||
98 | vp = u->d; | ||
99 | } else { | ||
100 | usize = u->nlimbs; | ||
101 | usign = u->sign; | ||
102 | vsize = v->nlimbs; | ||
103 | vsign = v->sign; | ||
104 | wsize = usize + 1; | ||
105 | if (RESIZE_IF_NEEDED(w, wsize) < 0) | ||
106 | return -ENOMEM; | ||
107 | /* These must be after realloc (u or v may be the same as w). */ | ||
108 | up = u->d; | ||
109 | vp = v->d; | ||
110 | } | ||
111 | wp = w->d; | ||
112 | wsign = 0; | ||
113 | |||
114 | if (!vsize) { /* simple */ | ||
115 | MPN_COPY(wp, up, usize); | ||
116 | wsize = usize; | ||
117 | wsign = usign; | ||
118 | } else if (usign != vsign) { /* different sign */ | ||
119 | /* This test is right since USIZE >= VSIZE */ | ||
120 | if (usize != vsize) { | ||
121 | mpihelp_sub(wp, up, usize, vp, vsize); | ||
122 | wsize = usize; | ||
123 | MPN_NORMALIZE(wp, wsize); | ||
124 | wsign = usign; | ||
125 | } else if (mpihelp_cmp(up, vp, usize) < 0) { | ||
126 | mpihelp_sub_n(wp, vp, up, usize); | ||
127 | wsize = usize; | ||
128 | MPN_NORMALIZE(wp, wsize); | ||
129 | if (!usign) | ||
130 | wsign = 1; | ||
131 | } else { | ||
132 | mpihelp_sub_n(wp, up, vp, usize); | ||
133 | wsize = usize; | ||
134 | MPN_NORMALIZE(wp, wsize); | ||
135 | if (usign) | ||
136 | wsign = 1; | ||
137 | } | ||
138 | } else { /* U and V have same sign. Add them. */ | ||
139 | mpi_limb_t cy = mpihelp_add(wp, up, usize, vp, vsize); | ||
140 | wp[usize] = cy; | ||
141 | wsize = usize + cy; | ||
142 | if (usign) | ||
143 | wsign = 1; | ||
144 | } | ||
145 | |||
146 | w->nlimbs = wsize; | ||
147 | w->sign = wsign; | ||
148 | return 0; | ||
149 | } | ||
150 | |||
151 | /**************** | ||
152 | * Subtract the unsigned integer V from the mpi-integer U and store the | ||
153 | * result in W. | ||
154 | */ | ||
155 | int mpi_sub_ui(MPI w, MPI u, unsigned long v) | ||
156 | { | ||
157 | mpi_ptr_t wp, up; | ||
158 | mpi_size_t usize, wsize; | ||
159 | int usign, wsign; | ||
160 | |||
161 | usize = u->nlimbs; | ||
162 | usign = u->sign; | ||
163 | wsign = 0; | ||
164 | |||
165 | /* If not space for W (and possible carry), increase space. */ | ||
166 | wsize = usize + 1; | ||
167 | if (w->alloced < wsize) | ||
168 | if (mpi_resize(w, wsize) < 0) | ||
169 | return -ENOMEM; | ||
170 | |||
171 | /* These must be after realloc (U may be the same as W). */ | ||
172 | up = u->d; | ||
173 | wp = w->d; | ||
174 | |||
175 | if (!usize) { /* simple */ | ||
176 | wp[0] = v; | ||
177 | wsize = v ? 1 : 0; | ||
178 | wsign = 1; | ||
179 | } else if (usign) { /* mpi and v are negative */ | ||
180 | mpi_limb_t cy; | ||
181 | cy = mpihelp_add_1(wp, up, usize, v); | ||
182 | wp[usize] = cy; | ||
183 | wsize = usize + cy; | ||
184 | } else { /* The signs are different. Need exact comparison to determine | ||
185 | * which operand to subtract from which. */ | ||
186 | if (usize == 1 && up[0] < v) { | ||
187 | wp[0] = v - up[0]; | ||
188 | wsize = 1; | ||
189 | wsign = 1; | ||
190 | } else { | ||
191 | mpihelp_sub_1(wp, up, usize, v); | ||
192 | /* Size can decrease with at most one limb. */ | ||
193 | wsize = usize - (wp[usize - 1] == 0); | ||
194 | } | ||
195 | } | ||
196 | |||
197 | w->nlimbs = wsize; | ||
198 | w->sign = wsign; | ||
199 | return 0; | ||
200 | } | ||
201 | |||
202 | int mpi_sub(MPI w, MPI u, MPI v) | ||
203 | { | ||
204 | int rc; | ||
205 | |||
206 | if (w == v) { | ||
207 | MPI vv; | ||
208 | if (mpi_copy(&vv, v) < 0) | ||
209 | return -ENOMEM; | ||
210 | vv->sign = !vv->sign; | ||
211 | rc = mpi_add(w, u, vv); | ||
212 | mpi_free(vv); | ||
213 | } else { | ||
214 | /* fixme: this is not thread-save (we temp. modify v) */ | ||
215 | v->sign = !v->sign; | ||
216 | rc = mpi_add(w, u, v); | ||
217 | v->sign = !v->sign; | ||
218 | } | ||
219 | return rc; | ||
220 | } | ||
221 | |||
222 | int mpi_addm(MPI w, MPI u, MPI v, MPI m) | ||
223 | { | ||
224 | if (mpi_add(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0) | ||
225 | return -ENOMEM; | ||
226 | return 0; | ||
227 | } | ||
228 | |||
229 | int mpi_subm(MPI w, MPI u, MPI v, MPI m) | ||
230 | { | ||
231 | if (mpi_sub(w, u, v) < 0 || mpi_fdiv_r(w, w, m) < 0) | ||
232 | return -ENOMEM; | ||
233 | return 0; | ||
234 | } | ||
diff --git a/lib/mpi/mpi-cmp.c b/lib/mpi/mpi-cmp.c new file mode 100644 index 000000000000..914bc42a8a80 --- /dev/null +++ b/lib/mpi/mpi-cmp.c | |||
@@ -0,0 +1,68 @@ | |||
1 | /* mpi-cmp.c - MPI functions | ||
2 | * Copyright (C) 1998, 1999 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 | |||
23 | int mpi_cmp_ui(MPI u, unsigned long v) | ||
24 | { | ||
25 | mpi_limb_t limb = v; | ||
26 | |||
27 | mpi_normalize(u); | ||
28 | if (!u->nlimbs && !limb) | ||
29 | return 0; | ||
30 | if (u->sign) | ||
31 | return -1; | ||
32 | if (u->nlimbs > 1) | ||
33 | return 1; | ||
34 | |||
35 | if (u->d[0] == limb) | ||
36 | return 0; | ||
37 | else if (u->d[0] > limb) | ||
38 | return 1; | ||
39 | else | ||
40 | return -1; | ||
41 | } | ||
42 | |||
43 | int mpi_cmp(MPI u, MPI v) | ||
44 | { | ||
45 | mpi_size_t usize, vsize; | ||
46 | int cmp; | ||
47 | |||
48 | mpi_normalize(u); | ||
49 | mpi_normalize(v); | ||
50 | usize = u->nlimbs; | ||
51 | vsize = v->nlimbs; | ||
52 | if (!u->sign && v->sign) | ||
53 | return 1; | ||
54 | if (u->sign && !v->sign) | ||
55 | return -1; | ||
56 | if (usize != vsize && !u->sign && !v->sign) | ||
57 | return usize - vsize; | ||
58 | if (usize != vsize && u->sign && v->sign) | ||
59 | return vsize + usize; | ||
60 | if (!usize) | ||
61 | return 0; | ||
62 | cmp = mpihelp_cmp(u->d, v->d, usize); | ||
63 | if (!cmp) | ||
64 | return 0; | ||
65 | if ((cmp < 0 ? 1 : 0) == (u->sign ? 1 : 0)) | ||
66 | return 1; | ||
67 | return -1; | ||
68 | } | ||
diff --git a/lib/mpi/mpi-div.c b/lib/mpi/mpi-div.c new file mode 100644 index 000000000000..c3087d1390ce --- /dev/null +++ b/lib/mpi/mpi-div.c | |||
@@ -0,0 +1,333 @@ | |||
1 | /* mpi-div.c - MPI functions | ||
2 | * Copyright (C) 1994, 1996 Free Software Foundation, Inc. | ||
3 | * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. | ||
4 | * | ||
5 | * This file is part of GnuPG. | ||
6 | * | ||
7 | * GnuPG is free software; you can redistribute it and/or modify | ||
8 | * it under the terms of the GNU General Public License as published by | ||
9 | * the Free Software Foundation; either version 2 of the License, or | ||
10 | * (at your option) any later version. | ||
11 | * | ||
12 | * GnuPG is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
15 | * GNU General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU General Public License | ||
18 | * along with this program; if not, write to the Free Software | ||
19 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA | ||
20 | * | ||
21 | * Note: This code is heavily based on the GNU MP Library. | ||
22 | * Actually it's the same code with only minor changes in the | ||
23 | * way the data is stored; this is to support the abstraction | ||
24 | * of an optional secure memory allocation which may be used | ||
25 | * to avoid revealing of sensitive data due to paging etc. | ||
26 | * The GNU MP Library itself is published under the LGPL; | ||
27 | * however I decided to publish this code under the plain GPL. | ||
28 | */ | ||
29 | |||
30 | #include <linux/string.h> | ||
31 | #include "mpi-internal.h" | ||
32 | #include "longlong.h" | ||
33 | |||
34 | int mpi_fdiv_r(MPI rem, MPI dividend, MPI divisor) | ||
35 | { | ||
36 | int rc = -ENOMEM; | ||
37 | int divisor_sign = divisor->sign; | ||
38 | MPI temp_divisor = NULL; | ||
39 | |||
40 | /* We need the original value of the divisor after the remainder has been | ||
41 | * preliminary calculated. We have to copy it to temporary space if it's | ||
42 | * the same variable as REM. */ | ||
43 | if (rem == divisor) { | ||
44 | if (mpi_copy(&temp_divisor, divisor) < 0) | ||
45 | goto nomem; | ||
46 | divisor = temp_divisor; | ||
47 | } | ||
48 | |||
49 | if (mpi_tdiv_qr(NULL, rem, dividend, divisor) < 0) | ||
50 | goto nomem; | ||
51 | if (((divisor_sign ? 1 : 0) ^ (dividend->sign ? 1 : 0)) && rem->nlimbs) | ||
52 | if (mpi_add(rem, rem, divisor) < 0) | ||
53 | goto nomem; | ||
54 | |||
55 | rc = 0; | ||
56 | |||
57 | nomem: | ||
58 | if (temp_divisor) | ||
59 | mpi_free(temp_divisor); | ||
60 | return rc; | ||
61 | } | ||
62 | |||
63 | /**************** | ||
64 | * Division rounding the quotient towards -infinity. | ||
65 | * The remainder gets the same sign as the denominator. | ||
66 | * rem is optional | ||
67 | */ | ||
68 | |||
69 | ulong mpi_fdiv_r_ui(MPI rem, MPI dividend, ulong divisor) | ||
70 | { | ||
71 | mpi_limb_t rlimb; | ||
72 | |||
73 | rlimb = mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor); | ||
74 | if (rlimb && dividend->sign) | ||
75 | rlimb = divisor - rlimb; | ||
76 | |||
77 | if (rem) { | ||
78 | rem->d[0] = rlimb; | ||
79 | rem->nlimbs = rlimb ? 1 : 0; | ||
80 | } | ||
81 | return rlimb; | ||
82 | } | ||
83 | |||
84 | int mpi_fdiv_q(MPI quot, MPI dividend, MPI divisor) | ||
85 | { | ||
86 | MPI tmp = mpi_alloc(mpi_get_nlimbs(quot)); | ||
87 | if (!tmp) | ||
88 | return -ENOMEM; | ||
89 | mpi_fdiv_qr(quot, tmp, dividend, divisor); | ||
90 | mpi_free(tmp); | ||
91 | return 0; | ||
92 | } | ||
93 | |||
94 | int mpi_fdiv_qr(MPI quot, MPI rem, MPI dividend, MPI divisor) | ||
95 | { | ||
96 | int divisor_sign = divisor->sign; | ||
97 | MPI temp_divisor = NULL; | ||
98 | |||
99 | if (quot == divisor || rem == divisor) { | ||
100 | if (mpi_copy(&temp_divisor, divisor) < 0) | ||
101 | return -ENOMEM; | ||
102 | divisor = temp_divisor; | ||
103 | } | ||
104 | |||
105 | if (mpi_tdiv_qr(quot, rem, dividend, divisor) < 0) | ||
106 | goto nomem; | ||
107 | |||
108 | if ((divisor_sign ^ dividend->sign) && rem->nlimbs) { | ||
109 | if (mpi_sub_ui(quot, quot, 1) < 0) | ||
110 | goto nomem; | ||
111 | if (mpi_add(rem, rem, divisor) < 0) | ||
112 | goto nomem; | ||
113 | } | ||
114 | |||
115 | if (temp_divisor) | ||
116 | mpi_free(temp_divisor); | ||
117 | |||
118 | return 0; | ||
119 | |||
120 | nomem: | ||
121 | mpi_free(temp_divisor); | ||
122 | return -ENOMEM; | ||
123 | } | ||
124 | |||
125 | /* If den == quot, den needs temporary storage. | ||
126 | * If den == rem, den needs temporary storage. | ||
127 | * If num == quot, num needs temporary storage. | ||
128 | * If den has temporary storage, it can be normalized while being copied, | ||
129 | * i.e no extra storage should be allocated. | ||
130 | */ | ||
131 | |||
132 | int mpi_tdiv_r(MPI rem, MPI num, MPI den) | ||
133 | { | ||
134 | return mpi_tdiv_qr(NULL, rem, num, den); | ||
135 | } | ||
136 | |||
137 | int mpi_tdiv_qr(MPI quot, MPI rem, MPI num, MPI den) | ||
138 | { | ||
139 | int rc = -ENOMEM; | ||
140 | mpi_ptr_t np, dp; | ||
141 | mpi_ptr_t qp, rp; | ||
142 | mpi_size_t nsize = num->nlimbs; | ||
143 | mpi_size_t dsize = den->nlimbs; | ||
144 | mpi_size_t qsize, rsize; | ||
145 | mpi_size_t sign_remainder = num->sign; | ||
146 | mpi_size_t sign_quotient = num->sign ^ den->sign; | ||
147 | unsigned normalization_steps; | ||
148 | mpi_limb_t q_limb; | ||
149 | mpi_ptr_t marker[5]; | ||
150 | int markidx = 0; | ||
151 | |||
152 | memset(marker, 0, sizeof(marker)); | ||
153 | |||
154 | /* Ensure space is enough for quotient and remainder. | ||
155 | * We need space for an extra limb in the remainder, because it's | ||
156 | * up-shifted (normalized) below. */ | ||
157 | rsize = nsize + 1; | ||
158 | if (mpi_resize(rem, rsize) < 0) | ||
159 | goto nomem; | ||
160 | |||
161 | qsize = rsize - dsize; /* qsize cannot be bigger than this. */ | ||
162 | if (qsize <= 0) { | ||
163 | if (num != rem) { | ||
164 | rem->nlimbs = num->nlimbs; | ||
165 | rem->sign = num->sign; | ||
166 | MPN_COPY(rem->d, num->d, nsize); | ||
167 | } | ||
168 | if (quot) { | ||
169 | /* This needs to follow the assignment to rem, in case the | ||
170 | * numerator and quotient are the same. */ | ||
171 | quot->nlimbs = 0; | ||
172 | quot->sign = 0; | ||
173 | } | ||
174 | return 0; | ||
175 | } | ||
176 | |||
177 | if (quot) | ||
178 | if (mpi_resize(quot, qsize) < 0) | ||
179 | goto nomem; | ||
180 | |||
181 | /* Read pointers here, when reallocation is finished. */ | ||
182 | np = num->d; | ||
183 | dp = den->d; | ||
184 | rp = rem->d; | ||
185 | |||
186 | /* Optimize division by a single-limb divisor. */ | ||
187 | if (dsize == 1) { | ||
188 | mpi_limb_t rlimb; | ||
189 | if (quot) { | ||
190 | qp = quot->d; | ||
191 | rlimb = mpihelp_divmod_1(qp, np, nsize, dp[0]); | ||
192 | qsize -= qp[qsize - 1] == 0; | ||
193 | quot->nlimbs = qsize; | ||
194 | quot->sign = sign_quotient; | ||
195 | } else | ||
196 | rlimb = mpihelp_mod_1(np, nsize, dp[0]); | ||
197 | rp[0] = rlimb; | ||
198 | rsize = rlimb != 0 ? 1 : 0; | ||
199 | rem->nlimbs = rsize; | ||
200 | rem->sign = sign_remainder; | ||
201 | return 0; | ||
202 | } | ||
203 | |||
204 | if (quot) { | ||
205 | qp = quot->d; | ||
206 | /* Make sure QP and NP point to different objects. Otherwise the | ||
207 | * numerator would be gradually overwritten by the quotient limbs. */ | ||
208 | if (qp == np) { /* Copy NP object to temporary space. */ | ||
209 | np = marker[markidx++] = mpi_alloc_limb_space(nsize); | ||
210 | MPN_COPY(np, qp, nsize); | ||
211 | } | ||
212 | } else /* Put quotient at top of remainder. */ | ||
213 | qp = rp + dsize; | ||
214 | |||
215 | count_leading_zeros(normalization_steps, dp[dsize - 1]); | ||
216 | |||
217 | /* Normalize the denominator, i.e. make its most significant bit set by | ||
218 | * shifting it NORMALIZATION_STEPS bits to the left. Also shift the | ||
219 | * numerator the same number of steps (to keep the quotient the same!). | ||
220 | */ | ||
221 | if (normalization_steps) { | ||
222 | mpi_ptr_t tp; | ||
223 | mpi_limb_t nlimb; | ||
224 | |||
225 | /* Shift up the denominator setting the most significant bit of | ||
226 | * the most significant word. Use temporary storage not to clobber | ||
227 | * the original contents of the denominator. */ | ||
228 | tp = marker[markidx++] = mpi_alloc_limb_space(dsize); | ||
229 | if (!tp) | ||
230 | goto nomem; | ||
231 | mpihelp_lshift(tp, dp, dsize, normalization_steps); | ||
232 | dp = tp; | ||
233 | |||
234 | /* Shift up the numerator, possibly introducing a new most | ||
235 | * significant word. Move the shifted numerator in the remainder | ||
236 | * meanwhile. */ | ||
237 | nlimb = mpihelp_lshift(rp, np, nsize, normalization_steps); | ||
238 | if (nlimb) { | ||
239 | rp[nsize] = nlimb; | ||
240 | rsize = nsize + 1; | ||
241 | } else | ||
242 | rsize = nsize; | ||
243 | } else { | ||
244 | /* The denominator is already normalized, as required. Copy it to | ||
245 | * temporary space if it overlaps with the quotient or remainder. */ | ||
246 | if (dp == rp || (quot && (dp == qp))) { | ||
247 | mpi_ptr_t tp; | ||
248 | |||
249 | tp = marker[markidx++] = mpi_alloc_limb_space(dsize); | ||
250 | if (!tp) | ||
251 | goto nomem; | ||
252 | MPN_COPY(tp, dp, dsize); | ||
253 | dp = tp; | ||
254 | } | ||
255 | |||
256 | /* Move the numerator to the remainder. */ | ||
257 | if (rp != np) | ||
258 | MPN_COPY(rp, np, nsize); | ||
259 | |||
260 | rsize = nsize; | ||
261 | } | ||
262 | |||
263 | q_limb = mpihelp_divrem(qp, 0, rp, rsize, dp, dsize); | ||
264 | |||
265 | if (quot) { | ||
266 | qsize = rsize - dsize; | ||
267 | if (q_limb) { | ||
268 | qp[qsize] = q_limb; | ||
269 | qsize += 1; | ||
270 | } | ||
271 | |||
272 | quot->nlimbs = qsize; | ||
273 | quot->sign = sign_quotient; | ||
274 | } | ||
275 | |||
276 | rsize = dsize; | ||
277 | MPN_NORMALIZE(rp, rsize); | ||
278 | |||
279 | if (normalization_steps && rsize) { | ||
280 | mpihelp_rshift(rp, rp, rsize, normalization_steps); | ||
281 | rsize -= rp[rsize - 1] == 0 ? 1 : 0; | ||
282 | } | ||
283 | |||
284 | rem->nlimbs = rsize; | ||
285 | rem->sign = sign_remainder; | ||
286 | |||
287 | rc = 0; | ||
288 | nomem: | ||
289 | while (markidx) | ||
290 | mpi_free_limb_space(marker[--markidx]); | ||
291 | return rc; | ||
292 | } | ||
293 | |||
294 | int mpi_tdiv_q_2exp(MPI w, MPI u, unsigned count) | ||
295 | { | ||
296 | mpi_size_t usize, wsize; | ||
297 | mpi_size_t limb_cnt; | ||
298 | |||
299 | usize = u->nlimbs; | ||
300 | limb_cnt = count / BITS_PER_MPI_LIMB; | ||
301 | wsize = usize - limb_cnt; | ||
302 | if (limb_cnt >= usize) | ||
303 | w->nlimbs = 0; | ||
304 | else { | ||
305 | mpi_ptr_t wp; | ||
306 | mpi_ptr_t up; | ||
307 | |||
308 | if (RESIZE_IF_NEEDED(w, wsize) < 0) | ||
309 | return -ENOMEM; | ||
310 | wp = w->d; | ||
311 | up = u->d; | ||
312 | |||
313 | count %= BITS_PER_MPI_LIMB; | ||
314 | if (count) { | ||
315 | mpihelp_rshift(wp, up + limb_cnt, wsize, count); | ||
316 | wsize -= !wp[wsize - 1]; | ||
317 | } else { | ||
318 | MPN_COPY_INCR(wp, up + limb_cnt, wsize); | ||
319 | } | ||
320 | |||
321 | w->nlimbs = wsize; | ||
322 | } | ||
323 | return 0; | ||
324 | } | ||
325 | |||
326 | /**************** | ||
327 | * Check whether dividend is divisible by divisor | ||
328 | * (note: divisor must fit into a limb) | ||
329 | */ | ||
330 | int mpi_divisible_ui(MPI dividend, ulong divisor) | ||
331 | { | ||
332 | return !mpihelp_mod_1(dividend->d, dividend->nlimbs, divisor); | ||
333 | } | ||
diff --git a/lib/mpi/mpi-gcd.c b/lib/mpi/mpi-gcd.c new file mode 100644 index 000000000000..13c48aef9c4e --- /dev/null +++ b/lib/mpi/mpi-gcd.c | |||
@@ -0,0 +1,59 @@ | |||
1 | /* mpi-gcd.c - MPI functions | ||
2 | * Copyright (C) 1998, 1999, 2000, 2001 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 | |||
23 | /**************** | ||
24 | * Find the greatest common divisor G of A and B. | ||
25 | * Return: true if this 1, false in all other cases | ||
26 | */ | ||
27 | int mpi_gcd(MPI g, const MPI xa, const MPI xb) | ||
28 | { | ||
29 | MPI a = NULL, b = NULL; | ||
30 | |||
31 | if (mpi_copy(&a, xa) < 0) | ||
32 | goto nomem; | ||
33 | |||
34 | if (mpi_copy(&b, xb) < 0) | ||
35 | goto nomem; | ||
36 | |||
37 | /* TAOCP Vol II, 4.5.2, Algorithm A */ | ||
38 | a->sign = 0; | ||
39 | b->sign = 0; | ||
40 | while (mpi_cmp_ui(b, 0)) { | ||
41 | if (mpi_fdiv_r(g, a, b) < 0) /* g used as temorary variable */ | ||
42 | goto nomem; | ||
43 | if (mpi_set(a, b) < 0) | ||
44 | goto nomem; | ||
45 | if (mpi_set(b, g) < 0) | ||
46 | goto nomem; | ||
47 | } | ||
48 | if (mpi_set(g, a) < 0) | ||
49 | goto nomem; | ||
50 | |||
51 | mpi_free(a); | ||
52 | mpi_free(b); | ||
53 | return !mpi_cmp_ui(g, 1); | ||
54 | |||
55 | nomem: | ||
56 | mpi_free(a); | ||
57 | mpi_free(b); | ||
58 | return -ENOMEM; | ||
59 | } | ||
diff --git a/lib/mpi/mpi-inline.c b/lib/mpi/mpi-inline.c new file mode 100644 index 000000000000..654f68aeed8b --- /dev/null +++ b/lib/mpi/mpi-inline.c | |||
@@ -0,0 +1,31 @@ | |||
1 | /* mpi-inline.c | ||
2 | * Copyright (C) 1999, 2000, 2001 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 | /* put the inline functions as real functions into the lib */ | ||
22 | #define G10_MPI_INLINE_DECL | ||
23 | |||
24 | #include "mpi-internal.h" | ||
25 | |||
26 | /* always include the header becuase it is only | ||
27 | * included by mpi-internal if __GCC__ is defined but we | ||
28 | * need it here in all cases and the above definition of | ||
29 | * of the macro allows us to do so | ||
30 | */ | ||
31 | #include "mpi-inline.h" | ||
diff --git a/lib/mpi/mpi-inv.c b/lib/mpi/mpi-inv.c new file mode 100644 index 000000000000..0951f9847745 --- /dev/null +++ b/lib/mpi/mpi-inv.c | |||
@@ -0,0 +1,187 @@ | |||
1 | /* mpi-inv.c - MPI functions | ||
2 | * Copyright (C) 1998, 1999, 2000, 2001 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 | |||
23 | /**************** | ||
24 | * Calculate the multiplicative inverse X of A mod N | ||
25 | * That is: Find the solution x for | ||
26 | * 1 = (a*x) mod n | ||
27 | */ | ||
28 | int mpi_invm(MPI x, const MPI a, const MPI n) | ||
29 | { | ||
30 | /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X) | ||
31 | * modified according to Michael Penk's solution for Exercice 35 | ||
32 | * with further enhancement */ | ||
33 | MPI u = NULL, v = NULL; | ||
34 | MPI u1 = NULL, u2 = NULL, u3 = NULL; | ||
35 | MPI v1 = NULL, v2 = NULL, v3 = NULL; | ||
36 | MPI t1 = NULL, t2 = NULL, t3 = NULL; | ||
37 | unsigned k; | ||
38 | int sign; | ||
39 | int odd = 0; | ||
40 | int rc = -ENOMEM; | ||
41 | |||
42 | if (mpi_copy(&u, a) < 0) | ||
43 | goto cleanup; | ||
44 | if (mpi_copy(&v, n) < 0) | ||
45 | goto cleanup; | ||
46 | |||
47 | for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) { | ||
48 | if (mpi_rshift(u, u, 1) < 0) | ||
49 | goto cleanup; | ||
50 | if (mpi_rshift(v, v, 1) < 0) | ||
51 | goto cleanup; | ||
52 | } | ||
53 | odd = mpi_test_bit(v, 0); | ||
54 | |||
55 | u1 = mpi_alloc_set_ui(1); | ||
56 | if (!u1) | ||
57 | goto cleanup; | ||
58 | if (!odd) { | ||
59 | u2 = mpi_alloc_set_ui(0); | ||
60 | if (!u2) | ||
61 | goto cleanup; | ||
62 | } | ||
63 | if (mpi_copy(&u3, u) < 0) | ||
64 | goto cleanup; | ||
65 | if (mpi_copy(&v1, v) < 0) | ||
66 | goto cleanup; | ||
67 | if (!odd) { | ||
68 | v2 = mpi_alloc(mpi_get_nlimbs(u)); | ||
69 | if (!v2) | ||
70 | goto cleanup; | ||
71 | if (mpi_sub(v2, u1, u) < 0) | ||
72 | goto cleanup; /* U is used as const 1 */ | ||
73 | } | ||
74 | if (mpi_copy(&v3, v) < 0) | ||
75 | goto cleanup; | ||
76 | if (mpi_test_bit(u, 0)) { /* u is odd */ | ||
77 | t1 = mpi_alloc_set_ui(0); | ||
78 | if (!t1) | ||
79 | goto cleanup; | ||
80 | if (!odd) { | ||
81 | t2 = mpi_alloc_set_ui(1); | ||
82 | if (!t2) | ||
83 | goto cleanup; | ||
84 | t2->sign = 1; | ||
85 | } | ||
86 | if (mpi_copy(&t3, v) < 0) | ||
87 | goto cleanup; | ||
88 | t3->sign = !t3->sign; | ||
89 | goto Y4; | ||
90 | } else { | ||
91 | t1 = mpi_alloc_set_ui(1); | ||
92 | if (!t1) | ||
93 | goto cleanup; | ||
94 | if (!odd) { | ||
95 | t2 = mpi_alloc_set_ui(0); | ||
96 | if (!t2) | ||
97 | goto cleanup; | ||
98 | } | ||
99 | if (mpi_copy(&t3, u) < 0) | ||
100 | goto cleanup; | ||
101 | } | ||
102 | do { | ||
103 | do { | ||
104 | if (!odd) { | ||
105 | if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { /* one is odd */ | ||
106 | if (mpi_add(t1, t1, v) < 0) | ||
107 | goto cleanup; | ||
108 | if (mpi_sub(t2, t2, u) < 0) | ||
109 | goto cleanup; | ||
110 | } | ||
111 | if (mpi_rshift(t1, t1, 1) < 0) | ||
112 | goto cleanup; | ||
113 | if (mpi_rshift(t2, t2, 1) < 0) | ||
114 | goto cleanup; | ||
115 | if (mpi_rshift(t3, t3, 1) < 0) | ||
116 | goto cleanup; | ||
117 | } else { | ||
118 | if (mpi_test_bit(t1, 0)) | ||
119 | if (mpi_add(t1, t1, v) < 0) | ||
120 | goto cleanup; | ||
121 | if (mpi_rshift(t1, t1, 1) < 0) | ||
122 | goto cleanup; | ||
123 | if (mpi_rshift(t3, t3, 1) < 0) | ||
124 | goto cleanup; | ||
125 | } | ||
126 | Y4: | ||
127 | ; | ||
128 | } while (!mpi_test_bit(t3, 0)); /* while t3 is even */ | ||
129 | |||
130 | if (!t3->sign) { | ||
131 | if (mpi_set(u1, t1) < 0) | ||
132 | goto cleanup; | ||
133 | if (!odd) | ||
134 | if (mpi_set(u2, t2) < 0) | ||
135 | goto cleanup; | ||
136 | if (mpi_set(u3, t3) < 0) | ||
137 | goto cleanup; | ||
138 | } else { | ||
139 | if (mpi_sub(v1, v, t1) < 0) | ||
140 | goto cleanup; | ||
141 | sign = u->sign; | ||
142 | u->sign = !u->sign; | ||
143 | if (!odd) | ||
144 | if (mpi_sub(v2, u, t2) < 0) | ||
145 | goto cleanup; | ||
146 | u->sign = sign; | ||
147 | sign = t3->sign; | ||
148 | t3->sign = !t3->sign; | ||
149 | if (mpi_set(v3, t3) < 0) | ||
150 | goto cleanup; | ||
151 | t3->sign = sign; | ||
152 | } | ||
153 | if (mpi_sub(t1, u1, v1) < 0) | ||
154 | goto cleanup; | ||
155 | if (!odd) | ||
156 | if (mpi_sub(t2, u2, v2) < 0) | ||
157 | goto cleanup; | ||
158 | if (mpi_sub(t3, u3, v3) < 0) | ||
159 | goto cleanup; | ||
160 | if (t1->sign) { | ||
161 | if (mpi_add(t1, t1, v) < 0) | ||
162 | goto cleanup; | ||
163 | if (!odd) | ||
164 | if (mpi_sub(t2, t2, u) < 0) | ||
165 | goto cleanup; | ||
166 | } | ||
167 | } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */ | ||
168 | /* mpi_lshift( u3, k ); */ | ||
169 | rc = mpi_set(x, u1); | ||
170 | |||
171 | cleanup: | ||
172 | mpi_free(u1); | ||
173 | mpi_free(v1); | ||
174 | mpi_free(t1); | ||
175 | if (!odd) { | ||
176 | mpi_free(u2); | ||
177 | mpi_free(v2); | ||
178 | mpi_free(t2); | ||
179 | } | ||
180 | mpi_free(u3); | ||
181 | mpi_free(v3); | ||
182 | mpi_free(t3); | ||
183 | |||
184 | mpi_free(u); | ||
185 | mpi_free(v); | ||
186 | return rc; | ||
187 | } | ||
diff --git a/lib/mpi/mpi-mpow.c b/lib/mpi/mpi-mpow.c new file mode 100644 index 000000000000..4cc75933c5a7 --- /dev/null +++ b/lib/mpi/mpi-mpow.c | |||
@@ -0,0 +1,133 @@ | |||
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 nomem; | ||
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 | return rc; | ||
133 | } | ||
diff --git a/lib/mpi/mpi-mul.c b/lib/mpi/mpi-mul.c new file mode 100644 index 000000000000..1f3219e27292 --- /dev/null +++ b/lib/mpi/mpi-mul.c | |||
@@ -0,0 +1,194 @@ | |||
1 | /* mpi-mul.c - MPI functions | ||
2 | * Copyright (C) 1994, 1996 Free Software Foundation, Inc. | ||
3 | * Copyright (C) 1998, 2001 Free Software Foundation, Inc. | ||
4 | * | ||
5 | * This file is part of GnuPG. | ||
6 | * | ||
7 | * GnuPG is free software; you can redistribute it and/or modify | ||
8 | * it under the terms of the GNU General Public License as published by | ||
9 | * the Free Software Foundation; either version 2 of the License, or | ||
10 | * (at your option) any later version. | ||
11 | * | ||
12 | * GnuPG is distributed in the hope that it will be useful, | ||
13 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
14 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
15 | * GNU General Public License for more details. | ||
16 | * | ||
17 | * You should have received a copy of the GNU General Public License | ||
18 | * along with this program; if not, write to the Free Software | ||
19 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA | ||
20 | * | ||
21 | * Note: This code is heavily based on the GNU MP Library. | ||
22 | * Actually it's the same code with only minor changes in the | ||
23 | * way the data is stored; this is to support the abstraction | ||
24 | * of an optional secure memory allocation which may be used | ||
25 | * to avoid revealing of sensitive data due to paging etc. | ||
26 | * The GNU MP Library itself is published under the LGPL; | ||
27 | * however I decided to publish this code under the plain GPL. | ||
28 | */ | ||
29 | |||
30 | #include "mpi-internal.h" | ||
31 | |||
32 | int mpi_mul_ui(MPI prod, MPI mult, unsigned long small_mult) | ||
33 | { | ||
34 | mpi_size_t size, prod_size; | ||
35 | mpi_ptr_t prod_ptr; | ||
36 | mpi_limb_t cy; | ||
37 | int sign; | ||
38 | |||
39 | size = mult->nlimbs; | ||
40 | sign = mult->sign; | ||
41 | |||
42 | if (!size || !small_mult) { | ||
43 | prod->nlimbs = 0; | ||
44 | prod->sign = 0; | ||
45 | return 0; | ||
46 | } | ||
47 | |||
48 | prod_size = size + 1; | ||
49 | if (prod->alloced < prod_size) | ||
50 | if (mpi_resize(prod, prod_size) < 0) | ||
51 | return -ENOMEM; | ||
52 | prod_ptr = prod->d; | ||
53 | |||
54 | cy = mpihelp_mul_1(prod_ptr, mult->d, size, (mpi_limb_t) small_mult); | ||
55 | if (cy) | ||
56 | prod_ptr[size++] = cy; | ||
57 | prod->nlimbs = size; | ||
58 | prod->sign = sign; | ||
59 | return 0; | ||
60 | } | ||
61 | |||
62 | int mpi_mul_2exp(MPI w, MPI u, unsigned long cnt) | ||
63 | { | ||
64 | mpi_size_t usize, wsize, limb_cnt; | ||
65 | mpi_ptr_t wp; | ||
66 | mpi_limb_t wlimb; | ||
67 | int usign, wsign; | ||
68 | |||
69 | usize = u->nlimbs; | ||
70 | usign = u->sign; | ||
71 | |||
72 | if (!usize) { | ||
73 | w->nlimbs = 0; | ||
74 | w->sign = 0; | ||
75 | return 0; | ||
76 | } | ||
77 | |||
78 | limb_cnt = cnt / BITS_PER_MPI_LIMB; | ||
79 | wsize = usize + limb_cnt + 1; | ||
80 | if (w->alloced < wsize) | ||
81 | if (mpi_resize(w, wsize) < 0) | ||
82 | return -ENOMEM; | ||
83 | wp = w->d; | ||
84 | wsize = usize + limb_cnt; | ||
85 | wsign = usign; | ||
86 | |||
87 | cnt %= BITS_PER_MPI_LIMB; | ||
88 | if (cnt) { | ||
89 | wlimb = mpihelp_lshift(wp + limb_cnt, u->d, usize, cnt); | ||
90 | if (wlimb) { | ||
91 | wp[wsize] = wlimb; | ||
92 | wsize++; | ||
93 | } | ||
94 | } else { | ||
95 | MPN_COPY_DECR(wp + limb_cnt, u->d, usize); | ||
96 | } | ||
97 | |||
98 | /* Zero all whole limbs at low end. Do it here and not before calling | ||
99 | * mpn_lshift, not to lose for U == W. */ | ||
100 | MPN_ZERO(wp, limb_cnt); | ||
101 | |||
102 | w->nlimbs = wsize; | ||
103 | w->sign = wsign; | ||
104 | return 0; | ||
105 | } | ||
106 | |||
107 | int mpi_mul(MPI w, MPI u, MPI v) | ||
108 | { | ||
109 | int rc = -ENOMEM; | ||
110 | mpi_size_t usize, vsize, wsize; | ||
111 | mpi_ptr_t up, vp, wp; | ||
112 | mpi_limb_t cy; | ||
113 | int usign, vsign, sign_product; | ||
114 | int assign_wp = 0; | ||
115 | mpi_ptr_t tmp_limb = NULL; | ||
116 | |||
117 | if (u->nlimbs < v->nlimbs) { /* Swap U and V. */ | ||
118 | usize = v->nlimbs; | ||
119 | usign = v->sign; | ||
120 | up = v->d; | ||
121 | vsize = u->nlimbs; | ||
122 | vsign = u->sign; | ||
123 | vp = u->d; | ||
124 | } else { | ||
125 | usize = u->nlimbs; | ||
126 | usign = u->sign; | ||
127 | up = u->d; | ||
128 | vsize = v->nlimbs; | ||
129 | vsign = v->sign; | ||
130 | vp = v->d; | ||
131 | } | ||
132 | sign_product = usign ^ vsign; | ||
133 | wp = w->d; | ||
134 | |||
135 | /* Ensure W has space enough to store the result. */ | ||
136 | wsize = usize + vsize; | ||
137 | if (w->alloced < (size_t) wsize) { | ||
138 | if (wp == up || wp == vp) { | ||
139 | wp = mpi_alloc_limb_space(wsize); | ||
140 | if (!wp) | ||
141 | goto nomem; | ||
142 | assign_wp = 1; | ||
143 | } else { | ||
144 | if (mpi_resize(w, wsize) < 0) | ||
145 | goto nomem; | ||
146 | wp = w->d; | ||
147 | } | ||
148 | } else { /* Make U and V not overlap with W. */ | ||
149 | if (wp == up) { | ||
150 | /* W and U are identical. Allocate temporary space for U. */ | ||
151 | up = tmp_limb = mpi_alloc_limb_space(usize); | ||
152 | if (!up) | ||
153 | goto nomem; | ||
154 | /* Is V identical too? Keep it identical with U. */ | ||
155 | if (wp == vp) | ||
156 | vp = up; | ||
157 | /* Copy to the temporary space. */ | ||
158 | MPN_COPY(up, wp, usize); | ||
159 | } else if (wp == vp) { | ||
160 | /* W and V are identical. Allocate temporary space for V. */ | ||
161 | vp = tmp_limb = mpi_alloc_limb_space(vsize); | ||
162 | if (!vp) | ||
163 | goto nomem; | ||
164 | /* Copy to the temporary space. */ | ||
165 | MPN_COPY(vp, wp, vsize); | ||
166 | } | ||
167 | } | ||
168 | |||
169 | if (!vsize) | ||
170 | wsize = 0; | ||
171 | else { | ||
172 | if (mpihelp_mul(wp, up, usize, vp, vsize, &cy) < 0) | ||
173 | goto nomem; | ||
174 | wsize -= cy ? 0 : 1; | ||
175 | } | ||
176 | |||
177 | if (assign_wp) | ||
178 | mpi_assign_limb_space(w, wp, wsize); | ||
179 | |||
180 | w->nlimbs = wsize; | ||
181 | w->sign = sign_product; | ||
182 | rc = 0; | ||
183 | nomem: | ||
184 | if (tmp_limb) | ||
185 | mpi_free_limb_space(tmp_limb); | ||
186 | return rc; | ||
187 | } | ||
188 | |||
189 | int mpi_mulm(MPI w, MPI u, MPI v, MPI m) | ||
190 | { | ||
191 | if (mpi_mul(w, u, v) < 0) | ||
192 | return -ENOMEM; | ||
193 | return mpi_fdiv_r(w, w, m); | ||
194 | } | ||
diff --git a/lib/mpi/mpi-scan.c b/lib/mpi/mpi-scan.c new file mode 100644 index 000000000000..b2da5ad96199 --- /dev/null +++ b/lib/mpi/mpi-scan.c | |||
@@ -0,0 +1,136 @@ | |||
1 | /* mpi-scan.c - MPI functions | ||
2 | * Copyright (C) 1998, 1999, 2000, 2001 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 | /**************** | ||
25 | * Scan through an mpi and return byte for byte. a -1 is returned to indicate | ||
26 | * the end of the mpi. Scanning is done from the lsb to the msb, returned | ||
27 | * values are in the range of 0 .. 255. | ||
28 | * | ||
29 | * FIXME: This code is VERY ugly! | ||
30 | */ | ||
31 | int mpi_getbyte(const MPI a, unsigned idx) | ||
32 | { | ||
33 | int i, j; | ||
34 | unsigned n; | ||
35 | mpi_ptr_t ap; | ||
36 | mpi_limb_t limb; | ||
37 | |||
38 | ap = a->d; | ||
39 | for (n = 0, i = 0; i < a->nlimbs; i++) { | ||
40 | limb = ap[i]; | ||
41 | for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++) | ||
42 | if (n == idx) | ||
43 | return (limb >> j * 8) & 0xff; | ||
44 | } | ||
45 | return -1; | ||
46 | } | ||
47 | |||
48 | /**************** | ||
49 | * Put a value at position IDX into A. idx counts from lsb to msb | ||
50 | */ | ||
51 | void mpi_putbyte(MPI a, unsigned idx, int xc) | ||
52 | { | ||
53 | int i, j; | ||
54 | unsigned n; | ||
55 | mpi_ptr_t ap; | ||
56 | mpi_limb_t limb, c; | ||
57 | |||
58 | c = xc & 0xff; | ||
59 | ap = a->d; | ||
60 | for (n = 0, i = 0; i < a->alloced; i++) { | ||
61 | limb = ap[i]; | ||
62 | for (j = 0; j < BYTES_PER_MPI_LIMB; j++, n++) | ||
63 | if (n == idx) { | ||
64 | #if BYTES_PER_MPI_LIMB == 4 | ||
65 | if (j == 0) | ||
66 | limb = (limb & 0xffffff00) | c; | ||
67 | else if (j == 1) | ||
68 | limb = (limb & 0xffff00ff) | (c << 8); | ||
69 | else if (j == 2) | ||
70 | limb = (limb & 0xff00ffff) | (c << 16); | ||
71 | else | ||
72 | limb = (limb & 0x00ffffff) | (c << 24); | ||
73 | #elif BYTES_PER_MPI_LIMB == 8 | ||
74 | if (j == 0) | ||
75 | limb = (limb & 0xffffffffffffff00) | c; | ||
76 | else if (j == 1) | ||
77 | limb = | ||
78 | (limb & 0xffffffffffff00ff) | (c << | ||
79 | 8); | ||
80 | else if (j == 2) | ||
81 | limb = | ||
82 | (limb & 0xffffffffff00ffff) | (c << | ||
83 | 16); | ||
84 | else if (j == 3) | ||
85 | limb = | ||
86 | (limb & 0xffffffff00ffffff) | (c << | ||
87 | 24); | ||
88 | else if (j == 4) | ||
89 | limb = | ||
90 | (limb & 0xffffff00ffffffff) | (c << | ||
91 | 32); | ||
92 | else if (j == 5) | ||
93 | limb = | ||
94 | (limb & 0xffff00ffffffffff) | (c << | ||
95 | 40); | ||
96 | else if (j == 6) | ||
97 | limb = | ||
98 | (limb & 0xff00ffffffffffff) | (c << | ||
99 | 48); | ||
100 | else | ||
101 | limb = | ||
102 | (limb & 0x00ffffffffffffff) | (c << | ||
103 | 56); | ||
104 | #else | ||
105 | #error please enhance this function, its ugly - i know. | ||
106 | #endif | ||
107 | if (a->nlimbs <= i) | ||
108 | a->nlimbs = i + 1; | ||
109 | ap[i] = limb; | ||
110 | return; | ||
111 | } | ||
112 | } | ||
113 | log_bug("index out of range\n"); | ||
114 | } | ||
115 | |||
116 | /**************** | ||
117 | * Count the number of zerobits at the low end of A | ||
118 | */ | ||
119 | unsigned mpi_trailing_zeros(const MPI a) | ||
120 | { | ||
121 | unsigned n, count = 0; | ||
122 | |||
123 | for (n = 0; n < a->nlimbs; n++) { | ||
124 | if (a->d[n]) { | ||
125 | unsigned nn; | ||
126 | mpi_limb_t alimb = a->d[n]; | ||
127 | |||
128 | count_trailing_zeros(nn, alimb); | ||
129 | count += nn; | ||
130 | break; | ||
131 | } | ||
132 | count += BITS_PER_MPI_LIMB; | ||
133 | } | ||
134 | return count; | ||
135 | |||
136 | } | ||