From 6c37af4a76a58f1b879d0c6df465cf01ae5f9e5d Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Wed, 14 Mar 2012 04:15:02 +0100 Subject: More renames, added secret key arithmetic --- include/libuecc/ecc.h | 28 ++++---- src/CMakeLists.txt | 2 +- src/ec25519.c | 32 ++++----- src/ec25519_secret.c | 181 ++++++++++++++++++++++++++++++++++++++++++++++++++ 4 files changed, 214 insertions(+), 29 deletions(-) create mode 100644 src/ec25519_secret.c diff --git a/include/libuecc/ecc.h b/include/libuecc/ecc.h index a5f0df7..9cf2b1e 100644 --- a/include/libuecc/ecc.h +++ b/include/libuecc/ecc.h @@ -27,27 +27,31 @@ #ifndef _LIBUECC_ECC_H_ #define _LIBUECC_ECC_H_ -typedef struct _ec_public_key_256 { +typedef struct _ecc_public_key_256 { unsigned char p[32]; -} ec_public_key_256; +} ecc_public_key_256; -typedef struct _ec_secret_key_256 { +typedef struct _ecc_secret_key_256 { unsigned char s[32]; -} ec_secret_key_256; +} ecc_secret_key_256; -typedef struct _ec_25519_work { +typedef struct _ecc_25519_work { unsigned int X[32]; unsigned int Y[32]; unsigned int Z[32]; -} ec_25519_work; +} ecc_25519_work; -void ec_25519_load(ec_25519_work *out, const ec_public_key_256 *in); -void ec_25519_store(ec_public_key_256 *out, const ec_25519_work *in); +void ecc_25519_load(ecc_25519_work *out, const ecc_public_key_256 *in); +void ecc_25519_store(ecc_public_key_256 *out, const ecc_25519_work *in); -void ec_25519_add(ec_25519_work *out, const ec_25519_work *in1, const ec_25519_work *in2); -void ec_25519_double(ec_25519_work *out, const ec_25519_work *in); -void ec_25519_scalarmult(ec_25519_work *out, const ec_secret_key_256 *n, const ec_25519_work *base); -void ec_25519_scalarmult_base(ec_25519_work *out, const ec_secret_key_256 *n); +void ecc_25519_add_secret(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2); +void ecc_25519_sub_secret(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2); +void ecc_25519_mult_secret(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2); + +void ecc_25519_add(ecc_25519_work *out, const ecc_25519_work *in1, const ecc_25519_work *in2); +void ecc_25519_double(ecc_25519_work *out, const ecc_25519_work *in); +void ecc_25519_scalarmult(ecc_25519_work *out, const ecc_secret_key_256 *n, const ecc_25519_work *base); +void ecc_25519_scalarmult_base(ecc_25519_work *out, const ecc_secret_key_256 *n); #endif /* _LIBUECC_ECC_H_ */ diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index 1bad208..edcee42 100644 --- a/src/CMakeLists.txt +++ b/src/CMakeLists.txt @@ -1,6 +1,6 @@ include_directories(${LIBUECC_SOURCE_DIR}/include) -add_library(uecc STATIC ec25519.c) +add_library(uecc STATIC ec25519.c ec25519_secret.c) install(TARGETS uecc ARCHIVE DESTINATION lib diff --git a/src/ec25519.c b/src/ec25519.c index effbfc6..7887f61 100644 --- a/src/ec25519.c +++ b/src/ec25519.c @@ -74,7 +74,7 @@ static void squeeze(unsigned int a[32]) { static const unsigned int minusp[32] = { 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128 -} ; +}; static void freeze(unsigned int a[32]) { unsigned int aorig[32]; @@ -156,13 +156,13 @@ static int check_equal(const unsigned int x[32], const unsigned int y[32]) { return (1-(1 & ((differentbits - 1) >> 16))); } -static void selectw(ec_25519_work *out, const ec_25519_work *r, const ec_25519_work *s, unsigned int b) { +static void selectw(ecc_25519_work *out, const ecc_25519_work *r, const ecc_25519_work *s, unsigned int b) { unsigned int j; unsigned int t; unsigned int bminus1; bminus1 = b - 1; - for (j = 0;j < 32;++j) { + for (j = 0; j < 32; ++j) { t = bminus1 & (r->X[j] ^ s->X[j]); out->X[j] = s->X[j] ^ t; @@ -340,7 +340,7 @@ static void recip(unsigned int out[32], const unsigned int z[32]) { /* 2^255 - 21 */ mult(out, t1, z11); } -void ec_25519_load(ec_25519_work *out, const ec_public_key_256 *in) { +void ecc_25519_load(ecc_25519_work *out, const ecc_public_key_256 *in) { int i; unsigned int X2[32], d_X2[32] = {0x04, 0x6d, 0x07} /* 486660 */, a_X2[32] = {0x08, 0x6d, 0x07} /* 486664 */, _1_a_X2[32], d_X2_a_X2[32], Y[32], Yt[32]; @@ -362,7 +362,7 @@ void ec_25519_load(ec_25519_work *out, const ec_public_key_256 *in) { select(out->Y, Y, Yt, (in->p[31] >> 7) ^ (Y[0] & 1)); } -void ec_25519_store(ec_public_key_256 *out, const ec_25519_work *in) { +void ecc_25519_store(ecc_public_key_256 *out, const ecc_25519_work *in) { unsigned int x[32], y[32], z[32]; int i; @@ -380,9 +380,9 @@ void ec_25519_store(ec_public_key_256 *out, const ec_25519_work *in) { out->p[31] |= (y[0] << 7); } -static const ec_25519_work infty = {{0}, {0}, {1}}; +static const ecc_25519_work infty = {{0}, {0}, {1}}; -void ec_25519_double(ec_25519_work *out, const ec_25519_work *in) { +void ecc_25519_double(ecc_25519_work *out, const ecc_25519_work *in) { unsigned int A[32], B[32], C[32], D[32], E[32], U[32], t0[32], t1[32], t2[32], t3[32], t4[32], t5[32]; square(A, in->X); @@ -403,7 +403,7 @@ void ec_25519_double(ec_25519_work *out, const ec_25519_work *in) { selectw(out, &infty, out, check_zero(out->X)*check_zero(out->Y)); } -void ec_25519_add(ec_25519_work *out, const ec_25519_work *in1, const ec_25519_work *in2) { +void ecc_25519_add(ecc_25519_work *out, const ecc_25519_work *in1, const ecc_25519_work *in2) { unsigned int A[32], B[32], C[32], D[32], E[32], H[32], I[32], t0[32], t1[32], t2[32], t3[32], t4[32], t5[32], t6[32], t7[32], t8[32]; mult(A, in1->Z, in2->Z); @@ -429,8 +429,8 @@ void ec_25519_add(ec_25519_work *out, const ec_25519_work *in1, const ec_25519_w selectw(out, in2, out, check_zero(t2)); } -void ec_25519_scalarmult(ec_25519_work *out, const ec_secret_key_256 *n, const ec_25519_work *base) { - ec_25519_work Q2, Q2p, cur; +void ecc_25519_scalarmult(ecc_25519_work *out, const ecc_secret_key_256 *n, const ecc_25519_work *base) { + ecc_25519_work Q2, Q2p, cur; int i, b, pos; for (i = 0; i < 32; i++) { @@ -439,12 +439,12 @@ void ec_25519_scalarmult(ec_25519_work *out, const ec_secret_key_256 *n, const e cur.Z[i] = (i == 0); } - for (pos = 254;pos >= 0;--pos) { + for (pos = 255; pos >= 0; --pos) { b = n->s[pos / 8] >> (pos & 7); b &= 1; - ec_25519_double(&Q2, &cur); - ec_25519_add(&Q2p, &Q2, base); + ecc_25519_double(&Q2, &cur); + ecc_25519_add(&Q2p, &Q2, base); selectw(&cur, &Q2, &Q2p, b); } @@ -455,7 +455,7 @@ void ec_25519_scalarmult(ec_25519_work *out, const ec_secret_key_256 *n, const e } } -static const ec_25519_work default_base = { +static const ecc_25519_work default_base = { {0x51, 0x89, 0xfa, 0x46, 0xa0, 0xc0, 0x8b, 0x3d, 0x30, 0x60, 0xf1, 0x7d, 0x2a, 0xec, 0xcd, 0xf3, 0x24, 0x50, 0x96, 0x62, 0x21, 0xfc, 0xe6, 0x18, @@ -467,6 +467,6 @@ static const ec_25519_work default_base = { {1} }; -void ec_25519_scalarmult_base(ec_25519_work *out, const ec_secret_key_256 *n) { - ec_25519_scalarmult(out, n, &default_base); +void ecc_25519_scalarmult_base(ecc_25519_work *out, const ecc_secret_key_256 *n) { + ecc_25519_scalarmult(out, n, &default_base); } diff --git a/src/ec25519_secret.c b/src/ec25519_secret.c new file mode 100644 index 0000000..0a58629 --- /dev/null +++ b/src/ec25519_secret.c @@ -0,0 +1,181 @@ +/* + Copyright (c) 2012, Matthias Schiffer + Partly based on public domain code by Matthew Dempsky and D. J. Bernstein. + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + 1. Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + 2. Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + Simple finite field operations on the prime field F_p for + p = 2^252 + 27742317777372353535851937790883648493, which + is the order of the base point used for ec25519 +*/ + +#include + + +#define IS_NEGATIVE(n) ((int)((((unsigned)n) >> (8*sizeof(n)-1))&1)) + + +static const unsigned char q[32] = { + 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, + 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, + 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10 +}; + + +static void select(unsigned char out[32], const unsigned char r[32], const unsigned char s[32], unsigned int b) { + unsigned int j; + unsigned int t; + unsigned int bminus1; + + bminus1 = b - 1; + for (j = 0;j < 32;++j) { + t = bminus1 & (r[j] ^ s[j]); + out[j] = s[j] ^ t; + } +} + +void ecc_25519_add_secret(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) { + unsigned int j; + int u1, u2, u3; + unsigned char out1[32], out2[32], out3[32]; + + u1 = u2 = u3 = 0; + for (j = 0; j < 31; ++j) { + u1 += in1->s[j] + in2->s[j]; + u2 += in1->s[j] + in2->s[j] - 8*q[j]; + u3 += in1->s[j] + in2->s[j] - 16*q[j]; + + out1[j] = u1; out2[j] = u2; out3[j] = u3; + u1 = (u1+IS_NEGATIVE(u1))/256 - IS_NEGATIVE(u1); + u2 = (u2+IS_NEGATIVE(u2))/256 - IS_NEGATIVE(u2); + u3 = (u3+IS_NEGATIVE(u3))/256 - IS_NEGATIVE(u3); + } + u1 += in1->s[31] + in2->s[31]; + u2 += in1->s[31] + in2->s[31] - 8*q[31]; + u3 += in1->s[31] + in2->s[31] - 16*q[31]; + out1[31] = u1; out2[31] = u2; out3[31] = u3; + + select(out->s, out1, out2, (u1 >> 8) & 1); + select(out->s, out->s, out3, ((u1 >> 8) & (u2 >> 8)) & 1); +} + +void ecc_25519_sub_secret(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) { + unsigned int j; + int u1, u2, u3; + unsigned char out1[32], out2[32], out3[32]; + + u1 = u2 = u3 = 0; + for (j = 0; j < 31; ++j) { + u1 += in1->s[j] - in2->s[j] + 16*q[j]; + u2 += in1->s[j] - in2->s[j] + 8*q[j]; + u3 += in1->s[j] - in2->s[j]; + + out1[j] = u1; out2[j] = u2; out3[j] = u3; + u1 = (u1+IS_NEGATIVE(u1))/256 - IS_NEGATIVE(u1); + u2 = (u2+IS_NEGATIVE(u2))/256 - IS_NEGATIVE(u2); + u3 = (u3+IS_NEGATIVE(u3))/256 - IS_NEGATIVE(u3); + } + u1 += in1->s[31] - in2->s[31] + 16*q[31]; + u2 += in1->s[31] - in2->s[31] + 8*q[31]; + u3 += in1->s[31] - in2->s[31]; + out1[31] = u1; out2[31] = u2; out3[31] = u3; + + select(out->s, out1, out2, (u1 >> 8) & 1); + select(out->s, out->s, out3, ((u1 >> 8) & (u2 >> 8)) & 1); +} + +static void reduce(unsigned char a[32]) { + unsigned int j; + int nq = a[31] >> 4; + int u1, u2; + unsigned char out1[32], out2[32]; + + u1 = u2 = 0; + for (j = 0; j < 31; ++j) { + u1 += a[j] - nq*q[j]; + u2 += a[j] - (nq-1)*q[j]; + + out1[j] = u1; out2[j] = u2; + u1 = (u1+IS_NEGATIVE(u1))/256 - IS_NEGATIVE(u1); + u2 = (u2+IS_NEGATIVE(u2))/256 - IS_NEGATIVE(u2); + } + u1 += a[31] - nq*q[31]; + u2 += a[31] - (nq-1)*q[31]; + out1[31] = u1; out2[31] = u2; + + select(a, out1, out2, IS_NEGATIVE(u1)); +} + +/* Montgomery modular multiplication algorithm */ +static void montgomery(unsigned char out[32], const unsigned char a[32], const unsigned char b[32]) { + unsigned int a_i; + unsigned int i, j; + unsigned int r0; + unsigned int u; + + for (i = 0; i < 32; i++) + out[i] = 0; + + for (i = 0; i < 256; i++) { + a_i = a[i / 8] >> (i & 7); + a_i &= 1; + + u = out[0] + a_i*b[0]; + r0 = u & 1; + u += r0 * q[0]; + + for (j = 1; j < 32; ++j) { + u += (out[j] + a_i*b[j] + r0*q[j]) << 8; + out[j-1] = (u >> 1) & 255; + u >>= 8; + } + + out[31] = u >> 1; + } +} + + +void ecc_25519_mult_secret(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) { + /* 2^512 mod p */ + static const unsigned char C[32] = { + 0x01, 0x0f, 0x9c, 0x44, 0xe3, 0x11, 0x06, 0xa4, + 0x47, 0x93, 0x85, 0x68, 0xa7, 0x1b, 0x0e, 0xd0, + 0x65, 0xbe, 0xf5, 0x17, 0xd2, 0x73, 0xec, 0xce, + 0x3d, 0x9a, 0x30, 0x7c, 0x1b, 0x41, 0x99, 0x03 + }; + + unsigned char B[32]; + unsigned char R[32]; + unsigned int i; + + for (i = 0; i < 32; i++) + B[i] = in2->s[i]; + + reduce(B); + + montgomery(R, in1->s, B); + montgomery(out->s, R, C); +} + -- cgit v1.2.3