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