nist P-192 optimized recude for ecdsa

diff --git a/ecdsa/nist_p192.c b/ecdsa/nist_p192.c
new file mode 100644 (file)
index 0000000..ed3db58
--- /dev/null
+++ b/ecdsa/nist_p192.c
@@ -0,0 +1,152 @@
+/* p192.c */
+/*
+    This file is part of the AVR-Crypto-Lib.
+    Copyright (C) 2006-2012 Daniel Otte (daniel.otte@rub.de)
+
+    This program is free software: you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation, either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#include <inttypes.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "bigint.h"
+
+/*
+ * p = 6277101735386680763835789423207666416083908700390324961279
+ *   = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
+ */
+
+static
+uint8_t nist_curve_p192_p_w[] = {
+        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+        0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
+        0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff
+};
+
+bigint_t nist_curve_p192_p = {
+        .length_W = 192 / BIGINT_WORD_SIZE,
+        .wordv = nist_curve_p192_p_w,
+        .info = 7
+};
+
+/*
+ * A = ( A5 || A4 || A3 || A2 || A1 || A0 ) ; An if 64-bit
+ * A mod p = B = T + S1 + S2 + S3 mod p
+ *
+ * T  = ( A2 || A1 || A0 )
+ * S1 = ( A3 || A3 )
+ * S2 = ( A4 || A4 || 0 )
+ * S3 = ( A5 || A5 || A5 )
+ *
+ */
+
+int bigint_reduce_p192(bigint_t *a){
+
+    bigint_word_t s_w[3 * 64 / BIGINT_WORD_SIZE];
+    bigint_t s;
+    uint16_t o_length;
+
+    o_length = a->length_W;
+
+    if(o_length < 192 / BIGINT_WORD_SIZE){
+        return 0;
+    }
+
+    if(o_length > 192 * 2 / BIGINT_WORD_SIZE){
+        bigint_reduce(a, &nist_curve_p192_p);
+    }
+
+    if(o_length > 192 / BIGINT_WORD_SIZE){
+        s.wordv = s_w;
+        s.length_W = 2 * 64 / BIGINT_WORD_SIZE;
+
+        /*
+         * copy A3 twice in s
+         */
+        if(o_length >= 4 * 64 / BIGINT_WORD_SIZE){
+            memcpy(s.wordv, a->wordv + 3 * 64 / BIGINT_WORD_SIZE, 64 / 8);
+        }else{
+            memset(s.wordv, 0, 8);
+            memcpy(s.wordv, a->wordv + 3 * 64 / BIGINT_WORD_SIZE,
+                    o_length * BIGINT_WORD_SIZE / 8 - 3 * 64 / 8);
+        }
+
+        memcpy(s.wordv + 64 / BIGINT_WORD_SIZE, s.wordv, 64 / 8);
+        bigint_adjust(&s);
+
+        /*
+         * Set A3 to zero so we can use a as T
+         */
+        memset(a->wordv + 3 * 64 / BIGINT_WORD_SIZE, 0, BIGINT_WORD_SIZE / 8);
+        a->length_W = 3 * 64 / BIGINT_WORD_SIZE;
+        bigint_adjust(a);
+
+        /*
+         * Add s (alias S1) to a (alias T)
+         */
+        bigint_add_u(a, a, &s);
+
+
+        if(o_length > 4 * 64 / BIGINT_WORD_SIZE){
+            /*
+             * copy A4 twice in s
+             */
+            if(o_length >= 5 * 64 / BIGINT_WORD_SIZE){
+                memcpy(s.wordv, a->wordv + 4 * 64 / BIGINT_WORD_SIZE, 64 / 8);
+            }else{
+                memset(s.wordv, 0, 8);
+                memcpy(s.wordv, a->wordv + 4 * 64 / BIGINT_WORD_SIZE,
+                        o_length * BIGINT_WORD_SIZE / 8 - 4 * 64 / 8);
+            }
+            memcpy(s.wordv + 64 / BIGINT_WORD_SIZE, s.wordv, 64 / 8);
+            bigint_adjust(&s);
+
+            /*
+             * Add s (alias S2) to a (alias T + S1)
+             */
+            bigint_add_scale_u(a, &s, 8);
+
+
+            if(o_length > 5 * 64 / BIGINT_WORD_SIZE){
+                /*
+                 * copy A5 three times in s
+                 */
+                if(o_length == 6 * 64 / BIGINT_WORD_SIZE){
+                    memcpy(s.wordv, a->wordv + 5 * 64 / BIGINT_WORD_SIZE, 64 / 8);
+                } else {
+                    memset(s.wordv, 0, 8);
+                    memcpy(s.wordv, a->wordv + 5 * 64 / BIGINT_WORD_SIZE,
+                            o_length * BIGINT_WORD_SIZE / 8 - 5 * 64 / 8);
+                }
+                memcpy(s.wordv + 64 / BIGINT_WORD_SIZE, s.wordv, 64 / 8);
+                memcpy(s.wordv + 2 * 64 / BIGINT_WORD_SIZE, s.wordv, 64 / 8);
+                s.length_W = 3 * 64 / BIGINT_WORD_SIZE;
+                bigint_adjust(&s);
+
+                /*
+                 * Add s (alias S2) to a (alias T + S1)
+                 */
+                bigint_add_u(a, a, &s);
+            }
+        }
+
+    }
+    while(bigint_cmp_u(a, &nist_curve_p192_p) >= 0){
+        bigint_sub_u(a, a, &nist_curve_p192_p);
+    }
+
+    return 0;
+}
+

