1 /* main-bigint-test.c */
3 This file is part of the AVR-Crypto-Lib.
4 Copyright (C) 2008, 2009, 2010 Daniel Otte (daniel.otte@rub.de)
6 This program is free software: you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation, either version 3 of the License, or
9 (at your option) any later version.
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>.
24 #include "main-test-common.h"
27 #include "noekeon_prng.h"
29 #include "bigint_io.h"
31 #include "performance_test.h"
33 char *algo_name = "BigInt";
35 /*****************************************************************************
36 * additional validation-functions *
37 *****************************************************************************/
38 void test_echo_bigint(void){
40 cli_putstr_P(PSTR("\r\necho test\r\n"));
42 cli_putstr_P(PSTR("\r\nenter hex number:"));
43 if(bigint_read_hex_echo(&a)){
44 cli_putstr_P(PSTR("\r\n end echo test"));
47 cli_putstr_P(PSTR("\r\necho: "));
49 cli_putstr_P(PSTR("\r\n"));
54 void test_add_bigint(void){
56 cli_putstr_P(PSTR("\r\nadd test\r\n"));
58 cli_putstr_P(PSTR("\r\nenter a:"));
59 if(bigint_read_hex_echo(&a)){
60 cli_putstr_P(PSTR("\r\n end add test"));
63 cli_putstr_P(PSTR("\r\nenter b:"));
64 if(bigint_read_hex_echo(&b)){
66 cli_putstr_P(PSTR("\r\n end add test"));
69 cli_putstr_P(PSTR("\r\n "));
71 cli_putstr_P(PSTR(" + "));
73 cli_putstr_P(PSTR(" = "));
75 c_b = malloc(((a.length_W>b.length_W)?a.length_W:b.length_W)+2);
77 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
83 bigint_add_s(&c, &a, &b);
85 cli_putstr_P(PSTR("\r\n"));
92 void test_add_scale_bigint(void){
95 cli_putstr_P(PSTR("\r\nadd-scale test\r\n"));
97 cli_putstr_P(PSTR("\r\nenter a:"));
98 if(bigint_read_hex_echo(&a)){
99 cli_putstr_P(PSTR("\r\n end add-scale test"));
102 cli_putstr_P(PSTR("\r\nenter b:"));
103 if(bigint_read_hex_echo(&b)){
104 cli_putstr_P(PSTR("\r\n end add-scale test"));
107 cli_putstr_P(PSTR("\r\nenter scale:"));
110 cli_getsn_cecho(str, 7);
114 if(bigint_read_hex_echo(&scale)){
116 cli_putstr_P(PSTR("\r\n end add test"));
121 c_b = malloc(((a.length_W>(b.length_W+scale))?a.length_W:(b.length_W+scale))+2);
123 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
130 bigint_add_scale_u(&c, &b, scale);
131 cli_putstr_P(PSTR("\r\n "));
132 bigint_print_hex(&a);
133 cli_putstr_P(PSTR(" + "));
134 bigint_print_hex(&b);
135 cli_putstr_P(PSTR("<<8*"));
136 cli_hexdump_rev(&scale, 2);
137 cli_putstr_P(PSTR(" = "));
138 bigint_print_hex(&c);
139 cli_putstr_P(PSTR("\r\n"));
146 void test_mul_bigint(void){
148 cli_putstr_P(PSTR("\r\nmul test\r\n"));
150 cli_putstr_P(PSTR("\r\nenter a:"));
151 if(bigint_read_hex_echo(&a)){
152 cli_putstr_P(PSTR("\r\n end mul test"));
155 cli_putstr_P(PSTR("\r\nenter b:"));
156 if(bigint_read_hex_echo(&b)){
158 cli_putstr_P(PSTR("\r\n end mul test"));
161 cli_putstr_P(PSTR("\r\n "));
162 bigint_print_hex(&a);
163 cli_putstr_P(PSTR(" * "));
164 bigint_print_hex(&b);
165 cli_putstr_P(PSTR(" = "));
167 c_b = malloc((((a.length_W>b.length_W)?a.length_W:b.length_W)+1)*2);
169 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
175 bigint_mul_s(&c, &a, &b);
176 bigint_print_hex(&c);
177 cli_putstr_P(PSTR("\r\n"));
184 void test_mul_mont_bigint(void){
185 bigint_t a, b, c, a_, b_, m_, res;
187 cli_putstr_P(PSTR("\r\nmul-mont test ( (a * b) % c )\r\n"));
189 cli_putstr_P(PSTR("\r\nenter a:"));
190 if(bigint_read_hex_echo(&a)){
191 cli_putstr_P(PSTR("\r\n end mul test"));
194 cli_putstr_P(PSTR("\r\nenter b:"));
195 if(bigint_read_hex_echo(&b)){
197 cli_putstr_P(PSTR("\r\n end mul test"));
200 cli_putstr_P(PSTR("\r\nenter c:"));
201 if(bigint_read_hex_echo(&c)){
204 cli_putstr_P(PSTR("\r\n end mul test"));
208 cli_putstr_P(PSTR("\r\n ("));
209 bigint_print_hex(&a);
210 cli_putstr_P(PSTR(" * "));
211 bigint_print_hex(&b);
212 cli_putstr_P(PSTR(") % "));
213 bigint_print_hex(&c);
214 cli_putstr_P(PSTR(" = "));
215 bigint_word_t res_w[s], a_w_[s], b_w_[s], m_w_[s + 1];
220 bigint_mont_gen_m_(&m_, &c);
221 bigint_mont_trans(&a_, &a, &c);
222 bigint_mont_trans(&b_, &b, &c);
223 bigint_mont_mul(&res, &a_, &b_, &c, &m_);
224 bigint_mont_red(&res, &res, &c, &m_);
225 bigint_print_hex(&res);
233 void test_mul_word_bigint(void){
236 cli_putstr_P(PSTR("\r\nmul test\r\n"));
238 cli_putstr_P(PSTR("\r\nenter a:"));
239 if(bigint_read_hex_echo(&a)){
240 cli_putstr_P(PSTR("\r\n end mul test"));
243 cli_putstr_P(PSTR("\r\nenter b:"));
244 if(bigint_read_hex_echo(&b)){
246 cli_putstr_P(PSTR("\r\n end mul test"));
249 cli_putstr_P(PSTR("\r\n "));
250 bigint_print_hex(&a);
251 cli_putstr_P(PSTR(" * "));
252 bigint_print_hex(&b);
253 cli_putstr_P(PSTR(" = "));
258 cli_putstr_P(PSTR("\r\n end mul test"));
261 t = realloc(a.wordv, a.length_W + 3);
263 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
269 bigint_mul_word_u(&a, b.wordv[0]);
270 bigint_print_hex(&a);
271 cli_putstr_P(PSTR("\r\n"));
277 void test_square_bigint(void){
279 cli_putstr_P(PSTR("\r\nsquare test\r\n"));
281 cli_putstr_P(PSTR("\r\nenter a:"));
282 if(bigint_read_hex_echo(&a)){
283 cli_putstr_P(PSTR("\r\n end square test"));
286 cli_putstr_P(PSTR("\r\n "));
287 bigint_print_hex(&a);
288 cli_putstr_P(PSTR("**2 = "));
290 c_b = malloc(a.length_W*2);
292 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
297 bigint_square(&c, &a);
298 bigint_print_hex(&c);
299 cli_putstr_P(PSTR("\r\n"));
305 void test_reduce_bigint(void){
307 cli_putstr_P(PSTR("\r\nreduce test\r\n"));
309 cli_putstr_P(PSTR("\r\nenter a:"));
310 if(bigint_read_hex_echo(&a)){
311 cli_putstr_P(PSTR("\r\n end reduce test"));
314 cli_putstr_P(PSTR("\r\nenter b:"));
315 if(bigint_read_hex_echo(&b)){
317 cli_putstr_P(PSTR("\r\n end reduce test"));
320 cli_putstr_P(PSTR("\r\n "));
321 bigint_print_hex(&a);
322 cli_putstr_P(PSTR(" % "));
323 bigint_print_hex(&b);
324 cli_putstr_P(PSTR(" = "));
325 bigint_reduce(&a, &b);
326 bigint_print_hex(&a);
327 cli_putstr_P(PSTR("\r\n"));
333 void test_expmod_bigint(void){
336 cli_putstr_P(PSTR("\r\nexpnonentiation-modulo test\r\n"));
338 cli_putstr_P(PSTR("\r\nenter a:"));
339 if(bigint_read_hex_echo(&a)){
340 cli_putstr_P(PSTR("\r\n end expmod test"));
343 cli_putstr_P(PSTR("\r\nenter b:"));
344 if(bigint_read_hex_echo(&b)){
346 cli_putstr_P(PSTR("\r\n end expmod test"));
349 cli_putstr_P(PSTR("\r\nenter c:"));
350 if(bigint_read_hex_echo(&c)){
353 cli_putstr_P(PSTR("\r\n end expmod test"));
356 d_b = malloc(c.length_W);
358 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
365 cli_putstr_P(PSTR("\r\n "));
366 bigint_print_hex(&a);
367 cli_putstr_P(PSTR("**"));
368 bigint_print_hex(&b);
369 cli_putstr_P(PSTR(" % "));
370 bigint_print_hex(&c);
371 cli_putstr_P(PSTR(" = "));
372 bigint_expmod_u(&d, &a, &b, &c);
373 bigint_print_hex(&d);
374 cli_putstr_P(PSTR("\r\n"));
384 void test_expmod_mont_bigint(void){
387 cli_putstr_P(PSTR("\r\nexpnonentiation-modulo-montgomory test\r\n"));
389 cli_putstr_P(PSTR("\r\nenter a:"));
390 if(bigint_read_hex_echo(&a)){
391 cli_putstr_P(PSTR("\r\n end expmod test"));
394 cli_putstr_P(PSTR("\r\nenter b:"));
395 if(bigint_read_hex_echo(&b)){
397 cli_putstr_P(PSTR("\r\n end expmod test"));
400 cli_putstr_P(PSTR("\r\nenter c:"));
401 if(bigint_read_hex_echo(&c)){
404 cli_putstr_P(PSTR("\r\n end expmod test"));
407 d_b = malloc(c.length_W);
409 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
416 cli_putstr_P(PSTR("\r\n "));
417 bigint_print_hex(&a);
418 cli_putstr_P(PSTR("**"));
419 bigint_print_hex(&b);
420 cli_putstr_P(PSTR(" % "));
421 bigint_print_hex(&c);
422 cli_putstr_P(PSTR(" = "));
423 bigint_expmod_u_mont_sam(&d, &a, &b, &c);
424 bigint_print_hex(&d);
425 cli_putstr_P(PSTR("\r\n"));
434 void test_gcdext_bigint(void){
435 bigint_t a, b, c, d, e;
436 cli_putstr_P(PSTR("\r\ngcdext test\r\n"));
438 cli_putstr_P(PSTR("\r\nenter a:"));
439 if(bigint_read_hex_echo(&a)){
440 cli_putstr_P(PSTR("\r\n end gcdext test"));
443 cli_putstr_P(PSTR("\r\nenter b:"));
444 if(bigint_read_hex_echo(&b)){
446 cli_putstr_P(PSTR("\r\n end gcdext test"));
449 c.wordv = malloc((a.length_W<b.length_W)?a.length_W:b.length_W);
450 d.wordv = malloc(1+(a.length_W>b.length_W)?a.length_W:b.length_W);
451 e.wordv = malloc(1+(a.length_W>b.length_W)?a.length_W:b.length_W);
453 cli_putstr_P(PSTR("\r\n gcdext( "));
454 bigint_print_hex(&a);
455 cli_putstr_P(PSTR(", "));
456 bigint_print_hex(&b);
457 cli_putstr_P(PSTR(") => "));
458 bigint_gcdext(&c, &d, &e, &a, &b);
459 cli_putstr_P(PSTR("a = "));
460 bigint_print_hex(&d);
461 cli_putstr_P(PSTR("; b = "));
462 bigint_print_hex(&e);
463 cli_putstr_P(PSTR("; gcd = "));
464 bigint_print_hex(&c);
466 cli_putstr_P(PSTR("\r\n"));
475 void test_simple(void){
477 uint8_t a_b[1], b_b[1], c_b[2];
485 bigint_add_u(&c, &a, &b);
486 cli_putstr_P(PSTR("\r\n 1+2="));
487 bigint_print_hex(&c);
490 void test_mul_simple(void){
492 uint8_t a_b[5] = {0x79, 0x36, 0x9e, 0x72, 0xec};
493 uint8_t b_b[5] = {0x4a, 0x47, 0x0d, 0xec, 0xfd};
502 bigint_mul_s(&c, &a, &b);
503 cli_putstr_P(PSTR("\r\n test: "));
504 bigint_print_hex(&c);
508 // -3d1d 6db7 8251 f371 * -7a18 3791 d18b b7c5 = 1d25ce4fdf93390f8d6c709f4d711cf5
509 // -20538248dece6d29068d * 400b1411b874f81394c6 = -81646b193d95136a6fedb73cee6d30c39fb950e
510 // -BC8B 7D53 4921 853D * 0DDA 6044 00CE DDE6 = -a33eb0c5847db8837589c22db395dce
511 void test_mul_simple(void){
514 // uint8_t a_b[10] = {0x8d, 0x06, 0x29, 0x6d, 0xce, 0xde, 0x48, 0x82, 0x53, 0x20};
515 // uint8_t b_b[10] = {0xc6, 0x94, 0x13, 0xf8, 0x74, 0xb8, 0x11, 0x14, 0x0b, 0x40};
516 uint8_t a_b[8] = {0x3d, 0x85, 0x21, 0x49, 0x53, 0x7d, 0x8b, 0xbc};
517 uint8_t b_b[8] = {0xe6, 0xdd, 0xce, 0x00, 0x44, 0x60, 0xda, 0x0d};
528 bigint_mul_s(&c, &a, &b);
529 cli_putstr_P(PSTR("\r\n test: "));
530 bigint_print_hex(&a);
531 cli_putstr_P(PSTR(" * "));
532 bigint_print_hex(&b);
533 cli_putstr_P(PSTR(" = "));
534 bigint_print_hex(&c);
537 // f4 b86a 2220 0774 437d 70e6 **2 = e9f00f29ca1c876a7a682bd1e04f6925caffd6660ea4
539 const uint8_t square_test_data[] PROGMEM = {
540 0xA0, 0x3C, 0x23, 0x9F, 0x7A, 0xFC, 0x60, 0xEB, 0x96, 0xC2, 0xA8, 0xAC, 0xC3, 0xC9, 0x9E, 0xEC,
541 0x4A, 0xF0, 0x1C, 0xB2, 0x36, 0x68, 0xD6, 0x4D, 0x3E, 0x4F, 0x8E, 0x55, 0xEA, 0x52, 0x46, 0x68,
542 0x6E, 0x18, 0x88, 0x37, 0x03, 0x70, 0xBD, 0x01, 0x60, 0xE2, 0xD6, 0x12, 0xA0, 0x0E, 0xD2, 0x72,
543 0x0D, 0x9D, 0x9F, 0x03, 0xC5, 0x81, 0xCA, 0x6E, 0x88, 0x1E, 0xF5, 0xD8, 0x14, 0x15, 0x30, 0xEB,
544 0x28, 0x7C, 0x80, 0x07, 0x34, 0x05, 0x5D, 0xAA, 0xDC, 0xA8, 0xAA, 0x88, 0xC5, 0xE5, 0xC9, 0xFE,
545 0x9C, 0xA1, 0xCE, 0xC2, 0x09, 0x0D, 0xC4, 0xC8, 0xD3, 0xE7, 0x3A, 0xF3, 0xEF, 0xDF, 0xAE, 0x07,
546 0xEC, 0xC7, 0x83, 0x50, 0x9F, 0x6D, 0xB9, 0x28, 0x77, 0xC0, 0xFE, 0x69, 0xB2, 0x2E, 0x55, 0x90,
547 0x50, 0xED, 0xE0, 0xA1, 0x4D, 0x3D, 0x38, 0xC9, 0x0E, 0xCD, 0x04, 0x3B, 0x64, 0x3F, 0x56, 0xC5,
548 0xC3, 0x9E, 0x89, 0x81, 0x44, 0x60, 0xBA, 0x8E, 0x88, 0xA4, 0xA3, 0x42, 0x7B, 0x06, 0x93, 0x1C,
549 0x6B, 0x04, 0x29, 0xF9, 0xDD, 0xFF, 0xB0, 0x48, 0x2F, 0x6D, 0xD1, 0x0F, 0x7D, 0xA6, 0x26, 0xD8,
550 0xEF, 0x5E, 0x04, 0x18, 0xD1, 0x61, 0x46, 0x37, 0x87, 0xE2, 0x97, 0xDF, 0x10, 0xB4, 0x9A, 0x39,
551 0xB1, 0xD0, 0xCA, 0x91, 0x48, 0x1E, 0x5D, 0xA1, 0x38, 0x89, 0x02, 0xC1, 0x49, 0x86, 0xB7, 0xAE,
552 0x69, 0x20, 0xFA, 0x0E, 0x39, 0xDA, 0xA5, 0xEF, 0x7F, 0xB2, 0x81, 0xB8, 0xC0, 0x3A, 0xF8, 0xDB,
553 0xBC, 0x45, 0xF6, 0xDA, 0xCD, 0xBE, 0x27, 0xBE, 0xF6, 0x20, 0x79, 0xF3, 0xC3, 0xC8, 0xFF, 0x85,
554 0x43, 0x9F, 0xB1, 0x9B, 0x72, 0x88, 0xDD, 0xA4, 0x0D, 0xFC, 0xC6, 0xB5, 0x74, 0x67, 0x29, 0xF5
558 void test_square_simple(void){
561 uint8_t a_b[11] = {0xe6, 0x70, 0x7d, 0x43, 0x74, 0x07, 0x20, 0x22, 0x6a, 0xb8, 0xf4};
568 bigint_square(&c, &a);
569 cli_putstr_P(PSTR("\r\n test: "));
570 bigint_print_hex(&a);
571 cli_putstr_P(PSTR("**2 = "));
572 bigint_print_hex(&c);
575 // [fail (c)]: A862 % 2752 = 0D1A ; should a862 % 2752 = b1a
576 void test_reduce_simple(void){
579 uint8_t a_b[2] = {0x62, 0xA8};
580 uint8_t b_b[2] = {0x52, 0x27};
592 bigint_reduce(&c, &b);
593 cli_putstr_P(PSTR("\r\n test: "));
594 bigint_print_hex(&a);
595 cli_putstr_P(PSTR(" % "));
596 bigint_print_hex(&b);
597 cli_putstr_P(PSTR(" = "));
598 bigint_print_hex(&c);
601 /* gcdext( B5DDAD, 6CBBC2) */
602 /* gcdext( CD319349, 9EFD76CC) */
603 /* gcdext( 1609000771, 6FAC577D72) */
605 void test_gcdext_simple(void){
606 bigint_t a, b, c, d, e;
608 uint8_t a_b[5] = {0x71, 0x07, 0x00, 0x09, 0x16};
609 uint8_t b_b[5] = {0x72, 0x7D, 0x57, 0xAC, 0X6F};
610 uint8_t c_b[6], d_b[6], e_b[6];
622 bigint_gcdext(&c, &d, &e, &a, &b);
623 cli_putstr_P(PSTR("\r\n test: gcd( "));
624 bigint_print_hex(&a);
625 cli_putstr_P(PSTR(", "));
626 bigint_print_hex(&b);
627 cli_putstr_P(PSTR(") => a = "));
628 bigint_print_hex(&d);
629 cli_putstr_P(PSTR("; b = "));
630 bigint_print_hex(&e);
631 cli_putstr_P(PSTR("; gcd = "));
632 bigint_print_hex(&c);
635 void testrun_performance_bigint(void){
638 /*****************************************************************************
640 *****************************************************************************/
642 const char echo_test_str[] PROGMEM = "echo-test";
643 const char add_test_str[] PROGMEM = "add-test";
644 const char add_scale_test_str[] PROGMEM = "add-scale-test";
645 const char mul_test_str[] PROGMEM = "mul-test";
646 const char mul_mont_test_str[] PROGMEM = "mul-mont-test";
647 const char mul_word_test_str[] PROGMEM = "mul-word-test";
648 const char square_test_str[] PROGMEM = "square-test";
649 const char reduce_test_str[] PROGMEM = "reduce-test";
650 const char expmod_test_str[] PROGMEM = "expmod-test";
651 const char expmod_mont_test_str[] PROGMEM = "expmod-mont-test";
652 const char gcdext_test_str[] PROGMEM = "gcdext-test";
653 const char quick_test_str[] PROGMEM = "quick-test";
654 const char performance_str[] PROGMEM = "performance";
655 const char echo_str[] PROGMEM = "echo";
657 const cmdlist_entry_t cmdlist[] PROGMEM = {
658 { add_test_str, NULL, test_add_bigint },
659 { add_scale_test_str, NULL, test_add_scale_bigint },
660 { mul_test_str, NULL, test_mul_bigint },
661 { mul_mont_test_str, NULL, test_mul_mont_bigint },
662 { mul_word_test_str, NULL, test_mul_word_bigint },
663 { square_test_str, NULL, test_square_bigint },
664 { reduce_test_str, NULL, test_reduce_bigint },
665 { expmod_test_str, NULL, test_expmod_bigint },
666 { expmod_mont_test_str, NULL, test_expmod_mont_bigint },
667 { gcdext_test_str, NULL, test_gcdext_bigint },
668 { quick_test_str, NULL, test_gcdext_simple },
669 { echo_test_str, NULL, test_echo_bigint },
670 { performance_str, NULL, testrun_performance_bigint },
671 { echo_str, (void*)1, (void_fpt)echo_ctrl },
679 welcome_msg(algo_name);
680 cmd_interface(cmdlist);