-
+ 66EDF48A07BB672B7D9329150436A40AB2F1628F1F289B4C52B2E4BDB987B9105F36C441FB21A141346406A675D34B6265A4A0BC00D3C4DE471F461D0ACC5765mpi/mpi-inv.c(0 . 0)(1 . 266)
9084 /* mpi-inv.c - MPI functions
9085 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
9086 *
9087 * This file is part of GnuPG.
9088 *
9089 * GnuPG is free software; you can redistribute it and/or modify
9090 * it under the terms of the GNU General Public License as published by
9091 * the Free Software Foundation; either version 3 of the License, or
9092 * (at your option) any later version.
9093 *
9094 * GnuPG is distributed in the hope that it will be useful,
9095 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9096 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
9097 * GNU General Public License for more details.
9098 *
9099 * You should have received a copy of the GNU General Public License
9100 * along with this program; if not, see <http://www.gnu.org/licenses/>.
9101 */
9102
9103 #include <config.h>
9104 #include <stdio.h>
9105 #include <stdlib.h>
9106 #include "mpi-internal.h"
9107
9108
9109 /****************
9110 * Calculate the multiplicative inverse X of A mod N
9111 * That is: Find the solution x for
9112 * 1 = (a*x) mod n
9113 */
9114 void
9115 mpi_invm( MPI x, MPI a, MPI n )
9116 {
9117 #if 0
9118 MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
9119 MPI ta, tb, tc;
9120
9121 u = mpi_copy(a);
9122 v = mpi_copy(n);
9123 u1 = mpi_alloc_set_ui(1);
9124 u2 = mpi_alloc_set_ui(0);
9125 u3 = mpi_copy(u);
9126 v1 = mpi_alloc_set_ui(0);
9127 v2 = mpi_alloc_set_ui(1);
9128 v3 = mpi_copy(v);
9129 q = mpi_alloc( mpi_get_nlimbs(u)+1 );
9130 t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
9131 t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
9132 t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
9133 while( mpi_cmp_ui( v3, 0 ) ) {
9134 mpi_fdiv_q( q, u3, v3 );
9135 mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
9136 mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
9137 mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
9138 mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
9139 }
9140 /* log_debug("result:\n");
9141 log_mpidump("q =", q );
9142 log_mpidump("u1=", u1);
9143 log_mpidump("u2=", u2);
9144 log_mpidump("u3=", u3);
9145 log_mpidump("v1=", v1);
9146 log_mpidump("v2=", v2); */
9147 mpi_set(x, u1);
9148
9149 mpi_free(u1);
9150 mpi_free(u2);
9151 mpi_free(u3);
9152 mpi_free(v1);
9153 mpi_free(v2);
9154 mpi_free(v3);
9155 mpi_free(q);
9156 mpi_free(t1);
9157 mpi_free(t2);
9158 mpi_free(t3);
9159 mpi_free(u);
9160 mpi_free(v);
9161 #elif 0
9162 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
9163 * modified according to Michael Penk's solution for Exercice 35 */
9164
9165 /* FIXME: we can simplify this in most cases (see Knuth) */
9166 MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
9167 unsigned k;
9168 int sign;
9169
9170 u = mpi_copy(a);
9171 v = mpi_copy(n);
9172 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
9173 mpi_rshift(u, u, 1);
9174 mpi_rshift(v, v, 1);
9175 }
9176
9177
9178 u1 = mpi_alloc_set_ui(1);
9179 u2 = mpi_alloc_set_ui(0);
9180 u3 = mpi_copy(u);
9181 v1 = mpi_copy(v); /* !-- used as const 1 */
9182 v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
9183 v3 = mpi_copy(v);
9184 if( mpi_test_bit(u, 0) ) { /* u is odd */
9185 t1 = mpi_alloc_set_ui(0);
9186 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
9187 t3 = mpi_copy(v); t3->sign = !t3->sign;
9188 goto Y4;
9189 }
9190 else {
9191 t1 = mpi_alloc_set_ui(1);
9192 t2 = mpi_alloc_set_ui(0);
9193 t3 = mpi_copy(u);
9194 }
9195 do {
9196 do {
9197 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
9198 mpi_add(t1, t1, v);
9199 mpi_sub(t2, t2, u);
9200 }
9201 mpi_rshift(t1, t1, 1);
9202 mpi_rshift(t2, t2, 1);
9203 mpi_rshift(t3, t3, 1);
9204 Y4:
9205 ;
9206 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
9207
9208 if( !t3->sign ) {
9209 mpi_set(u1, t1);
9210 mpi_set(u2, t2);
9211 mpi_set(u3, t3);
9212 }
9213 else {
9214 mpi_sub(v1, v, t1);
9215 sign = u->sign; u->sign = !u->sign;
9216 mpi_sub(v2, u, t2);
9217 u->sign = sign;
9218 sign = t3->sign; t3->sign = !t3->sign;
9219 mpi_set(v3, t3);
9220 t3->sign = sign;
9221 }
9222 mpi_sub(t1, u1, v1);
9223 mpi_sub(t2, u2, v2);
9224 mpi_sub(t3, u3, v3);
9225 if( t1->sign ) {
9226 mpi_add(t1, t1, v);
9227 mpi_sub(t2, t2, u);
9228 }
9229 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
9230 /* mpi_lshift( u3, k ); */
9231 mpi_set(x, u1);
9232
9233 mpi_free(u1);
9234 mpi_free(u2);
9235 mpi_free(u3);
9236 mpi_free(v1);
9237 mpi_free(v2);
9238 mpi_free(v3);
9239 mpi_free(t1);
9240 mpi_free(t2);
9241 mpi_free(t3);
9242 #else
9243 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
9244 * modified according to Michael Penk's solution for Exercice 35
9245 * with further enhancement */
9246 MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
9247 unsigned k;
9248 int sign;
9249 int odd ;
9250
9251 u = mpi_copy(a);
9252 v = mpi_copy(n);
9253
9254 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
9255 mpi_rshift(u, u, 1);
9256 mpi_rshift(v, v, 1);
9257 }
9258 odd = mpi_test_bit(v,0);
9259
9260 u1 = mpi_alloc_set_ui(1);
9261 if( !odd )
9262 u2 = mpi_alloc_set_ui(0);
9263 u3 = mpi_copy(u);
9264 v1 = mpi_copy(v);
9265 if( !odd ) {
9266 v2 = mpi_alloc( mpi_get_nlimbs(u) );
9267 mpi_sub( v2, u1, u ); /* U is used as const 1 */
9268 }
9269 v3 = mpi_copy(v);
9270 if( mpi_test_bit(u, 0) ) { /* u is odd */
9271 t1 = mpi_alloc_set_ui(0);
9272 if( !odd ) {
9273 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
9274 }
9275 t3 = mpi_copy(v); t3->sign = !t3->sign;
9276 goto Y4;
9277 }
9278 else {
9279 t1 = mpi_alloc_set_ui(1);
9280 if( !odd )
9281 t2 = mpi_alloc_set_ui(0);
9282 t3 = mpi_copy(u);
9283 }
9284 do {
9285 do {
9286 if( !odd ) {
9287 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
9288 mpi_add(t1, t1, v);
9289 mpi_sub(t2, t2, u);
9290 }
9291 mpi_rshift(t1, t1, 1);
9292 mpi_rshift(t2, t2, 1);
9293 mpi_rshift(t3, t3, 1);
9294 }
9295 else {
9296 if( mpi_test_bit(t1, 0) )
9297 mpi_add(t1, t1, v);
9298 mpi_rshift(t1, t1, 1);
9299 mpi_rshift(t3, t3, 1);
9300 }
9301 Y4:
9302 ;
9303 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
9304
9305 if( !t3->sign ) {
9306 mpi_set(u1, t1);
9307 if( !odd )
9308 mpi_set(u2, t2);
9309 mpi_set(u3, t3);
9310 }
9311 else {
9312 mpi_sub(v1, v, t1);
9313 sign = u->sign; u->sign = !u->sign;
9314 if( !odd )
9315 mpi_sub(v2, u, t2);
9316 u->sign = sign;
9317 sign = t3->sign; t3->sign = !t3->sign;
9318 mpi_set(v3, t3);
9319 t3->sign = sign;
9320 }
9321 mpi_sub(t1, u1, v1);
9322 if( !odd )
9323 mpi_sub(t2, u2, v2);
9324 mpi_sub(t3, u3, v3);
9325 if( t1->sign ) {
9326 mpi_add(t1, t1, v);
9327 if( !odd )
9328 mpi_sub(t2, t2, u);
9329 }
9330 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
9331 /* mpi_lshift( u3, k ); */
9332 mpi_set(x, u1);
9333
9334 mpi_free(u1);
9335 mpi_free(v1);
9336 mpi_free(t1);
9337 if( !odd ) {
9338 mpi_free(u2);
9339 mpi_free(v2);
9340 mpi_free(t2);
9341 }
9342 mpi_free(u3);
9343 mpi_free(v3);
9344 mpi_free(t3);
9345
9346 mpi_free(u);
9347 mpi_free(v);
9348 #endif
9349 }