mpi-genesis~ 1
mpi-genesis~ 2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
mpi-genesis~ 3 *
mpi-genesis~ 4 * This file is part of GnuPG.
mpi-genesis~ 5 *
mpi-genesis~ 6 * GnuPG is free software; you can redistribute it and/or modify
mpi-genesis~ 7 * it under the terms of the GNU General Public License as published by
mpi-genesis~ 8 * the Free Software Foundation; either version 3 of the License, or
mpi-genesis~ 9 * (at your option) any later version.
mpi-genesis~ 10 *
mpi-genesis~ 11 * GnuPG is distributed in the hope that it will be useful,
mpi-genesis~ 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
mpi-genesis~ 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
mpi-genesis~ 14 * GNU General Public License for more details.
mpi-genesis~ 15 *
mpi-genesis~ 16 * You should have received a copy of the GNU General Public License
mpi-genesis~ 17 * along with this program; if not, see <http:
mpi-genesis~ 18 */
mpi-genesis~ 19
mpi-genesis~ 20 #include <config.h>
mpi-genesis~ 21 #include <stdio.h>
mpi-genesis~ 22 #include <stdlib.h>
mpi-genesis~ 23 #include "mpi-internal.h"
mpi-genesis~ 24
mpi-genesis~ 25
mpi-genesis~ 26
mpi-genesis~ 27 * Calculate the multiplicative inverse X of A mod N
mpi-genesis~ 28 * That is: Find the solution x for
mpi-genesis~ 29 * 1 = (a*x) mod n
mpi-genesis~ 30 */
mpi-genesis~ 31 void
mpi-genesis~ 32 mpi_invm( MPI x, MPI a, MPI n )
mpi-genesis~ 33 {
mpi-genesis~ 34 #if 0
mpi-genesis~ 35 MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
mpi-genesis~ 36 MPI ta, tb, tc;
mpi-genesis~ 37
mpi-genesis~ 38 u = mpi_copy(a);
mpi-genesis~ 39 v = mpi_copy(n);
mpi-genesis~ 40 u1 = mpi_alloc_set_ui(1);
mpi-genesis~ 41 u2 = mpi_alloc_set_ui(0);
mpi-genesis~ 42 u3 = mpi_copy(u);
mpi-genesis~ 43 v1 = mpi_alloc_set_ui(0);
mpi-genesis~ 44 v2 = mpi_alloc_set_ui(1);
mpi-genesis~ 45 v3 = mpi_copy(v);
mpi-genesis~ 46 q = mpi_alloc( mpi_get_nlimbs(u)+1 );
mpi-genesis~ 47 t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
mpi-genesis~ 48 t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
mpi-genesis~ 49 t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
mpi-genesis~ 50 while( mpi_cmp_ui( v3, 0 ) ) {
mpi-genesis~ 51 mpi_fdiv_q( q, u3, v3 );
mpi-genesis~ 52 mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
mpi-genesis~ 53 mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
mpi-genesis~ 54 mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
mpi-genesis~ 55 mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
mpi-genesis~ 56 }
mpi-genesis~ 57
mpi-genesis~ 58 log_mpidump("q =", q );
mpi-genesis~ 59 log_mpidump("u1=", u1);
mpi-genesis~ 60 log_mpidump("u2=", u2);
mpi-genesis~ 61 log_mpidump("u3=", u3);
mpi-genesis~ 62 log_mpidump("v1=", v1);
mpi-genesis~ 63 log_mpidump("v2=", v2); */
mpi-genesis~ 64 mpi_set(x, u1);
mpi-genesis~ 65
mpi-genesis~ 66 mpi_free(u1);
mpi-genesis~ 67 mpi_free(u2);
mpi-genesis~ 68 mpi_free(u3);
mpi-genesis~ 69 mpi_free(v1);
mpi-genesis~ 70 mpi_free(v2);
mpi-genesis~ 71 mpi_free(v3);
mpi-genesis~ 72 mpi_free(q);
mpi-genesis~ 73 mpi_free(t1);
mpi-genesis~ 74 mpi_free(t2);
mpi-genesis~ 75 mpi_free(t3);
mpi-genesis~ 76 mpi_free(u);
mpi-genesis~ 77 mpi_free(v);
mpi-genesis~ 78 #elif 0
mpi-genesis~ 79
mpi-genesis~ 80 * modified according to Michael Penk's solution for Exercice 35 */
mpi-genesis~ 81
mpi-genesis~ 82
mpi-genesis~ 83 MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
mpi-genesis~ 84 unsigned k;
mpi-genesis~ 85 int sign;
mpi-genesis~ 86
mpi-genesis~ 87 u = mpi_copy(a);
mpi-genesis~ 88 v = mpi_copy(n);
mpi-genesis~ 89 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
mpi-genesis~ 90 mpi_rshift(u, u, 1);
mpi-genesis~ 91 mpi_rshift(v, v, 1);
mpi-genesis~ 92 }
mpi-genesis~ 93
mpi-genesis~ 94
mpi-genesis~ 95 u1 = mpi_alloc_set_ui(1);
mpi-genesis~ 96 u2 = mpi_alloc_set_ui(0);
mpi-genesis~ 97 u3 = mpi_copy(u);
mpi-genesis~ 98 v1 = mpi_copy(v);
mpi-genesis~ 99 v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
mpi-genesis~ 100 v3 = mpi_copy(v);
mpi-genesis~ 101 if( mpi_test_bit(u, 0) ) {
mpi-genesis~ 102 t1 = mpi_alloc_set_ui(0);
mpi-genesis~ 103 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
mpi-genesis~ 104 t3 = mpi_copy(v); t3->sign = !t3->sign;
mpi-genesis~ 105 goto Y4;
mpi-genesis~ 106 }
mpi-genesis~ 107 else {
mpi-genesis~ 108 t1 = mpi_alloc_set_ui(1);
mpi-genesis~ 109 t2 = mpi_alloc_set_ui(0);
mpi-genesis~ 110 t3 = mpi_copy(u);
mpi-genesis~ 111 }
mpi-genesis~ 112 do {
mpi-genesis~ 113 do {
mpi-genesis~ 114 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) {
mpi-genesis~ 115 mpi_add(t1, t1, v);
mpi-genesis~ 116 mpi_sub(t2, t2, u);
mpi-genesis~ 117 }
mpi-genesis~ 118 mpi_rshift(t1, t1, 1);
mpi-genesis~ 119 mpi_rshift(t2, t2, 1);
mpi-genesis~ 120 mpi_rshift(t3, t3, 1);
mpi-genesis~ 121 Y4:
mpi-genesis~ 122 ;
mpi-genesis~ 123 } while( !mpi_test_bit( t3, 0 ) );
mpi-genesis~ 124
mpi-genesis~ 125 if( !t3->sign ) {
mpi-genesis~ 126 mpi_set(u1, t1);
mpi-genesis~ 127 mpi_set(u2, t2);
mpi-genesis~ 128 mpi_set(u3, t3);
mpi-genesis~ 129 }
mpi-genesis~ 130 else {
mpi-genesis~ 131 mpi_sub(v1, v, t1);
mpi-genesis~ 132 sign = u->sign; u->sign = !u->sign;
mpi-genesis~ 133 mpi_sub(v2, u, t2);
mpi-genesis~ 134 u->sign = sign;
mpi-genesis~ 135 sign = t3->sign; t3->sign = !t3->sign;
mpi-genesis~ 136 mpi_set(v3, t3);
mpi-genesis~ 137 t3->sign = sign;
mpi-genesis~ 138 }
mpi-genesis~ 139 mpi_sub(t1, u1, v1);
mpi-genesis~ 140 mpi_sub(t2, u2, v2);
mpi-genesis~ 141 mpi_sub(t3, u3, v3);
mpi-genesis~ 142 if( t1->sign ) {
mpi-genesis~ 143 mpi_add(t1, t1, v);
mpi-genesis~ 144 mpi_sub(t2, t2, u);
mpi-genesis~ 145 }
mpi-genesis~ 146 } while( mpi_cmp_ui( t3, 0 ) );
mpi-genesis~ 147
mpi-genesis~ 148 mpi_set(x, u1);
mpi-genesis~ 149
mpi-genesis~ 150 mpi_free(u1);
mpi-genesis~ 151 mpi_free(u2);
mpi-genesis~ 152 mpi_free(u3);
mpi-genesis~ 153 mpi_free(v1);
mpi-genesis~ 154 mpi_free(v2);
mpi-genesis~ 155 mpi_free(v3);
mpi-genesis~ 156 mpi_free(t1);
mpi-genesis~ 157 mpi_free(t2);
mpi-genesis~ 158 mpi_free(t3);
mpi-genesis~ 159 #else
mpi-genesis~ 160
mpi-genesis~ 161 * modified according to Michael Penk's solution for Exercice 35
mpi-genesis~ 162 * with further enhancement */
mpi-genesis~ 163 MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
mpi-genesis~ 164 unsigned k;
mpi-genesis~ 165 int sign;
mpi-genesis~ 166 int odd ;
mpi-genesis~ 167
mpi-genesis~ 168 u = mpi_copy(a);
mpi-genesis~ 169 v = mpi_copy(n);
mpi-genesis~ 170
mpi-genesis~ 171 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
mpi-genesis~ 172 mpi_rshift(u, u, 1);
mpi-genesis~ 173 mpi_rshift(v, v, 1);
mpi-genesis~ 174 }
mpi-genesis~ 175 odd = mpi_test_bit(v,0);
mpi-genesis~ 176
mpi-genesis~ 177 u1 = mpi_alloc_set_ui(1);
mpi-genesis~ 178 if( !odd )
mpi-genesis~ 179 u2 = mpi_alloc_set_ui(0);
mpi-genesis~ 180 u3 = mpi_copy(u);
mpi-genesis~ 181 v1 = mpi_copy(v);
mpi-genesis~ 182 if( !odd ) {
mpi-genesis~ 183 v2 = mpi_alloc( mpi_get_nlimbs(u) );
mpi-genesis~ 184 mpi_sub( v2, u1, u );
mpi-genesis~ 185 }
mpi-genesis~ 186 v3 = mpi_copy(v);
mpi-genesis~ 187 if( mpi_test_bit(u, 0) ) {
mpi-genesis~ 188 t1 = mpi_alloc_set_ui(0);
mpi-genesis~ 189 if( !odd ) {
mpi-genesis~ 190 t2 = mpi_alloc_set_ui(1); t2->sign = 1;
mpi-genesis~ 191 }
mpi-genesis~ 192 t3 = mpi_copy(v); t3->sign = !t3->sign;
mpi-genesis~ 193 goto Y4;
mpi-genesis~ 194 }
mpi-genesis~ 195 else {
mpi-genesis~ 196 t1 = mpi_alloc_set_ui(1);
mpi-genesis~ 197 if( !odd )
mpi-genesis~ 198 t2 = mpi_alloc_set_ui(0);
mpi-genesis~ 199 t3 = mpi_copy(u);
mpi-genesis~ 200 }
mpi-genesis~ 201 do {
mpi-genesis~ 202 do {
mpi-genesis~ 203 if( !odd ) {
mpi-genesis~ 204 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) {
mpi-genesis~ 205 mpi_add(t1, t1, v);
mpi-genesis~ 206 mpi_sub(t2, t2, u);
mpi-genesis~ 207 }
mpi-genesis~ 208 mpi_rshift(t1, t1, 1);
mpi-genesis~ 209 mpi_rshift(t2, t2, 1);
mpi-genesis~ 210 mpi_rshift(t3, t3, 1);
mpi-genesis~ 211 }
mpi-genesis~ 212 else {
mpi-genesis~ 213 if( mpi_test_bit(t1, 0) )
mpi-genesis~ 214 mpi_add(t1, t1, v);
mpi-genesis~ 215 mpi_rshift(t1, t1, 1);
mpi-genesis~ 216 mpi_rshift(t3, t3, 1);
mpi-genesis~ 217 }
mpi-genesis~ 218 Y4:
mpi-genesis~ 219 ;
mpi-genesis~ 220 } while( !mpi_test_bit( t3, 0 ) );
mpi-genesis~ 221
mpi-genesis~ 222 if( !t3->sign ) {
mpi-genesis~ 223 mpi_set(u1, t1);
mpi-genesis~ 224 if( !odd )
mpi-genesis~ 225 mpi_set(u2, t2);
mpi-genesis~ 226 mpi_set(u3, t3);
mpi-genesis~ 227 }
mpi-genesis~ 228 else {
mpi-genesis~ 229 mpi_sub(v1, v, t1);
mpi-genesis~ 230 sign = u->sign; u->sign = !u->sign;
mpi-genesis~ 231 if( !odd )
mpi-genesis~ 232 mpi_sub(v2, u, t2);
mpi-genesis~ 233 u->sign = sign;
mpi-genesis~ 234 sign = t3->sign; t3->sign = !t3->sign;
mpi-genesis~ 235 mpi_set(v3, t3);
mpi-genesis~ 236 t3->sign = sign;
mpi-genesis~ 237 }
mpi-genesis~ 238 mpi_sub(t1, u1, v1);
mpi-genesis~ 239 if( !odd )
mpi-genesis~ 240 mpi_sub(t2, u2, v2);
mpi-genesis~ 241 mpi_sub(t3, u3, v3);
mpi-genesis~ 242 if( t1->sign ) {
mpi-genesis~ 243 mpi_add(t1, t1, v);
mpi-genesis~ 244 if( !odd )
mpi-genesis~ 245 mpi_sub(t2, t2, u);
mpi-genesis~ 246 }
mpi-genesis~ 247 } while( mpi_cmp_ui( t3, 0 ) );
mpi-genesis~ 248
mpi-genesis~ 249 mpi_set(x, u1);
mpi-genesis~ 250
mpi-genesis~ 251 mpi_free(u1);
mpi-genesis~ 252 mpi_free(v1);
mpi-genesis~ 253 mpi_free(t1);
mpi-genesis~ 254 if( !odd ) {
mpi-genesis~ 255 mpi_free(u2);
mpi-genesis~ 256 mpi_free(v2);
mpi-genesis~ 257 mpi_free(t2);
mpi-genesis~ 258 }
mpi-genesis~ 259 mpi_free(u3);
mpi-genesis~ 260 mpi_free(v3);
mpi-genesis~ 261 mpi_free(t3);
mpi-genesis~ 262
mpi-genesis~ 263 mpi_free(u);
mpi-genesis~ 264 mpi_free(v);
mpi-genesis~ 265 #endif
mpi-genesis~ 266 }