test_src/main-ecdsa-test.c

   1 /* main-dsa-test.c */
   2 /*
   3     This file is part of the AVR-Crypto-Lib.
   4     Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de)
   5
   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.
  10
  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.
  15
  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/>.
  18 */
  19 /*
  20  * ECDSA test-suit
  21  *
  22 */
  23
  24 #include "main-test-common.h"
  25
  26 #include "noekeon.h"
  27 #include "noekeon_prng.h"
  28 #include "bigint.h"
  29 #include "bigint_io.h"
  30 #include "nist_p192.h"
  31
  32 #include "performance_test.h"
  33 #include "hfal_sha1.h"
  34 #include "base64_enc.h"
  35 #include "base64_dec.h"
  36
  37 char* algo_name = "ECDSA";
  38
  39 /*****************************************************************************
  40  *  additional validation-functions                                                                                      *
  41  *****************************************************************************/
  42
  43 void testrun_performance_invert_bigint(void){
  44     printf_P(PSTR("\n=== performance measurement (invert) ===\n"));
  45     unsigned i,j;
  46     uint64_t time = 0;
  47     bigint_t a, v;
  48     bigint_word_t v_w[192 / BIGINT_WORD_SIZE];
  49     bigint_word_t a_w[192 / BIGINT_WORD_SIZE];
  50
  51     a.wordv = a_w;
  52     v.wordv = v_w;
  53
  54     for(j = 0; j < 32; ++j){
  55         for(i = 0; i < 192 / BIGINT_WORD_SIZE; ++i){
  56             ((uint8_t*)v_w)[i] = random();
  57         }
  58         v.length_W = 192 / BIGINT_WORD_SIZE;
  59         v.info = 0;
  60         bigint_adjust(&v);
  61
  62         for(i = 0; i < 16; ++i){
  63             startTimer(1);
  64             START_TIMER;
  65             bigint_inverse(&a, &v, &nist_curve_p192_p);
  66             STOP_TIMER;
  67             time += stopTimer();
  68         }
  69     }
  70
  71     time >>= 8;
  72     ++time;
  73     time >>= 1;
  74
  75     printf_P(PSTR("  invert costs %"PRIu32" cycles\n"), (uint32_t)time);
  76 }
  77
  78 void testrun_performance_multiply_bigint(void){
  79     printf_P(PSTR("\n=== performance measurement (invert) ===\n"));
  80     unsigned i,j;
  81     uint64_t time_a = 0, time_b = 0;
  82     uint32_t tmp;
  83     bigint_t a, b, v;
  84     bigint_word_t v_w[192 * 2 / BIGINT_WORD_SIZE];
  85     bigint_word_t a_w[192 / BIGINT_WORD_SIZE];
  86     bigint_word_t b_w[192 / BIGINT_WORD_SIZE];
  87
  88     a.wordv = a_w;
  89     b.wordv = b_w;
  90     v.wordv = v_w;
  91
  92     for(j = 0; j < 32; ++j){
  93         for(i = 0; i < 192 / BIGINT_WORD_SIZE; ++i){
  94             ((uint8_t*)a_w)[i] = random();
  95         }
  96         a.length_W = 192 / BIGINT_WORD_SIZE;
  97         a.info = 0;
  98         bigint_adjust(&a);
  99
 100         for(i = 0; i < 192 / BIGINT_WORD_SIZE; ++i){
 101             ((uint8_t*)b_w)[i] = random();
 102         }
 103         b.length_W = 192 / BIGINT_WORD_SIZE;
 104         b.info = 0;
 105         bigint_adjust(&b);
 106
 107         for(i = 0; i < 16; ++i){
 108             startTimer(1);
 109             START_TIMER;
 110             bigint_mul_u(&v,&a, &b);
 111             STOP_TIMER;
 112             tmp = stopTimer();
 113             time_a += tmp;
 114             time_b += tmp;
 115
 116             START_TIMER;
 117             bigint_reduce_p192(&v);
 118             STOP_TIMER;
 119             tmp = stopTimer();
 120             time_b += tmp;
 121          }
 122     }
 123
 124     time_a >>= 8;
 125     ++time_a;
 126     time_a >>= 1;
 127
 128     time_b >>= 8;
 129     ++time_b;
 130     time_b >>= 1;
 131
 132
 133     printf_P(PSTR("  multiply          costs %7"PRIu32" cycles\n"), (uint32_t)time_a);
 134     printf_P(PSTR("  multiply + reduce costs %7"PRIu32" cycles\n"), (uint32_t)time_b);
 135 }
 136
 137 void testrun_performance_reduce_bigint(void){
 138     printf_P(PSTR("\n=== performance measurement (reduce) ===\n"));
 139     unsigned i, j;
 140     bigint_t a,b,v;
 141     bigint_word_t v_w[192 * 2 / BIGINT_WORD_SIZE];
 142     bigint_word_t a_w[192 * 2 / BIGINT_WORD_SIZE];
 143     bigint_word_t b_w[192 * 2 / BIGINT_WORD_SIZE];
 144     uint32_t time_a, time_b;
 145     int32_t time_diff;
 146     int16_t faster_percent;
 147     v.wordv = v_w;
 148     for(j = 0; j < 32; ++j){
 149         do{
 150             for(i = 0; i < 192 * 2 / BIGINT_WORD_SIZE; ++i){
 151                 ((uint8_t*)v_w)[i] = random();
 152             }
 153             v.length_W = 192 * 2 / BIGINT_WORD_SIZE;
 154             v.info = 0;
 155             bigint_adjust(&v);
 156         }while(0);
 157
 158     //    printf_P(PSTR("candidate:\n"));
 159     //    bigint_print_hex(&v);
 160         a.wordv = a_w;
 161         b.wordv = b_w;
 162         calibrateTimer();
 163
 164     //    printf_P(PSTR("\n  going to test optimized version: ...\n"));
 165         uart0_flush();
 166         time_a = 0;
 167         for(i = 0; i < 16; ++i){
 168             bigint_copy(&a, &v);
 169             startTimer(1);
 170             START_TIMER;
 171             bigint_reduce_p192(&a);
 172             STOP_TIMER;
 173             time_a += stopTimer();
 174         }
 175     //    printf_P(PSTR("    took: %"PRIu32" cycles\nresult:"), time);
 176     //    bigint_print_hex(&a);
 177
 178
 179     //    printf_P(PSTR("\n  going to test not-optimized version: ...\n"));
 180     //    uart0_flush();
 181         time_b = 0;
 182         for(i = 0; i < 16; ++i){
 183             bigint_copy(&b, &v);
 184             startTimer(1);
 185             START_TIMER;
 186             bigint_reduce(&b, &nist_curve_p192_p);
 187             STOP_TIMER;
 188             time_b += stopTimer();
 189         }
 190     //    printf_P(PSTR("    took: %"PRIu32" cycles\nresult:"), time);
 191     //    bigint_print_hex(&b);
 192
 193         time_diff = time_b - time_a;
 194         faster_percent = (time_diff * 100) / time_b;
 195
 196         printf_P(PSTR("  delta: %7"PRId32"  (%3"PRId16"%%)  :-"), time_diff, faster_percent);
 197         if(bigint_cmp_u(&a, &b)){
 198             printf_P(PSTR("(\n"));
 199         } else {
 200             printf_P(PSTR(")\n"));
 201         }
 202         uart0_flush();
 203     }
 204 }
 205
 206 uint8_t ecc_affine_point_alloc(ecc_affine_point_t *p, uint16_t length_b){
 207     size_t len = (length_b + BIGINT_WORD_SIZE - 1)/ BIGINT_WORD_SIZE;
 208     if (! (p->x.wordv = malloc(len))){
 209         return 1;
 210     }
 211     if (! (p->y.wordv = malloc(len))){
 212         free(p->x.wordv);
 213         return 2;
 214     }
 215     return 0;
 216 }
 217
 218 void ecc_affine_point_free(ecc_affine_point_t *p){
 219     free(p->x.wordv);
 220     free(p->y.wordv);
 221 }
 222
 223 uint8_t ecc_chudnovsky_point_alloc(ecc_chudnovsky_point_t *p, uint16_t length_b){
 224     size_t len = (length_b + BIGINT_WORD_SIZE - 1)/ BIGINT_WORD_SIZE;
 225     if (! (p->x.wordv = malloc(len))){
 226         return 1;
 227     }
 228     if (! (p->y.wordv = malloc(len))){
 229         free(p->x.wordv);
 230         return 2;
 231     }
 232     if (! (p->z1.wordv = malloc(len))){
 233         free(p->x.wordv);
 234         free(p->y.wordv);
 235         return 3;
 236     }
 237     if (! (p->z2.wordv = malloc(len))){
 238         free(p->x.wordv);
 239         free(p->y.wordv);
 240         free(p->z1.wordv);
 241         return 4;
 242     }
 243     if (! (p->z3.wordv = malloc(len))){
 244         free(p->x.wordv);
 245         free(p->y.wordv);
 246         free(p->z1.wordv);
 247         free(p->z2.wordv);
 248         return 5;
 249     }
 250     return 0;
 251 }
 252
 253 void ecc_chudnovsky_point_free(ecc_chudnovsky_point_t *p){
 254     free(p->x.wordv);
 255     free(p->y.wordv);
 256     free(p->z1.wordv);
 257     free(p->z2.wordv);
 258     free(p->z3.wordv);
 259 }
 260
 261 void testrun_square(void){
 262     bigint_word_t a_w[] = {
 263         0x82, 0x6f, 0x79, 0x39, 0x47, 0x06, 0x26, 0x9f,
 264         0x4b, 0xe2, 0x15, 0x61, 0x6f, 0xa1, 0xd4, 0x0c,
 265         0x1f, 0x24, 0x3a, 0xd4, 0xc2, 0x6d, 0xe8, 0xb6
 266     };
 267
 268     bigint_word_t b_w[2 * 192 / BIGINT_WORD_SIZE];
 269     bigint_t a, b;
 270
 271     a.wordv = a_w;
 272     a.length_W = sizeof(a_w);
 273     a.info = 7;
 274
 275     b.wordv = b_w;
 276     b.info = 0;
 277     b.length_W = 0;
 278
 279     printf_P(PSTR("\n a = "));
 280     bigint_print_hex(&a);
 281     bigint_square(&b, &a);
 282     printf_P(PSTR("\n a^2 = "));
 283     bigint_print_hex(&b);
 284     bigint_reduce_p192(&b);
 285     printf_P(PSTR("\n a^2 %% p = "));
 286     bigint_print_hex(&b);
 287     putchar('\n');
 288
 289
 290 }
 291
 292 #if 1
 293 /*
 294 0: b3cfed2634516540528622e16c396c229e50bbdf773f8423
 295 1: b6e86dc2d43a241f0cd4a16f6115e24b9f26064739796f82
 296 2: 563f557e41731f268f82fe81c8fed959600dd46649ebeeee
 297 3: 5e45169bd87475db886b8a7833bb0845f5b011a7ce0c1766
 298 4: 4abf34c505a73308a804dcefacbd8f7b10b59fa6ac6421a
 299 */
 300 uint8_t test_point_x_w[] = {
 301     0x23, 0x84, 0x3f, 0x77, 0xdf, 0xbb, 0x50, 0x9e,
 302     0x22, 0x6c, 0x39, 0x6c, 0xe1, 0x22, 0x86, 0x52,
 303     0x40, 0x65, 0x51, 0x34, 0x26, 0xed, 0xcf, 0xb3
 304 };
 305
 306 uint8_t test_point_y_w[] = {
 307     0x82, 0x6f, 0x79, 0x39, 0x47, 0x06, 0x26, 0x9f,
 308     0x4b, 0xe2, 0x15, 0x61, 0x6f, 0xa1, 0xd4, 0x0c,
 309     0x1f, 0x24, 0x3a, 0xd4, 0xc2, 0x6d, 0xe8, 0xb6
 310 };
 311
 312 uint8_t test_point_z1_w[] = {
 313     0xee, 0xee, 0xeb, 0x49, 0x66, 0xd4, 0x0d, 0x60,
 314     0x59, 0xd9, 0xfe, 0xc8, 0x81, 0xfe, 0x82, 0x8f,
 315     0x26, 0x1f, 0x73, 0x41, 0x7e, 0x55, 0x3f, 0x56
 316 };
 317
 318 uint8_t test_point_z2_w[] = {
 319     0x66, 0x17, 0x0c, 0xce, 0xa7, 0x11, 0xb0, 0xf5,
 320     0x45, 0x08, 0xbb, 0x33, 0x78, 0x8a, 0x6b, 0x88,
 321     0xdb, 0x75, 0x74, 0xd8, 0x9b, 0x16, 0x45, 0x5e
 322 };
 323
 324 uint8_t test_point_z3_w[] = {
 325     0x1a, 0x42, 0xc6, 0x6a, 0xfa, 0x59, 0x0b, 0xb1,
 326     0xf7, 0xd8, 0xcb, 0xfa, 0xce, 0x4d, 0x80, 0x8a,
 327     0x30, 0x73, 0x5a, 0x50, 0x4c, 0xf3, 0xab, 0x04
 328 };
 329
 330 ecc_combi_point_t test_point = {
 331     .chudnovsky = {
 332         .x = {
 333             .wordv = test_point_x_w,
 334             .length_W = sizeof(test_point_x_w),
 335             .info = 7
 336         },
 337         .y = {
 338             .wordv = test_point_y_w,
 339             .length_W = sizeof(test_point_y_w),
 340             .info = 7
 341         },
 342         .z1 = {
 343             .wordv = test_point_z1_w,
 344             .length_W = sizeof(test_point_z1_w),
 345             .info = 6
 346         },
 347         .z2 = {
 348             .wordv = test_point_z2_w,
 349             .length_W = sizeof(test_point_z2_w),
 350             .info = 6
 351         },
 352         .z3 = {
 353             .wordv = test_point_z3_w,
 354             .length_W = sizeof(test_point_z3_w),
 355             .info = 2
 356         }
 357     }
 358 };
 359 void testrun_genkey2(void){
 360     ecc_chudnovsky_point_t q;
 361     ecc_affine_point_t qa;
 362
 363     printf_P(PSTR("\n== testing key generation (2) ==\n"));
 364
 365     if(ecc_chudnovsky_point_alloc(&q, 192)){
 366         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 367         return;
 368     }
 369     if(ecc_affine_point_alloc(&qa, 192)){
 370         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 371         return;
 372     }
 373
 374     ecc_chudnovsky_point_print(&test_point.chudnovsky);
 375     ecc_chudnovsky_to_affine_point(&qa, &test_point.chudnovsky, &nist_curve_p192);
 376     printf_P(PSTR("\n  Qx: "));
 377     bigint_print_hex(&qa.x);
 378     printf_P(PSTR("\n  Qy: "));
 379     bigint_print_hex(&qa.y);
 380     printf_P(PSTR("\n================\n"));
 381     ecc_chudnovsky_point_double_sp(&q, &test_point.chudnovsky, &nist_curve_p192);
 382     ecc_chudnovsky_point_print(&q);
 383
 384     ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192);
 385
 386     printf_P(PSTR("\n  Qx: "));
 387     bigint_print_hex(&qa.x);
 388     printf_P(PSTR("\n  Qy: "));
 389     bigint_print_hex(&qa.y);
 390     puts("\n");
 391
 392 }
 393
 394 void testrun_genkey1(void){
 395     ecc_chudnovsky_point_t q;
 396     ecc_affine_point_t qa;
 397
 398     uint8_t k_w[] = {
 399     //  e5ce89a34adddf25ff3bf1ffe6803f57d0220de3118798ea
 400         0xea, 0x98, 0x87, 0x11, 0xe3, 0x0d, 0x22, 0xd0,
 401         0x57, 0x3f, 0x80, 0xe6, 0xff, 0xf1, 0x3b, 0xff,
 402         0x25, 0xdf, 0xdd, 0x4a, 0xa3, 0x89, 0xce, 0xe5
 403     };
 404
 405     bigint_t k = {
 406             .length_W = sizeof(k_w),
 407             .wordv = k_w,
 408             .info = 7
 409     };
 410
 411     printf_P(PSTR("\n== testing key generation ==\n"));
 412
 413     if(ecc_chudnovsky_point_alloc(&q, 192)){
 414         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 415         return;
 416     }
 417     if(ecc_affine_point_alloc(&qa, 192)){
 418         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 419         return;
 420     }
 421
 422     printf_P(PSTR("  k:  "));
 423     bigint_print_hex(&k);
 424     ecc_chudnovsky_multiplication(&q, &k, &nist_curve_p192_basepoint.chudnovsky, &nist_curve_p192);
 425     ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192);
 426
 427     printf_P(PSTR("\n  Qx: "));
 428     bigint_print_hex(&qa.x);
 429     printf_P(PSTR("\n  Qy: "));
 430     bigint_print_hex(&qa.y);
 431     puts("\n");
 432 }
 433
 434 void testrun_genkey3(void){
 435     ecc_chudnovsky_point_t q;
 436     ecc_affine_point_t qa;
 437
 438     uint8_t k_w[] = {
 439         0xb2, 0x51, 0x97, 0xc3, 0x7c, 0x61, 0xf8, 0x8f,
 440         0x19, 0x91, 0xcc, 0x67, 0xb5, 0x1c, 0x34, 0x23,
 441         0xff, 0x13, 0xad, 0x14, 0x57, 0x43, 0x14, 0x7d
 442     };
 443
 444     bigint_t k = {
 445             .length_W = sizeof(k_w),
 446             .wordv = k_w,
 447             .info = 6
 448     };
 449
 450     printf_P(PSTR("\n== testing key generation ==\n"));
 451
 452     if(ecc_chudnovsky_point_alloc(&q, 192)){
 453         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 454         return;
 455     }
 456     if(ecc_affine_point_alloc(&qa, 192)){
 457         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 458         return;
 459     }
 460
 461     printf_P(PSTR("  k:  "));
 462     bigint_print_hex(&k);
 463     ecc_chudnovsky_double_and_add(&q, &k, &nist_curve_p192_basepoint.chudnovsky, &nist_curve_p192);
 464     ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192);
 465
 466     printf_P(PSTR("\n  Qx: "));
 467     bigint_print_hex(&qa.x);
 468     printf_P(PSTR("\n  Qy: "));
 469     bigint_print_hex(&qa.y);
 470     puts("\n");
 471 }
 472
 473 void testrun_genkey(void){
 474     ecc_chudnovsky_point_t q;
 475     ecc_affine_point_t qa;
 476
 477     bigint_t k;
 478
 479     printf_P(PSTR("\n== testing key generation ==\n"));
 480
 481     printf_P(PSTR("enter secret key d: "));
 482     bigint_read_hex_echo(&k);
 483     putchar('\n');
 484
 485     if(ecc_chudnovsky_point_alloc(&q, 192)){
 486         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 487         return;
 488     }
 489     if(ecc_affine_point_alloc(&qa, 192)){
 490         printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__);
 491         return;
 492     }
 493
 494     printf_P(PSTR("  k:  "));
 495     bigint_print_hex(&k);
 496     ecc_chudnovsky_multiplication(&q, &k, &nist_curve_p192_basepoint.chudnovsky, &nist_curve_p192);
 497     ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192);
 498
 499     printf_P(PSTR("\n  Qx: "));
 500     bigint_print_hex(&qa.x);
 501     printf_P(PSTR("\n  Qy: "));
 502     bigint_print_hex(&qa.y);
 503     puts("\n");
 504 }
 505
 506
 507 #endif
 508
 509 /*****************************************************************************
 510  *  main                                                                                                                                         *
 511  *****************************************************************************/
 512
 513 const char echo_test_str[]               PROGMEM = "echo-test";
 514 const char reset_prng_str[]              PROGMEM = "reset-prng";
 515 const char quick_test_str[]              PROGMEM = "quick-test";
 516 const char performance_reduce_str[]      PROGMEM = "performance_reduce";
 517 const char performance_invert_str[]      PROGMEM = "performance_invert";
 518 const char performance_multiply_str[]    PROGMEM = "performance_multiply";
 519 const char genkey1_str[]                 PROGMEM = "genkey1";
 520 const char genkey2_str[]                 PROGMEM = "genkey2";
 521 const char genkey3_str[]                 PROGMEM = "genkey3";
 522 const char genkey_str[]                  PROGMEM = "genkey";
 523 const char square_str[]                  PROGMEM = "square";
 524 const char echo_str[]                    PROGMEM = "echo";
 525
 526 const const cmdlist_entry_t cmdlist[] PROGMEM = {
 527 //      { reset_prng_str,              NULL, reset_prng                           },
 528 //      { quick_test_str,              NULL, quick_test                           },
 529     { square_str,                  NULL, testrun_square                       },
 530     { genkey_str,                  NULL, testrun_genkey                       },
 531     { genkey1_str,                 NULL, testrun_genkey1                      },
 532     { genkey2_str,                 NULL, testrun_genkey2                      },
 533     { genkey3_str,                 NULL, testrun_genkey3                      },
 534         { performance_reduce_str,      NULL, testrun_performance_reduce_bigint    },
 535     { performance_invert_str,      NULL, testrun_performance_invert_bigint    },
 536     { performance_multiply_str,    NULL, testrun_performance_multiply_bigint  },
 537         { echo_str,                (void*)1, (void_fpt)echo_ctrl                  },
 538         { NULL,                        NULL, NULL                                 }
 539 };
 540
 541 int main (void){
 542     int8_t r;
 543     main_setup();
 544
 545     for(;;){
 546         welcome_msg(algo_name);
 547         r = cmd_interface(cmdlist);
 548         printf("r = %"PRId8"\n", r);
 549         cli_putstr_P(PSTR("\r\nHello!\r\n"));
 550         }
 551 }