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