From bccf64ec1b9b1b139259c03907f00d97430d43c5 Mon Sep 17 00:00:00 2001 From: Matthias Schiffer Date: Fri, 7 Dec 2012 19:07:37 +0100 Subject: Reworked the API --- include/libuecc/ecc.h | 46 ++++++++---- src/CMakeLists.txt | 2 +- src/ec25519.c | 60 +++++++++++----- src/ec25519_gf.c | 188 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/ec25519_secret.c | 188 -------------------------------------------------- 5 files changed, 261 insertions(+), 223 deletions(-) create mode 100644 src/ec25519_gf.c delete mode 100644 src/ec25519_secret.c diff --git a/include/libuecc/ecc.h b/include/libuecc/ecc.h index cf584cf..b8f8bc5 100644 --- a/include/libuecc/ecc.h +++ b/include/libuecc/ecc.h @@ -27,14 +27,14 @@ #ifndef _LIBUECC_ECC_H_ #define _LIBUECC_ECC_H_ -typedef struct _ecc_public_key_256 { +typedef union _ecc_int_256 { unsigned char p[32]; -} ecc_public_key_256; -typedef struct _ecc_secret_key_256 { + /* old name */ unsigned char s[32]; -} ecc_secret_key_256; +} ecc_int_256, ecc_secret_key_256, ecc_public_key_256; +/* a point on the curve unpacked for efficient calculation */ typedef struct _ecc_25519_work { unsigned int X[32]; unsigned int Y[32]; @@ -43,20 +43,36 @@ typedef struct _ecc_25519_work { } ecc_25519_work; -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 ecc_25519_load_xy(ecc_25519_work *out, const ecc_int_256 *x, const ecc_int_256 *y); +void ecc_25519_store_xy(ecc_int_256 *x, ecc_int_256 *y, const ecc_25519_work *in); + +void ecc_25519_load_packed(ecc_25519_work *out, const ecc_int_256 *in); +void ecc_25519_store_packed(ecc_int_256 *out, const ecc_25519_work *in); int ecc_25519_is_identity(const ecc_25519_work *in); 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); - -int ecc_25519_secret_is_zero(const ecc_secret_key_256 *in); -void ecc_25519_secret_add(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2); -void ecc_25519_secret_sub(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2); -void ecc_25519_secret_reduce(ecc_secret_key_256 *out, const ecc_secret_key_256 *in); -void ecc_25519_secret_mult(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2); -void ecc_25519_secret_sanitize(ecc_secret_key_256 *out, const ecc_secret_key_256 *in); +void ecc_25519_scalarmult(ecc_25519_work *out, const ecc_int_256 *n, const ecc_25519_work *base); +void ecc_25519_scalarmult_base(ecc_25519_work *out, const ecc_int_256 *n); + +/* operations on elements of the prime field F_q for q = 2^252 + 27742317777372353535851937790883648493 */ +int ecc_25519_gf_is_zero(const ecc_int_256 *in); +void ecc_25519_gf_add(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2); +void ecc_25519_gf_sub(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2); +void ecc_25519_gf_reduce(ecc_int_256 *out, const ecc_int_256 *in); +void ecc_25519_gf_mult(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2); + +void ecc_25519_gf_sanitize_secret(ecc_int_256 *out, const ecc_int_256 *in); + +/* defines for the old names */ +#define ecc_25519_load ecc_25519_load_packed +#define ecc_25519_store ecc_25519_store_packed + +#define ecc_25519_secret_is_zero ecc_25519_gf_is_zero +#define ecc_25519_secret_add ecc_25519_gf_add +#define ecc_25519_secret_sub ecc_25519_gf_sub +#define ecc_25519_secret_reduce ecc_25519_gf_reduce +#define ecc_25519_secret_mult ecc_25519_gf_mult +#define ecc_25519_secret_sanitize ecc_25519_gf_sanitize_secret #endif /* _LIBUECC_ECC_H_ */ diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt index edcee42..318d4f8 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 ec25519_secret.c) +add_library(uecc STATIC ec25519.c ec25519_gf.c) install(TARGETS uecc ARCHIVE DESTINATION lib diff --git a/src/ec25519.c b/src/ec25519.c index bfb49a0..915bd2c 100644 --- a/src/ec25519.c +++ b/src/ec25519.c @@ -347,7 +347,40 @@ static void recip(unsigned int out[32], const unsigned int z[32]) { /* 2^255 - 21 */ mult(out, t1, z11); } -void ecc_25519_load(ecc_25519_work *out, const ecc_public_key_256 *in) { +void ecc_25519_load_xy(ecc_25519_work *out, const ecc_int_256 *x, const ecc_int_256 *y) { + int i; + + for (i = 0; i < 32; i++) { + out->X[i] = x->p[i]; + out->Y[i] = y->p[i]; + out->Z[i] = (i == 0); + } + + mult(out->T, out->X, out->Y); +} + +void ecc_25519_store_xy(ecc_int_256 *x, ecc_int_256 *y, const ecc_25519_work *in) { + unsigned int X[32], Y[32], Z[32]; + int i; + + recip(Z, in->Z); + + if (x) { + mult(X, Z, in->X); + freeze(X); + for (i = 0; i < 32; i++) + x->p[i] = X[i]; + } + + if (y) { + mult(Y, Z, in->Y); + freeze(Y); + for (i = 0; i < 32; i++) + y->p[i] = Y[i]; + } +} + +void ecc_25519_load_packed(ecc_25519_work *out, const ecc_int_256 *in) { static const unsigned int zero[32] = {0}; static const unsigned int one[32] = {1}; @@ -377,22 +410,11 @@ void ecc_25519_load(ecc_25519_work *out, const ecc_public_key_256 *in) { mult(out->T, out->X, out->Y); } -void ecc_25519_store(ecc_public_key_256 *out, const ecc_25519_work *in) { - unsigned int x[32], y[32], z[32]; - int i; - - recip(z, in->Z); - - mult(x, z, in->X); - mult(y, z, in->Y); - - freeze(x); - freeze(y); - - for (i = 0; i < 32; i++) - out->p[i] = x[i]; +void ecc_25519_store_packed(ecc_int_256 *out, const ecc_25519_work *in) { + ecc_int_256 y; - out->p[31] |= (y[0] << 7); + ecc_25519_store_xy(out, &y, in); + out->p[31] |= (y.p[0] << 7); } static const ecc_25519_work id = {{0}, {1}, {1}, {0}}; @@ -450,13 +472,13 @@ void ecc_25519_add(ecc_25519_work *out, const ecc_25519_work *in1, const ecc_255 mult(out->Z, F, G); } -void ecc_25519_scalarmult(ecc_25519_work *out, const ecc_secret_key_256 *n, const ecc_25519_work *base) { +void ecc_25519_scalarmult(ecc_25519_work *out, const ecc_int_256 *n, const ecc_25519_work *base) { ecc_25519_work Q2, Q2p; ecc_25519_work cur = id; int b, pos; for (pos = 255; pos >= 0; --pos) { - b = n->s[pos / 8] >> (pos & 7); + b = n->p[pos / 8] >> (pos & 7); b &= 1; ecc_25519_double(&Q2, &cur); @@ -483,6 +505,6 @@ static const ecc_25519_work default_base = { 0x47, 0x4b, 0x4c, 0x81, 0xa6, 0x02, 0xfd, 0x29} }; -void ecc_25519_scalarmult_base(ecc_25519_work *out, const ecc_secret_key_256 *n) { +void ecc_25519_scalarmult_base(ecc_25519_work *out, const ecc_int_256 *n) { ecc_25519_scalarmult(out, n, &default_base); } diff --git a/src/ec25519_gf.c b/src/ec25519_gf.c new file mode 100644 index 0000000..6847cb1 --- /dev/null +++ b/src/ec25519_gf.c @@ -0,0 +1,188 @@ +/* + 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_q for + q = 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)) +#define ASR(n,s) (((n) >> s)|(IS_NEGATIVE(n)*((unsigned)-1) << (8*sizeof(n)-s))) + + +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; + } +} + +int ecc_25519_gf_is_zero(const ecc_int_256 *in) { + int i; + ecc_int_256 r; + unsigned int bits; + + ecc_25519_gf_reduce(&r, in); + + for (i = 0; i < 32; i++) + bits |= r.p[i]; + + return (((bits-1)>>8) & 1); +} + +void ecc_25519_gf_add(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2) { + unsigned int j; + unsigned int u; + int nq = 1 - (in1->p[31]>>4) - (in2->p[31]>>4); + + u = 0; + for (j = 0; j < 32; ++j) { + u += in1->p[j] + in2->p[j] + nq*q[j]; + + out->p[j] = u; + u = ASR(u, 8); + } +} + +void ecc_25519_gf_sub(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2) { + unsigned int j; + unsigned int u; + int nq = 8 - (in1->p[31]>>4) + (in2->p[31]>>4); + + u = 0; + for (j = 0; j < 32; ++j) { + u += in1->p[j] - in2->p[j] + nq*q[j]; + + out->p[j] = u; + u = ASR(u, 8); + } +} + +static void reduce(unsigned char a[32]) { + unsigned int j; + unsigned int nq = a[31] >> 4; + unsigned 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 = ASR(u1, 8); + u2 = ASR(u2, 8); + } + 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)); +} + +void ecc_25519_gf_reduce(ecc_int_256 *out, const ecc_int_256 *in) { + int i; + + for (i = 0; i < 32; i++) + out->p[i] = in->p[i]; + + reduce(out->p); +} + +/* Montgomery modular multiplication algorithm */ +static void montgomery(unsigned char out[32], const unsigned char a[32], const unsigned char b[32]) { + unsigned int i, j; + unsigned int nq; + unsigned int u; + + for (i = 0; i < 32; i++) + out[i] = 0; + + for (i = 0; i < 32; i++) { + u = out[0] + a[i]*b[0]; + nq = (u*27) & 255; + u += nq*q[0]; + + for (j = 1; j < 32; ++j) { + u += (out[j] + a[i]*b[j] + nq*q[j]) << 8; + u >>= 8; + out[j-1] = u; + } + + out[31] = u >> 8; + } +} + + +void ecc_25519_gf_mult(ecc_int_256 *out, const ecc_int_256 *in1, const ecc_int_256 *in2) { + /* 2^512 mod q */ + 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->p[i]; + + reduce(B); + + montgomery(R, in1->p, B); + montgomery(out->p, R, C); +} + +void ecc_25519_gf_sanitize_secret(ecc_int_256 *out, const ecc_int_256 *in) { + int i; + + for (i = 0; i < 32; i++) + out->p[i] = in->p[i]; + + out->p[0] &= 0xf8; + out->p[31] &= 0x7f; + out->p[31] |= 0x40; +} diff --git a/src/ec25519_secret.c b/src/ec25519_secret.c deleted file mode 100644 index 7f3d987..0000000 --- a/src/ec25519_secret.c +++ /dev/null @@ -1,188 +0,0 @@ -/* - 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_q for - q = 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)) -#define ASR(n,s) (((n) >> s)|(IS_NEGATIVE(n)*((unsigned)-1) << (8*sizeof(n)-s))) - - -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; - } -} - -int ecc_25519_secret_is_zero(const ecc_secret_key_256 *in) { - int i; - ecc_secret_key_256 r; - unsigned int bits; - - ecc_25519_secret_reduce(&r, in); - - for (i = 0; i < 32; i++) - bits |= r.s[i]; - - return (((bits-1)>>8) & 1); -} - -void ecc_25519_secret_add(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) { - unsigned int j; - unsigned int u; - int nq = 1 - (in1->s[31]>>4) - (in2->s[31]>>4); - - u = 0; - for (j = 0; j < 32; ++j) { - u += in1->s[j] + in2->s[j] + nq*q[j]; - - out->s[j] = u; - u = ASR(u, 8); - } -} - -void ecc_25519_secret_sub(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) { - unsigned int j; - unsigned int u; - int nq = 8 - (in1->s[31]>>4) + (in2->s[31]>>4); - - u = 0; - for (j = 0; j < 32; ++j) { - u += in1->s[j] - in2->s[j] + nq*q[j]; - - out->s[j] = u; - u = ASR(u, 8); - } -} - -static void reduce(unsigned char a[32]) { - unsigned int j; - unsigned int nq = a[31] >> 4; - unsigned 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 = ASR(u1, 8); - u2 = ASR(u2, 8); - } - 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)); -} - -void ecc_25519_secret_reduce(ecc_secret_key_256 *out, const ecc_secret_key_256 *in) { - int i; - - for (i = 0; i < 32; i++) - out->s[i] = in->s[i]; - - reduce(out->s); -} - -/* Montgomery modular multiplication algorithm */ -static void montgomery(unsigned char out[32], const unsigned char a[32], const unsigned char b[32]) { - unsigned int i, j; - unsigned int nq; - unsigned int u; - - for (i = 0; i < 32; i++) - out[i] = 0; - - for (i = 0; i < 32; i++) { - u = out[0] + a[i]*b[0]; - nq = (u*27) & 255; - u += nq*q[0]; - - for (j = 1; j < 32; ++j) { - u += (out[j] + a[i]*b[j] + nq*q[j]) << 8; - u >>= 8; - out[j-1] = u; - } - - out[31] = u >> 8; - } -} - - -void ecc_25519_secret_mult(ecc_secret_key_256 *out, const ecc_secret_key_256 *in1, const ecc_secret_key_256 *in2) { - /* 2^512 mod q */ - 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); -} - -void ecc_25519_secret_sanitize(ecc_secret_key_256 *out, const ecc_secret_key_256 *in) { - int i; - - for (i = 0; i < 32; i++) - out->s[i] = in->s[i]; - - out->s[0] &= 0xf8; - out->s[31] &= 0x7f; - out->s[31] |= 0x40; -} -- cgit v1.2.3