From 45d15fcc098c9eece5c39b5e421a1706f187a0d3 Mon Sep 17 00:00:00 2001 From: bg Date: Sat, 29 Sep 2012 15:59:32 +0200 Subject: [PATCH] more ecc stuff --- ecdsa/ecc.h | 78 ++++++ ecdsa/ecc_chudnovsky.c | 470 +++++++++++++++++++++++++++++++++++++ ecdsa/nist_p192.c | 147 +++++++++++- ecdsa/nist_p192.h | 8 + mkfiles/ecdsa.mk | 2 +- test_src/main-ecdsa-test.c | 435 +++++++++++++++++++++++++++++++++- 6 files changed, 1119 insertions(+), 21 deletions(-) create mode 100644 ecdsa/ecc.h create mode 100644 ecdsa/ecc_chudnovsky.c diff --git a/ecdsa/ecc.h b/ecdsa/ecc.h new file mode 100644 index 0000000..ac7d98c --- /dev/null +++ b/ecdsa/ecc.h @@ -0,0 +1,78 @@ +/* ecc.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 ECC_H_ +#define ECC_H_ + +typedef struct { + bigint_t x; + bigint_t y; + bigint_t z1; + bigint_t z2; + bigint_t z3; +} ecc_chudnovsky_point_t; + +typedef struct { + bigint_t x; + bigint_t y; +} ecc_affine_point_t; + +typedef struct __attribute__((packed)){ + ecc_affine_point_t affine; + ecc_chudnovsky_point_t chudnovsky; +} ecc_combi_point_t; + +typedef struct { + bigint_t* p; + bigint_t* b; + int (*reduce_p)(bigint_t*); +} ecc_curve_sp_t; + +void ecc_chudnovsky_point_print(const ecc_chudnovsky_point_t *p); + + +uint8_t ecc_affine_to_chudnovsky_point(ecc_chudnovsky_point_t *dest, + const ecc_affine_point_t *src); +uint8_t ecc_chudnovsky_to_affine_point(ecc_affine_point_t *dest, + const ecc_chudnovsky_point_t *src, + const ecc_curve_sp_t *curve); +uint8_t ecc_chudnovsky_point_double_sp(ecc_chudnovsky_point_t *dest, + const ecc_chudnovsky_point_t *a, + const ecc_curve_sp_t *curve); +void ecc_chudnovsky_point_copy(ecc_chudnovsky_point_t *dest, + const ecc_chudnovsky_point_t *src); +uint8_t ecc_chudnovsky_point_add_sp(ecc_chudnovsky_point_t *dest, + const ecc_chudnovsky_point_t *a, + const ecc_chudnovsky_point_t *b, + const ecc_curve_sp_t *curve); +uint8_t ecc_chudnovsky_double_and_add(ecc_chudnovsky_point_t *dest, + const bigint_t *k, + const ecc_chudnovsky_point_t *p, + const ecc_curve_sp_t* curve); +uint8_t bigint_to_naf(uint8_t* dest, uint16_t *length, const bigint_t *src); +uint8_t ecc_chudnovsky_naf_multiplication(ecc_chudnovsky_point_t *dest, + const bigint_t *k, + const ecc_chudnovsky_point_t *p, + const ecc_curve_sp_t* curve); +uint8_t ecc_chudnovsky_multiplication(ecc_chudnovsky_point_t *dest, + const bigint_t *k, + const ecc_chudnovsky_point_t *p, + const ecc_curve_sp_t* curve); + +#endif /* ECC_H_ */ diff --git a/ecdsa/ecc_chudnovsky.c b/ecdsa/ecc_chudnovsky.c new file mode 100644 index 0000000..f5a8f37 --- /dev/null +++ b/ecdsa/ecc_chudnovsky.c @@ -0,0 +1,470 @@ +/* ecc_chudnovsky.c */ +/* + This file is part of the ARM-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 "bigint.h" +#include "ecc.h" +#include +#include + +#if 1 +#include +#include "bigint_io.h" +#include "uart_i.h" +#include +#endif + +#if 0 +#define printf_P(...) +#define bigint_print_hex(a) +#undef putchar +#define putchar(a) +#endif + +/* + * if (Y == 0) + * return POINT_AT_INFINITY + * S = 4*X*Y^2 + * M = 3*(X + Z^2)*(X - Z^2) + * X' = M^2 - 2*S + * Y' = M*(S - X') - 8*Y^4 + * Z' = 2*Y*Z + * Z'^2 = Z'^2 + * Z'^3 = Z'^2 * Z' + * return (X', Y', Z', Z'^2, Z'^3) + */ + +uint8_t ecc_affine_to_chudnovsky_point(ecc_chudnovsky_point_t *dest, + const ecc_affine_point_t *src){ + if(src->y.length_W == 0){ + /* point at infinity */ + bigint_set_zero(&dest->y); + return 0; + } + bigint_copy(&dest->x, &src->x); + bigint_copy(&dest->y, &src->y); + dest->z1.wordv[0] = 1; + dest->z2.wordv[0] = 1; + dest->z3.wordv[0] = 1; + dest->z1.length_W = 1; + dest->z2.length_W = 1; + dest->z3.length_W = 1; + dest->z1.info = 0; + dest->z2.info = 0; + dest->z3.info = 0; + bigint_adjust(&dest->z1); + bigint_adjust(&dest->z2); + bigint_adjust(&dest->z3); + return 0; +} + +uint8_t ecc_chudnovsky_to_affine_point(ecc_affine_point_t *dest, + const ecc_chudnovsky_point_t *src, + const ecc_curve_sp_t *curve){ + if(src->y.length_W == 0){ + /* point at infinity */ + bigint_set_zero(&dest->y); + return 0; + } + bigint_word_t t_w[curve->p->length_W * 2]; + bigint_word_t z1_w[curve->p->length_W * 2]; + bigint_word_t z2_w[curve->p->length_W]; + bigint_t t, z1, z2; + t.wordv = t_w; + z1.wordv = z1_w; + z2.wordv = z2_w; + + bigint_inverse(&z1, &src->z1, curve->p); + bigint_square(&t, &z1); + curve->reduce_p(&t); + bigint_copy(&z2, &t); + bigint_mul_u(&t, &src->x, &z2); + curve->reduce_p(&t); + bigint_copy(&dest->x, &t); + bigint_mul_u(&t, &z1, &z2); + curve->reduce_p(&t); + bigint_mul_u(&t, &t, &src->y); + curve->reduce_p(&t); + bigint_copy(&dest->y, &t); + + return 0; +} + +void ecc_chudnovsky_point_print(const ecc_chudnovsky_point_t *p){ + if(p->y.length_W == 0){ + printf_P(PSTR(" ECC point = point-at-infinity\n")); + return; + } + printf_P(PSTR(" ECC point x = ")); + bigint_print_hex(&p->x); + printf_P(PSTR("\n ECC point y = ")); + bigint_print_hex(&p->y); + printf_P(PSTR("\n ECC point z1 = ")); + bigint_print_hex(&p->z1); + printf_P(PSTR("\n ECC point z2 = ")); + bigint_print_hex(&p->z2); + printf_P(PSTR("\n ECC point z3 = ")); + bigint_print_hex(&p->z3); + putchar('\n'); +} + +uint8_t ecc_chudnovsky_point_double_sp(ecc_chudnovsky_point_t *dest, + const ecc_chudnovsky_point_t *a, + const ecc_curve_sp_t *curve){ + if(a->y.length_W == 0){ + /* point at infinity */ + bigint_set_zero(&dest->y); + return 0; + } + bigint_word_t s_w[curve->p->length_W * 2]; + bigint_word_t m_w[curve->p->length_W * 2]; + bigint_word_t t_w[curve->p->length_W * 2]; + bigint_t s, m, t; + + s.wordv = s_w; + m.wordv = m_w; + t.wordv = t_w; + + /* compute s*/ + bigint_square(&t, &a->y); + curve->reduce_p(&t); + bigint_mul_u(&s, &t, &a->x); + curve->reduce_p(&s); + bigint_shiftleft(&s, 2); + curve->reduce_p(&s); + + /* compute m */ + bigint_sub_u(&t, &a->x, &a->z2); +// /**/curve->reduce_p(&t); + bigint_add_u(&m, &a->x, &a->z2); +// /**/curve->reduce_p(&m); + bigint_mul_s(&m, &m, &t); + curve->reduce_p(&m); + bigint_copy(&t, &m); + bigint_shiftleft(&t, 1); + bigint_add_s(&m, &m, &t); + curve->reduce_p(&m); + + /* compute new z1 */ + bigint_mul_u(&t, &a->z1, &a->y); + curve->reduce_p(&t); + bigint_shiftleft(&t, 1); + curve->reduce_p(&t); + bigint_copy(&dest->z1, &t); + + /* compute new x */ + bigint_square(&t, &m); + curve->reduce_p(&t); + bigint_sub_s(&t, &t, &s); + bigint_sub_s(&t, &t, &s); + curve->reduce_p(&t); + bigint_copy(&dest->x, &t); + + /* compute new y */ + bigint_sub_s(&s, &s, &t); + curve->reduce_p(&s); + bigint_mul_s(&s, &s, &m); + curve->reduce_p(&s); + bigint_square(&t, &a->y); + curve->reduce_p(&t); + bigint_square(&t, &t); + curve->reduce_p(&t); + bigint_shiftleft(&t, 3); + curve->reduce_p(&t); + bigint_sub_s(&s, &s, &t); + curve->reduce_p(&s); + bigint_copy(&dest->y, &s); + + /* compute new z2 */ + bigint_square(&t, &dest->z1); + curve->reduce_p(&t); + bigint_copy(&dest->z2, &t); + + /* compute new z3 */ + bigint_mul_u(&t, &t, &dest->z1); + curve->reduce_p(&t); + bigint_copy(&dest->z3, &t); + + return 0; +} + +void ecc_chudnovsky_point_copy(ecc_chudnovsky_point_t *dest, + const ecc_chudnovsky_point_t *src){ + bigint_copy(&dest->x, &src->x); + bigint_copy(&dest->y, &src->y); + bigint_copy(&dest->z1, &src->z1); + bigint_copy(&dest->z2, &src->z2); + bigint_copy(&dest->z3, &src->z3); +} + +uint8_t ecc_chudnovsky_point_add_sp(ecc_chudnovsky_point_t *dest, + const ecc_chudnovsky_point_t *a, + const ecc_chudnovsky_point_t *b, + const ecc_curve_sp_t *curve){ + if(a->y.length_W == 0){ + ecc_chudnovsky_point_copy(dest, b); + return 0; + } + if(b->y.length_W == 0){ + ecc_chudnovsky_point_copy(dest, a); + return 0; + } + bigint_word_t u1_w[curve->p->length_W * 2]; + bigint_word_t u2_w[curve->p->length_W * 2]; + bigint_word_t s1_w[curve->p->length_W * 2]; + bigint_word_t s2_w[curve->p->length_W * 2]; + bigint_t u1, u2, s1, s2; + + u1.wordv = u1_w; + u2.wordv = u2_w; + s1.wordv = s1_w; + s2.wordv = s2_w; + + /* compute u1 */ + bigint_mul_u(&u1, &a->x, &b->z2); + curve->reduce_p(&u1); + + /* compute u2 */ + bigint_mul_u(&u2, &b->x, &a->z2); + curve->reduce_p(&u2); + + /* compute s1 */ + bigint_mul_u(&s1, &a->y, &b->z3); + curve->reduce_p(&s1); + + /* compute s2 */ + bigint_mul_u(&s2, &b->y, &a->z3); + curve->reduce_p(&s2); + + if(bigint_cmp_u(&u1, &u2) == 0){ + if(bigint_cmp_u(&s1, &s2)){ + /* point at infinity */ + bigint_set_zero(&dest->y); + return 0; + }else{ + /* a == b --> dest = 2*a */ + ecc_chudnovsky_point_double_sp(dest, a, curve); + } + } + + bigint_word_t h_w[curve->p->length_W * 2]; + bigint_word_t r_w[curve->p->length_W * 2]; + bigint_t h, r; + + h.wordv = h_w; + r.wordv = r_w; + /* compute h */ + bigint_sub_s(&h, &u2, &u1); + /**/curve->reduce_p(&h); + + /* compute r */ + bigint_sub_s(&r, &s2, &s1); +// /**/curve->reduce_p(&r); + + /* compute new z */ + bigint_mul_u(&s2, &a->z1, &b->z1); + curve->reduce_p(&s2); + bigint_mul_s(&s2, &s2, &h); + curve->reduce_p(&s2); + bigint_copy(&dest->z1, &s2); + + /* compute u1*h^2 and h^3 */ + bigint_square(&s2, &h); + curve->reduce_p(&s2); + bigint_mul_s(&h, &s2, &h); + curve->reduce_p(&h); + bigint_mul_s(&u1, &s2, &u1); + curve->reduce_p(&u1); + + /* compute new x */ + bigint_square(&u2, &r); + curve->reduce_p(&u2); + bigint_sub_s(&u2, &u2, &h); + curve->reduce_p(&u2); + bigint_sub_s(&u2, &u2, &u1); + bigint_sub_s(&u2, &u2, &u1); + curve->reduce_p(&u2); + bigint_copy(&dest->x, &u2); + + /* compute new y */ + bigint_sub_s(&u1, &u1, &u2); + curve->reduce_p(&u1); + bigint_mul_s(&s2, &u1, &r); + curve->reduce_p(&s2); + bigint_mul_s(&s1, &s1, &h); + curve->reduce_p(&s1); + bigint_sub_s(&s2, &s2, &s1); + curve->reduce_p(&s2); + bigint_copy(&dest->y, &s2); + + + /* compute new z2 */ + bigint_square(&s1, &dest->z1); + curve->reduce_p(&s1); + bigint_copy(&dest->z2, &s1); + + /* compute new z2 */ + bigint_mul_u(&s1, &s1, &dest->z1); + curve->reduce_p(&s1); + bigint_copy(&dest->z3, &s1); + + return 0; +} + +uint8_t ecc_chudnovsky_double_and_add(ecc_chudnovsky_point_t *dest, + const bigint_t *k, + const ecc_chudnovsky_point_t *p, + const ecc_curve_sp_t* curve){ + uint16_t i; + uint8_t s = 0; + bigint_word_t v, t; + + for(i = k->length_W; i > 0; --i){ + v = 1 << (BIGINT_WORD_SIZE - 1); + t = k->wordv[i - 1]; + do{ + if(s){ + ecc_chudnovsky_point_double_sp(dest, dest, curve); + if(v & t){ + ecc_chudnovsky_point_add_sp(dest, dest, p, curve); + } + }else{ + if(v & t){ + s = 1; + ecc_chudnovsky_point_copy(dest, p); + } + } + v >>= 1; + }while(v); + } + return 0; +} + +uint8_t bigint_to_naf(uint8_t* dest, uint16_t *length, const bigint_t *src){ + if(src->length_W == 0){ + *dest = 0; + *length = 2; + return 0; + } + + memset(dest, 0, src->length_W * sizeof(bigint_word_t)); + + uint16_t i = 0; + uint8_t t; /* 3 -> -1 ; 1 -> 1; 0 -> 0 (2 should not happen) */ + bigint_t k, p; + bigint_word_t k_w[src->length_W]; + bigint_word_t p_w = 1; + p.wordv = &p_w; + p.info = 0; + p.length_W = 1; + k.wordv = k_w; + bigint_copy(&k, src); + + while(k.length_W >= 1){ + if(k.wordv[0] & 1){ + t = k.wordv[0] & 3; + if(t == 1){ + bigint_sub_u(&k, &k, &p); + }else{ + bigint_add_u(&k, &k, &p); + } + }else{ + t = 0; + } + dest[(i * 2) / 8] |= t << ((2 * i) & 7); + bigint_shiftright(&k, 1); + i += 1; + } + *length = i; + return 0; +} + +void print_naf(uint8_t* naf, uint16_t length){ + if(!length){ + return; + } + --length; + int8_t t; + do{ + t = (naf[(length * 2) / 8] >> ((length * 2) & 7)) & 3; + switch(t & 3){ + case 0: putchar('0'); break; + case 1: putchar('1'); break; + case 3: putchar('-'); putchar('1'); break; + default: putchar('E'); + } + if(length){ + putchar(' '); + } + }while(length--); +} + +uint8_t ecc_chudnovsky_naf_multiplication(ecc_chudnovsky_point_t *dest, + const bigint_t *k, + const ecc_chudnovsky_point_t *p, + const ecc_curve_sp_t* curve){ + if(k->length_W == 0 || p->y.length_W == 0){ + bigint_set_zero(&dest->y); + return 0; + } + + uint8_t *t, q; + uint16_t i; + ecc_chudnovsky_point_t p_; + bigint_word_t y_[curve->p->length_W]; + + /* p_ = -p*/ + + memcpy(&p_, p, sizeof(p_)); + p_.y.wordv = y_; + bigint_copy(&p_.y, &p->y); + p_.y.info |= BIGINT_NEG_MASK; + bigint_add_s(&p_.y, &p_.y, curve->p); + + + if(!(t = malloc(k->length_W * sizeof(bigint_word_t) * 2))){ + return 1; + } + bigint_to_naf(t, &i, k); + + --i; + dest->y.length_W = 0; + do{ + q = (t[(i * 2) / 8] >> ((i * 2) & 7)) & 3; + ecc_chudnovsky_point_double_sp(dest, dest, curve); + if(q == 1){ + ecc_chudnovsky_point_add_sp(dest, dest, p, curve); + } + if(q == 3){ + ecc_chudnovsky_point_add_sp(dest, dest, &p_, curve); + } + }while(i--); + + free(t); + + return 0; +} + +uint8_t ecc_chudnovsky_multiplication(ecc_chudnovsky_point_t *dest, + const bigint_t *k, + const ecc_chudnovsky_point_t *p, + const ecc_curve_sp_t* curve){ + return ecc_chudnovsky_naf_multiplication(dest, k, p, curve); +} diff --git a/ecdsa/nist_p192.c b/ecdsa/nist_p192.c index ed3db58..4e68e25 100644 --- a/ecdsa/nist_p192.c +++ b/ecdsa/nist_p192.c @@ -21,26 +21,113 @@ #include #include + #include "bigint.h" +#include "ecc.h" +#include "nist_p192.h" + +#include +#include +#include "bigint_io.h" + +#define printf_P(...) +#define bigint_print_hex(a) +#undef putchar +#define putchar(a) /* * 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 + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, + 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff +}; + +uint8_t nist_curve_p192_b_w[] = { + 0xb1, 0xb9, 0x46, 0xc1, 0xec, 0xde, 0xb8, 0xfe, + 0x49, 0x30, 0x24, 0x72, 0xab, 0xe9, 0xa7, 0x0f, + 0xe7, 0x80, 0x9c, 0xe5, 0x19, 0x05, 0x21, 0x64 +}; + +uint8_t nist_curve_p192_gx_w[] = { + 0x12, 0x10, 0xff, 0x82, 0xfd, 0x0a, 0xff, 0xf4, + 0x00, 0x88, 0xa1, 0x43, 0xeb, 0x20, 0xbf, 0x7c, + 0xf6, 0x90, 0x30, 0xb0, 0x0e, 0xa8, 0x8d, 0x18 }; +uint8_t nist_curve_p192_gy_w[] = { + 0x11, 0x48, 0x79, 0x1e, 0xa1, 0x77, 0xf9, 0x73, + 0xd5, 0xcd, 0x24, 0x6b, 0xed, 0x11, 0x10, 0x63, + 0x78, 0xda, 0xc8, 0xff, 0x95, 0x2b, 0x19, 0x07 +}; + +uint8_t nist_curve_p192_z1_w[192 / BIGINT_WORD_SIZE] = { + 1, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0 }; + +uint8_t nist_curve_p192_z2_w[192 / BIGINT_WORD_SIZE] = { + 1, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0 }; + +uint8_t nist_curve_p192_z3_w[192 / BIGINT_WORD_SIZE] = { + 1, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0 }; + bigint_t nist_curve_p192_p = { - .length_W = 192 / BIGINT_WORD_SIZE, - .wordv = nist_curve_p192_p_w, - .info = 7 + .length_W = 192 / BIGINT_WORD_SIZE, + .wordv = nist_curve_p192_p_w, + .info = 7 +}; + +bigint_t nist_curve_p192_b = { + .length_W = 192 / BIGINT_WORD_SIZE, + .wordv = nist_curve_p192_b_w, + .info = 6 }; +ecc_combi_point_t nist_curve_p192_basepoint = { + .chudnovsky = { + .x = { + .length_W = 192 / BIGINT_WORD_SIZE, + .wordv = nist_curve_p192_gx_w, + .info = 4 + }, + .y = { + .length_W = 192 / BIGINT_WORD_SIZE, + .wordv = nist_curve_p192_gy_w, + .info = 2 + }, + .z1 = { + .length_W = 1, + .wordv = nist_curve_p192_z1_w, + .info = 0 + }, + .z2 = { + .length_W = 1, + .wordv = nist_curve_p192_z2_w, + .info = 0 + }, + .z3 = { + .length_W = 1, + .wordv = nist_curve_p192_z3_w, + .info = 0 + } + } +}; + +ecc_curve_sp_t nist_curve_p192 = { + .b = &nist_curve_p192_b, + .p = &nist_curve_p192_p, + .reduce_p = bigint_reduce_p192 +}; + + /* * A = ( A5 || A4 || A3 || A2 || A1 || A0 ) ; An if 64-bit * A mod p = B = T + S1 + S2 + S3 mod p @@ -58,6 +145,16 @@ int bigint_reduce_p192(bigint_t *a){ bigint_t s; uint16_t o_length; + if(a->info & BIGINT_NEG_MASK){ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); + /* negative value */ + a->info &= ~BIGINT_NEG_MASK; + bigint_reduce_p192(a); + a->info |= BIGINT_NEG_MASK; + bigint_add_s(a, a, &nist_curve_p192_p); + return 0; + } + o_length = a->length_W; if(o_length < 192 / BIGINT_WORD_SIZE){ @@ -71,13 +168,17 @@ int bigint_reduce_p192(bigint_t *a){ if(o_length > 192 / BIGINT_WORD_SIZE){ s.wordv = s_w; s.length_W = 2 * 64 / BIGINT_WORD_SIZE; + s.info = 0; + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); /* * copy A3 twice in s */ if(o_length >= 4 * 64 / BIGINT_WORD_SIZE){ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); memcpy(s.wordv, a->wordv + 3 * 64 / BIGINT_WORD_SIZE, 64 / 8); }else{ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); memset(s.wordv, 0, 8); memcpy(s.wordv, a->wordv + 3 * 64 / BIGINT_WORD_SIZE, o_length * BIGINT_WORD_SIZE / 8 - 3 * 64 / 8); @@ -89,23 +190,35 @@ int bigint_reduce_p192(bigint_t *a){ /* * Set A3 to zero so we can use a as T */ - memset(a->wordv + 3 * 64 / BIGINT_WORD_SIZE, 0, BIGINT_WORD_SIZE / 8); + memset(a->wordv + 3 * 64 / BIGINT_WORD_SIZE, 0, sizeof(bigint_word_t)); a->length_W = 3 * 64 / BIGINT_WORD_SIZE; bigint_adjust(a); /* * Add s (alias S1) to a (alias T) */ + + printf_P(PSTR("T: ")); + bigint_print_hex(a); + putchar('\n'); + + printf_P(PSTR("s1: ")); + bigint_print_hex(&s); + putchar('\n'); bigint_add_u(a, a, &s); if(o_length > 4 * 64 / BIGINT_WORD_SIZE){ + s.length_W = 2 * 64 / BIGINT_WORD_SIZE; /* * copy A4 twice in s */ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); if(o_length >= 5 * 64 / BIGINT_WORD_SIZE){ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); memcpy(s.wordv, a->wordv + 4 * 64 / BIGINT_WORD_SIZE, 64 / 8); }else{ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); memset(s.wordv, 0, 8); memcpy(s.wordv, a->wordv + 4 * 64 / BIGINT_WORD_SIZE, o_length * BIGINT_WORD_SIZE / 8 - 4 * 64 / 8); @@ -116,6 +229,9 @@ int bigint_reduce_p192(bigint_t *a){ /* * Add s (alias S2) to a (alias T + S1) */ + printf_P(PSTR("s2: ")); + bigint_print_hex(&s); + putchar('\n'); bigint_add_scale_u(a, &s, 8); @@ -123,9 +239,12 @@ int bigint_reduce_p192(bigint_t *a){ /* * copy A5 three times in s */ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); if(o_length == 6 * 64 / BIGINT_WORD_SIZE){ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); memcpy(s.wordv, a->wordv + 5 * 64 / BIGINT_WORD_SIZE, 64 / 8); } else { + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); memset(s.wordv, 0, 8); memcpy(s.wordv, a->wordv + 5 * 64 / BIGINT_WORD_SIZE, o_length * BIGINT_WORD_SIZE / 8 - 5 * 64 / 8); @@ -138,15 +257,27 @@ int bigint_reduce_p192(bigint_t *a){ /* * Add s (alias S2) to a (alias T + S1) */ + printf_P(PSTR("s3: ")); + bigint_print_hex(&s); + putchar('\n'); + bigint_add_u(a, a, &s); } } } + printf_P(PSTR("pre-result: ")); + bigint_print_hex(a); + putchar('\n'); while(bigint_cmp_u(a, &nist_curve_p192_p) >= 0){ + printf_P(PSTR("DBG: Line: %d\n"), __LINE__); bigint_sub_u(a, a, &nist_curve_p192_p); } + printf_P(PSTR("result: ")); + bigint_print_hex(a); + putchar('\n'); return 0; } + diff --git a/ecdsa/nist_p192.h b/ecdsa/nist_p192.h index 9959bd8..16a9c23 100644 --- a/ecdsa/nist_p192.h +++ b/ecdsa/nist_p192.h @@ -21,8 +21,16 @@ #define NIST_P192_H_ #include "bigint.h" +#include "ecc.h" extern bigint_t nist_curve_p192_p; + +extern bigint_t nist_curve_p192_b; + +extern ecc_combi_point_t nist_curve_p192_basepoint; + +extern ecc_curve_sp_t nist_curve_p192; + int bigint_reduce_p192(bigint_t *a); #endif /* NIST_P192_H_ */ diff --git a/mkfiles/ecdsa.mk b/mkfiles/ecdsa.mk index 4aeff73..61978f3 100644 --- a/mkfiles/ecdsa.mk +++ b/mkfiles/ecdsa.mk @@ -6,7 +6,7 @@ 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)_OBJ := bigint.o bigint_io.o sha1-asm.o nist_p192.o ecc_chudnovsky.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 diff --git a/test_src/main-ecdsa-test.c b/test_src/main-ecdsa-test.c index 2da259d..505e926 100644 --- a/test_src/main-ecdsa-test.c +++ b/test_src/main-ecdsa-test.c @@ -40,8 +40,102 @@ char* algo_name = "ECDSA"; * additional validation-functions * *****************************************************************************/ -void testrun_performance_bigint(void){ - printf_P(PSTR("\n=== performance measurement ===\n")); +void testrun_performance_invert_bigint(void){ + printf_P(PSTR("\n=== performance measurement (invert) ===\n")); + unsigned i,j; + uint64_t time = 0; + bigint_t a, v; + bigint_word_t v_w[192 / BIGINT_WORD_SIZE]; + bigint_word_t a_w[192 / BIGINT_WORD_SIZE]; + + a.wordv = a_w; + v.wordv = v_w; + + for(j = 0; j < 32; ++j){ + for(i = 0; i < 192 / BIGINT_WORD_SIZE; ++i){ + ((uint8_t*)v_w)[i] = random(); + } + v.length_W = 192 / BIGINT_WORD_SIZE; + v.info = 0; + bigint_adjust(&v); + + for(i = 0; i < 16; ++i){ + startTimer(1); + START_TIMER; + bigint_inverse(&a, &v, &nist_curve_p192_p); + STOP_TIMER; + time += stopTimer(); + } + } + + time >>= 8; + ++time; + time >>= 1; + + printf_P(PSTR(" invert costs %"PRIu32" cycles\n"), (uint32_t)time); +} + +void testrun_performance_multiply_bigint(void){ + printf_P(PSTR("\n=== performance measurement (invert) ===\n")); + unsigned i,j; + uint64_t time_a = 0, time_b = 0; + uint32_t tmp; + bigint_t a, b, v; + bigint_word_t v_w[192 * 2 / BIGINT_WORD_SIZE]; + bigint_word_t a_w[192 / BIGINT_WORD_SIZE]; + bigint_word_t b_w[192 / BIGINT_WORD_SIZE]; + + a.wordv = a_w; + b.wordv = b_w; + v.wordv = v_w; + + for(j = 0; j < 32; ++j){ + for(i = 0; i < 192 / BIGINT_WORD_SIZE; ++i){ + ((uint8_t*)a_w)[i] = random(); + } + a.length_W = 192 / BIGINT_WORD_SIZE; + a.info = 0; + bigint_adjust(&a); + + for(i = 0; i < 192 / BIGINT_WORD_SIZE; ++i){ + ((uint8_t*)b_w)[i] = random(); + } + b.length_W = 192 / BIGINT_WORD_SIZE; + b.info = 0; + bigint_adjust(&b); + + for(i = 0; i < 16; ++i){ + startTimer(1); + START_TIMER; + bigint_mul_u(&v,&a, &b); + STOP_TIMER; + tmp = stopTimer(); + time_a += tmp; + time_b += tmp; + + START_TIMER; + bigint_reduce_p192(&v); + STOP_TIMER; + tmp = stopTimer(); + time_b += tmp; + } + } + + time_a >>= 8; + ++time_a; + time_a >>= 1; + + time_b >>= 8; + ++time_b; + time_b >>= 1; + + + printf_P(PSTR(" multiply costs %7"PRIu32" cycles\n"), (uint32_t)time_a); + printf_P(PSTR(" multiply + reduce costs %7"PRIu32" cycles\n"), (uint32_t)time_b); +} + +void testrun_performance_reduce_bigint(void){ + printf_P(PSTR("\n=== performance measurement (reduce) ===\n")); unsigned i, j; bigint_t a,b,v; bigint_word_t v_w[192 * 2 / BIGINT_WORD_SIZE]; @@ -109,22 +203,339 @@ void testrun_performance_bigint(void){ } } +uint8_t ecc_affine_point_alloc(ecc_affine_point_t *p, uint16_t length_b){ + size_t len = (length_b + BIGINT_WORD_SIZE - 1)/ BIGINT_WORD_SIZE; + if (! (p->x.wordv = malloc(len))){ + return 1; + } + if (! (p->y.wordv = malloc(len))){ + free(p->x.wordv); + return 2; + } + return 0; +} + +void ecc_affine_point_free(ecc_affine_point_t *p){ + free(p->x.wordv); + free(p->y.wordv); +} + +uint8_t ecc_chudnovsky_point_alloc(ecc_chudnovsky_point_t *p, uint16_t length_b){ + size_t len = (length_b + BIGINT_WORD_SIZE - 1)/ BIGINT_WORD_SIZE; + if (! (p->x.wordv = malloc(len))){ + return 1; + } + if (! (p->y.wordv = malloc(len))){ + free(p->x.wordv); + return 2; + } + if (! (p->z1.wordv = malloc(len))){ + free(p->x.wordv); + free(p->y.wordv); + return 3; + } + if (! (p->z2.wordv = malloc(len))){ + free(p->x.wordv); + free(p->y.wordv); + free(p->z1.wordv); + return 4; + } + if (! (p->z3.wordv = malloc(len))){ + free(p->x.wordv); + free(p->y.wordv); + free(p->z1.wordv); + free(p->z2.wordv); + return 5; + } + return 0; +} + +void ecc_chudnovsky_point_free(ecc_chudnovsky_point_t *p){ + free(p->x.wordv); + free(p->y.wordv); + free(p->z1.wordv); + free(p->z2.wordv); + free(p->z3.wordv); +} + +void testrun_square(void){ + bigint_word_t a_w[] = { + 0x82, 0x6f, 0x79, 0x39, 0x47, 0x06, 0x26, 0x9f, + 0x4b, 0xe2, 0x15, 0x61, 0x6f, 0xa1, 0xd4, 0x0c, + 0x1f, 0x24, 0x3a, 0xd4, 0xc2, 0x6d, 0xe8, 0xb6 + }; + + bigint_word_t b_w[2 * 192 / BIGINT_WORD_SIZE]; + bigint_t a, b; + + a.wordv = a_w; + a.length_W = sizeof(a_w); + a.info = 7; + + b.wordv = b_w; + b.info = 0; + b.length_W = 0; + + printf_P(PSTR("\n a = ")); + bigint_print_hex(&a); + bigint_square(&b, &a); + printf_P(PSTR("\n a^2 = ")); + bigint_print_hex(&b); + bigint_reduce_p192(&b); + printf_P(PSTR("\n a^2 %% p = ")); + bigint_print_hex(&b); + putchar('\n'); + + +} + +#if 1 +/* +0: b3cfed2634516540528622e16c396c229e50bbdf773f8423 +1: b6e86dc2d43a241f0cd4a16f6115e24b9f26064739796f82 +2: 563f557e41731f268f82fe81c8fed959600dd46649ebeeee +3: 5e45169bd87475db886b8a7833bb0845f5b011a7ce0c1766 +4: 4abf34c505a73308a804dcefacbd8f7b10b59fa6ac6421a +*/ +uint8_t test_point_x_w[] = { + 0x23, 0x84, 0x3f, 0x77, 0xdf, 0xbb, 0x50, 0x9e, + 0x22, 0x6c, 0x39, 0x6c, 0xe1, 0x22, 0x86, 0x52, + 0x40, 0x65, 0x51, 0x34, 0x26, 0xed, 0xcf, 0xb3 +}; + +uint8_t test_point_y_w[] = { + 0x82, 0x6f, 0x79, 0x39, 0x47, 0x06, 0x26, 0x9f, + 0x4b, 0xe2, 0x15, 0x61, 0x6f, 0xa1, 0xd4, 0x0c, + 0x1f, 0x24, 0x3a, 0xd4, 0xc2, 0x6d, 0xe8, 0xb6 +}; + +uint8_t test_point_z1_w[] = { + 0xee, 0xee, 0xeb, 0x49, 0x66, 0xd4, 0x0d, 0x60, + 0x59, 0xd9, 0xfe, 0xc8, 0x81, 0xfe, 0x82, 0x8f, + 0x26, 0x1f, 0x73, 0x41, 0x7e, 0x55, 0x3f, 0x56 +}; + +uint8_t test_point_z2_w[] = { + 0x66, 0x17, 0x0c, 0xce, 0xa7, 0x11, 0xb0, 0xf5, + 0x45, 0x08, 0xbb, 0x33, 0x78, 0x8a, 0x6b, 0x88, + 0xdb, 0x75, 0x74, 0xd8, 0x9b, 0x16, 0x45, 0x5e +}; + +uint8_t test_point_z3_w[] = { + 0x1a, 0x42, 0xc6, 0x6a, 0xfa, 0x59, 0x0b, 0xb1, + 0xf7, 0xd8, 0xcb, 0xfa, 0xce, 0x4d, 0x80, 0x8a, + 0x30, 0x73, 0x5a, 0x50, 0x4c, 0xf3, 0xab, 0x04 +}; + +ecc_combi_point_t test_point = { + .chudnovsky = { + .x = { + .wordv = test_point_x_w, + .length_W = sizeof(test_point_x_w), + .info = 7 + }, + .y = { + .wordv = test_point_y_w, + .length_W = sizeof(test_point_y_w), + .info = 7 + }, + .z1 = { + .wordv = test_point_z1_w, + .length_W = sizeof(test_point_z1_w), + .info = 6 + }, + .z2 = { + .wordv = test_point_z2_w, + .length_W = sizeof(test_point_z2_w), + .info = 6 + }, + .z3 = { + .wordv = test_point_z3_w, + .length_W = sizeof(test_point_z3_w), + .info = 2 + } + } +}; +void testrun_genkey2(void){ + ecc_chudnovsky_point_t q; + ecc_affine_point_t qa; + + printf_P(PSTR("\n== testing key generation (2) ==\n")); + + if(ecc_chudnovsky_point_alloc(&q, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + if(ecc_affine_point_alloc(&qa, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + + ecc_chudnovsky_point_print(&test_point.chudnovsky); + ecc_chudnovsky_to_affine_point(&qa, &test_point.chudnovsky, &nist_curve_p192); + printf_P(PSTR("\n Qx: ")); + bigint_print_hex(&qa.x); + printf_P(PSTR("\n Qy: ")); + bigint_print_hex(&qa.y); + printf_P(PSTR("\n================\n")); + ecc_chudnovsky_point_double_sp(&q, &test_point.chudnovsky, &nist_curve_p192); + ecc_chudnovsky_point_print(&q); + + ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192); + + printf_P(PSTR("\n Qx: ")); + bigint_print_hex(&qa.x); + printf_P(PSTR("\n Qy: ")); + bigint_print_hex(&qa.y); + puts("\n"); + +} + +void testrun_genkey1(void){ + ecc_chudnovsky_point_t q; + ecc_affine_point_t qa; + + uint8_t k_w[] = { + // e5ce89a34adddf25ff3bf1ffe6803f57d0220de3118798ea + 0xea, 0x98, 0x87, 0x11, 0xe3, 0x0d, 0x22, 0xd0, + 0x57, 0x3f, 0x80, 0xe6, 0xff, 0xf1, 0x3b, 0xff, + 0x25, 0xdf, 0xdd, 0x4a, 0xa3, 0x89, 0xce, 0xe5 + }; + + bigint_t k = { + .length_W = sizeof(k_w), + .wordv = k_w, + .info = 7 + }; + + printf_P(PSTR("\n== testing key generation ==\n")); + + if(ecc_chudnovsky_point_alloc(&q, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + if(ecc_affine_point_alloc(&qa, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + + printf_P(PSTR(" k: ")); + bigint_print_hex(&k); + ecc_chudnovsky_multiplication(&q, &k, &nist_curve_p192_basepoint.chudnovsky, &nist_curve_p192); + ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192); + + printf_P(PSTR("\n Qx: ")); + bigint_print_hex(&qa.x); + printf_P(PSTR("\n Qy: ")); + bigint_print_hex(&qa.y); + puts("\n"); +} + +void testrun_genkey3(void){ + ecc_chudnovsky_point_t q; + ecc_affine_point_t qa; + + uint8_t k_w[] = { + 0xb2, 0x51, 0x97, 0xc3, 0x7c, 0x61, 0xf8, 0x8f, + 0x19, 0x91, 0xcc, 0x67, 0xb5, 0x1c, 0x34, 0x23, + 0xff, 0x13, 0xad, 0x14, 0x57, 0x43, 0x14, 0x7d + }; + + bigint_t k = { + .length_W = sizeof(k_w), + .wordv = k_w, + .info = 6 + }; + + printf_P(PSTR("\n== testing key generation ==\n")); + + if(ecc_chudnovsky_point_alloc(&q, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + if(ecc_affine_point_alloc(&qa, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + + printf_P(PSTR(" k: ")); + bigint_print_hex(&k); + ecc_chudnovsky_double_and_add(&q, &k, &nist_curve_p192_basepoint.chudnovsky, &nist_curve_p192); + ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192); + + printf_P(PSTR("\n Qx: ")); + bigint_print_hex(&qa.x); + printf_P(PSTR("\n Qy: ")); + bigint_print_hex(&qa.y); + puts("\n"); +} + +void testrun_genkey(void){ + ecc_chudnovsky_point_t q; + ecc_affine_point_t qa; + + bigint_t k; + + printf_P(PSTR("\n== testing key generation ==\n")); + + printf_P(PSTR("enter secret key d: ")); + bigint_read_hex_echo(&k); + putchar('\n'); + + if(ecc_chudnovsky_point_alloc(&q, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + if(ecc_affine_point_alloc(&qa, 192)){ + printf_P(PSTR("ERROR: OOM! <%s %s %d>\n"), __FILE__, __func__, __LINE__); + return; + } + + printf_P(PSTR(" k: ")); + bigint_print_hex(&k); + ecc_chudnovsky_multiplication(&q, &k, &nist_curve_p192_basepoint.chudnovsky, &nist_curve_p192); + ecc_chudnovsky_to_affine_point(&qa, &q, &nist_curve_p192); + + printf_P(PSTR("\n Qx: ")); + bigint_print_hex(&qa.x); + printf_P(PSTR("\n Qy: ")); + bigint_print_hex(&qa.y); + puts("\n"); +} + + +#endif + /***************************************************************************** * 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 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_reduce_str[] PROGMEM = "performance_reduce"; +const char performance_invert_str[] PROGMEM = "performance_invert"; +const char performance_multiply_str[] PROGMEM = "performance_multiply"; +const char genkey1_str[] PROGMEM = "genkey1"; +const char genkey2_str[] PROGMEM = "genkey2"; +const char genkey3_str[] PROGMEM = "genkey3"; +const char genkey_str[] PROGMEM = "genkey"; +const char square_str[] PROGMEM = "square"; +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 } +// { reset_prng_str, NULL, reset_prng }, +// { quick_test_str, NULL, quick_test }, + { square_str, NULL, testrun_square }, + { genkey_str, NULL, testrun_genkey }, + { genkey1_str, NULL, testrun_genkey1 }, + { genkey2_str, NULL, testrun_genkey2 }, + { genkey3_str, NULL, testrun_genkey3 }, + { performance_reduce_str, NULL, testrun_performance_reduce_bigint }, + { performance_invert_str, NULL, testrun_performance_invert_bigint }, + { performance_multiply_str, NULL, testrun_performance_multiply_bigint }, + { echo_str, (void*)1, (void_fpt)echo_ctrl }, + { NULL, NULL, NULL } }; int main (void){ -- 2.39.5