diff --git a/ecdsa/nist_p192.h b/ecdsa/nist_p192.h
new file mode 100644 (file)
index 0000000..9959bd8
--- /dev/null
+++ b/ecdsa/nist_p192.h
@@ -0,0 +1,28 @@
+/* nist_p192.h */
+/*
+    This file is part of the AVR-Crypto-Lib.
+    Copyright (C) 2012 Daniel Otte (daniel.otte@rub.de)
+
+    This program is free software: you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation, either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+#ifndef NIST_P192_H_
+#define NIST_P192_H_
+
+#include "bigint.h"
+
+extern bigint_t nist_curve_p192_p;
+int bigint_reduce_p192(bigint_t *a);
+
+#endif /* NIST_P192_H_ */

diff --git a/mkfiles/ecdsa.mk b/mkfiles/ecdsa.mk
new file mode 100644 (file)
index 0000000..4aeff73
--- /dev/null
+++ b/mkfiles/ecdsa.mk
@@ -0,0 +1,14 @@
+# Makefile for ECDSA
+ALGO_NAME := ECDSA
+
+# comment out the following line for removement of ECDSA from the build process
+SIGNATURE += $(ALGO_NAME)
+
+$(ALGO_NAME)_DIR      := ecdsa/
+$(ALGO_NAME)_INCDIR   := memxor/ bigint/ sha1/ noekeon/ base64/ hfal/
+$(ALGO_NAME)_OBJ      := bigint.o bigint_io.o sha1-asm.o nist_p192.o base64_enc.o
+$(ALGO_NAME)_TESTBIN  := main-ecdsa-test.o $(CLI_STD) hfal_sha1.o $(HFAL_STD) \
+                         noekeon_asm.o noekeon_prng.o memxor.o 
+                        
+$(ALGO_NAME)_PERFORMANCE_TEST := performance
+

