Commit | Line | Data |
---|---|---|
a8ea8bdd TZ |
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 "mpi-internal.h" | |
21 | ||
22 | /**************** | |
23 | * Calculate the multiplicative inverse X of A mod N | |
24 | * That is: Find the solution x for | |
25 | * 1 = (a*x) mod n | |
26 | */ | |
27 | int mpi_invm(MPI x, MPI a, MPI n) | |
28 | { | |
29 | /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X) | |
30 | * modified according to Michael Penk's solution for Exercise 35 | |
31 | * with further enhancement | |
32 | */ | |
33 | MPI u, v, u1, u2 = NULL, u3, v1, v2 = NULL, v3, t1, t2 = NULL, t3; | |
34 | unsigned int k; | |
35 | int sign; | |
36 | int odd; | |
37 | ||
38 | if (!mpi_cmp_ui(a, 0)) | |
39 | return 0; /* Inverse does not exists. */ | |
40 | if (!mpi_cmp_ui(n, 1)) | |
41 | return 0; /* Inverse does not exists. */ | |
42 | ||
43 | u = mpi_copy(a); | |
44 | v = mpi_copy(n); | |
45 | ||
46 | for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) { | |
47 | mpi_rshift(u, u, 1); | |
48 | mpi_rshift(v, v, 1); | |
49 | } | |
50 | odd = mpi_test_bit(v, 0); | |
51 | ||
52 | u1 = mpi_alloc_set_ui(1); | |
53 | if (!odd) | |
54 | u2 = mpi_alloc_set_ui(0); | |
55 | u3 = mpi_copy(u); | |
56 | v1 = mpi_copy(v); | |
57 | if (!odd) { | |
58 | v2 = mpi_alloc(mpi_get_nlimbs(u)); | |
59 | mpi_sub(v2, u1, u); /* U is used as const 1 */ | |
60 | } | |
61 | v3 = mpi_copy(v); | |
62 | if (mpi_test_bit(u, 0)) { /* u is odd */ | |
63 | t1 = mpi_alloc_set_ui(0); | |
64 | if (!odd) { | |
65 | t2 = mpi_alloc_set_ui(1); | |
66 | t2->sign = 1; | |
67 | } | |
68 | t3 = mpi_copy(v); | |
69 | t3->sign = !t3->sign; | |
70 | goto Y4; | |
71 | } else { | |
72 | t1 = mpi_alloc_set_ui(1); | |
73 | if (!odd) | |
74 | t2 = mpi_alloc_set_ui(0); | |
75 | t3 = mpi_copy(u); | |
76 | } | |
77 | ||
78 | do { | |
79 | do { | |
80 | if (!odd) { | |
81 | if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) { | |
82 | /* one is odd */ | |
83 | mpi_add(t1, t1, v); | |
84 | mpi_sub(t2, t2, u); | |
85 | } | |
86 | mpi_rshift(t1, t1, 1); | |
87 | mpi_rshift(t2, t2, 1); | |
88 | mpi_rshift(t3, t3, 1); | |
89 | } else { | |
90 | if (mpi_test_bit(t1, 0)) | |
91 | mpi_add(t1, t1, v); | |
92 | mpi_rshift(t1, t1, 1); | |
93 | mpi_rshift(t3, t3, 1); | |
94 | } | |
95 | Y4: | |
96 | ; | |
97 | } while (!mpi_test_bit(t3, 0)); /* while t3 is even */ | |
98 | ||
99 | if (!t3->sign) { | |
100 | mpi_set(u1, t1); | |
101 | if (!odd) | |
102 | mpi_set(u2, t2); | |
103 | mpi_set(u3, t3); | |
104 | } else { | |
105 | mpi_sub(v1, v, t1); | |
106 | sign = u->sign; u->sign = !u->sign; | |
107 | if (!odd) | |
108 | mpi_sub(v2, u, t2); | |
109 | u->sign = sign; | |
110 | sign = t3->sign; t3->sign = !t3->sign; | |
111 | mpi_set(v3, t3); | |
112 | t3->sign = sign; | |
113 | } | |
114 | mpi_sub(t1, u1, v1); | |
115 | if (!odd) | |
116 | mpi_sub(t2, u2, v2); | |
117 | mpi_sub(t3, u3, v3); | |
118 | if (t1->sign) { | |
119 | mpi_add(t1, t1, v); | |
120 | if (!odd) | |
121 | mpi_sub(t2, t2, u); | |
122 | } | |
123 | } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */ | |
124 | /* mpi_lshift( u3, k ); */ | |
125 | mpi_set(x, u1); | |
126 | ||
127 | mpi_free(u1); | |
128 | mpi_free(v1); | |
129 | mpi_free(t1); | |
130 | if (!odd) { | |
131 | mpi_free(u2); | |
132 | mpi_free(v2); | |
133 | mpi_free(t2); | |
134 | } | |
135 | mpi_free(u3); | |
136 | mpi_free(v3); | |
137 | mpi_free(t3); | |
138 | ||
139 | mpi_free(u); | |
140 | mpi_free(v); | |
141 | return 1; | |
142 | } | |
143 | EXPORT_SYMBOL_GPL(mpi_invm); |