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(u: a, v: 0)) |
39 | return 0; /* Inverse does not exists. */ |
40 | if (!mpi_cmp_ui(u: n, v: 1)) |
41 | return 0; /* Inverse does not exists. */ |
42 | |
43 | u = mpi_copy(a); |
44 | v = mpi_copy(a: n); |
45 | |
46 | for (k = 0; !mpi_test_bit(a: u, n: 0) && !mpi_test_bit(a: v, n: 0); k++) { |
47 | mpi_rshift(x: u, a: u, n: 1); |
48 | mpi_rshift(x: v, a: v, n: 1); |
49 | } |
50 | odd = mpi_test_bit(a: v, n: 0); |
51 | |
52 | u1 = mpi_alloc_set_ui(u: 1); |
53 | if (!odd) |
54 | u2 = mpi_alloc_set_ui(u: 0); |
55 | u3 = mpi_copy(a: u); |
56 | v1 = mpi_copy(a: v); |
57 | if (!odd) { |
58 | v2 = mpi_alloc(mpi_get_nlimbs(u)); |
59 | mpi_sub(w: v2, u: u1, v: u); /* U is used as const 1 */ |
60 | } |
61 | v3 = mpi_copy(a: v); |
62 | if (mpi_test_bit(a: u, n: 0)) { /* u is odd */ |
63 | t1 = mpi_alloc_set_ui(u: 0); |
64 | if (!odd) { |
65 | t2 = mpi_alloc_set_ui(u: 1); |
66 | t2->sign = 1; |
67 | } |
68 | t3 = mpi_copy(a: v); |
69 | t3->sign = !t3->sign; |
70 | goto Y4; |
71 | } else { |
72 | t1 = mpi_alloc_set_ui(u: 1); |
73 | if (!odd) |
74 | t2 = mpi_alloc_set_ui(u: 0); |
75 | t3 = mpi_copy(a: u); |
76 | } |
77 | |
78 | do { |
79 | do { |
80 | if (!odd) { |
81 | if (mpi_test_bit(a: t1, n: 0) || mpi_test_bit(a: t2, n: 0)) { |
82 | /* one is odd */ |
83 | mpi_add(w: t1, u: t1, v); |
84 | mpi_sub(w: t2, u: t2, v: u); |
85 | } |
86 | mpi_rshift(x: t1, a: t1, n: 1); |
87 | mpi_rshift(x: t2, a: t2, n: 1); |
88 | mpi_rshift(x: t3, a: t3, n: 1); |
89 | } else { |
90 | if (mpi_test_bit(a: t1, n: 0)) |
91 | mpi_add(w: t1, u: t1, v); |
92 | mpi_rshift(x: t1, a: t1, n: 1); |
93 | mpi_rshift(x: t3, a: t3, n: 1); |
94 | } |
95 | Y4: |
96 | ; |
97 | } while (!mpi_test_bit(a: t3, n: 0)); /* while t3 is even */ |
98 | |
99 | if (!t3->sign) { |
100 | mpi_set(w: u1, u: t1); |
101 | if (!odd) |
102 | mpi_set(w: u2, u: t2); |
103 | mpi_set(w: u3, u: t3); |
104 | } else { |
105 | mpi_sub(w: v1, u: v, v: t1); |
106 | sign = u->sign; u->sign = !u->sign; |
107 | if (!odd) |
108 | mpi_sub(w: v2, u, v: t2); |
109 | u->sign = sign; |
110 | sign = t3->sign; t3->sign = !t3->sign; |
111 | mpi_set(w: v3, u: t3); |
112 | t3->sign = sign; |
113 | } |
114 | mpi_sub(w: t1, u: u1, v: v1); |
115 | if (!odd) |
116 | mpi_sub(w: t2, u: u2, v: v2); |
117 | mpi_sub(w: t3, u: u3, v: v3); |
118 | if (t1->sign) { |
119 | mpi_add(w: t1, u: t1, v); |
120 | if (!odd) |
121 | mpi_sub(w: t2, u: t2, v: u); |
122 | } |
123 | } while (mpi_cmp_ui(u: t3, v: 0)); /* while t3 != 0 */ |
124 | /* mpi_lshift( u3, k ); */ |
125 | mpi_set(w: x, u: u1); |
126 | |
127 | mpi_free(a: u1); |
128 | mpi_free(a: v1); |
129 | mpi_free(a: t1); |
130 | if (!odd) { |
131 | mpi_free(a: u2); |
132 | mpi_free(a: v2); |
133 | mpi_free(a: t2); |
134 | } |
135 | mpi_free(a: u3); |
136 | mpi_free(a: v3); |
137 | mpi_free(a: t3); |
138 | |
139 | mpi_free(a: u); |
140 | mpi_free(a: v); |
141 | return 1; |
142 | } |
143 | EXPORT_SYMBOL_GPL(mpi_invm); |
144 | |