summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--powm.c524
1 files changed, 396 insertions, 128 deletions
diff --git a/powm.c b/powm.c
index e847e54..b8599df 100644
--- a/powm.c
+++ b/powm.c
@@ -1,3 +1,4 @@
1#include <stdlib.h>
1#include <stdint.h> 2#include <stdint.h>
2#include <string.h> 3#include <string.h>
3#include <stdio.h> 4#include <stdio.h>
@@ -24,6 +25,7 @@ does not leak information about the number of bits set, but on average doubling
24time needed. Discuss ;) 25time needed. Discuss ;)
25*/ 26*/
26 27
28static int run_tests( );
27#if 0 29#if 0
28typedef uint32_t leg_t; 30typedef uint32_t leg_t;
29typedef uint64_t dleg_t; 31typedef uint64_t dleg_t;
@@ -37,6 +39,7 @@ typedef uint128_t dleg_t;
37//#define WITH_PREVENT_TIMING_ATTACKS 39//#define WITH_PREVENT_TIMING_ATTACKS
38#define WITH_ROUNDS 128 40#define WITH_ROUNDS 128
39#define KARATSUBA_THRESHOLD 16 41#define KARATSUBA_THRESHOLD 16
42//#define WITH_TESTS
40 43
41#ifdef WITH_MEASURE_GMP 44#ifdef WITH_MEASURE_GMP
42#include <gmp.h> 45#include <gmp.h>
@@ -47,7 +50,7 @@ static void dump_int( int level, char * prefix, leg_t const * p, int l, int nl )
47{ 50{
48 printf( "L%d %s: ", level, prefix ); 51 printf( "L%d %s: ", level, prefix );
49 while( l-- ) 52 while( l-- )
50 printf( "%08llX", *(p++) ); 53 printf( "%08llX", p[l] );
51 if( nl ) 54 if( nl )
52 putchar( 10 ); 55 putchar( 10 );
53} 56}
@@ -137,54 +140,53 @@ static const leg_t g_r_inverse = 1;
137#if 1 140#if 1
138/* Standard prime for leg_t defined as uint64_t */ 141/* Standard prime for leg_t defined as uint64_t */
139static const leg_t g_prime[] = { 142static const leg_t g_prime[] = {
140 0xFFFFFFFFFFFFFFFF, 0xC90FDAA22168C234, 0xC4C6628B80DC1CD1, 0x29024E088A67CC74, 143 0xFFFFFFFFFFFFFFFF, 0x4DF435C934063199, 0x86FFB7DC90A6C08F, 0x93B4EA988D8FDDC1,
141 0x020BBEA63B139B22, 0x514A08798E3404DD, 0xEF9519B3CD3A431B, 0x302B0A6DF25F1437, 144 0xD0069127D5B05AA9, 0xB81BDD762170481C, 0x1F612970CEE2D7AF, 0x233BA186515BE7ED,
142 0x4FE1356D6D51C245, 0xE485B576625E7EC6, 0xF44C42E9A637ED6B, 0x0BFF5CB6F406B7ED, 145 0x99B2964FA090C3A2, 0x287C59474E6BC05D, 0x2E8EFC141FBECAA6, 0xDBBBC2DB04DE8EF9,
143 0xEE386BFB5A899FA5, 0xAE9F24117C4B1FE6, 0x49286651ECE45B3D, 0xC2007CB8A163BF05, 146 0x2583E9CA2AD44CE8, 0x1A946834B6150BDA, 0x99C327186AF4E23C, 0x88719A10BDBA5B26,
144 0x98DA48361C55D39A, 0x69163FA8FD24CF5F, 0x83655D23DCA3AD96, 0x1C62F356208552BB, 147 0x1A723C12A787E6D7, 0x4B82D120A9210801, 0x43DB5BFCE0FD108E, 0x08E24FA074E5AB31,
145 0x9ED529077096966D, 0x670C354E4ABC9804, 0xF1746C08CA18217C, 0x32905E462E36CE3B, 148 0x770988C0BAD946E2, 0xBBE117577A615D6C, 0x521F2B18177B200C, 0xD87602733EC86A64,
146 0xE39E772C180E8603, 0x9B2783A2EC07A28F, 0xB5C55DF06F4C52C9, 0xDE2BCBF695581718, 149 0xF12FFA06D98A0864, 0xCEE3D2261AD2EE6B, 0x1E8C94E04A25619D, 0xABF5AE8CDB0933D7,
147 0x3995497CEA956AE5, 0x15D2261898FA0510, 0x15728E5A8AAAC42D, 0xAD33170D04507A33, 150 0xB3970F85A6E1E4C7, 0x8AEA71575D060C7D, 0xECFB850458DBEF0A, 0xA85521ABDF1CBA64,
148 0xA85521ABDF1CBA64, 0xECFB850458DBEF0A, 0x8AEA71575D060C7D, 0xB3970F85A6E1E4C7, 151 0xAD33170D04507A33, 0x15728E5A8AAAC42D, 0x15D2261898FA0510, 0x3995497CEA956AE5,
149 0xABF5AE8CDB0933D7, 0x1E8C94E04A25619D, 0xCEE3D2261AD2EE6B, 0xF12FFA06D98A0864, 152 0xDE2BCBF695581718, 0xB5C55DF06F4C52C9, 0x9B2783A2EC07A28F, 0xE39E772C180E8603,
150 0xD87602733EC86A64, 0x521F2B18177B200C, 0xBBE117577A615D6C, 0x770988C0BAD946E2, 153 0x32905E462E36CE3B, 0xF1746C08CA18217C, 0x670C354E4ABC9804, 0x9ED529077096966D,
151 0x08E24FA074E5AB31, 0x43DB5BFCE0FD108E, 0x4B82D120A9210801, 0x1A723C12A787E6D7, 154 0x1C62F356208552BB, 0x83655D23DCA3AD96, 0x69163FA8FD24CF5F, 0x98DA48361C55D39A,
152 0x88719A10BDBA5B26, 0x99C327186AF4E23C, 0x1A946834B6150BDA, 0x2583E9CA2AD44CE8, 155 0xC2007CB8A163BF05, 0x49286651ECE45B3D, 0xAE9F24117C4B1FE6, 0xEE386BFB5A899FA5,
153 0xDBBBC2DB04DE8EF9, 0x2E8EFC141FBECAA6, 0x287C59474E6BC05D, 0x99B2964FA090C3A2, 156 0x0BFF5CB6F406B7ED, 0xF44C42E9A637ED6B, 0xE485B576625E7EC6, 0x4FE1356D6D51C245,
154 0x233BA186515BE7ED, 0x1F612970CEE2D7AF, 0xB81BDD762170481C, 0xD0069127D5B05AA9, 157 0x302B0A6DF25F1437, 0xEF9519B3CD3A431B, 0x514A08798E3404DD, 0x020BBEA63B139B22,
155 0x93B4EA988D8FDDC1, 0x86FFB7DC90A6C08F, 0x4DF435C934063199, 0xFFFFFFFFFFFFFFFF 158 0x29024E088A67CC74, 0xC4C6628B80DC1CD1, 0xC90FDAA22168C234, 0xFFFFFFFFFFFFFFFF
156}; 159 };
157 160
158static const leg_t g_r_square[] = { 161static const leg_t g_r_square[] = {
159 0x3DA97659E280DB0B, 0xE65BCC3AB78FDAA9, 0xB7B768C89931D78D, 0xF8B11725339EBC93, 162 0xC14AB0DDCC03AA20, 0x8A1AC024B30E9B12, 0xFA8F75F0067E82B1, 0x37BF90FE52074F19,
160 0xAA7FBD9562059F1F, 0x4C2DE67DAD47527E, 0x526A653A7A674BD5, 0x5401EA4F3ED73A2F, 163 0x55EA6F7541C4F82B, 0xB850DE95D97AC40A, 0x3549C5777A17FB04, 0x2A434CEB230B2DFE,
161 0x70B56F527F6F604F, 0xF3E56CC2BD9F048C, 0xFEA80D9A6EC9FCD3, 0x3AD36FD822C39F34, 164 0x524E7C7A7ED36C41, 0xE44040921C1E467C, 0xA796D18204A636F7, 0xC9C77F0C352D408C,
162 0x91F30C52F798DA6A, 0x18C3DCE20188D84C, 0xCB225176259E080F, 0xA89D1DCD9D381CC5, 165 0x51E75D9998F001DB, 0x8267537D4A612A18, 0x912A04913E9EBD87, 0x2E52989ECCF85F34,
163 0xBEACD46F3CDD1196, 0x91A4F5572929B90C, 0x67DE8FA023864714, 0xC28A61D47411402D, 166 0xD203A9E0D7CE25D0, 0x53C44FAB734810F7, 0x20BD72B9B21E6B3D, 0x62D218771296EF6A,
164 0x6C09060D41058639, 0xE4FCCF1D638F4566, 0x9E10FDE28E54806B, 0xF1D27D0B5C7DC9C2, 167 0x8563215F72C8D989, 0x04BA044AEB4EEFD4, 0xAE01E0F363A9315D, 0x5F666146CB441F59,
165 0xB616D6FA8BE2C91D, 0xE8105464E9F80A5F, 0x3472086990DACF1A, 0x7E2C75A58E25F142, 168 0xE60C6EFDFFB7A9A9, 0x6C7951A523CEF785, 0x0995484320E739F4, 0xFDC65A269B51C1EF,
166 0x8FB4832EF827DE84, 0xCA06DA91C2B3E7E2, 0x4F024193787A8278, 0x8BD70562DA60E392, 169 0xC93919D12A4B1A67, 0xB18A9EF150C8953A, 0x1D7D37A23FB8CF61, 0x46BDB7336E8452D9,
167 0x46BDB7336E8452D9, 0x1D7D37A23FB8CF61, 0xB18A9EF150C8953A, 0xC93919D12A4B1A67, 170 0x8BD70562DA60E392, 0x4F024193787A8278, 0xCA06DA91C2B3E7E2, 0x8FB4832EF827DE84,
168 0xFDC65A269B51C1EF, 0x0995484320E739F4, 0x6C7951A523CEF785, 0xE60C6EFDFFB7A9A9, 171 0x7E2C75A58E25F142, 0x3472086990DACF1A, 0xE8105464E9F80A5F, 0xB616D6FA8BE2C91D,
169 0x5F666146CB441F59, 0xAE01E0F363A9315D, 0x04BA044AEB4EEFD4, 0x8563215F72C8D989, 172 0xF1D27D0B5C7DC9C2, 0x9E10FDE28E54806B, 0xE4FCCF1D638F4566, 0x6C09060D41058639,
170 0x62D218771296EF6A, 0x20BD72B9B21E6B3D, 0x53C44FAB734810F7, 0xD203A9E0D7CE25D0, 173 0xC28A61D47411402D, 0x67DE8FA023864714, 0x91A4F5572929B90C, 0xBEACD46F3CDD1196,
171 0x2E52989ECCF85F34, 0x912A04913E9EBD87, 0x8267537D4A612A18, 0x51E75D9998F001DB, 174 0xA89D1DCD9D381CC5, 0xCB225176259E080F, 0x18C3DCE20188D84C, 0x91F30C52F798DA6A,
172 0xC9C77F0C352D408C, 0xA796D18204A636F7, 0xE44040921C1E467C, 0x524E7C7A7ED36C41, 175 0x3AD36FD822C39F34, 0xFEA80D9A6EC9FCD3, 0xF3E56CC2BD9F048C, 0x70B56F527F6F604F,
173 0x2A434CEB230B2DFE, 0x3549C5777A17FB04, 0xB850DE95D97AC40A, 0x55EA6F7541C4F82B, 176 0x5401EA4F3ED73A2F, 0x526A653A7A674BD5, 0x4C2DE67DAD47527E, 0xAA7FBD9562059F1F,
174 0x37BF90FE52074F19, 0xFA8F75F0067E82B1, 0x8A1AC024B30E9B12, 0xC14AB0DDCC03AA20 177 0xF8B11725339EBC93, 0xB7B768C89931D78D, 0xE65BCC3AB78FDAA9, 0x3DA97659E280DB0B
175}; 178};
176 179
177static const leg_t g_r_inverse = 1; 180static const leg_t g_r_inverse = 1;
178#endif 181#endif
179 182
180/* Returns 0 if a and b are equal, -1 if a < b, 1 if a > b */ 183/* Returns 0 if a and b are equal, -1 if a < b, 1 if a > b */
181static int mp_cmp( leg_t const *a, leg_t const *b, int const legs ) 184static int mp_cmp( leg_t const *a, leg_t const *b, int legs )
182{ 185{
183 int leg; 186 while( legs-- )
184 for( leg=0; leg<legs; ++leg )
185 { 187 {
186 if( a[leg] < b[leg] ) return -1; 188 if( a[legs] < b[legs] ) return -1;
187 if( a[leg] > b[leg] ) return 1; 189 if( a[legs] > b[legs] ) return 1;
188 } 190 }
189 return 0; 191 return 0;
190} 192}
@@ -196,34 +198,34 @@ static void mp_sub( leg_t *a, leg_t const *b, int legs )
196 int borrow = 0, borrow_temp; 198 int borrow = 0, borrow_temp;
197 while( legs-- ) 199 while( legs-- )
198 { 200 {
199 leg_t temp = a[legs] - b[legs]; 201 leg_t temp = *a - *(b++);
200 borrow_temp = temp > a[legs]; 202 borrow_temp = temp > *a;
201 a[legs] = temp - borrow; 203 *a = temp - borrow;
202 borrow = borrow_temp | ( a[legs] > temp ); 204 borrow = borrow_temp | ( *(a++) > temp );
203 } 205 }
204 while( borrow ) 206 while( borrow )
205 { 207 {
206 leg_t temp = a[legs] - borrow; 208 leg_t temp = *a - borrow;
207 borrow = temp > a[legs]; 209 borrow = temp > *a;
208 a[legs--] = temp; 210 *(a++) = temp;
209 } 211 }
210} 212}
211 213
212/* Add b to a, store in a. Operates on legs + flegs words, with 214/* Add b to a, store in a. Operates on legs + flegs words, with
213 flegs the amount of legs to propagate the carry to */ 215 flegs the amount of legs to propagate the carry to */
214static void mp_adm( leg_t *a, leg_t const *b, int legs, int flegs ) 216static void mp_add( leg_t *a, leg_t const *b, int legs, int flegs )
215{ 217{
216 dleg_t acc = 0; 218 dleg_t acc = 0;
217 while( legs-- > 0 ) 219 while( legs-- )
218 { 220 {
219 acc += (dleg_t)a[legs] + (dleg_t)b[legs]; 221 acc += (dleg_t)*a + (dleg_t)*(b++);
220 a[legs] = (leg_t)acc; 222 *(a++) = (leg_t)acc;
221 acc >>= 8*sizeof(leg_t); 223 acc >>= 8*sizeof(leg_t);
222 } 224 }
223 while( acc && flegs-- ) 225 while( acc && flegs-- )
224 { 226 {
225 acc += (dleg_t)a[legs]; 227 acc += (dleg_t)*a;
226 a[legs--] = (leg_t)acc; 228 *(a++) = (leg_t)acc;
227 acc >>= 8*sizeof(leg_t); 229 acc >>= 8*sizeof(leg_t);
228 } 230 }
229} 231}
@@ -234,19 +236,25 @@ static void mp_sub_mod( leg_t * result, leg_t const *a, leg_t const * b, int leg
234 int borrow = 0, borrow_temp; 236 int borrow = 0, borrow_temp;
235 while( legs-- ) 237 while( legs-- )
236 { 238 {
237 leg_t temp = a[legs] - b[legs]; 239 leg_t temp = *a - *(b++);
238 borrow_temp = temp > a[legs]; 240 borrow_temp = temp > *(a++);
239 result[legs] = temp - borrow; 241 *result = temp - borrow;
240 borrow = borrow_temp | (result[legs] > temp ); 242 borrow = borrow_temp | (*(result++) > temp );
241 } 243 }
242} 244}
243 245
244/* Fast negate */ 246/* Fast negate */
245static void mp_negate( leg_t * p, int legs ) 247static void mp_negate( leg_t * p, int legs )
246{ 248{
247 int legss = legs; 249 /* Only as long as we find 0 along the way, we need to
248 while( legs--) p[legs]^=(leg_t)-1; 250 propagate the carry of -x == !x+1 */
249 while( legss-- && !++p[legss] ); 251 int carry = 1;
252 while( legs-- )
253 {
254 leg_t v = carry + ( *p ^ (leg_t)-1 );
255 if(v) carry = 0;
256 *(p++)=v;
257 }
250} 258}
251 259
252/* Multiplies a with fac, adds to result. 260/* Multiplies a with fac, adds to result.
@@ -254,17 +262,16 @@ static void mp_negate( leg_t * p, int legs )
254static void mp_mul_uint_add( leg_t *result, leg_t const *a, leg_t fac, int legs ) 262static void mp_mul_uint_add( leg_t *result, leg_t const *a, leg_t fac, int legs )
255{ 263{
256 dleg_t acc = 0; 264 dleg_t acc = 0;
257 leg_t *r = result+legs-1;
258 while( legs-- ) 265 while( legs-- )
259 { 266 {
260 acc += (dleg_t)*r + (dleg_t)a[legs] * (dleg_t)fac; 267 acc += (dleg_t)*result + (dleg_t)*(a++) * (dleg_t)fac;
261 *(r--) = (leg_t)acc; 268 *(result++) = (leg_t)acc;
262 acc >>= 8*sizeof(leg_t); 269 acc >>= 8*sizeof(leg_t);
263 } 270 }
264 while( acc ) 271 while( acc )
265 { 272 {
266 acc += (dleg_t)*r; 273 acc += (dleg_t)*result;
267 *(r--) = (leg_t)acc; 274 *(result++) = (leg_t)acc;
268 acc >>= 8*sizeof(leg_t); 275 acc >>= 8*sizeof(leg_t);
269 } 276 }
270} 277}
@@ -274,28 +281,29 @@ static void mp_mul_oper_add( leg_t * result, leg_t const *a, leg_t const *b, int
274{ 281{
275 int leg = legs; 282 int leg = legs;
276 while( leg-- ) 283 while( leg-- )
277 mp_mul_uint_add( result + 1 + leg, a, b[leg], legs ); 284 mp_mul_uint_add( result++, a, *(b++), legs );
278} 285}
279 286
280/* Optimized mp_mul_oper_add for a == b, i.e. squaring */ 287/* Optimized mp_mul_oper_add for a == b, i.e. squaring */
281static void mp_sqr( leg_t *result, leg_t const * a, int legs ) 288static void mp_sqr( leg_t *result, leg_t const * a, int legs )
282{ 289{
283 while( legs-- ) { 290 while( legs-- ) {
284 leg_t *offs = result+2*legs+1; 291 leg_t fac = *(a++), *dest = result;
285 leg_t fac = a[legs]; 292 leg_t const *src = a;
286 int leg = legs; 293 int leg = legs;
287 dleg_t acc = (dleg_t)*offs + (dleg_t)fac * (dleg_t)fac;
288 294
289 *(offs--) = (leg_t)acc; 295 dleg_t acc = (dleg_t)*dest + (dleg_t)fac * (dleg_t)fac;
296
297 *(dest++) = (leg_t)acc;
290 acc >>= 8*sizeof(leg_t); 298 acc >>= 8*sizeof(leg_t);
291 299
292 while( leg-- ) 300 while( leg-- )
293 { 301 {
294 dleg_t subresult = (dleg_t)fac * (dleg_t)a[leg]; 302 dleg_t subresult = (dleg_t)fac * (dleg_t)*(src++);
295 int carry = !!( subresult >> (16*sizeof(leg_t)-1)); 303 int carry = !!( subresult >> (16*sizeof(leg_t)-1));
296 304
297 acc += 2 * subresult + (dleg_t)*offs; 305 acc += 2 * subresult + (dleg_t)*dest;
298 *(offs--) = (leg_t)acc; 306 *(dest++) = (leg_t)acc;
299 307
300 acc >>= 8*sizeof(leg_t); 308 acc >>= 8*sizeof(leg_t);
301 acc += (dleg_t)carry << 8*sizeof(leg_t); 309 acc += (dleg_t)carry << 8*sizeof(leg_t);
@@ -303,10 +311,11 @@ static void mp_sqr( leg_t *result, leg_t const * a, int legs )
303 311
304 while( acc ) 312 while( acc )
305 { 313 {
306 acc += (dleg_t)*offs; 314 acc += (dleg_t)*dest;
307 *(offs--) = (leg_t)acc; 315 *(dest++) = (leg_t)acc;
308 acc >>= 8*sizeof(leg_t); 316 acc >>= 8*sizeof(leg_t);
309 } 317 }
318 result += 2;
310 } 319 }
311} 320}
312 321
@@ -326,15 +335,15 @@ static void mp_mul_kara_square( leg_t* p, leg_t const *a, int len, leg_t *scratc
326 mp_sub_mod( scratch, a + n, a, n ); 335 mp_sub_mod( scratch, a + n, a, n );
327 336
328 mp_mul_kara_square( p + n, scratch, n, scratch + len ); 337 mp_mul_kara_square( p + n, scratch, n, scratch + len );
329 mp_negate( p, len + n ); 338 mp_negate( p + n, len + n );
330 339
331 mp_mul_kara_square( scratch, a + n, n, scratch + len ); 340 mp_mul_kara_square( scratch, a + n, n, scratch + len );
332 mp_adm( p + len, scratch, len, len ); 341 mp_add( p + len, scratch, len, 0 );
333 mp_adm( p + n, scratch, len, n ); 342 mp_add( p + n, scratch, len, n );
334 343
335 mp_mul_kara_square( scratch, a, n, scratch + len ); 344 mp_mul_kara_square( scratch, a, n, scratch + len );
336 mp_adm( p + n, scratch, len, n ); 345 mp_add( p + n, scratch, len, n );
337 mp_adm( p, scratch, len, 0 ); 346 mp_add( p, scratch, len, len );
338 } 347 }
339} 348}
340 349
@@ -366,15 +375,15 @@ static void mp_mul_kara( leg_t* p, leg_t const *a, leg_t const *b, int len, leg_
366 375
367 mp_mul_kara( p + n, scratch, scratch + n, n, scratch + len ); 376 mp_mul_kara( p + n, scratch, scratch + n, n, scratch + len );
368 if( !sign ) 377 if( !sign )
369 mp_negate( p, len + n ); 378 mp_negate( p + n, len + n );
370 379
371 mp_mul_kara( scratch, a + n, b + n, n, scratch + len ); 380 mp_mul_kara( scratch, a + n, b + n, n, scratch + len );
372 mp_adm( p + len, scratch, len, len ); 381 mp_add( p + len, scratch, len, 0 );
373 mp_adm( p + n, scratch, len, n ); 382 mp_add( p + n, scratch, len, n );
374 383
375 mp_mul_kara( scratch, a, b, n, scratch + len ); 384 mp_mul_kara( scratch, a, b, n, scratch + len );
376 mp_adm( p + n, scratch, len, n ); 385 mp_add( p + n, scratch, len, n );
377 mp_adm( p, scratch, len, 0 ); 386 mp_add( p, scratch, len, len );
378 } 387 }
379} 388}
380 389
@@ -387,38 +396,40 @@ static void mp_mul_kara( leg_t* p, leg_t const *a, leg_t const *b, int len, leg_
387 */ 396 */
388static void redc( leg_t *a, leg_t const *b, int legs, int do_mul ) 397static void redc( leg_t *a, leg_t const *b, int legs, int do_mul )
389{ 398{
390 leg_t scratch[ 2 * ( legs * legs / KARATSUBA_THRESHOLD ) ]; 399 leg_t scratch[ 2 * ( legs - KARATSUBA_THRESHOLD ) ];
391 leg_t temp[1 + 2 * legs]; 400 leg_t temp[1 + 2 * legs];
392 leg_t leg = legs; 401 leg_t leg;
393 402
394 /* Not necessary for transforming back */ 403 /* Not necessary for transforming back */
395 if( do_mul ) 404 if( do_mul )
396 { 405 {
397 temp[0] = 0; 406 temp[2*legs] = 0;
398 if( a == b ) 407 if( a == b )
399 mp_mul_kara_square( temp + 1, a, legs, scratch ); 408 mp_mul_kara_square( temp, a, legs, scratch );
400 else 409 else
401 mp_mul_kara( temp + 1, a, b, legs, scratch ); 410 mp_mul_kara( temp, a, b, legs, scratch );
402 } 411 }
403 else 412 else
404 { 413 {
405 memset( temp, 0, ( 1 + legs ) * sizeof(leg_t)); 414 memset( temp + legs, 0, (legs + 1 ) * sizeof(leg_t));
406 memcpy( temp + 1 + legs, a, legs * sizeof(leg_t)); 415 memcpy( temp, a, legs * sizeof(leg_t));
407 } 416 }
408 417
409 /* m = p * ( m * R_1 ) % R */ 418 /* m = p * ( m * R_1 ) % R */
410 while( leg-- ) 419 for( leg = 0; leg < legs; ++leg )
411 { 420 {
412 leg_t k = temp[1+legs+leg] * 1; // g_r_inverse; 421 leg_t k = temp[leg] * g_r_inverse;
413 mp_mul_uint_add( temp + 1 + leg + 1, g_prime, k, legs ); 422 mp_mul_uint_add( temp+leg, g_prime, k, legs );
414 } 423 }
415 424
416 /* the lower legs of temp are now zero */ 425 /* the lower legs of temp are now zero
417 /* if necessary, reduce temp to fit in legs */ 426 if necessary, reduce temp to fit in legs */
418 if( temp[0] || mp_cmp( temp + 1, g_prime, legs ) > 0 ) 427 if( temp[2*legs] || mp_cmp( temp + legs, g_prime, legs ) > 0 )
419 mp_sub( temp + 1, g_prime, legs ); 428 mp_sub( temp + legs, g_prime, legs );
420 429
421 memcpy( a, temp + 1, legs * sizeof(leg_t) ); 430 memcpy( a, temp + legs, legs * sizeof(leg_t) );
431 memset( scratch, 0, sizeof( scratch ) );
432 memset( temp, 0, sizeof( temp ) );
422} 433}
423 434
424/* calculate base ^ exponent modulo g_prime */ 435/* calculate base ^ exponent modulo g_prime */
@@ -428,18 +439,18 @@ static void powm( leg_t * result, leg_t const *exponent, leg_t base, int legs )
428#ifdef WITH_PREVENT_TIMING_ATTACKS 439#ifdef WITH_PREVENT_TIMING_ATTACKS
429 leg_t dummy[legs]; 440 leg_t dummy[legs];
430#endif 441#endif
431 int first = 0, bit = legs * 8 * sizeof(leg_t); 442 int first = 0, bit;
432 443
433 memset( acc, 0, sizeof(acc) ); 444 memset( acc, 0, sizeof(acc) );
434 acc[legs-1] = base; 445 *acc = base;
435 446
436 /* Transform base into montgomery domain */ 447 /* Transform base into montgomery domain */
437 redc( acc, g_r_square, legs, 1 ); 448 redc( acc, g_r_square, legs, 1 );
438 449
439 /* mul in temp and if bit set in exponent, multiply into accumulator */ 450 /* mul in temp and if bit set in exponent, multiply into accumulator */
440 while( bit-- ) 451 for( bit = 0; bit < legs * 8 * sizeof(leg_t); bit++ )
441 { 452 {
442 int this_bit = sizeof(leg_t) * 8 - 1 - ( bit % ( sizeof(leg_t) * 8 ) ); 453 int this_bit = bit % ( sizeof(leg_t) * 8 );
443 if( ( exponent[ bit / ( sizeof(leg_t) * 8 ) ] >> this_bit ) & 1 ) { 454 if( ( exponent[ bit / ( sizeof(leg_t) * 8 ) ] >> this_bit ) & 1 ) {
444 if( first++ ) 455 if( first++ )
445 redc( result, acc, legs, 1 ); 456 redc( result, acc, legs, 1 );
@@ -450,8 +461,7 @@ static void powm( leg_t * result, leg_t const *exponent, leg_t base, int legs )
450 else 461 else
451 redc( dummy, acc, legs, 1 ); 462 redc( dummy, acc, legs, 1 );
452#endif 463#endif
453 if( bit ) 464 redc( acc, acc, legs, 1 );
454 redc( acc, acc, legs, 1 );
455 } 465 }
456 466
457 /* Transform result in acc back into mod p domain */ 467 /* Transform result in acc back into mod p domain */
@@ -459,44 +469,66 @@ static void powm( leg_t * result, leg_t const *exponent, leg_t base, int legs )
459 redc( result, 0, legs, 0 ); 469 redc( result, 0, legs, 0 );
460 else /* base ^ 0 mod p = 1 */ 470 else /* base ^ 0 mod p = 1 */
461 { 471 {
462 memset( result, 0, legs * sizeof(leg_t) ); 472 memset( result+1, 0, legs * sizeof(leg_t) );
463 result[legs-1] = 1; 473 *result = 1;
464 } 474 }
465} 475}
466 476
477static void mp_import( leg_t *dest, uint8_t const * src, size_t len )
478{
479 int byte = 0;
480 leg_t acc = 0;
481 while( len-- )
482 {
483 acc |= ((leg_t)src[len]) << ( 8 * byte );
484 if( ++byte == sizeof(leg_t))
485 {
486 *(dest++) = acc;
487 acc = 0;
488 byte = 0;
489 }
490 }
491 if( byte )
492 *dest = acc;
493}
494
467int main() 495int main()
468{ 496{
469 int i, legs = 64; 497 int i, legs = 64;
470 leg_t input[ /*legs*/ ] = { 498 leg_t input[ /*legs*/ ] = {
471 0x1de7eae6c0d6a0b0, 0x9ac2961fe160f837, 0xe5d85f8fb8fced5c, 0xb563a9cf79c6eaec, 499 0x281b04b30bb62984, 0xe0cc506399225574, 0xb08ad95f8040183f, 0x56eee1ba0dc1936c,
472 0xa6d78571af8d3688, 0x118727b5eb17dfbd, 0x6060e2cd96000219, 0x52292d56ea2960a9, 500 0x5ec1d62932d6937a, 0xfa8718685a5b8359, 0xfb4e8dadb3111df4, 0x87e90f5b6397727e,
473 0x72d720399b4ad2d4, 0xd07dc909e7070b0e, 0xcb650843a43a4a00, 0x950e895d7777d182, 501 0x6b984d2e7b9cc244, 0x9ae478fd69254dc9, 0x21da1ef76099ed94, 0xe407bde8519bc534,
474 0x3ca892560247ca32, 0xac5ecd1fe4997513, 0xb420bd7e538ef88b, 0x2bca50f311573101, 502 0x051a88159adc842b, 0x547fd48d3b471c7c, 0xd6b85c29e8e8a528, 0x74fc0b5dcdfaa679,
475 0x31052a6fc332563d, 0xd151e2770baec00b, 0x094d72c301b8f25d, 0x70f0c055dde43121, 503 0xe0c022a74c073360, 0xc0dc8c759af7492b, 0xa86946df6abbea0f, 0xfcc2a7f6d4b0d4f7,
476 0x1f61b1ea0e5aafb4, 0x0e84ab94e744b8ba, 0x87e0db1397d9f2fd, 0xa13b801d1ac631d5, 504 0xd2111f6ce69c2bc6, 0x4ab8b5e0adaad6a0, 0xf8df973a9842e7b2, 0x2d44f438b889673c,
477 0xb5444312b3b43541, 0xa3612061c92319ce, 0x0e2aab629710919b, 0xd7ac4896d4e08b35, 505 0x82b4e75bf0e60d06, 0x4c3b1333a07fee24, 0x353eb64e067f86cc, 0x518781609b447bf8,
478 0x1785bbfb88755c99, 0x70cc7ff6ea8f1b51, 0x5479eaeb9b64ba87, 0xa77b229138f2d5d1, 506 0xe9228ae741da24cd, 0xd8aec44d430026aa, 0x196bcb0cc0e353f8, 0x942fad7b2cc3dcc5,
479 0x942fad7b2cc3dcc5, 0x196bcb0cc0e353f8, 0xd8aec44d430026aa, 0xe9228ae741da24cd, 507 0xa77b229138f2d5d1, 0x5479eaeb9b64ba87, 0x70cc7ff6ea8f1b51, 0x1785bbfb88755c99,
480 0x518781609b447bf8, 0x353eb64e067f86cc, 0x4c3b1333a07fee24, 0x82b4e75bf0e60d06, 508 0xd7ac4896d4e08b35, 0x0e2aab629710919b, 0xa3612061c92319ce, 0xb5444312b3b43541,
481 0x2d44f438b889673c, 0xf8df973a9842e7b2, 0x4ab8b5e0adaad6a0, 0xd2111f6ce69c2bc6, 509 0xa13b801d1ac631d5, 0x87e0db1397d9f2fd, 0x0e84ab94e744b8ba, 0x1f61b1ea0e5aafb4,
482 0xfcc2a7f6d4b0d4f7, 0xa86946df6abbea0f, 0xc0dc8c759af7492b, 0xe0c022a74c073360, 510 0x70f0c055dde43121, 0x094d72c301b8f25d, 0xd151e2770baec00b, 0x31052a6fc332563d,
483 0x74fc0b5dcdfaa679, 0xd6b85c29e8e8a528, 0x547fd48d3b471c7c, 0x051a88159adc842b, 511 0x2bca50f311573101, 0xb420bd7e538ef88b, 0xac5ecd1fe4997513, 0x3ca892560247ca32,
484 0xe407bde8519bc534, 0x21da1ef76099ed94, 0x9ae478fd69254dc9, 0x6b984d2e7b9cc244, 512 0x950e895d7777d182, 0xcb650843a43a4a00, 0xd07dc909e7070b0e, 0x72d720399b4ad2d4,
485 0x87e90f5b6397727e, 0xfb4e8dadb3111df4, 0xfa8718685a5b8359, 0x5ec1d62932d6937a, 513 0x52292d56ea2960a9, 0x6060e2cd96000219, 0x118727b5eb17dfbd, 0xa6d78571af8d3688,
486 0x56eee1ba0dc1936c, 0xb08ad95f8040183f, 0xe0cc506399225574, 0x281b04b30bb62984 514 0xb563a9cf79c6eaec, 0xe5d85f8fb8fced5c, 0x9ac2961fe160f837, 0x1de7eae6c0d6a0b0,
487 }; 515 };
488 516
489 leg_t res[legs]; /* 517 leg_t res[legs]; /*
490= { 569D056BC5485C6F3C026935CFC1FC36CFC5A6B770B442323750EE08A32C63F64743A4902E32A41F7C5A9097509EB9AAA5C5B425D9BDAEDC3B98EE3A9F99AE6FB8723EBE01154937ECC1E4AE38CBC12B767FD17264A4AAEB310EA5B0E72D12FE3969532C5A0718B45F251BFB2A126EFB87F819BDCD434EAEE3B9108C387F4DFFEFA0E9532A0532192034DB0EF5C5BB2A77BCA5B4A08DFFD22F6B1D4F17F5123935CAB4F40EC7E77F4FEEEC6A8CD20CDB2D37DD1BB44544C50B01E98F8B3F5E1ABF91817D40B7E526D6ED80CDE416C6CD32218D3ECCA753D15BBB007661754E44A937C5A68957C3C2D3F39A220930567E9F720B3AAE9D34FEBA6E5A047C131F32271A3BC1E85BC1BC210F49B09F3938226399991BC90299B4E0E684B2DE6BDA684693F40CF728FD24A4B1D1A2B8F4CD3316A02DBC44069A40C1AC64F862091A888DD284AB180918B379A3BD173EDDEA5E08DF4BE51B441AEA7EDA4E439CF57914F68E0FB3E756AB7286616C3736CA72DD40A88FC37B598BF561300AFD1F80F7D44E53C4C1D85FF215250A0C56222A177299C61C2E654B040176F4A8D44BE2612B36E066E7AA6E58D84D4C4CB9A5952E1668CDF04EE55C38ABA59614CB7F43D12921551DD82062AFC3F340B33F43C643BC9D5DB6D6BAB2C94F100D139443B20BCB80384C3231261C5ABFFF3D971CB878116F4EBB7D4D24A2B6F5869 } 518= { 569D056BC5485C6F3C026935CFC1FC36CFC5A6B770B442323750EE08A32C63F64743A4902E32A41F7C5A9097509EB9AAA5C5B425D9BDAEDC3B98EE3A9F99AE6FB8723EBE01154937ECC1E4AE38CBC12B767FD17264A4AAEB310EA5B0E72D12FE3969532C5A0718B45F251BFB2A126EFB87F819BDCD434EAEE3B9108C387F4DFFEFA0E9532A0532192034DB0EF5C5BB2A77BCA5B4A08DFFD22F6B1D4F17F5123935CAB4F40EC7E77F4FEEEC6A8CD20CDB2D37DD1BB44544C50B01E98F8B3F5E1ABF91817D40B7E526D6ED80CDE416C6CD32218D3ECCA753D15BBB007661754E44A937C5A68957C3C2D3F39A220930567E9F720B3AAE9D34FEBA6E5A047C131F32271A3BC1E85BC1BC210F49B09F3938226399991BC90299B4E0E684B2DE6BDA684693F40CF728FD24A4B1D1A2B8F4CD3316A02DBC44069A40C1AC64F862091A888DD284AB180918B379A3BD173EDDEA5E08DF4BE51B441AEA7EDA4E439CF57914F68E0FB3E756AB7286616C3736CA72DD40A88FC37B598BF561300AFD1F80F7D44E53C4C1D85FF215250A0C56222A177299C61C2E654B040176F4A8D44BE2612B36E066E7AA6E58D84D4C4CB9A5952E1668CDF04EE55C38ABA59614CB7F43D12921551DD82062AFC3F340B33F43C643BC9D5DB6D6BAB2C94F100D139443B20BCB80384C3231261C5ABFFF3D971CB878116F4EBB7D4D24A2B6F5869 }
491*/ 519*/
492 520
521#ifdef WITH_TESTS
522 run_tests();
523#endif
524
493#ifdef WITH_MEASURE_GMP 525#ifdef WITH_MEASURE_GMP
494 mpz_t m, base, exp, result; 526 mpz_t m, base, exp, result;
495 527
496 mpz_init( m ); mpz_init( base ); mpz_init( exp ); mpz_init( result ); 528 mpz_init( m ); mpz_init( base ); mpz_init( exp ); mpz_init( result );
497 mpz_import( m, sizeof(g_prime) / sizeof(uint64_t), 1, sizeof(uint64_t), 0, 0, g_prime ); 529 mpz_import( m, sizeof(g_prime) / sizeof(uint64_t), -1, sizeof(uint64_t), 0, 0, g_prime );
498 mpz_set_ui( base, 2 ); 530 mpz_set_ui( base, 2 );
499 mpz_import( exp, sizeof(input) / sizeof(uint64_t), 1, sizeof(uint64_t), 0, 0, input ); 531 mpz_import( exp, sizeof(input) / sizeof(uint64_t), -1, sizeof(uint64_t), 0, 0, input );
500 532
501 for( i=0; i< WITH_ROUNDS; ++i ) 533 for( i=0; i< WITH_ROUNDS; ++i )
502 mpz_powm( result, base, exp, m ); 534 mpz_powm( result, base, exp, m );
@@ -507,10 +539,246 @@ int main()
507 for( i=0; i<WITH_ROUNDS; ++i ) 539 for( i=0; i<WITH_ROUNDS; ++i )
508 powm( res, input, 2, legs ); 540 powm( res, input, 2, legs );
509 541
510 for( i=0; i<legs; ++i ) 542 for( i=legs-1; i>=0; --i )
511 printf( "%08llX", res[i] ); 543 printf( "%016llX", res[i] );
512 putchar(10); putchar(10); 544 putchar(10); putchar(10);
513#endif 545#endif
514 546
515 return 0; 547 return 0;
516} 548}
549
550#ifdef WITH_TESTS
551#define TEST_MAX 1024
552static void REPORT( char * fail ) { fprintf( stderr, "\nFailed in %s\n", fail ); exit(-1); }
553static leg_t test_001[] = { (leg_t)-1, 1 };
554static leg_t test_002[] = { (leg_t)-1, 2 };
555static leg_t test_003[] = { 0, 1 };
556static leg_t test_004[] = { (leg_t)-1, 1, 1 };
557static leg_t test_005[] = { 0, (leg_t)-1, 0 };
558static leg_t test_006[] = { (leg_t)-2, 4, 0 };
559static leg_t test_007[] = { (leg_t)-1, (leg_t)-2 };
560static leg_t test_008[] = { (leg_t)-1, (leg_t)-3 };
561static leg_t test_009[] = { (leg_t)-2, (leg_t)-4, 0 };
562static leg_t test_010[] = { (leg_t)-2, (leg_t)-4, 1 };
563
564static uint8_t test_011[] = {
565 0xf2, 0xda, 0xe5, 0x35, 0xa0, 0xbd, 0xb8, 0x4c, 0x88, 0x65, 0x50, 0xca, 0xe8, 0x17, 0xa8, 0xab, 0x34, 0xd6, 0x86, 0xc4, 0x29, 0xa0, 0xc8, 0x51, 0x84, 0x05, 0x3e, 0x9d, 0x4d, 0x23, 0xce, 0x75,
566 0x1f, 0xa6, 0xc1, 0x36, 0x86, 0x35, 0xf5, 0x6f, 0xcc, 0x0b, 0x13, 0x40, 0x89, 0xc2, 0x41, 0xb0, 0x0e, 0xa7, 0x68, 0xd4, 0x68, 0x6a, 0xd2, 0x08, 0xf7, 0xf5, 0x2c, 0x05, 0x11, 0x43, 0x00, 0x9b,
567 0xf4, 0x92, 0xe1, 0x17, 0xae, 0xcc, 0x05, 0x98, 0x95, 0xc4, 0x33, 0xfd, 0x54, 0x42, 0x06, 0x98, 0x90, 0x62, 0x61, 0x15, 0x34, 0xe8, 0xbd, 0x37, 0xe0, 0x57, 0x27, 0x90, 0x75, 0x08, 0x33, 0x15,
568 0xe5, 0x48, 0x19, 0xbb, 0x2c, 0xc1, 0xda, 0xeb, 0x95, 0x72, 0x97, 0x05, 0x60, 0xbf, 0xbf, 0x80, 0xfe, 0x04, 0x7a, 0x4a, 0xff, 0x0e, 0xa0, 0x47, 0x82, 0x0d, 0x90, 0xf0, 0x5b, 0xfc, 0x21, 0x82
569};
570static uint8_t test_012[] = {
571 0x0c, 0xc4, 0xc0, 0xb7, 0x13, 0xee, 0xf6, 0xf3, 0xcd, 0xf7, 0x02, 0x0b, 0x97, 0x70, 0xc0, 0x59, 0x27, 0xd2, 0x74, 0xbf, 0x54, 0xbf, 0x9d, 0x77, 0x59, 0xe0, 0x86, 0x06, 0x18, 0x7a, 0x3c, 0x3e,
572 0x12, 0x52, 0xed, 0x77, 0x10, 0xf9, 0x4b, 0xb8, 0xb7, 0x2b, 0xdc, 0x23, 0xe0, 0x45, 0x79, 0xe2, 0xe9, 0xef, 0x12, 0x97, 0x22, 0xf8, 0x72, 0xa2, 0x05, 0x1f, 0x5f, 0x36, 0xae, 0xfb, 0x7a, 0xb2,
573 0x7d, 0xd7, 0xa2, 0x15, 0xa4, 0x9f, 0x27, 0x55, 0x65, 0x2a, 0x49, 0x0f, 0xca, 0x9f, 0xf3, 0xf6, 0x26, 0xcb, 0x57, 0x07, 0x82, 0xb7, 0x04, 0x1a, 0x7b, 0x65, 0x40, 0xb8, 0x55, 0x93, 0xee, 0xd4,
574 0x09, 0x3e, 0x30, 0xa1, 0x6c, 0x00, 0x90, 0x54, 0x9b, 0x05, 0xb4, 0x08, 0xc4, 0xcc, 0xcd, 0xa2, 0xf6, 0xe6, 0x34, 0xf3, 0x5f, 0xe0, 0xe4, 0xb3, 0xcd, 0xd3, 0x8f, 0x83, 0xb2, 0xe8, 0x08, 0xb6
575};
576static uint8_t test_013[] = {
577 0x0C, 0x1C, 0xE9, 0x27, 0xD9, 0xE2, 0xF8, 0x92, 0x97, 0x0B, 0x8E, 0x79, 0x91, 0x07, 0xE7, 0xAA, 0xF8, 0x5C, 0x11, 0xAB, 0x84, 0xFA, 0x0C, 0x6F, 0xED, 0xA5, 0x0C, 0x1F, 0x4C, 0x55, 0x5F, 0x5B,
578 0x70, 0x63, 0x22, 0x85, 0x72, 0x6B, 0x3D, 0x9A, 0x78, 0x6E, 0xBF, 0x2E, 0x29, 0xB8, 0x2E, 0xE4, 0x4C, 0x09, 0x35, 0x45, 0x92, 0x26, 0xCC, 0x29, 0x15, 0xFC, 0x9A, 0x2F, 0x58, 0x4E, 0x70, 0xDD,
579 0x00, 0xA9, 0xC7, 0xDE, 0xF5, 0x26, 0x85, 0x23, 0xDF, 0xBF, 0x00, 0x61, 0xC7, 0x47, 0x0E, 0x23, 0x9D, 0xC3, 0xB6, 0x17, 0x8C, 0x36, 0x19, 0x03, 0x70, 0xD1, 0xE1, 0xE7, 0x58, 0xDD, 0x10, 0xD5,
580 0x76, 0x3B, 0xA7, 0xAE, 0x73, 0xAC, 0x4E, 0xBF, 0x4B, 0x79, 0xE5, 0xDE, 0x19, 0x68, 0x1D, 0x19, 0xD4, 0xF1, 0xF9, 0x90, 0x0B, 0x55, 0x9A, 0x8A, 0xAE, 0x5C, 0x85, 0x0C, 0x84, 0xB1, 0x33, 0x2F,
581 0x0E, 0x99, 0xFC, 0xC6, 0x57, 0xE8, 0x81, 0x53, 0x23, 0x87, 0x5D, 0x41, 0xDF, 0xC9, 0xE0, 0xE5, 0xE1, 0x8C, 0x2C, 0x4E, 0x69, 0xAE, 0x99, 0x54, 0x19, 0x85, 0x7F, 0x7F, 0x19, 0x1E, 0x28, 0xC2,
582 0x04, 0xAB, 0x16, 0x1D, 0xE9, 0x22, 0x55, 0xD2, 0x2D, 0x45, 0x44, 0xD2, 0x16, 0x3C, 0x2B, 0xD3, 0xE5, 0x88, 0xF2, 0x5E, 0x97, 0x92, 0x51, 0xF0, 0x64, 0x7D, 0x27, 0x5E, 0x0F, 0x5C, 0x99, 0xD8,
583 0x02, 0xA8, 0xD3, 0x87, 0x90, 0x02, 0x9E, 0x4E, 0x9A, 0x9D, 0x72, 0xF3, 0xA8, 0xBC, 0x28, 0x74, 0xBD, 0x60, 0x92, 0xE1, 0x4A, 0x7E, 0x3E, 0xC2, 0xB3, 0x88, 0xBA, 0xAD, 0x8F, 0xFF, 0xCD, 0x57,
584 0xE2, 0x7E, 0x43, 0x68, 0x91, 0xC3, 0xBE, 0x50, 0x9E, 0xB8, 0xFA, 0x53, 0x3C, 0xEE, 0x1F, 0x4C, 0x59, 0x5D, 0x4B, 0xE8, 0x42, 0x32, 0xD5, 0xE4, 0xFC, 0xD7, 0xFD, 0x12, 0x08, 0x1B, 0xE2, 0x6C
585};
586
587static uint8_t test_014[] = {
588 0xE6, 0x62, 0x94, 0x84, 0x90, 0x75, 0x70, 0x5D, 0xF3, 0x6C, 0xC7, 0xFC, 0x45, 0x0C, 0x9F, 0xF7, 0x37, 0xB9, 0x71, 0x65, 0x62, 0x47, 0xC6, 0xD8, 0xFE, 0x93, 0xB0, 0xF1, 0xE2, 0x34, 0x78, 0x99,
589 0xE1, 0xED, 0x3C, 0xA7, 0xF0, 0xD3, 0x00, 0x26, 0xA0, 0x18, 0xAA, 0x43, 0xDB, 0xFA, 0xD1, 0xFE, 0x2A, 0x71, 0xC5, 0xD1, 0xA1, 0x1D, 0xC0, 0xD3, 0x26, 0x15, 0x43, 0x6F, 0x06, 0x35, 0x5D, 0x02,
590 0x3A, 0xFD, 0x58, 0xAA, 0x91, 0x4A, 0x27, 0xFC, 0xD5, 0x78, 0xBC, 0x65, 0xE6, 0xE6, 0xEC, 0x4E, 0x25, 0xBE, 0xEC, 0xDD, 0x82, 0xDB, 0x6D, 0xDE, 0x42, 0x4D, 0xE6, 0x39, 0x71, 0x80, 0x4B, 0xDA,
591 0x2E, 0xD2, 0x25, 0x70, 0x96, 0x9D, 0x7B, 0x1B, 0x61, 0x85, 0xE6, 0x3C, 0x31, 0x4B, 0x60, 0x07, 0xCA, 0x66, 0xEF, 0x98, 0xEA, 0xAE, 0xED, 0xB8, 0x91, 0xC2, 0x8A, 0x70, 0x3B, 0xAC, 0x0B, 0x0A,
592 0x3D, 0x80, 0xC9, 0x55, 0x96, 0x2F, 0xF3, 0xED, 0x55, 0xBC, 0x8B, 0x06, 0x62, 0xD9, 0x3F, 0x18, 0x4D, 0x87, 0x51, 0xD2, 0x11, 0x97, 0x7D, 0x16, 0xC5, 0xF0, 0xAB, 0x25, 0xCA, 0xB4, 0xF2, 0x66,
593 0xCE, 0xCE, 0x58, 0xBB, 0x23, 0x10, 0x53, 0x6E, 0xA8, 0x96, 0xAD, 0x67, 0x9A, 0xEE, 0x53, 0xF0, 0x37, 0xCF, 0x51, 0x88, 0x51, 0xB8, 0x45, 0x15, 0x19, 0xCD, 0x84, 0xAD, 0xEB, 0xC5, 0xAA, 0x9C,
594 0xCC, 0x03, 0x47, 0x2B, 0xDC, 0xCF, 0x86, 0x67, 0x04, 0xA0, 0xBA, 0xF5, 0x1D, 0x6B, 0xB2, 0xAB, 0x2E, 0xAA, 0x83, 0x5F, 0x56, 0x3F, 0x33, 0xB7, 0xA6, 0xA9, 0xF1, 0x0D, 0x95, 0x7B, 0x2F, 0x21,
595 0xB6, 0xC0, 0x0E, 0xF2, 0x03, 0x91, 0x56, 0x3C, 0x56, 0x4C, 0x91, 0x87, 0xB3, 0x68, 0x49, 0xC5, 0x8E, 0x12, 0x41, 0xB6, 0xFD, 0xD9, 0xC8, 0xE7, 0xAE, 0xB2, 0x4B, 0xE4, 0x68, 0x52, 0xC6, 0x04
596};
597
598static uint8_t test_015[] = {
599 0x00, 0xA3, 0x09, 0x48, 0xD3, 0x48, 0x0D, 0xE4, 0xF4, 0x42, 0xA7, 0xA7, 0x7E, 0x47, 0xE0, 0x07, 0x6E, 0x93, 0x73, 0x43, 0xE9, 0x42, 0x6D, 0xCC, 0x87, 0xAE, 0x3B, 0x87, 0x33, 0xAE, 0xDF, 0x4E,
600 0x32, 0xE5, 0x78, 0x0C, 0x93, 0xD9, 0x84, 0xCC, 0x31, 0x8B, 0xB4, 0x83, 0xC7, 0x45, 0x71, 0xA9, 0x3C, 0x9F, 0x60, 0x8E, 0xA0, 0xED, 0x80, 0xF5, 0xBD, 0xC1, 0x75, 0x70, 0xB5, 0xFE, 0x39, 0x2A,
601 0x90, 0xB9, 0x00, 0xF7, 0x7D, 0x78, 0x91, 0x43, 0xB4, 0xC2, 0x9F, 0xC9, 0x77, 0x8A, 0x26, 0xC9, 0x17, 0xF4, 0x08, 0x0F, 0x5A, 0x5A, 0x64, 0x99, 0x47, 0xF6, 0x6E, 0x41, 0x77, 0x35, 0x20, 0x03,
602 0xB6, 0xCC, 0x3C, 0x21, 0x4C, 0x87, 0x18, 0x7E, 0x8A, 0x13, 0xCA, 0x2D, 0x51, 0x53, 0x76, 0xAE, 0x94, 0x37, 0xA4, 0x32, 0x5F, 0x0E, 0x47, 0x50, 0x9A, 0xD6, 0xDB, 0x30, 0xED, 0x43, 0xAC, 0xC3,
603 0xD4, 0x1E, 0x53, 0xD2, 0x9C, 0x29, 0x69, 0x98, 0xF6, 0x82, 0xF2, 0x12, 0x50, 0x04, 0x72, 0xC9, 0x57, 0x17, 0xA8, 0xF9, 0x80, 0xED, 0xDF, 0x96, 0x54, 0x5E, 0x1D, 0x21, 0x51, 0xCB, 0xC9, 0xAF,
604 0xC5, 0xC2, 0x71, 0xE1, 0xB4, 0xF1, 0xDF, 0xCA, 0xC9, 0xF3, 0x71, 0x4C, 0x91, 0x03, 0xA9, 0x71, 0x3B, 0x08, 0xCA, 0x67, 0x2D, 0x65, 0x35, 0x38, 0x16, 0x02, 0xE5, 0xF9, 0x1C, 0x58, 0x23, 0xE6,
605 0x7E, 0x14, 0x97, 0x51, 0x6B, 0xDE, 0xEB, 0x14, 0xB0, 0xE7, 0xB8, 0x59, 0xAD, 0xC4, 0x98, 0xA2, 0xEC, 0x1F, 0x32, 0x35, 0x31, 0x96, 0x64, 0x82, 0x7B, 0x2A, 0x48, 0x59, 0x1B, 0xC8, 0x9C, 0xBB,
606 0x55, 0x6D, 0xE7, 0xAD, 0xBC, 0x14, 0x48, 0xF8, 0xF5, 0xBB, 0xD1, 0xF6, 0xC5, 0xD5, 0xDC, 0x62, 0x8F, 0x4D, 0x91, 0x92, 0xA2, 0x95, 0x4C, 0x95, 0xA8, 0x3F, 0xBC, 0xB0, 0xE2, 0x2B, 0xE1, 0x64
607};
608
609static int run_tests( )
610{
611 leg_t val1[TEST_MAX], val2[TEST_MAX], val3[TEST_MAX], scratch[TEST_MAX];
612 int i;
613
614 /***********************************************************************/
615 printf( "Testing mp_cmp... " );
616
617 printf( "1 " );
618 if( mp_cmp( test_001, test_001, sizeof(test_001) / sizeof(leg_t ) ))
619 REPORT( "MP_CMP test 1" );
620
621 printf( "2 " );
622 if( mp_cmp( test_001, test_002, sizeof(test_001) / sizeof(leg_t ) ) != -1 )
623 REPORT( "MP_CMP test 2" );
624
625 printf( "3 " );
626 if( mp_cmp( test_002, test_001, sizeof(test_001) / sizeof(leg_t ) ) != 1 )
627 REPORT( "MP_CMP test 3" );
628
629 printf( "success.\n" );
630
631 /***********************************************************************/
632 printf( "Testing mp_sub... " );
633 printf( "1 " );
634 memcpy( val1, test_002, sizeof(test_002) );
635 mp_sub( val1, test_001, sizeof(test_001) / sizeof(leg_t ) );
636 if( memcmp( val1, test_003, sizeof(test_003)) )
637 REPORT( "MP_SUB test 1" );
638
639 printf( "2 " );
640 memset( val1, 0, sizeof(val1) );
641 memcpy( val1, test_004, sizeof(test_004) );
642 mp_sub( val1, test_002, sizeof(test_002) / sizeof(leg_t ) );
643 if( memcmp( val1, test_005, sizeof(test_005)))
644 REPORT( "MP_SUB test 2" );
645
646 printf( "success.\n" );
647
648 /***********************************************************************/
649 printf( "Testing mp_add... " );
650 printf( "1 " );
651 memset( val1, 0, sizeof(val1) );
652 memcpy( val1, test_002, sizeof(test_002) );
653 mp_add( val1, test_001, sizeof(test_001) / sizeof(leg_t ), 0 );
654 if( memcmp( val1, test_006, sizeof(test_006)) )
655 REPORT( "MP_ADD test 1" );
656
657 printf( "2 " );
658 memset( val1, 0, sizeof(val1) );
659 memcpy( val1, test_007, sizeof(test_007) );
660 mp_add( val1, test_008, sizeof(test_008) / sizeof(leg_t ), 0 );
661 if( memcmp( val1, test_009, sizeof(test_009)) )
662 REPORT( "MP_ADD test 2" );
663
664 printf( "3 " );
665 memset( val1, 0, sizeof(val1) );
666 memcpy( val1, test_007, sizeof(test_007) );
667 mp_add( val1, test_008, sizeof(test_008) / sizeof(leg_t ), 1 );
668 if( memcmp( val1, test_010, sizeof(test_010)) )
669 REPORT( "MP_ADD test 3" );
670
671 printf( "success.\n" );
672 /***********************************************************************/
673
674 printf( "Testing mp_mul_oper_add... " );
675 printf( "1 " );
676 memset( val1, 0, sizeof(val1) );
677 mp_import( val2, test_011, sizeof(test_011) );
678 mp_import( val3, test_012, sizeof(test_012) );
679 mp_mul_oper_add( val1, val2, val3, sizeof(test_011) / sizeof(leg_t ) );
680 mp_import( val3, test_013, sizeof(test_013) );
681
682 if( memcmp( val1, val3, sizeof(test_013)) )
683 REPORT( "MP_MUL_OPER_ADD test 1" );
684
685 printf( "2 " );
686 memset( val1, 0, sizeof(val1) );
687 mp_import( val2, test_011, sizeof(test_011) );
688 mp_mul_oper_add( val1, val2, val2, sizeof(test_011) / sizeof(leg_t ) );
689 mp_import( val3, test_014, sizeof(test_014) );
690
691 if( memcmp( val1, val3, sizeof(test_014)) )
692 REPORT( "MP_MUL_OPER_ADD test 2" );
693
694 printf( "success.\n" );
695 /***********************************************************************/
696
697 printf( "Testing mp_sqr... " );
698 printf( "1 " );
699 memset( val1, 0, sizeof(val1) );
700 mp_import( val2, test_011, sizeof(test_011) );
701 mp_sqr( val1, val2, sizeof(test_011) / sizeof(leg_t ) );
702 mp_import( val3, test_014, sizeof(test_014) );
703
704 if( memcmp( val1, val3, sizeof(test_014)) )
705 REPORT( "MP_SQR test 1" );
706
707 printf( "2 " );
708 memset( val1, 0, sizeof(val1) );
709 mp_import( val2, test_012, sizeof(test_012) );
710 mp_sqr( val1, val2, sizeof(test_012) / sizeof(leg_t ) );
711 mp_import( val3, test_015, sizeof(test_015) );
712
713 if( memcmp( val1, val3, sizeof(test_015)) )
714 REPORT( "MP_SQR test 2" );
715
716 printf( "success.\n" );
717 /***********************************************************************/
718
719 printf( "Testing mp_mul_kara_square... " );
720 printf( "1 " );
721 memset( val1, 0, sizeof(val1) );
722 mp_import( val2, test_011, sizeof(test_011) );
723 mp_mul_kara_square( val1, val2, sizeof(test_011) / sizeof(leg_t ), scratch );
724 mp_import( val3, test_014, sizeof(test_014) );
725
726 if( memcmp( val1, val3, sizeof(test_014)) )
727 REPORT( "MP_MUL_KARA_SQUARE test 1" );
728
729 printf( "2 " );
730 memset( val1, 0, sizeof(val1) );
731 mp_import( val2, test_012, sizeof(test_012) );
732 mp_mul_kara_square( val1, val2, sizeof(test_012) / sizeof(leg_t ), scratch );
733 mp_import( val3, test_015, sizeof(test_015) );
734
735 if( memcmp( val1, val3, sizeof(test_015)) )
736 REPORT( "MP_MUL_KARA_SQUARE test 2" );
737
738 printf( "success.\n" );
739 /***********************************************************************/
740
741 printf( "Testing mp_mul_kara... " );
742 printf( "1 " );
743 memset( val1, 0, sizeof(val1) );
744 mp_import( val2, test_011, sizeof(test_011) );
745 mp_import( val3, test_012, sizeof(test_012) );
746 mp_mul_kara( val1, val2, val3, sizeof(test_011) / sizeof(leg_t ), scratch );
747 mp_import( val3, test_013, sizeof(test_013) );
748
749 if( memcmp( val1, val3, sizeof(test_013)) )
750 REPORT( "MP_MUL_KARA test 1" );
751
752 printf( "2 " );
753 memset( val1, 0, sizeof(val1) );
754 mp_import( val2, test_011, sizeof(test_011) );
755 mp_import( val2, test_011, sizeof(test_011) );
756 mp_mul_kara( val1, val2, val2, sizeof(test_011) / sizeof(leg_t ), scratch );
757 mp_import( val3, test_014, sizeof(test_014) );
758
759 if( memcmp( val1, val3, sizeof(test_014)) )
760 REPORT( "MP_MUL_KARA test 2" );
761
762 printf( "3 " );
763 memset( val1, 0, sizeof(val1) );
764 mp_import( val2, test_012, sizeof(test_012) );
765 mp_import( val2, test_012, sizeof(test_012) );
766 mp_mul_kara( val1, val2, val2, sizeof(test_012) / sizeof(leg_t ), scratch );
767 mp_import( val3, test_015, sizeof(test_015) );
768
769 if( memcmp( val1, val3, sizeof(test_015)) )
770 REPORT( "MP_MUL_KARA test 3" );
771
772 printf( "success.\n" );
773 /***********************************************************************/
774
775
776// putchar(10);
777// for( i = sizeof(test_013)/sizeof(leg_t )-1; i>=0; --i) printf( "%016llX", val1[i] );
778// putchar(10);
779// for( i = sizeof(test_013)/sizeof(leg_t )-1; i>=0; --i) printf( "%016llX", val3[i] );
780// putchar(10);
781
782}
783
784#endif