Line data Source code
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, see <http://www.gnu.org/licenses/>.
18 : */
19 :
20 : #include <config.h>
21 : #include <stdio.h>
22 : #include <stdlib.h>
23 : #include "mpi-internal.h"
24 : #include "g10lib.h"
25 :
26 : /****************
27 : * Calculate the multiplicative inverse X of A mod N
28 : * That is: Find the solution x for
29 : * 1 = (a*x) mod n
30 : */
31 : int
32 8020 : _gcry_mpi_invm (gcry_mpi_t x, gcry_mpi_t a, gcry_mpi_t n)
33 : {
34 : #if 0
35 : gcry_mpi_t u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
36 : gcry_mpi_t ta, tb, tc;
37 :
38 : u = mpi_copy(a);
39 : v = mpi_copy(n);
40 : u1 = mpi_alloc_set_ui(1);
41 : u2 = mpi_alloc_set_ui(0);
42 : u3 = mpi_copy(u);
43 : v1 = mpi_alloc_set_ui(0);
44 : v2 = mpi_alloc_set_ui(1);
45 : v3 = mpi_copy(v);
46 : q = mpi_alloc( mpi_get_nlimbs(u)+1 );
47 : t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
48 : t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
49 : t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
50 : while( mpi_cmp_ui( v3, 0 ) ) {
51 : mpi_fdiv_q( q, u3, v3 );
52 : mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
53 : mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
54 : mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
55 : mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
56 : }
57 : /* log_debug("result:\n");
58 : log_mpidump("q =", q );
59 : log_mpidump("u1=", u1);
60 : log_mpidump("u2=", u2);
61 : log_mpidump("u3=", u3);
62 : log_mpidump("v1=", v1);
63 : log_mpidump("v2=", v2); */
64 : mpi_set(x, u1);
65 :
66 : mpi_free(u1);
67 : mpi_free(u2);
68 : mpi_free(u3);
69 : mpi_free(v1);
70 : mpi_free(v2);
71 : mpi_free(v3);
72 : mpi_free(q);
73 : mpi_free(t1);
74 : mpi_free(t2);
75 : mpi_free(t3);
76 : mpi_free(u);
77 : mpi_free(v);
78 : #elif 0
79 : /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X)
80 : * modified according to Michael Penk's solution for Exercise 35 */
81 :
82 : /* FIXME: we can simplify this in most cases (see Knuth) */
83 : gcry_mpi_t u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
84 : unsigned k;
85 : int sign;
86 :
87 : u = mpi_copy(a);
88 : v = mpi_copy(n);
89 : for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
90 : mpi_rshift(u, u, 1);
91 : mpi_rshift(v, v, 1);
92 : }
93 :
94 :
95 : u1 = mpi_alloc_set_ui(1);
96 : u2 = mpi_alloc_set_ui(0);
97 : u3 = mpi_copy(u);
98 : v1 = mpi_copy(v); /* !-- used as const 1 */
99 : v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
100 : v3 = mpi_copy(v);
101 : if( mpi_test_bit(u, 0) ) { /* u is odd */
102 : t1 = mpi_alloc_set_ui(0);
103 : t2 = mpi_alloc_set_ui(1); t2->sign = 1;
104 : t3 = mpi_copy(v); t3->sign = !t3->sign;
105 : goto Y4;
106 : }
107 : else {
108 : t1 = mpi_alloc_set_ui(1);
109 : t2 = mpi_alloc_set_ui(0);
110 : t3 = mpi_copy(u);
111 : }
112 : do {
113 : do {
114 : if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
115 : mpi_add(t1, t1, v);
116 : mpi_sub(t2, t2, u);
117 : }
118 : mpi_rshift(t1, t1, 1);
119 : mpi_rshift(t2, t2, 1);
120 : mpi_rshift(t3, t3, 1);
121 : Y4:
122 : ;
123 : } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
124 :
125 : if( !t3->sign ) {
126 : mpi_set(u1, t1);
127 : mpi_set(u2, t2);
128 : mpi_set(u3, t3);
129 : }
130 : else {
131 : mpi_sub(v1, v, t1);
132 : sign = u->sign; u->sign = !u->sign;
133 : mpi_sub(v2, u, t2);
134 : u->sign = sign;
135 : sign = t3->sign; t3->sign = !t3->sign;
136 : mpi_set(v3, t3);
137 : t3->sign = sign;
138 : }
139 : mpi_sub(t1, u1, v1);
140 : mpi_sub(t2, u2, v2);
141 : mpi_sub(t3, u3, v3);
142 : if( t1->sign ) {
143 : mpi_add(t1, t1, v);
144 : mpi_sub(t2, t2, u);
145 : }
146 : } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
147 : /* mpi_lshift( u3, k ); */
148 : mpi_set(x, u1);
149 :
150 : mpi_free(u1);
151 : mpi_free(u2);
152 : mpi_free(u3);
153 : mpi_free(v1);
154 : mpi_free(v2);
155 : mpi_free(v3);
156 : mpi_free(t1);
157 : mpi_free(t2);
158 : mpi_free(t3);
159 : #else
160 : /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X)
161 : * modified according to Michael Penk's solution for Exercise 35
162 : * with further enhancement */
163 8020 : gcry_mpi_t u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
164 : unsigned k;
165 : int sign;
166 : int odd ;
167 :
168 8020 : if (!mpi_cmp_ui (a, 0))
169 0 : return 0; /* Inverse does not exists. */
170 8020 : if (!mpi_cmp_ui (n, 1))
171 0 : return 0; /* Inverse does not exists. */
172 :
173 8020 : u = mpi_copy(a);
174 8020 : v = mpi_copy(n);
175 :
176 8020 : for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
177 0 : mpi_rshift(u, u, 1);
178 0 : mpi_rshift(v, v, 1);
179 : }
180 8020 : odd = mpi_test_bit(v,0);
181 :
182 8020 : u1 = mpi_alloc_set_ui(1);
183 8020 : if( !odd )
184 50 : u2 = mpi_alloc_set_ui(0);
185 8020 : u3 = mpi_copy(u);
186 8020 : v1 = mpi_copy(v);
187 8020 : if( !odd ) {
188 50 : v2 = mpi_alloc( mpi_get_nlimbs(u) );
189 50 : mpi_sub( v2, u1, u ); /* U is used as const 1 */
190 : }
191 8020 : v3 = mpi_copy(v);
192 8020 : if( mpi_test_bit(u, 0) ) { /* u is odd */
193 4461 : t1 = mpi_alloc_set_ui(0);
194 4461 : if( !odd ) {
195 50 : t2 = mpi_alloc_set_ui(1); t2->sign = 1;
196 : }
197 4461 : t3 = mpi_copy(v); t3->sign = !t3->sign;
198 4461 : goto Y4;
199 : }
200 : else {
201 3559 : t1 = mpi_alloc_set_ui(1);
202 3559 : if( !odd )
203 0 : t2 = mpi_alloc_set_ui(0);
204 3559 : t3 = mpi_copy(u);
205 : }
206 : do {
207 : do {
208 4520248 : if( !odd ) {
209 66735 : if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
210 33483 : mpi_add(t1, t1, v);
211 33483 : mpi_sub(t2, t2, u);
212 : }
213 66735 : mpi_rshift(t1, t1, 1);
214 66735 : mpi_rshift(t2, t2, 1);
215 66735 : mpi_rshift(t3, t3, 1);
216 : }
217 : else {
218 4453513 : if( mpi_test_bit(t1, 0) )
219 2305027 : mpi_add(t1, t1, v);
220 4453513 : mpi_rshift(t1, t1, 1);
221 4453513 : mpi_rshift(t3, t3, 1);
222 : }
223 : Y4:
224 : ;
225 4524709 : } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
226 :
227 2427138 : if( !t3->sign ) {
228 1014278 : mpi_set(u1, t1);
229 1014278 : if( !odd )
230 3849 : mpi_set(u2, t2);
231 1014278 : mpi_set(u3, t3);
232 : }
233 : else {
234 1412860 : mpi_sub(v1, v, t1);
235 1412860 : sign = u->sign; u->sign = !u->sign;
236 1412860 : if( !odd )
237 29403 : mpi_sub(v2, u, t2);
238 1412860 : u->sign = sign;
239 1412860 : sign = t3->sign; t3->sign = !t3->sign;
240 1412860 : mpi_set(v3, t3);
241 1412860 : t3->sign = sign;
242 : }
243 2427138 : mpi_sub(t1, u1, v1);
244 2427138 : if( !odd )
245 33252 : mpi_sub(t2, u2, v2);
246 2427138 : mpi_sub(t3, u3, v3);
247 2427138 : if( t1->sign ) {
248 1433973 : mpi_add(t1, t1, v);
249 1433973 : if( !odd )
250 29465 : mpi_sub(t2, t2, u);
251 : }
252 2427138 : } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
253 : /* mpi_lshift( u3, k ); */
254 8020 : mpi_set(x, u1);
255 :
256 8020 : mpi_free(u1);
257 8020 : mpi_free(v1);
258 8020 : mpi_free(t1);
259 8020 : if( !odd ) {
260 50 : mpi_free(u2);
261 50 : mpi_free(v2);
262 50 : mpi_free(t2);
263 : }
264 8020 : mpi_free(u3);
265 8020 : mpi_free(v3);
266 8020 : mpi_free(t3);
267 :
268 8020 : mpi_free(u);
269 8020 : mpi_free(v);
270 : #endif
271 8020 : return 1;
272 : }
|
