Diffstat (limited to 'pwmanager/libcrypt/mpi/mpi-inv.c') (more/less context) (ignore whitespace changes)
-rw-r--r-- | pwmanager/libcrypt/mpi/mpi-inv.c | 275 |
1 files changed, 275 insertions, 0 deletions
diff --git a/pwmanager/libcrypt/mpi/mpi-inv.c b/pwmanager/libcrypt/mpi/mpi-inv.c new file mode 100644 index 0000000..2e737b8 --- a/dev/null +++ b/pwmanager/libcrypt/mpi/mpi-inv.c | |||
@@ -0,0 +1,275 @@ | |||
1 | /* mpi-inv.c - MPI functions | ||
2 | *Copyright (C) 1998, 2001, 2002, 2003 Free Software Foundation, Inc. | ||
3 | * | ||
4 | * This file is part of Libgcrypt. | ||
5 | * | ||
6 | * Libgcrypt is free software; you can redistribute it and/or modify | ||
7 | * it under the terms of the GNU Lesser General Public License as | ||
8 | * published by the Free Software Foundation; either version 2.1 of | ||
9 | * the License, or (at your option) any later version. | ||
10 | * | ||
11 | * Libgcrypt 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 Lesser General Public License for more details. | ||
15 | * | ||
16 | * You should have received a copy of the GNU Lesser General Public | ||
17 | * License 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 <config.h> | ||
22 | #include <stdio.h> | ||
23 | #include <stdlib.h> | ||
24 | #include "mpi-internal.h" | ||
25 | #include "g10lib.h" | ||
26 | |||
27 | /**************** | ||
28 | * Calculate the multiplicative inverse X of A mod N | ||
29 | * That is: Find the solution x for | ||
30 | * 1 = (a*x) mod n | ||
31 | */ | ||
32 | void | ||
33 | _gcry_mpi_invm( gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n ) | ||
34 | { | ||
35 | #if 0 | ||
36 | gcry_mpi_t u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3; | ||
37 | gcry_mpi_t ta, tb, tc; | ||
38 | |||
39 | u = mpi_copy(a); | ||
40 | v = mpi_copy(n); | ||
41 | u1 = mpi_alloc_set_ui(1); | ||
42 | u2 = mpi_alloc_set_ui(0); | ||
43 | u3 = mpi_copy(u); | ||
44 | v1 = mpi_alloc_set_ui(0); | ||
45 | v2 = mpi_alloc_set_ui(1); | ||
46 | v3 = mpi_copy(v); | ||
47 | q = mpi_alloc( mpi_get_nlimbs(u)+1 ); | ||
48 | t1 = mpi_alloc( mpi_get_nlimbs(u)+1 ); | ||
49 | t2 = mpi_alloc( mpi_get_nlimbs(u)+1 ); | ||
50 | t3 = mpi_alloc( mpi_get_nlimbs(u)+1 ); | ||
51 | while( mpi_cmp_ui( v3, 0 ) ) { | ||
52 | mpi_fdiv_q( q, u3, v3 ); | ||
53 | mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q); | ||
54 | mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3); | ||
55 | mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3); | ||
56 | mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3); | ||
57 | } | ||
58 | /*log_debug("result:\n"); | ||
59 | log_mpidump("q =", q ); | ||
60 | log_mpidump("u1=", u1); | ||
61 | log_mpidump("u2=", u2); | ||
62 | log_mpidump("u3=", u3); | ||
63 | log_mpidump("v1=", v1); | ||
64 | log_mpidump("v2=", v2); */ | ||
65 | mpi_set(x, u1); | ||
66 | |||
67 | mpi_free(u1); | ||
68 | mpi_free(u2); | ||
69 | mpi_free(u3); | ||
70 | mpi_free(v1); | ||
71 | mpi_free(v2); | ||
72 | mpi_free(v3); | ||
73 | mpi_free(q); | ||
74 | mpi_free(t1); | ||
75 | mpi_free(t2); | ||
76 | mpi_free(t3); | ||
77 | mpi_free(u); | ||
78 | mpi_free(v); | ||
79 | #elif 0 | ||
80 | /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X) | ||
81 | * modified according to Michael Penk's solution for Exercise 35 */ | ||
82 | |||
83 | /* FIXME: we can simplify this in most cases (see Knuth) */ | ||
84 | gcry_mpi_t u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3; | ||
85 | unsigned k; | ||
86 | int sign; | ||
87 | |||
88 | u = mpi_copy(a); | ||
89 | v = mpi_copy(n); | ||
90 | for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) { | ||
91 | mpi_rshift(u, u, 1); | ||
92 | mpi_rshift(v, v, 1); | ||
93 | } | ||
94 | |||
95 | |||
96 | u1 = mpi_alloc_set_ui(1); | ||
97 | u2 = mpi_alloc_set_ui(0); | ||
98 | u3 = mpi_copy(u); | ||
99 | v1 = mpi_copy(v); /* !-- used as const 1 */ | ||
100 | v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u ); | ||
101 | v3 = mpi_copy(v); | ||
102 | if( mpi_test_bit(u, 0) ) { /* u is odd */ | ||
103 | t1 = mpi_alloc_set_ui(0); | ||
104 | t2 = mpi_alloc_set_ui(1); t2->sign = 1; | ||
105 | t3 = mpi_copy(v); t3->sign = !t3->sign; | ||
106 | goto Y4; | ||
107 | } | ||
108 | else { | ||
109 | t1 = mpi_alloc_set_ui(1); | ||
110 | t2 = mpi_alloc_set_ui(0); | ||
111 | t3 = mpi_copy(u); | ||
112 | } | ||
113 | do { | ||
114 | do { | ||
115 | if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */ | ||
116 | mpi_add(t1, t1, v); | ||
117 | mpi_sub(t2, t2, u); | ||
118 | } | ||
119 | mpi_rshift(t1, t1, 1); | ||
120 | mpi_rshift(t2, t2, 1); | ||
121 | mpi_rshift(t3, t3, 1); | ||
122 | Y4: | ||
123 | ; | ||
124 | } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */ | ||
125 | |||
126 | if( !t3->sign ) { | ||
127 | mpi_set(u1, t1); | ||
128 | mpi_set(u2, t2); | ||
129 | mpi_set(u3, t3); | ||
130 | } | ||
131 | else { | ||
132 | mpi_sub(v1, v, t1); | ||
133 | sign = u->sign; u->sign = !u->sign; | ||
134 | mpi_sub(v2, u, t2); | ||
135 | u->sign = sign; | ||
136 | sign = t3->sign; t3->sign = !t3->sign; | ||
137 | mpi_set(v3, t3); | ||
138 | t3->sign = sign; | ||
139 | } | ||
140 | mpi_sub(t1, u1, v1); | ||
141 | mpi_sub(t2, u2, v2); | ||
142 | mpi_sub(t3, u3, v3); | ||
143 | if( t1->sign ) { | ||
144 | mpi_add(t1, t1, v); | ||
145 | mpi_sub(t2, t2, u); | ||
146 | } | ||
147 | } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */ | ||
148 | /* mpi_lshift( u3, k ); */ | ||
149 | mpi_set(x, u1); | ||
150 | |||
151 | mpi_free(u1); | ||
152 | mpi_free(u2); | ||
153 | mpi_free(u3); | ||
154 | mpi_free(v1); | ||
155 | mpi_free(v2); | ||
156 | mpi_free(v3); | ||
157 | mpi_free(t1); | ||
158 | mpi_free(t2); | ||
159 | mpi_free(t3); | ||
160 | #else | ||
161 | /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X) | ||
162 | * modified according to Michael Penk's solution for Exercise 35 | ||
163 | * with further enhancement */ | ||
164 | gcry_mpi_t u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3; | ||
165 | unsigned k; | ||
166 | int sign; | ||
167 | int odd ; | ||
168 | |||
169 | u = mpi_copy(a); | ||
170 | v = mpi_copy(n); | ||
171 | |||
172 | for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) { | ||
173 | mpi_rshift(u, u, 1); | ||
174 | mpi_rshift(v, v, 1); | ||
175 | } | ||
176 | odd = mpi_test_bit(v,0); | ||
177 | |||
178 | u1 = mpi_alloc_set_ui(1); | ||
179 | if( !odd ) | ||
180 | u2 = mpi_alloc_set_ui(0); | ||
181 | u3 = mpi_copy(u); | ||
182 | v1 = mpi_copy(v); | ||
183 | if( !odd ) { | ||
184 | v2 = mpi_alloc( mpi_get_nlimbs(u) ); | ||
185 | mpi_sub( v2, u1, u ); /* U is used as const 1 */ | ||
186 | } | ||
187 | v3 = mpi_copy(v); | ||
188 | if( mpi_test_bit(u, 0) ) { /* u is odd */ | ||
189 | t1 = mpi_alloc_set_ui(0); | ||
190 | if( !odd ) { | ||
191 | t2 = mpi_alloc_set_ui(1); t2->sign = 1; | ||
192 | } | ||
193 | t3 = mpi_copy(v); t3->sign = !t3->sign; | ||
194 | goto Y4; | ||
195 | } | ||
196 | else { | ||
197 | t1 = mpi_alloc_set_ui(1); | ||
198 | if( !odd ) | ||
199 | t2 = mpi_alloc_set_ui(0); | ||
200 | t3 = mpi_copy(u); | ||
201 | } | ||
202 | do { | ||
203 | do { | ||
204 | if( !odd ) { | ||
205 | if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */ | ||
206 | mpi_add(t1, t1, v); | ||
207 | mpi_sub(t2, t2, u); | ||
208 | } | ||
209 | mpi_rshift(t1, t1, 1); | ||
210 | mpi_rshift(t2, t2, 1); | ||
211 | mpi_rshift(t3, t3, 1); | ||
212 | } | ||
213 | else { | ||
214 | if( mpi_test_bit(t1, 0) ) | ||
215 | mpi_add(t1, t1, v); | ||
216 | mpi_rshift(t1, t1, 1); | ||
217 | mpi_rshift(t3, t3, 1); | ||
218 | } | ||
219 | Y4: | ||
220 | ; | ||
221 | } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */ | ||
222 | |||
223 | if( !t3->sign ) { | ||
224 | mpi_set(u1, t1); | ||
225 | if( !odd ) | ||
226 | mpi_set(u2, t2); | ||
227 | mpi_set(u3, t3); | ||
228 | } | ||
229 | else { | ||
230 | mpi_sub(v1, v, t1); | ||
231 | sign = u->sign; u->sign = !u->sign; | ||
232 | if( !odd ) | ||
233 | mpi_sub(v2, u, t2); | ||
234 | u->sign = sign; | ||
235 | sign = t3->sign; t3->sign = !t3->sign; | ||
236 | mpi_set(v3, t3); | ||
237 | t3->sign = sign; | ||
238 | } | ||
239 | mpi_sub(t1, u1, v1); | ||
240 | if( !odd ) | ||
241 | mpi_sub(t2, u2, v2); | ||
242 | mpi_sub(t3, u3, v3); | ||
243 | if( t1->sign ) { | ||
244 | mpi_add(t1, t1, v); | ||
245 | if( !odd ) | ||
246 | mpi_sub(t2, t2, u); | ||
247 | } | ||
248 | } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */ | ||
249 | /* mpi_lshift( u3, k ); */ | ||
250 | mpi_set(x, u1); | ||
251 | |||
252 | mpi_free(u1); | ||
253 | mpi_free(v1); | ||
254 | mpi_free(t1); | ||
255 | if( !odd ) { | ||
256 | mpi_free(u2); | ||
257 | mpi_free(v2); | ||
258 | mpi_free(t2); | ||
259 | } | ||
260 | mpi_free(u3); | ||
261 | mpi_free(v3); | ||
262 | mpi_free(t3); | ||
263 | |||
264 | mpi_free(u); | ||
265 | mpi_free(v); | ||
266 | #endif | ||
267 | } | ||
268 | |||
269 | |||
270 | int | ||
271 | gcry_mpi_invm (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n) | ||
272 | { | ||
273 | _gcry_mpi_invm (x, a, n); | ||
274 | return 1; | ||
275 | } | ||