Commit | Line | Data |
---|---|---|
7e8dec91 DK |
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 | } |