From d737ff292fb96ea6148dd4c92744f49c93286c4c Mon Sep 17 00:00:00 2001 From: Loup Vaillant Date: Thu, 9 Feb 2017 19:52:14 +0100 Subject: [PATCH] added ed25519 --- build.sh | 4 +- ed25519.c | 391 ++++++++++++++++++++++++++++++++++++++++++++++++ ed25519.h | 20 +++ test.c | 47 +++++- vectors_ed25519 | 19 +++ 5 files changed, 472 insertions(+), 9 deletions(-) create mode 100644 ed25519.c create mode 100644 ed25519.h create mode 100644 vectors_ed25519 diff --git a/build.sh b/build.sh index 56bad3d..affbfd4 100755 --- a/build.sh +++ b/build.sh @@ -9,9 +9,9 @@ $CC $CFLAGS -c poly1305.c $CC $CFLAGS -c argon2i.c $CC $CFLAGS -c ae.c $CC $CFLAGS -c x25519.c -#$CC $CFLAGS -c ed25519.c +$CC $CFLAGS -c ed25519.c -DED25519_SHA512 $CC $CFLAGS -c lock.c $CC $CFLAGS -c sha512.c $CC $CFLAGS -c test.c -$CC $CFLAGS -o test test.o chacha20.o argon2i.o blake2b.o poly1305.o x25519.o ae.o lock.o sha512.o +$CC $CFLAGS -o test test.o chacha20.o argon2i.o blake2b.o poly1305.o x25519.o ae.o lock.o sha512.o ed25519.o diff --git a/ed25519.c b/ed25519.c new file mode 100644 index 0000000..a1baa65 --- /dev/null +++ b/ed25519.c @@ -0,0 +1,391 @@ +// Taken from TweetNaCl. +// I tried the ref10 implementation, but that was too damn big + +#include "ed25519.h" + +#define FOR(i, start, end) for (size_t i = start; i < end; i++) +#define sv static void +#define sc static const + +typedef uint8_t u8; +typedef int64_t i64; +typedef uint64_t u64; +typedef i64 gf[16]; + +sc gf gf0; +sc gf gf1 = { 1 }; +sc gf D = { 0x78a3, 0x1359, 0x4dca, 0x75eb, 0xd8ab, 0x4141, 0x0a4d, 0x0070, + 0xe898, 0x7779, 0x4079, 0x8cc7, 0xfe73, 0x2b6f, 0x6cee, 0x5203}; +sc gf D2 = { 0xf159, 0x26b2, 0x9b94, 0xebd6, 0xb156, 0x8283, 0x149a, 0x00e0, + 0xd130, 0xeef3, 0x80f2, 0x198e, 0xfce7, 0x56df, 0xd9dc, 0x2406}; +sc gf X = { 0xd51a, 0x8f25, 0x2d60, 0xc956, 0xa7b2, 0x9525, 0xc760, 0x692c, + 0xdc5c, 0xfdd6, 0xe231, 0xc0a4, 0x53fe, 0xcd6e, 0x36d3, 0x2169}; +sc gf Y = { 0x6658, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, + 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666, 0x6666}; +sc gf I = { 0xa0b0, 0x4a0e, 0x1b27, 0xc4ee, 0xe478, 0xad2f, 0x1806, 0x2f43, + 0xd7a7, 0x3dfb, 0x0099, 0x2b4d, 0xdf0b, 0x4fc1, 0x2480, 0x2b83}; + +sc u64 L[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 }; + +sv car_25519(gf o) +{ + FOR(i, 0, 16) { + o[i] += 1LL << 16; + i64 c = o[i] >> 16; + o[(i+1) * (i<15)] += c - 1 + (37 * (c-1) * (i==15)); + o[i] -= c << 16; + } +} + +sv sel_25519(gf p, gf q, int b) +{ + i64 c = ~(b-1); + FOR(i, 0, 16) { + i64 t = c & (p[i] ^ q[i]); + p[i] ^= t; + q[i] ^= t; + } +} + +sv pack_25519(u8 *o, const gf n) +{ + gf t; + FOR(i, 0, 16) t[i] = n[i]; + car_25519(t); + car_25519(t); + car_25519(t); + FOR(j, 0, 2) { + gf m; + m[0] = t[0] - 0xffed; + FOR(i, 1, 15) { + m[i ] = t[i] - 0xffff - ((m[i-1] >> 16) & 1); + m[i-1] &= 0xffff; + } + m[15] = t[15] - 0x7fff - ((m[14] >> 16) & 1); + int b = (m[15] >> 16) & 1; + m[14] &= 0xffff; + sel_25519(t, m, 1-b); + } + FOR(i, 0, 16) { + o[2*i ] = t[i] & 0xff; + o[2*i + 1] = t[i] >> 8; + } +} + +sv A(gf o, const gf a, const gf b) { FOR(i, 0, 16) o[i] = a[i] + b[i]; } +sv Z(gf o, const gf a, const gf b) { FOR(i, 0, 16) o[i] = a[i] - b[i]; } +sv M(gf o, const gf a, const gf b) +{ + i64 t[31]; + FOR(i, 0, 31) t[i] = 0; + FOR(i, 0, 16) FOR(j, 0, 16) t[i+j] += a[i] * b[j]; + FOR(i, 0, 15) t[i] += 38 * t[i+16]; + FOR(i, 0, 16) o[i] = t[i]; + car_25519(o); + car_25519(o); +} +sv S(gf o,const gf a){ M(o, a, a); } + +sv inv_25519(gf o,const gf i) +{ + gf c; + FOR(a, 0, 16) c[a] = i[a]; + for(int a = 253; a >= 0; a--) { + S(c, c); + if(a != 2 && a != 4) + M(c, c, i); + } + FOR(a, 0, 16) o[a] = c[a]; +} + +sv unpack_25519(gf o, const u8 *n) +{ + FOR(i, 0, 16) o[i] = n[2*i] + ((i64)n[2*i + 1] << 8); + o[15] &= 0x7fff; +} + +sv set_25519(gf r, const gf a) { FOR(i, 0, 16) r[i] = a[i]; } + +static u8 par_25519(const gf a) +{ + u8 d[32]; + pack_25519(d, a); + return d[0] & 1; +} + +sv pow2523(gf o,const gf i) +{ + gf c; + FOR(a, 0, 16) c[a] = i[a]; + for(int a = 250; a >= 0; a--) { + S(c, c); + if(a != 1) M(c, c, i); + } + FOR(a, 0, 16) o[a] = c[a]; +} + +static int vn(const u8 *x, const u8 *y, size_t n) +{ + uint32_t d = 0; + FOR(i, 0, n) d |= x[i] ^ y[i]; + return (1 & ((d - 1) >> 8)) - 1; +} + +static int neq_25519(const gf a, const gf b) +{ + u8 c[32],d[32]; + pack_25519(c, a); + pack_25519(d, b); + return vn(c, d, 32); +} + +sv add(gf p[4], gf q[4]) +{ + gf a, b, c, d, t, e, f, g, h; + Z(a, p[1], p[0]); + Z(t, q[1], q[0]); + M(a, a, t); + A(b, p[0], p[1]); + A(t, q[0], q[1]); + M(b, b, t); + M(c, p[3], q[3]); + M(c, c, D2); + M(d, p[2], q[2]); + A(d, d, d); + Z(e, b, a); + Z(f, d, c); + A(g, d, c); + A(h, b, a); + + M(p[0], e, f); + M(p[1], h, g); + M(p[2], g, f); + M(p[3], e, h); +} + +sv cswap(gf p[4], gf q[4], u8 b) +{ + FOR(i, 0, 4) + sel_25519(p[i],q[i],b); +} + +sv pack(u8 *r, gf p[4]) +{ + gf tx, ty, zi; + inv_25519(zi, p[2]); + M(tx, p[0], zi); + M(ty, p[1], zi); + pack_25519(r, ty); + r[31] ^= par_25519(tx) << 7; +} + +sv scalarmult(gf p[4], gf q[4], const u8 *s) +{ + set_25519(p[0], gf0); + set_25519(p[1], gf1); + set_25519(p[2], gf1); + set_25519(p[3], gf0); + for (int i = 255; i >= 0; i--) { + u8 b = (s[i/8] >> (i & 7)) & 1; + cswap(p, q, b); + add(q, p); + add(p, p); + cswap(p, q, b); + } +} + +sv scalarbase(gf p[4], const u8 *s) +{ + gf q[4]; + set_25519(q[0], X); + set_25519(q[1], Y); + set_25519(q[2], gf1); + M(q[3], X, Y); + scalarmult(p, q, s); +} + +sv modL(u8 *r, i64 x[64]) +{ + i64 i, j; + for (i = 63;i >= 32;--i) { + i64 carry = 0; + for (j = i - 32;j < i - 12;++j) { + x[j] += carry - 16 * x[i] * L[j - (i - 32)]; + carry = (x[j] + 128) >> 8; + x[j] -= carry << 8; + } + x[j] += carry; + x[i] = 0; + } + i64 carry = 0; + FOR(j, 0, 32) { + x[j] += carry - (x[31] >> 4) * L[j]; + carry = x[j] >> 8; + x[j] &= 255; + } + FOR(j, 0, 32) x[j] -= carry * L[j]; + FOR(i, 0, 32) { + x[i+1] += x[i] >> 8; + r[i ] = x[i] & 255; + } +} + +sv reduce(u8 r[64]) +{ + i64 x[64]; + FOR(i, 0, 64) x[i] = (u64) r[i]; + FOR(i, 0, 64) r[i] = 0; + modL(r, x); +} + +static int unpackneg(gf r[4],const u8 p[32]) +{ + gf t, chk, num, den, den2, den4, den6; + set_25519(r[2], gf1); + unpack_25519(r[1], p); + S(num,r [1]); + M(den, num, D); + Z(num, num, r[2]); + A(den, r[2], den); + + S(den2, den); + S(den4, den2); + M(den6, den4, den2); + M(t, den6, num); + M(t, t, den); + + pow2523(t, t); + M(t, t, num); + M(t, t, den); + M(t, t, den); + M(r[0], t, den); + + S(chk, r[0]); + M(chk, chk, den); + if (neq_25519(chk, num)) M(r[0], r[0], I); + + S(chk, r[0]); + M(chk, chk, den); + if (neq_25519(chk, num)) return -1; + + if (par_25519(r[0]) == (p[31]>>7)) Z(r[0],gf0,r[0]); + + M(r[3], r[0], r[1]); + return 0; +} + +#ifdef ED25519_BLAKE2B + #include "blake2b.h" + #define HASH crypto_blake2b +#else + #ifdef ED25519_SHA512 + #include "sha512.h" + #define HASH crypto_sha512 + #endif +#endif + +#define COMBINE1(x, y) x ## y +#define COMBINE2(x, y) COMBINE1(x, y) +#define HASH_CTX COMBINE2(HASH, _ctx) +#define HASH_INIT COMBINE2(HASH, _init) +#define HASH_UPDATE COMBINE2(HASH, _update) +#define HASH_FINAL COMBINE2(HASH, _final) + +// hash function interface +// Typical uses: sha512 for tests vectors, blake2b for production. +void HASH_INIT (HASH_CTX *ctx); +void HASH_UPDATE(HASH_CTX *ctx, const u8 *in, size_t inlen); +void HASH_FINAL (HASH_CTX *ctx, u8 hash[64]); +void HASH(u8 hash[64], const u8 *in, size_t inlen); + +sv hash_k(u8 k[64], const u8 R[32], const u8 A[32], const u8 *M, size_t M_size) +{ + HASH_CTX ctx; + HASH_INIT (&ctx); + HASH_UPDATE(&ctx, R , 32 ); + HASH_UPDATE(&ctx, A , 32 ); + HASH_UPDATE(&ctx, M , M_size); + HASH_FINAL (&ctx, k); + reduce(k); +} + +void crypto_ed25519_public_key(uint8_t public_key[32], + const uint8_t secret_key[32]) +{ + // hash the private key, turn the hash into a scalar + u8 a[64]; + HASH(a, secret_key, 32); + a[ 0] &= 248; + a[31] &= 127; + a[31] |= 64; + + // the public key is the packed form of the point aB (B == basepoint) + gf aB[4]; + scalarbase(aB, a); + pack(public_key, aB); +} + +void crypto_ed25519_sign(uint8_t signature[64], + const uint8_t secret_key[32], + const uint8_t *message, + size_t message_size) +{ + u8 h[64]; + u8 *a = h; // secret scalar + u8 *prefix = h + 32; // prefix for nonce generation + HASH(h, secret_key, 32); + + // build public key from secret key + a[ 0] &= 248; + a[31] &= 127; + a[31] |= 64; + gf aB[4]; + scalarbase(aB, a); + u8 public_key[32]; + pack(public_key, aB); + + // Constructs the "random" nonce from the secret key and message. + // An actual random number would work just fine, and would save us + // the trouble of hashing the message twice. If we did that + // however, the user could fuck it up and reuse the nonce. + u8 r[64]; + HASH_CTX ctx; + HASH_INIT (&ctx); + HASH_UPDATE(&ctx, prefix , 32 ); + HASH_UPDATE(&ctx, message, message_size); + HASH_FINAL (&ctx, r); + + gf rB[4]; + reduce(r); + scalarbase(rB, r); + pack(signature, rB); // first half of the signature = "random" nonce + + u8 k[64]; + hash_k(k, signature, public_key, message, message_size); + + i64 s[64]; // s = r + k a + FOR(i, 0, 32) s[i] = (u64) r[i]; + FOR(i, 32, 64) s[i] = 0; + FOR(i, 0, 32) { + FOR(j, 0, 32) { + s[i+j] += k[i] * (u64) a[j]; + } + } + modL(signature + 32, s); // second half of the signature = s +} + +int crypto_ed25519_check(const uint8_t signature[64], + const uint8_t public_key[32], + const uint8_t *message, + size_t message_size) +{ + gf aB[4]; if (unpackneg(aB, public_key)) return -1; // -aB + u8 k[64]; hash_k(k, signature, public_key, message, message_size); + gf p[4]; scalarmult(p, aB, k); // p = -aB k + gf sB[4]; scalarbase(sB, signature + 32); add(p, sB); // p = s - aB k + u8 t[32]; pack(t, p); + return vn(signature, t, 32); // R == s - aB k ? OK : fail +} diff --git a/ed25519.h b/ed25519.h new file mode 100644 index 0000000..f03764b --- /dev/null +++ b/ed25519.h @@ -0,0 +1,20 @@ +#ifndef ED25519_H +#define ED25519_H + +#include +#include + +void crypto_ed25519_public_key(uint8_t public_key[32], + const uint8_t secret_key[32]); + +void crypto_ed25519_sign(uint8_t signature[64], + const uint8_t secret_key[32], + const uint8_t *message, + size_t message_size); + +int crypto_ed25519_check(const uint8_t signature[64], + const uint8_t public_key[32], + const uint8_t *message, + size_t message_size); + +#endif // ED25519_H diff --git a/test.c b/test.c index 5aaecbf..ffab27c 100644 --- a/test.c +++ b/test.c @@ -291,13 +291,45 @@ static void sha512(const vector in[], vector *out) crypto_sha512(out->buffer, in->buffer, in->size); } -/* static int ed25519(const vector in[], vector *out) */ -/* { */ -/* const vector *secret = in; */ -/* const vector *public = in + 1; */ -/* const vector *message = in + 2; */ - -/* } */ +static void ed25519(const vector in[], vector *out) +{ + const vector *secret = in; + const vector *public = in + 1; + const vector *message = in + 2; + + // test that secret an public keys match + uint8_t generated_public[32]; + crypto_ed25519_public_key(generated_public, secret->buffer); + if (memcmp(generated_public, public->buffer, 32)) { + printf("FAILURE: secret/public key mismatch!\n"); + } + + // the test proper + crypto_ed25519_sign(out->buffer, + secret->buffer, + message->buffer, message->size); + + // test successful signature verification + if (crypto_ed25519_check(out->buffer, public->buffer, + message->buffer, message->size)) { + printf("FAILURE: signature check failed to recognise signature\n"); + } + // test forgery rejections + uint8_t fake_signature1[64]; + uint8_t fake_signature2[64]; + for (int i = 0; i < 64; i++) { + fake_signature1[i] = out->buffer[i]; + fake_signature2[i] = out->buffer[i]; + } + fake_signature1[ 0]++; // modify R + fake_signature2[63]++; // modify s + if (!crypto_ed25519_check(fake_signature1, public->buffer, + message->buffer, message->size) || + !crypto_ed25519_check(fake_signature2, public->buffer, + message->buffer, message->size)) { + printf("FAILURE: signature check failed to reject forgery\n"); + } +} static int test_ae() { @@ -330,6 +362,7 @@ int main(void) status |= test(x25519 , "vectors_x25519" , 2); status |= test(sha512 , "vectors_sha512" , 1); // status |= test_x25519(); // Too Long; Didn't Run + status |= test(ed25519 , "vectors_ed25519" , 3); status |= test_ae(); printf(status ? "TESTS FAILED\n" : "ALL TESTS OK\n"); return status; diff --git a/vectors_ed25519 b/vectors_ed25519 new file mode 100644 index 0000000..042ae2b --- /dev/null +++ b/vectors_ed25519 @@ -0,0 +1,19 @@ +secret: 9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60 +public: d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a +msg: +sig: e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b + +secret: 4ccd089b28ff96da9db6c346ec114e0f5b8a319f35aba624da8cf6ed4fb8a6fb +public: 3d4017c3e843895a92b70aa74d1b7ebc9c982ccf2ec4968cc0cd55f12af4660c +msg: 72 +sig: 92a009a9f0d4cab8720e820b5f642540a2b27b5416503f8fb3762223ebdb69da085ac1e43e15996e458f3613d0f11d8c387b2eaeb4302aeeb00d291612bb0c00 + +secret: c5aa8df43f9f837bedb7442f31dcb7b166d38535076f094b85ce3a2e0b4458f7 +public: fc51cd8e6218a1a38da47ed00230f0580816ed13ba3303ac5deb911548908025 +msg: af82 +sig: 6291d657deec24024827e69c3abe01a30ce548a284743a445e3680d7db5ac3ac18ff9b538d16f290ae67f760984dc6594a7c15e9716ed28dc027beceea1ec40a + +secret: f5e5767cf153319517630f226876b86c8160cc583bc013744c6bf255f5cc0ee5 +public: 278117fc144c72340f67d0f2316e8386ceffbf2b2428c9c51fef7c597f1d426e +msg: 08b8b2b733424243760fe426a4b54908632110a66c2f6591eabd3345e3e4eb98fa6e264bf09efe12ee50f8f54e9f77b1e355f6c50544e23fb1433ddf73be84d879de7c0046dc4996d9e773f4bc9efe5738829adb26c81b37c93a1b270b20329d658675fc6ea534e0810a4432826bf58c941efb65d57a338bbd2e26640f89ffbc1a858efcb8550ee3a5e1998bd177e93a7363c344fe6b199ee5d02e82d522c4feba15452f80288a821a579116ec6dad2b3b310da903401aa62100ab5d1a36553e06203b33890cc9b832f79ef80560ccb9a39ce767967ed628c6ad573cb116dbefefd75499da96bd68a8a97b928a8bbc103b6621fcde2beca1231d206be6cd9ec7aff6f6c94fcd7204ed3455c68c83f4a41da4af2b74ef5c53f1d8ac70bdcb7ed185ce81bd84359d44254d95629e9855a94a7c1958d1f8ada5d0532ed8a5aa3fb2d17ba70eb6248e594e1a2297acbbb39d502f1a8c6eb6f1ce22b3de1a1f40cc24554119a831a9aad6079cad88425de6bde1a9187ebb6092cf67bf2b13fd65f27088d78b7e883c8759d2c4f5c65adb7553878ad575f9fad878e80a0c9ba63bcbcc2732e69485bbc9c90bfbd62481d9089beccf80cfe2df16a2cf65bd92dd597b0707e0917af48bbb75fed413d238f5555a7a569d80c3414a8d0859dc65a46128bab27af87a71314f318c782b23ebfe808b82b0ce26401d2e22f04d83d1255dc51addd3b75a2b1ae0784504df543af8969be3ea7082ff7fc9888c144da2af58429ec96031dbcad3dad9af0dcbaaaf268cb8fcffead94f3c7ca495e056a9b47acdb751fb73e666c6c655ade8297297d07ad1ba5e43f1bca32301651339e22904cc8c42f58c30c04aafdb038dda0847dd988dcda6f3bfd15c4b4c4525004aa06eeff8ca61783aacec57fb3d1f92b0fe2fd1a85f6724517b65e614ad6808d6f6ee34dff7310fdc82aebfd904b01e1dc54b2927094b2db68d6f903b68401adebf5a7e08d78ff4ef5d63653a65040cf9bfd4aca7984a74d37145986780fc0b16ac451649de6188a7dbdf191f64b5fc5e2ab47b57f7f7276cd419c17a3ca8e1b939ae49e488acba6b965610b5480109c8b17b80e1b7b750dfc7598d5d5011fd2dcc5600a32ef5b52a1ecc820e308aa342721aac0943bf6686b64b2579376504ccc493d97e6aed3fb0f9cd71a43dd497f01f17c0e2cb3797aa2a2f256656168e6c496afc5fb93246f6b1116398a346f1a641f3b041e989f7914f90cc2c7fff357876e506b50d334ba77c225bc307ba537152f3f1610e4eafe595f6d9d90d11faa933a15ef1369546868a7f3a45a96768d40fd9d03412c091c6315cf4fde7cb68606937380db2eaaa707b4c4185c32eddcdd306705e4dc1ffc872eeee475a64dfac86aba41c0618983f8741c5ef68d3a101e8a3b8cac60c905c15fc910840b94c00a0b9d0 +sig: 0aab4c900501b3e24d7cdf4663326a3a87df5e4843b2cbdb67cbf6e460fec350aa5371b1508f9f4528ecea23c436d94b5e8fcd4f681e30a6ac00a9704a188a03 -- 2.47.3