diff --git a/test_src/main-ecdsa-test.c b/test_src/main-ecdsa-test.c
new file mode 100644 (file)
index 0000000..2da259d
--- /dev/null
+++ b/test_src/main-ecdsa-test.c
@@ -0,0 +1,140 @@
+/* main-dsa-test.c */
+/*
+    This file is part of the AVR-Crypto-Lib.
+    Copyright (C) 2010 Daniel Otte (daniel.otte@rub.de)
+
+    This program is free software: you can redistribute it and/or modify
+    it under the terms of the GNU General Public License as published by
+    the Free Software Foundation, either version 3 of the License, or
+    (at your option) any later version.
+
+    This program is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+    GNU General Public License for more details.
+
+    You should have received a copy of the GNU General Public License
+    along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/*
+ * ECDSA test-suit
+ *
+*/
+
+#include "main-test-common.h"
+
+#include "noekeon.h"
+#include "noekeon_prng.h"
+#include "bigint.h"
+#include "bigint_io.h"
+#include "nist_p192.h"
+
+#include "performance_test.h"
+#include "hfal_sha1.h"
+#include "base64_enc.h"
+#include "base64_dec.h"
+
+char* algo_name = "ECDSA";
+
+/*****************************************************************************
+ *  additional validation-functions                                                                                     *
+ *****************************************************************************/
+
+void testrun_performance_bigint(void){
+    printf_P(PSTR("\n=== performance measurement ===\n"));
+    unsigned i, j;
+    bigint_t a,b,v;
+    bigint_word_t v_w[192 * 2 / BIGINT_WORD_SIZE];
+    bigint_word_t a_w[192 * 2 / BIGINT_WORD_SIZE];
+    bigint_word_t b_w[192 * 2 / BIGINT_WORD_SIZE];
+    uint32_t time_a, time_b;
+    int32_t time_diff;
+    int16_t faster_percent;
+    v.wordv = v_w;
+    for(j = 0; j < 32; ++j){
+        do{
+            for(i = 0; i < 192 * 2 / BIGINT_WORD_SIZE; ++i){
+                ((uint8_t*)v_w)[i] = random();
+            }
+            v.length_W = 192 * 2 / BIGINT_WORD_SIZE;
+            v.info = 0;
+            bigint_adjust(&v);
+        }while(0);
+
+    //    printf_P(PSTR("candidate:\n"));
+    //    bigint_print_hex(&v);
+        a.wordv = a_w;
+        b.wordv = b_w;
+        calibrateTimer();
+
+    //    printf_P(PSTR("\n  going to test optimized version: ...\n"));
+        uart0_flush();
+        time_a = 0;
+        for(i = 0; i < 16; ++i){
+            bigint_copy(&a, &v);
+            startTimer(1);
+            START_TIMER;
+            bigint_reduce_p192(&a);
+            STOP_TIMER;
+            time_a += stopTimer();
+        }
+    //    printf_P(PSTR("    took: %"PRIu32" cycles\nresult:"), time);
+    //    bigint_print_hex(&a);
+
+
+    //    printf_P(PSTR("\n  going to test not-optimized version: ...\n"));
+    //    uart0_flush();
+        time_b = 0;
+        for(i = 0; i < 16; ++i){
+            bigint_copy(&b, &v);
+            startTimer(1);
+            START_TIMER;
+            bigint_reduce(&b, &nist_curve_p192_p);
+            STOP_TIMER;
+            time_b += stopTimer();
+        }
+    //    printf_P(PSTR("    took: %"PRIu32" cycles\nresult:"), time);
+    //    bigint_print_hex(&b);
+
+        time_diff = time_b - time_a;
+        faster_percent = (time_diff * 100) / time_b;
+
+        printf_P(PSTR("  delta: %7"PRId32"  (%3"PRId16"%%)  :-"), time_diff, faster_percent);
+        if(bigint_cmp_u(&a, &b)){
+            printf_P(PSTR("(\n"));
+        } else {
+            printf_P(PSTR(")\n"));
+        }
+        uart0_flush();
+    }
+}
+
+/*****************************************************************************
+ *  main                                                                                                                                        *
+ *****************************************************************************/
+
+const char echo_test_str[]        PROGMEM = "echo-test";
+const char reset_prng_str[]       PROGMEM = "reset-prng";
+const char quick_test_str[]       PROGMEM = "quick-test";
+const char performance_str[]      PROGMEM = "performance";
+const char echo_str[]             PROGMEM = "echo";
+
+const const cmdlist_entry_t cmdlist[] PROGMEM = {
+//     { reset_prng_str,       NULL, reset_prng                    },
+//     { quick_test_str,       NULL, quick_test                    },
+       { performance_str,      NULL, testrun_performance_bigint    },
+       { echo_str,         (void*)1, (void_fpt)echo_ctrl           },
+       { NULL,                 NULL, NULL                          }
+};
+
+int main (void){
+    int8_t r;
+    main_setup();
+
+    for(;;){
+        welcome_msg(algo_name);
+        r = cmd_interface(cmdlist);
+        printf("r = %"PRId8"\n", r);
+        cli_putstr_P(PSTR("\r\nHello!\r\n"));
+       }
+}