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); 144