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