From 32705e6283b34dd709dc8fafdf5c3e32d6a944a1 Mon Sep 17 00:00:00 2001 From: bg Date: Tue, 18 Sep 2012 14:19:37 +0200 Subject: [PATCH] nist P-192 optimized recude for ecdsa --- ecdsa/nist_p192.c | 152 +++++++++++++++++++++++++++++++++++++ ecdsa/nist_p192.h | 28 +++++++ mkfiles/ecdsa.mk | 14 ++++ test_src/main-ecdsa-test.c | 140 ++++++++++++++++++++++++++++++++++ 4 files changed, 334 insertions(+) create mode 100644 ecdsa/nist_p192.c create mode 100644 ecdsa/nist_p192.h create mode 100644 mkfiles/ecdsa.mk create mode 100644 test_src/main-ecdsa-test.c diff --git a/ecdsa/nist_p192.c b/ecdsa/nist_p192.c new file mode 100644 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 . +*/ + +#include +#include +#include + +#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 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 . +*/ + +#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 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 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 . +*/ +/* + * 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")); + } +} -- 2.39.2