1 /* TFM demo program */
2 #include <tfm.h>
3 #include <time.h>
4 #include <unistd.h>
5
6
7 #ifndef TFM_DEMO_TEST_VS_MTEST
8 #define TFM_DEMO_TEST_VS_MTEST 1
9 #endif
10
draw(fp_int * a)11 void draw(fp_int *a)
12 {
13 int x;
14 printf("%d, %d, ", a->used, a->sign);
15 for (x = a->used - 1; x >= 0; x--) {
16 #if SIZEOF_FP_DIGIT == 4
17 printf("%08lx ", a->dp[x]);
18 #else
19 printf("%016llx ", a->dp[x]);
20 #endif
21 }
22 printf("\n");
23 }
24
myrng(unsigned char * dst,int len,void * dat)25 int myrng(unsigned char *dst, int len, void *dat)
26 {
27 int x;
28 (void)dat;
29 for (x = 0; x < len; x++) dst[x] = rand() & 0xFF;
30 return len;
31 }
32
33 char cmd[4096], buf[4096];
34
main(void)35 int main(void)
36 {
37 fp_int a,b,c,d,e,f;
38 unsigned long ix;
39 #if TFM_DEMO_TEST_VS_MTEST
40 unsigned long expt_n, add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n, gcd_n, lcm_n, inv_n,
41 div2_n, mul2_n, add_d_n, sub_d_n, mul_d_n, cnt, rr;
42 #else
43 fp_digit fp;
44 int n, err;
45 #endif
46
47 srand(time(NULL));
48 printf("TFM Ident string:\n%s\n\n", fp_ident());
49 fp_zero(&b); fp_zero(&c); fp_zero(&d); fp_zero(&e); fp_zero(&f);
50 fp_zero(&a);
51
52 #if TFM_DEMO_TEST_VS_MTEST == 0
53
54 draw(&a);
55
56 /* test set and simple shifts */
57 printf("Testing mul/div 2\n");
58 fp_set(&a, 1); draw(&a);
59 for (n = 0; n <= DIGIT_BIT; n++) {
60 fp_mul_2(&a, &a); printf("(%d) ", fp_count_bits(&a));
61 draw(&a);
62
63 }
64 for (n = 0; n <= (DIGIT_BIT + 1); n++) {
65 fp_div_2(&a, &a);
66 draw(&a);
67 }
68 fp_set(&a, 1);
69
70 /* test lshd/rshd */
71 printf("testing lshd/rshd\n");
72 fp_lshd(&a, 3); draw(&a);
73 fp_rshd(&a, 3); draw(&a);
74
75 /* test more complicated shifts */
76 printf("Testing mul/div 2d\n");
77 fp_mul_2d(&a, DIGIT_BIT/2, &a); draw(&a);
78 fp_div_2d(&a, DIGIT_BIT/2, &a, NULL); draw(&a);
79
80 fp_mul_2d(&a, DIGIT_BIT + DIGIT_BIT/2, &a); draw(&a);
81 fp_div_2d(&a, DIGIT_BIT + DIGIT_BIT/2, &a, NULL); draw(&a);
82
83 /* test neg/abs */
84 printf("testing neg/abs\n");
85 fp_neg(&a, &a); draw(&a);
86 fp_neg(&a, &a); draw(&a);
87 fp_neg(&a, &a); draw(&a);
88 fp_abs(&a, &a); draw(&a);
89
90 /* test comparisons */
91 fp_set(&b, 3);
92 fp_set(&c, 4); fp_neg(&c, &c);
93 fp_set(&d, 1);
94 printf("Testing compares\n%d, %d, %d, %d\n", fp_cmp(&a, &b), fp_cmp(&a, &c), fp_cmp(&a, &d), fp_cmp(&b, &c));
95
96 /* test add/sub */
97 printf("Testing add/sub \n");
98 fp_set(&a, ((fp_digit)1)<<(DIGIT_BIT-1)); draw(&a);
99 fp_set(&b, ((fp_digit)1)<<(DIGIT_BIT-2));
100 fp_add(&a, &b, &a); draw(&a);
101 fp_add(&a, &b, &a); draw(&a);
102 fp_add(&a, &b, &a); draw(&a);
103 printf("sub...\n");
104 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
105 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
106 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
107 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
108 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
109 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
110 fp_read_radix(&a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001", 16); draw(&a);
111 fp_sub_d(&a, 3, &b); draw(&b);
112 fp_read_radix(&a, "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE", 16);
113 printf("cmp returns: %d, ", fp_cmp(&a, &b)); fp_sub(&a, &b, &a); draw(&a);
114
115 /* test mul_d */
116 printf("Testing mul_d and div_d\n");
117 fp_set(&a, 1);
118 fp_mul_d(&a, ((fp_digit)1)<<(DIGIT_BIT/2), &a); draw(&a);
119 fp_mul_d(&a, ((fp_digit)1)<<(DIGIT_BIT/2), &a); draw(&a);
120 fp_mul_d(&a, ((fp_digit)1)<<(DIGIT_BIT/2), &a); draw(&a);
121 printf("div_d\n");
122 fp_div_d(&a, ((fp_digit)1)<<(DIGIT_BIT/2), &a, NULL); draw(&a);
123 fp_div_d(&a, ((fp_digit)1)<<(DIGIT_BIT/2), &a, NULL); draw(&a);
124 fp_div_d(&a, ((fp_digit)1)<<(DIGIT_BIT/2), &a, NULL); draw(&a);
125
126 /* testing read radix */
127 printf("Testing read_radix\n");
128 fp_read_radix(&a, "123456789012345678901234567890", 16); draw(&a);
129
130 /* test mont */
131 printf("Montgomery test #1\n");
132 fp_set(&a, 0x1234567ULL);
133 fp_montgomery_setup(&a, &fp);
134 fp_montgomery_calc_normalization(&b, &a);
135
136 fp_read_radix(&d, "123456789123", 16);
137 for (n = 0; n < 1000000; n++) {
138 fp_add_d(&d, 1, &d); fp_sqrmod(&d, &a, &d);
139 fp_mul(&d, &b, &c);
140 fp_montgomery_reduce(&c, &a, fp);
141 if (fp_cmp(&c, &d) != FP_EQ) {
142 printf("Failed mont %d\n", n);
143 draw(&a);
144 draw(&d);
145 draw(&c);
146 return EXIT_FAILURE;
147 }
148 }
149 printf("Passed.\n");
150
151 printf("Montgomery test #2\n");
152 fp_set(&a, 0x1234567ULL);
153 fp_lshd(&a, 4);
154 fp_add_d(&a, 1, &a);
155 fp_montgomery_setup(&a, &fp);
156 fp_montgomery_calc_normalization(&b, &a);
157
158 fp_read_radix(&d, "123456789123", 16);
159 for (n = 0; n < 1000000; n++) {
160 fp_add_d(&d, 1, &d); fp_sqrmod(&d, &a, &d);
161 fp_mul(&d, &b, &c);
162 fp_montgomery_reduce(&c, &a, fp);
163 if (fp_cmp(&c, &d) != FP_EQ) {
164 printf("Failed mont %d\n", n);
165 draw(&a);
166 draw(&d);
167 draw(&c);
168 return EXIT_FAILURE;
169 }
170 }
171 printf("Passed.\n");
172
173 /* test for size */
174 for (ix = 8*DIGIT_BIT; ix < 10*DIGIT_BIT; ix++) {
175 printf("Testing (not safe-prime): %9lu bits \r", ix); fflush(stdout);
176 err = fp_prime_random_ex(&a, 8, ix, (rand()&1)?TFM_PRIME_2MSB_OFF:TFM_PRIME_2MSB_ON, myrng, NULL);
177 if (err != FP_OKAY) {
178 printf("failed with err code %d\n", err);
179 return EXIT_FAILURE;
180 }
181 if ((unsigned long)fp_count_bits(&a) != ix) {
182 printf("Prime is %d not %lu bits!!!\n", fp_count_bits(&a), ix);
183 return EXIT_FAILURE;
184 }
185 }
186 printf("\n\n");
187
188 return 0;
189
190 #else
191
192 fp_zero(&b); fp_zero(&c); fp_zero(&d); fp_zero(&e); fp_zero(&f); fp_zero(&a);
193
194
195 div2_n = mul2_n = inv_n = expt_n = lcm_n = gcd_n = add_n =
196 sub_n = mul_n = div_n = sqr_n = mul2d_n = div2d_n = cnt = add_d_n = sub_d_n= mul_d_n = 0;
197
198 for (;;) {
199 printf("%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu/%4lu ", add_n, sub_n, mul_n, div_n, sqr_n, mul2d_n, div2d_n, gcd_n, lcm_n, expt_n, inv_n, div2_n, mul2_n, add_d_n, sub_d_n, mul_d_n);
200 fgets(cmd, 4095, stdin);
201 cmd[strlen(cmd)-1] = 0;
202 printf("%s ]\r",cmd); fflush(stdout);
203 if (!strcmp(cmd, "mul2d")) { ++mul2d_n;
204 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
205 fgets(buf, 4095, stdin); sscanf(buf, "%lu", &rr);
206 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
207
208 fp_mul_2d(&a, rr, &a);
209 a.sign = b.sign;
210 if (fp_cmp(&a, &b) != FP_EQ) {
211 printf("\nmul2d failed, rr == %lu\n",rr);
212 draw(&a);
213 draw(&b);
214 return 0;
215 }
216 } else if (!strcmp(cmd, "div2d")) { ++div2d_n;
217 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
218 fgets(buf, 4095, stdin); sscanf(buf, "%lu", &rr);
219 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
220
221 fp_div_2d(&a, rr, &a, &e);
222 a.sign = b.sign;
223 if (a.used == b.used && a.used == 0) { a.sign = b.sign = FP_ZPOS; }
224 if (fp_cmp(&a, &b) != FP_EQ) {
225 printf("\ndiv2d failed, rr == %lu\n",rr);
226 draw(&a);
227 draw(&b);
228 return 0;
229 }
230 } else if (!strcmp(cmd, "add")) { ++add_n;
231 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
232 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
233 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
234 fp_copy(&a, &d);
235 fp_add(&d, &b, &d);
236 if (fp_cmp(&c, &d) != FP_EQ) {
237 printf("\nadd %lu failure!\n", add_n);
238 draw(&a);draw(&b);draw(&c);draw(&d);
239 return 0;
240 }
241
242 /* test the sign/unsigned storage functions */
243
244 rr = fp_signed_bin_size(&c);
245 fp_to_signed_bin(&c, (unsigned char *)cmd);
246 memset(cmd+rr, rand()&255, sizeof(cmd)-rr);
247 fp_read_signed_bin(&d, (unsigned char *)cmd, rr);
248 if (fp_cmp(&c, &d) != FP_EQ) {
249 printf("f\np_signed_bin failure!\n");
250 draw(&c);
251 draw(&d);
252 return 0;
253 }
254
255 rr = fp_unsigned_bin_size(&c);
256 fp_to_unsigned_bin(&c, (unsigned char *)cmd);
257 memset(cmd+rr, rand()&255, sizeof(cmd)-rr);
258 fp_read_unsigned_bin(&d, (unsigned char *)cmd, rr);
259 if (fp_cmp_mag(&c, &d) != FP_EQ) {
260 printf("\nfp_unsigned_bin failure!\n");
261 draw(&c);
262 draw(&d);
263 return 0;
264 }
265
266 } else if (!strcmp(cmd, "sub")) { ++sub_n;
267 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
268 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
269 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
270 fp_copy(&a, &d);
271 fp_sub(&d, &b, &d);
272 if (fp_cmp(&c, &d) != FP_EQ) {
273 printf("\nsub %lu failure!\n", sub_n);
274 draw(&a);draw(&b);draw(&c);draw(&d);
275 return 0;
276 }
277 } else if (!strcmp(cmd, "mul")) { ++mul_n;
278 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
279 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
280 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
281 //continue;
282 fp_copy(&a, &d);
283 fp_mul(&d, &b, &d);
284 if (fp_cmp(&c, &d) != FP_EQ) {
285 printf("\nmul %lu failure!\n", mul_n);
286 draw(&a);draw(&b);draw(&c);draw(&d);
287 return 0;
288 }
289 } else if (!strcmp(cmd, "div")) { ++div_n;
290 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
291 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
292 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
293 fgets(buf, 4095, stdin); fp_read_radix(&d, buf, 64);
294 // continue;
295 fp_div(&a, &b, &e, &f);
296 if (fp_cmp(&c, &e) != FP_EQ || fp_cmp(&d, &f) != FP_EQ) {
297 printf("\ndiv %lu failure!\n", div_n);
298 draw(&a);draw(&b);draw(&c);draw(&d); draw(&e); draw(&f);
299 return 0;
300 }
301
302 } else if (!strcmp(cmd, "sqr")) { ++sqr_n;
303 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
304 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
305 // continue;
306 fp_copy(&a, &c);
307 fp_sqr(&c, &c);
308 if (fp_cmp(&b, &c) != FP_EQ) {
309 printf("\nsqr %lu failure!\n", sqr_n);
310 draw(&a);draw(&b);draw(&c);
311 return 0;
312 }
313 } else if (!strcmp(cmd, "gcd")) { ++gcd_n;
314 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
315 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
316 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
317 // continue;
318 fp_copy(&a, &d);
319 fp_gcd(&d, &b, &d);
320 d.sign = c.sign;
321 if (fp_cmp(&c, &d) != FP_EQ) {
322 printf("\ngcd %lu failure!\n", gcd_n);
323 draw(&a);draw(&b);draw(&c);draw(&d);
324 return 0;
325 }
326 } else if (!strcmp(cmd, "lcm")) { ++lcm_n;
327 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
328 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
329 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
330 //continue;
331 fp_copy(&a, &d);
332 fp_lcm(&d, &b, &d);
333 d.sign = c.sign;
334 if (fp_cmp(&c, &d) != FP_EQ) {
335 printf("\nlcm %lu failure!\n", lcm_n);
336 draw(&a);draw(&b);draw(&c);draw(&d);
337 return 0;
338 }
339 } else if (!strcmp(cmd, "expt")) { ++expt_n;
340 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
341 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
342 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
343 fgets(buf, 4095, stdin); fp_read_radix(&d, buf, 64);
344 // continue;
345 fp_copy(&a, &e);
346 fp_exptmod(&e, &b, &c, &e);
347 if (fp_cmp(&d, &e) != FP_EQ) {
348 printf("\nexpt %lu failure!\n", expt_n);
349 draw(&a);draw(&b);draw(&c);draw(&d); draw(&e);
350 return 0;
351 }
352 } else if (!strcmp(cmd, "invmod")) { ++inv_n;
353 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
354 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
355 fgets(buf, 4095, stdin); fp_read_radix(&c, buf, 64);
356 //continue;
357 fp_invmod(&a, &b, &d);
358 #if 1
359 fp_mulmod(&d,&a,&b,&e);
360 if (fp_cmp_d(&e, 1) != FP_EQ) {
361 #else
362 if (fp_cmp(&d, &c) != FP_EQ) {
363 #endif
364 printf("\ninv [wrong value from MPI?!] failure\n");
365 draw(&a);draw(&b);draw(&c);draw(&d);
366 return 0;
367 }
368
369 } else if (!strcmp(cmd, "div2")) { ++div2_n;
370 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
371 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
372 fp_div_2(&a, &c);
373 if (fp_cmp(&c, &b) != FP_EQ) {
374 printf("\ndiv_2 %lu failure\n", div2_n);
375 draw(&a);
376 draw(&b);
377 draw(&c);
378 return 0;
379 }
380 } else if (!strcmp(cmd, "mul2")) { ++mul2_n;
381 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
382 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
383 fp_mul_2(&a, &c);
384 if (fp_cmp(&c, &b) != FP_EQ) {
385 printf("\nmul_2 %lu failure\n", mul2_n);
386 draw(&a);
387 draw(&b);
388 draw(&c);
389 return 0;
390 }
391 } else if (!strcmp(cmd, "add_d")) { ++add_d_n;
392 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
393 fgets(buf, 4095, stdin); sscanf(buf, "%lu", &ix);
394 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
395 fp_add_d(&a, ix, &c);
396 if (fp_cmp(&b, &c) != FP_EQ) {
397 printf("\nadd_d %lu failure\n", add_d_n);
398 draw(&a);
399 draw(&b);
400 draw(&c);
401 printf("d == %lu\n", ix);
402 return 0;
403 }
404 } else if (!strcmp(cmd, "sub_d")) { ++sub_d_n;
405 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
406 fgets(buf, 4095, stdin); sscanf(buf, "%lu", &ix);
407 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
408 fp_sub_d(&a, ix, &c);
409 if (fp_cmp(&b, &c) != FP_EQ) {
410 printf("\nsub_d %lu failure\n", sub_d_n);
411 draw(&a);
412 draw(&b);
413 draw(&c);
414 printf("d == %lu\n", ix);
415 return 0;
416 }
417 } else if (!strcmp(cmd, "mul_d")) { ++mul_d_n;
418 fgets(buf, 4095, stdin); fp_read_radix(&a, buf, 64);
419 fgets(buf, 4095, stdin); sscanf(buf, "%lu", &ix);
420 fgets(buf, 4095, stdin); fp_read_radix(&b, buf, 64);
421 fp_mul_d(&a, ix, &c);
422 if (fp_cmp(&b, &c) != FP_EQ) {
423 printf("\nmul_d %lu failure\n", mul_d_n);
424 draw(&a);
425 draw(&b);
426 draw(&c);
427 printf("d == %lu\n", ix);
428 return 0;
429 }
430 }
431
432 }
433 #endif
434 }
435
436
437
438 /* $Source$ */
439 /* $Revision$ */
440 /* $Date$ */
441