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 */ 31int 32gcry_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 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 u = mpi_copy(a); 169 v = mpi_copy(n); 170 171 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) { 172 mpi_rshift(u, u, 1); 173 mpi_rshift(v, v, 1); 174 } 175 odd = mpi_test_bit(v,0); 176 177 u1 = mpi_alloc_set_ui(1); 178 if( !odd ) 179 u2 = mpi_alloc_set_ui(0); 180 u3 = mpi_copy(u); 181 v1 = mpi_copy(v); 182 if( !odd ) { 183 v2 = mpi_alloc( mpi_get_nlimbs(u) ); 184 mpi_sub( v2, u1, u ); /* U is used as const 1 */ 185 } 186 v3 = mpi_copy(v); 187 if( mpi_test_bit(u, 0) ) { /* u is odd */ 188 t1 = mpi_alloc_set_ui(0); 189 if( !odd ) { 190 t2 = mpi_alloc_set_ui(1); t2->sign = 1; 191 } 192 t3 = mpi_copy(v); t3->sign = !t3->sign; 193 goto Y4; 194 } 195 else { 196 t1 = mpi_alloc_set_ui(1); 197 if( !odd ) 198 t2 = mpi_alloc_set_ui(0); 199 t3 = mpi_copy(u); 200 } 201 do { 202 do { 203 if( !odd ) { 204 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */ 205 mpi_add(t1, t1, v); 206 mpi_sub(t2, t2, u); 207 } 208 mpi_rshift(t1, t1, 1); 209 mpi_rshift(t2, t2, 1); 210 mpi_rshift(t3, t3, 1); 211 } 212 else { 213 if( mpi_test_bit(t1, 0) ) 214 mpi_add(t1, t1, v); 215 mpi_rshift(t1, t1, 1); 216 mpi_rshift(t3, t3, 1); 217 } 218 Y4: 219 ; 220 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */ 221 222 if( !t3->sign ) { 223 mpi_set(u1, t1); 224 if( !odd ) 225 mpi_set(u2, t2); 226 mpi_set(u3, t3); 227 } 228 else { 229 mpi_sub(v1, v, t1); 230 sign = u->sign; u->sign = !u->sign; 231 if( !odd ) 232 mpi_sub(v2, u, t2); 233 u->sign = sign; 234 sign = t3->sign; t3->sign = !t3->sign; 235 mpi_set(v3, t3); 236 t3->sign = sign; 237 } 238 mpi_sub(t1, u1, v1); 239 if( !odd ) 240 mpi_sub(t2, u2, v2); 241 mpi_sub(t3, u3, v3); 242 if( t1->sign ) { 243 mpi_add(t1, t1, v); 244 if( !odd ) 245 mpi_sub(t2, t2, u); 246 } 247 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */ 248 /* mpi_lshift( u3, k ); */ 249 mpi_set(x, u1); 250 251 mpi_free(u1); 252 mpi_free(v1); 253 mpi_free(t1); 254 if( !odd ) { 255 mpi_free(u2); 256 mpi_free(v2); 257 mpi_free(t2); 258 } 259 mpi_free(u3); 260 mpi_free(v3); 261 mpi_free(t3); 262 263 mpi_free(u); 264 mpi_free(v); 265#endif 266 return 1; 267} 268