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 #define MAX(a,b) ((a) > (b) ? (a) : (b))
36 #define MIN(a,b) ((a) < (b) ? (a) : (b))
38 /*****************************************************************************
39 * additional validation-functions *
40 *****************************************************************************/
41 void test_echo_bigint(void) {
43 cli_putstr_P(PSTR("\r\necho test\r\n"));
45 cli_putstr_P(PSTR("\r\nenter hex number:"));
46 if (bigint_read_hex_echo(&a)) {
47 cli_putstr_P(PSTR("\r\n end echo test"));
50 cli_putstr_P(PSTR("\r\necho: "));
52 cli_putstr_P(PSTR("\r\n"));
57 void test_add_bigint(void){
59 cli_putstr_P(PSTR("\r\nadd test\r\n"));
61 cli_putstr_P(PSTR("\r\nenter a:"));
62 if (bigint_read_hex_echo(&a)) {
63 cli_putstr_P(PSTR("\r\n end add test"));
66 cli_putstr_P(PSTR("\r\nenter b:"));
67 if (bigint_read_hex_echo(&b)) {
69 cli_putstr_P(PSTR("\r\n end add test"));
72 cli_putstr_P(PSTR("\r\n "));
74 cli_putstr_P(PSTR(" + "));
76 cli_putstr_P(PSTR(" = "));
78 c_b = malloc((MAX(a.length_W, b.length_W) + 2) * sizeof(bigint_word_t));
80 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
86 bigint_add_s(&c, &a, &b);
88 cli_putstr_P(PSTR("\r\n"));
95 void test_add_scale_bigint(void){
98 cli_putstr_P(PSTR("\r\nadd-scale test\r\n"));
100 cli_putstr_P(PSTR("\r\nenter a:"));
101 if (bigint_read_hex_echo(&a)) {
102 cli_putstr_P(PSTR("\r\n end add-scale test"));
105 cli_putstr_P(PSTR("\r\nenter b:"));
106 if (bigint_read_hex_echo(&b)) {
107 cli_putstr_P(PSTR("\r\n end add-scale test"));
110 cli_putstr_P(PSTR("\r\nenter scale:"));
113 cli_getsn_cecho(str, 7);
117 if(bigint_read_hex_echo(&scale)){
119 cli_putstr_P(PSTR("\r\n end add test"));
124 c_b = malloc((MAX(a.length_W, b.length_W+scale) + 2) * sizeof(bigint_word_t));
126 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
133 bigint_add_scale_u(&c, &b, scale);
134 cli_putstr_P(PSTR("\r\n "));
135 bigint_print_hex(&a);
136 cli_putstr_P(PSTR(" + "));
137 bigint_print_hex(&b);
138 cli_putstr_P(PSTR("<<8*"));
139 cli_hexdump_rev(&scale, 2);
140 cli_putstr_P(PSTR(" = "));
141 bigint_print_hex(&c);
142 cli_putstr_P(PSTR("\r\n"));
149 void test_mul_bigint(void){
151 cli_putstr_P(PSTR("\r\nmul test\r\n"));
153 cli_putstr_P(PSTR("\r\nenter a:"));
154 if (bigint_read_hex_echo(&a)) {
155 cli_putstr_P(PSTR("\r\n end mul test"));
158 cli_putstr_P(PSTR("\r\nenter b:"));
159 if (bigint_read_hex_echo(&b)) {
161 cli_putstr_P(PSTR("\r\n end mul test"));
164 cli_putstr_P(PSTR("\r\n "));
165 bigint_print_hex(&a);
166 cli_putstr_P(PSTR(" * "));
167 bigint_print_hex(&b);
168 cli_putstr_P(PSTR(" = "));
170 c_b = malloc((MAX(a.length_W, b.length_W) + 1) * 2 * sizeof(bigint_word_t));
172 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
178 bigint_mul_s(&c, &a, &b);
179 bigint_print_hex(&c);
180 cli_putstr_P(PSTR("\r\n"));
187 void test_mul_mont_bigint(void){
188 bigint_t a, b, c, a_, b_, m_, res;
190 cli_putstr_P(PSTR("\r\nmul-mont test ( (a * b) % c )\r\n"));
192 cli_putstr_P(PSTR("\r\nenter a:"));
193 if (bigint_read_hex_echo(&a)) {
194 cli_putstr_P(PSTR("\r\n end mul test"));
197 cli_putstr_P(PSTR("\r\nenter b:"));
198 if (bigint_read_hex_echo(&b)) {
200 cli_putstr_P(PSTR("\r\n end mul test"));
203 cli_putstr_P(PSTR("\r\nenter c:"));
204 if (bigint_read_hex_echo(&c)) {
207 cli_putstr_P(PSTR("\r\n end mul test"));
211 cli_putstr_P(PSTR("\r\n ("));
212 bigint_print_hex(&a);
213 cli_putstr_P(PSTR(" * "));
214 bigint_print_hex(&b);
215 cli_putstr_P(PSTR(") % "));
216 bigint_print_hex(&c);
217 cli_putstr_P(PSTR(" = "));
218 bigint_word_t res_w[s], a_w_[s], b_w_[s], m_w_[s + 1];
223 bigint_mont_gen_m_(&m_, &c);
224 bigint_mont_trans(&a_, &a, &c);
225 bigint_mont_trans(&b_, &b, &c);
226 bigint_mont_mul(&res, &a_, &b_, &c, &m_);
227 bigint_mont_red(&res, &res, &c, &m_);
228 bigint_print_hex(&res);
236 void test_mul_word_bigint(void){
239 cli_putstr_P(PSTR("\r\nmul test\r\n"));
241 cli_putstr_P(PSTR("\r\nenter a:"));
242 if (bigint_read_hex_echo(&a)) {
243 cli_putstr_P(PSTR("\r\n end mul test"));
246 cli_putstr_P(PSTR("\r\nenter b:"));
247 if (bigint_read_hex_echo(&b)) {
249 cli_putstr_P(PSTR("\r\n end mul test"));
252 cli_putstr_P(PSTR("\r\n "));
253 bigint_print_hex(&a);
254 cli_putstr_P(PSTR(" * "));
255 bigint_print_hex(&b);
256 cli_putstr_P(PSTR(" = "));
258 if (b.length_W > 1) {
261 cli_putstr_P(PSTR("\r\n end mul test"));
264 t = realloc(a.wordv, (a.length_W + 3) * sizeof(bigint_word_t));
266 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
272 bigint_mul_word_u(&a, b.wordv[0]);
273 bigint_print_hex(&a);
274 cli_putstr_P(PSTR("\r\n"));
280 void test_square_bigint(void){
282 cli_putstr_P(PSTR("\r\nsquare test\r\n"));
284 cli_putstr_P(PSTR("\r\nenter a:"));
285 if(bigint_read_hex_echo(&a)){
286 cli_putstr_P(PSTR("\r\n end square test"));
289 cli_putstr_P(PSTR("\r\n "));
290 bigint_print_hex(&a);
291 cli_putstr_P(PSTR("**2 = "));
293 c_b = malloc(a.length_W * 2 * sizeof(bigint_word_t));
295 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
300 bigint_square(&c, &a);
301 bigint_print_hex(&c);
302 cli_putstr_P(PSTR("\r\n"));
308 void test_reduce_bigint(void){
310 cli_putstr_P(PSTR("\r\nreduce test\r\n"));
312 cli_putstr_P(PSTR("\r\nenter a:"));
313 if (bigint_read_hex_echo(&a)) {
314 cli_putstr_P(PSTR("\r\n end reduce test"));
317 cli_putstr_P(PSTR("\r\nenter b:"));
318 if (bigint_read_hex_echo(&b)) {
320 cli_putstr_P(PSTR("\r\n end reduce test"));
323 cli_putstr_P(PSTR("\r\n "));
324 bigint_print_hex(&a);
325 cli_putstr_P(PSTR(" % "));
326 bigint_print_hex(&b);
327 cli_putstr_P(PSTR(" = "));
328 bigint_reduce(&a, &b);
329 bigint_print_hex(&a);
330 cli_putstr_P(PSTR("\r\n"));
336 void test_expmod_bigint(void){
339 cli_putstr_P(PSTR("\r\nexpnonentiation-modulo test\r\n"));
341 cli_putstr_P(PSTR("\r\nenter a:"));
342 if (bigint_read_hex_echo(&a)) {
343 cli_putstr_P(PSTR("\r\n end expmod test"));
346 cli_putstr_P(PSTR("\r\nenter b:"));
347 if (bigint_read_hex_echo(&b)) {
349 cli_putstr_P(PSTR("\r\n end expmod test"));
352 cli_putstr_P(PSTR("\r\nenter c:"));
353 if (bigint_read_hex_echo(&c)) {
356 cli_putstr_P(PSTR("\r\n end expmod test"));
359 d_b = malloc(c.length_W * sizeof(bigint_word_t));
361 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
368 cli_putstr_P(PSTR("\r\n "));
369 bigint_print_hex(&a);
370 cli_putstr_P(PSTR("**"));
371 bigint_print_hex(&b);
372 cli_putstr_P(PSTR(" % "));
373 bigint_print_hex(&c);
374 cli_putstr_P(PSTR(" = "));
375 bigint_expmod_u_sam(&d, &a, &b, &c);
376 bigint_print_hex(&d);
377 cli_putstr_P(PSTR("\r\n"));
387 void test_expmod_mont_bigint(void){
390 cli_putstr_P(PSTR("\r\nexpnonentiation-modulo-montgomory test\r\n"));
392 cli_putstr_P(PSTR("\r\nenter a:"));
393 if (bigint_read_hex_echo(&a)) {
394 cli_putstr_P(PSTR("\r\n end expmod test"));
397 cli_putstr_P(PSTR("\r\nenter b:"));
398 if (bigint_read_hex_echo(&b)) {
400 cli_putstr_P(PSTR("\r\n end expmod test"));
403 cli_putstr_P(PSTR("\r\nenter c:"));
404 if (bigint_read_hex_echo(&c)) {
407 cli_putstr_P(PSTR("\r\n end expmod test"));
410 d_b = malloc(c.length_W * sizeof(bigint_word_t));
412 cli_putstr_P(PSTR("\n\rERROR: Out of memory!"));
419 cli_putstr_P(PSTR("\r\n "));
420 bigint_print_hex(&a);
421 cli_putstr_P(PSTR("**"));
422 bigint_print_hex(&b);
423 cli_putstr_P(PSTR(" % "));
424 bigint_print_hex(&c);
425 cli_putstr_P(PSTR(" = "));
426 bigint_expmod_u_mont_sam(&d, &a, &b, &c);
427 bigint_print_hex(&d);
428 cli_putstr_P(PSTR("\r\n"));
437 void test_gcdext_bigint(void){
438 bigint_t a, b, c, d, e;
439 cli_putstr_P(PSTR("\r\ngcdext test\r\n"));
441 cli_putstr_P(PSTR("\r\nenter a:"));
442 if (bigint_read_hex_echo(&a)) {
443 cli_putstr_P(PSTR("\r\n end gcdext test"));
446 cli_putstr_P(PSTR("\r\nenter b:"));
447 if (bigint_read_hex_echo(&b)) {
449 cli_putstr_P(PSTR("\r\n end gcdext test"));
452 c.wordv = malloc(MIN(a.length_W, b.length_W) * sizeof(bigint_word_t));
453 d.wordv = malloc((MAX(a.length_W, b.length_W) + 1) * sizeof(bigint_word_t));
454 e.wordv = malloc((MAX(a.length_W, b.length_W) + 1) * sizeof(bigint_word_t));
456 cli_putstr_P(PSTR("\r\n gcdext( "));
457 bigint_print_hex(&a);
458 cli_putstr_P(PSTR(", "));
459 bigint_print_hex(&b);
460 cli_putstr_P(PSTR(") => "));
461 bigint_gcdext(&c, &d, &e, &a, &b);
462 cli_putstr_P(PSTR("a = "));
463 bigint_print_hex(&d);
464 cli_putstr_P(PSTR("; b = "));
465 bigint_print_hex(&e);
466 cli_putstr_P(PSTR("; gcd = "));
467 bigint_print_hex(&c);
469 cli_putstr_P(PSTR("\r\n"));
478 void test_simple(void){
480 bigint_word_t a_b[1], b_b[1], c_b[2];
488 bigint_add_u(&c, &a, &b);
489 cli_putstr_P(PSTR("\r\n 1+2="));
490 bigint_print_hex(&c);
493 void test_mul_simple(void){
495 uint8_t a_b[5] = {0x79, 0x36, 0x9e, 0x72, 0xec};
496 uint8_t b_b[5] = {0x4a, 0x47, 0x0d, 0xec, 0xfd};
505 bigint_mul_s(&c, &a, &b);
506 cli_putstr_P(PSTR("\r\n test: "));
507 bigint_print_hex(&c);
511 // -3d1d 6db7 8251 f371 * -7a18 3791 d18b b7c5 = 1d25ce4fdf93390f8d6c709f4d711cf5
512 // -20538248dece6d29068d * 400b1411b874f81394c6 = -81646b193d95136a6fedb73cee6d30c39fb950e
513 // -BC8B 7D53 4921 853D * 0DDA 6044 00CE DDE6 = -a33eb0c5847db8837589c22db395dce
514 void test_mul_simple(void){
517 // uint8_t a_b[10] = {0x8d, 0x06, 0x29, 0x6d, 0xce, 0xde, 0x48, 0x82, 0x53, 0x20};
518 // uint8_t b_b[10] = {0xc6, 0x94, 0x13, 0xf8, 0x74, 0xb8, 0x11, 0x14, 0x0b, 0x40};
519 uint8_t a_b[8] = {0x3d, 0x85, 0x21, 0x49, 0x53, 0x7d, 0x8b, 0xbc};
520 uint8_t b_b[8] = {0xe6, 0xdd, 0xce, 0x00, 0x44, 0x60, 0xda, 0x0d};
523 a.wordv = (bigint_word_t*)a_b;
524 b.wordv = (bigint_word_t*)b_b;
525 c.wordv = (bigint_word_t*)c_b;
526 a.length_W = 8 / sizeof(bigint_word_t);
527 b.length_W = 8 / sizeof(bigint_word_t);
531 bigint_mul_s(&c, &a, &b);
532 cli_putstr_P(PSTR("\r\n test: "));
533 bigint_print_hex(&a);
534 cli_putstr_P(PSTR(" * "));
535 bigint_print_hex(&b);
536 cli_putstr_P(PSTR(" = "));
537 bigint_print_hex(&c);
540 // f4 b86a 2220 0774 437d 70e6 **2 = e9f00f29ca1c876a7a682bd1e04f6925caffd6660ea4
542 const uint8_t square_test_data[] PROGMEM = {
543 0xA0, 0x3C, 0x23, 0x9F, 0x7A, 0xFC, 0x60, 0xEB, 0x96, 0xC2, 0xA8, 0xAC, 0xC3, 0xC9, 0x9E, 0xEC,
544 0x4A, 0xF0, 0x1C, 0xB2, 0x36, 0x68, 0xD6, 0x4D, 0x3E, 0x4F, 0x8E, 0x55, 0xEA, 0x52, 0x46, 0x68,
545 0x6E, 0x18, 0x88, 0x37, 0x03, 0x70, 0xBD, 0x01, 0x60, 0xE2, 0xD6, 0x12, 0xA0, 0x0E, 0xD2, 0x72,
546 0x0D, 0x9D, 0x9F, 0x03, 0xC5, 0x81, 0xCA, 0x6E, 0x88, 0x1E, 0xF5, 0xD8, 0x14, 0x15, 0x30, 0xEB,
547 0x28, 0x7C, 0x80, 0x07, 0x34, 0x05, 0x5D, 0xAA, 0xDC, 0xA8, 0xAA, 0x88, 0xC5, 0xE5, 0xC9, 0xFE,
548 0x9C, 0xA1, 0xCE, 0xC2, 0x09, 0x0D, 0xC4, 0xC8, 0xD3, 0xE7, 0x3A, 0xF3, 0xEF, 0xDF, 0xAE, 0x07,
549 0xEC, 0xC7, 0x83, 0x50, 0x9F, 0x6D, 0xB9, 0x28, 0x77, 0xC0, 0xFE, 0x69, 0xB2, 0x2E, 0x55, 0x90,
550 0x50, 0xED, 0xE0, 0xA1, 0x4D, 0x3D, 0x38, 0xC9, 0x0E, 0xCD, 0x04, 0x3B, 0x64, 0x3F, 0x56, 0xC5,
551 0xC3, 0x9E, 0x89, 0x81, 0x44, 0x60, 0xBA, 0x8E, 0x88, 0xA4, 0xA3, 0x42, 0x7B, 0x06, 0x93, 0x1C,
552 0x6B, 0x04, 0x29, 0xF9, 0xDD, 0xFF, 0xB0, 0x48, 0x2F, 0x6D, 0xD1, 0x0F, 0x7D, 0xA6, 0x26, 0xD8,
553 0xEF, 0x5E, 0x04, 0x18, 0xD1, 0x61, 0x46, 0x37, 0x87, 0xE2, 0x97, 0xDF, 0x10, 0xB4, 0x9A, 0x39,
554 0xB1, 0xD0, 0xCA, 0x91, 0x48, 0x1E, 0x5D, 0xA1, 0x38, 0x89, 0x02, 0xC1, 0x49, 0x86, 0xB7, 0xAE,
555 0x69, 0x20, 0xFA, 0x0E, 0x39, 0xDA, 0xA5, 0xEF, 0x7F, 0xB2, 0x81, 0xB8, 0xC0, 0x3A, 0xF8, 0xDB,
556 0xBC, 0x45, 0xF6, 0xDA, 0xCD, 0xBE, 0x27, 0xBE, 0xF6, 0x20, 0x79, 0xF3, 0xC3, 0xC8, 0xFF, 0x85,
557 0x43, 0x9F, 0xB1, 0x9B, 0x72, 0x88, 0xDD, 0xA4, 0x0D, 0xFC, 0xC6, 0xB5, 0x74, 0x67, 0x29, 0xF5
561 void test_square_simple(void){
564 uint8_t a_b[16] = {0xe6, 0x70, 0x7d, 0x43, 0x74, 0x07, 0x20, 0x22, 0x6a, 0xb8, 0xf4, 0, 0, 0, 0, 0};
566 a.wordv = (bigint_word_t*)a_b;
567 c.wordv = (bigint_word_t*)c_b;
568 a.length_W = 16 / sizeof(bigint_word_t);
571 bigint_square(&c, &a);
572 cli_putstr_P(PSTR("\r\n test: "));
573 bigint_print_hex(&a);
574 cli_putstr_P(PSTR("**2 = "));
575 bigint_print_hex(&c);
578 // [fail (c)]: A862 % 2752 = 0D1A ; should a862 % 2752 = b1a
579 void test_reduce_simple(void){
582 uint8_t a_b[4] = {0x62, 0xA8};
583 uint8_t b_b[4] = {0x52, 0x27};
585 a.wordv = (bigint_word_t*)a_b;
586 a.length_W = 4 / sizeof(bigint_word_t);
589 b.wordv = (bigint_word_t*)b_b;
590 b.length_W = 4 / sizeof(bigint_word_t);
593 c.wordv = (bigint_word_t*)c_b;
595 bigint_reduce(&c, &b);
596 cli_putstr_P(PSTR("\r\n test: "));
597 bigint_print_hex(&a);
598 cli_putstr_P(PSTR(" % "));
599 bigint_print_hex(&b);
600 cli_putstr_P(PSTR(" = "));
601 bigint_print_hex(&c);
604 /* gcdext( B5DDAD, 6CBBC2) */
605 /* gcdext( CD319349, 9EFD76CC) */
606 /* gcdext( 1609000771, 6FAC577D72) */
608 void test_gcdext_simple(void){
609 bigint_t a, b, c, d, e;
611 uint8_t a_b[8] = {0x71, 0x07, 0x00, 0x09, 0x16};
612 uint8_t b_b[8] = {0x72, 0x7D, 0x57, 0xAC, 0X6F};
613 uint8_t c_b[8], d_b[8], e_b[8];
614 a.wordv = (bigint_word_t*)a_b;
615 a.length_W = 8 / sizeof(bigint_word_t);
618 b.wordv = (bigint_word_t*)b_b;
619 b.length_W = 8 / sizeof(bigint_word_t);
622 c.wordv = (bigint_word_t*)c_b;
623 d.wordv = (bigint_word_t*)d_b;
624 e.wordv = (bigint_word_t*)e_b;
625 bigint_gcdext(&c, &d, &e, &a, &b);
626 cli_putstr_P(PSTR("\r\n test: gcd( "));
627 bigint_print_hex(&a);
628 cli_putstr_P(PSTR(", "));
629 bigint_print_hex(&b);
630 cli_putstr_P(PSTR(") => a = "));
631 bigint_print_hex(&d);
632 cli_putstr_P(PSTR("; b = "));
633 bigint_print_hex(&e);
634 cli_putstr_P(PSTR("; gcd = "));
635 bigint_print_hex(&c);
638 void testrun_performance_bigint(void){
641 /*****************************************************************************
643 *****************************************************************************/
645 const char echo_test_str[] PROGMEM = "echo-test";
646 const char add_test_str[] PROGMEM = "add-test";
647 const char add_scale_test_str[] PROGMEM = "add-scale-test";
648 const char mul_test_str[] PROGMEM = "mul-test";
649 const char mul_mont_test_str[] PROGMEM = "mul-mont-test";
650 const char mul_word_test_str[] PROGMEM = "mul-word-test";
651 const char square_test_str[] PROGMEM = "square-test";
652 const char reduce_test_str[] PROGMEM = "reduce-test";
653 const char expmod_test_str[] PROGMEM = "expmod-test";
654 const char expmod_mont_test_str[] PROGMEM = "expmod-mont-test";
655 const char gcdext_test_str[] PROGMEM = "gcdext-test";
656 const char quick_test_str[] PROGMEM = "quick-test";
657 const char performance_str[] PROGMEM = "performance";
658 const char echo_str[] PROGMEM = "echo";
660 const cmdlist_entry_t cmdlist[] PROGMEM = {
661 { add_test_str, NULL, test_add_bigint },
662 { add_scale_test_str, NULL, test_add_scale_bigint },
663 { mul_test_str, NULL, test_mul_bigint },
664 { mul_mont_test_str, NULL, test_mul_mont_bigint },
665 { mul_word_test_str, NULL, test_mul_word_bigint },
666 { square_test_str, NULL, test_square_bigint },
667 { reduce_test_str, NULL, test_reduce_bigint },
668 { expmod_test_str, NULL, test_expmod_bigint },
669 { expmod_mont_test_str, NULL, test_expmod_mont_bigint },
670 { gcdext_test_str, NULL, test_gcdext_bigint },
671 { quick_test_str, NULL, test_gcdext_simple },
672 { echo_test_str, NULL, test_echo_bigint },
673 { performance_str, NULL, testrun_performance_bigint },
674 { echo_str, (void*)1, (void_fpt)echo_ctrl },
682 welcome_msg(algo_name);
683 cmd_interface(cmdlist);