From e4aab13413d6fb73ae1f271a50f0ddd5696a7fbe Mon Sep 17 00:00:00 2001 From: cathugger Date: Mon, 2 Oct 2017 14:11:23 +0000 Subject: [PATCH] ed25519-donna implementation --- Makefile.in | 28 +++++++++++-- configure.ac | 45 +++++++++++++++++---- ed25519/ed25519-donna | 1 + ed25519/ed25519.h | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++ main.c | 3 +- 5 files changed, 171 insertions(+), 12 deletions(-) create mode 160000 ed25519/ed25519-donna diff --git a/Makefile.in b/Makefile.in index 306ab21..c072aa6 100644 --- a/Makefile.in +++ b/Makefile.in @@ -6,6 +6,7 @@ ASFLAGS= LDFLAGS= -no-pie MV= mv +ED25519_DEFS= -DED25519_ref10 -DED25519_amd64_51_30k -DED25519_amd64_64_24k -DED25519_donna ED25519_ref10= $(patsubst %.c,%.c.o,$(wildcard ed25519/ref10/*.c)) ED25519_amd64_51_30k= \ $(patsubst %.c,%.c.o,$(wildcard ed25519/amd64-51-30k/*.c)) \ @@ -13,6 +14,7 @@ ED25519_amd64_51_30k= \ ED25519_amd64_64_24k= \ $(patsubst %.c,%.c.o,$(wildcard ed25519/amd64-64-24k/*.c)) \ $(patsubst %.s,%.s.o,$(wildcard ed25519/amd64-64-24k/*.s)) +ED25519_donna= ED25519OBJ= $(ED25519_@ED25519IMPL@) MAINOBJ= \ @@ -81,7 +83,7 @@ clean: $(RM) $(EXE) depend: - makedepend -Y -fMakefile.in -o.c.o -- $(CSTD) -DED25519_ref10 -DED25519_amd64_51_30k -DED25519_amd64_64_24k -- $(ALLC) + makedepend -Y -fMakefile.in -o.c.o -- $(CSTD) $(ED25519_DEFS) -- $(ALLC) # DO NOT DELETE THIS LINE @@ -349,12 +351,22 @@ ed25519/ref10/sign.c.o: ed25519/amd64-51-30k/crypto_hash_sha512.h ed25519/ref10/sign.c.o: ed25519/ref10/ge.h ed25519/ref10/fe.h ed25519/ref10/sign.c.o: ed25519/ref10/crypto_int32.h ed25519/ref10/sc.h keccak.c.o: types.h keccak.h -main.c.o: types.h likely.h vec.h base32.h ed25519/ed25519.h +main.c.o: types.h likely.h vec.h base32.h keccak.h ed25519/ed25519.h main.c.o: ed25519/ref10/ed25519.h ed25519/ref10/ge.h ed25519/ref10/fe.h main.c.o: ed25519/ref10/crypto_int32.h ed25519/amd64-51-30k/ed25519.h main.c.o: ed25519/amd64-51-30k/ge25519.h ed25519/amd64-51-30k/fe25519.h main.c.o: ed25519/amd64-51-30k/sc25519.h ed25519/amd64-64-24k/ed25519.h -main.c.o: ed25519/amd64-64-24k/ge25519.h keccak.h +main.c.o: ed25519/amd64-64-24k/ge25519.h +main.c.o: ed25519/ed25519-donna/ed25519-donna.h +main.c.o: ed25519/ed25519-donna/ed25519-donna-portable.h +main.c.o: ed25519/ed25519-donna/ed25519-donna-portable-identify.h +main.c.o: ed25519/ed25519-donna/curve25519-donna-64bit.h +main.c.o: ed25519/ed25519-donna/curve25519-donna-helpers.h +main.c.o: ed25519/ed25519-donna/modm-donna-64bit.h +main.c.o: ed25519/ed25519-donna/ed25519-donna-basepoint-table.h +main.c.o: ed25519/ed25519-donna/ed25519-donna-64bit-tables.h +main.c.o: ed25519/ed25519-donna/ed25519-donna-64bit-x86.h +main.c.o: ed25519/ed25519-donna/ed25519-donna-impl-base.h test_base16.c.o: types.h base16.h test_base32.c.o: types.h base32.h test_ed25519.c.o: types.h base16.h ed25519/ed25519.h ed25519/ref10/ed25519.h @@ -365,3 +377,13 @@ test_ed25519.c.o: ed25519/amd64-51-30k/fe25519.h test_ed25519.c.o: ed25519/amd64-51-30k/sc25519.h test_ed25519.c.o: ed25519/amd64-64-24k/ed25519.h test_ed25519.c.o: ed25519/amd64-64-24k/ge25519.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna-portable.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna-portable-identify.h +test_ed25519.c.o: ed25519/ed25519-donna/curve25519-donna-64bit.h +test_ed25519.c.o: ed25519/ed25519-donna/curve25519-donna-helpers.h +test_ed25519.c.o: ed25519/ed25519-donna/modm-donna-64bit.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna-basepoint-table.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna-64bit-tables.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna-64bit-x86.h +test_ed25519.c.o: ed25519/ed25519-donna/ed25519-donna-impl-base.h diff --git a/configure.ac b/configure.ac index aa5ec7b..9f2cb3e 100644 --- a/configure.ac +++ b/configure.ac @@ -5,10 +5,12 @@ AC_CONFIG_SRCDIR([main.c]) : ${CFLAGS="-O3 -march=native -fomit-frame-pointer"} AC_PROG_CC +MYDEFS="" + ed25519impl="" AC_ARG_ENABLE([ref10], [AS_HELP_STRING([--enable-ref10], - [use ref10 ed25519 implementation @<:@default=yes@:>@])], + [use SUPERCOP ref10 ed25519 implementation @<:@default=yes@:>@])], [ AS_IF([test "x$ed25519impl" != "x" -a "$ed25519impl" != "ref10"], [AC_ERROR([only one ed25519 implementation can be defined])]) @@ -17,9 +19,9 @@ AC_ARG_ENABLE([ref10], [] ) -AC_ARG_ENABLE([amd64_51_30k], - [AS_HELP_STRING([--enable-amd64_51_30k], - [use amd64_51_30k ed25519 implementation @<:@default=no@:>@])], +AC_ARG_ENABLE([amd64-51-30k], + [AS_HELP_STRING([--enable-amd64-51-30k], + [use SUPERCOP amd64-51-30k ed25519 implementation @<:@default=no@:>@])], [ AS_IF([test "x$ed25519impl" != "x" -a "$ed25519impl" != "amd64_51_30k"], [AC_ERROR([only one ed25519 implementation can be defined])]) @@ -28,9 +30,9 @@ AC_ARG_ENABLE([amd64_51_30k], [] ) -AC_ARG_ENABLE([amd64_64_24k], - [AS_HELP_STRING([--enable-amd64_64_24k], - [use amd64_64_24k ed25519 implementation @<:@default=no@:>@])], +AC_ARG_ENABLE([amd64-64-24k], + [AS_HELP_STRING([--enable-amd64-64-24k], + [use SUPERCOP amd64-64-24k ed25519 implementation @<:@default=no@:>@])], [ AS_IF([test "x$ed25519impl" != "x" -a "$ed25519impl" != "amd64_64_24k"], [AC_ERROR([only one ed25519 implementation can be defined])]) @@ -39,9 +41,36 @@ AC_ARG_ENABLE([amd64_64_24k], [] ) +AC_ARG_ENABLE([donna], + [AS_HELP_STRING([--enable-donna], + [use ed25519-donna implementation @<:@default=no@:>@])], + [ + AS_IF([test "x$ed25519impl" != "x" -a "$ed25519impl" != "donna"], + [AC_ERROR([only one ed25519 implementation can be defined])]) + ed25519impl="donna" + ], + [] +) + +AC_ARG_ENABLE([donna-sse2], + [AS_HELP_STRING([--enable-donna-sse2], + [use ed25519-donna SSE2 implementation @<:@default=no@:>@])], + [ + AS_IF([test "x$ed25519impl" != "x" -a "$ed25519impl" != "donna-sse2"], + [AC_ERROR([only one ed25519 implementation can be defined])]) + ed25519impl="donna-sse2" + ], + [] +) + AS_IF([test "x$ed25519impl" == "x"],[ed25519impl=ref10]) -MYDEFS="" +if test "$ed25519impl" = "donna-sse2" +then + ed25519impl="donna" + MYDEFS="$MYDEFS -DED25519_SSE2" + CFLAGS="$CFLAGS -msse2" +fi AC_ARG_ENABLE([intfilter], [AS_HELP_STRING([--enable-intfilter], diff --git a/ed25519/ed25519-donna b/ed25519/ed25519-donna new file mode 160000 index 0000000..8757bd4 --- /dev/null +++ b/ed25519/ed25519-donna @@ -0,0 +1 @@ +Subproject commit 8757bd4cd209cb032853ece0ce413f122eef212c diff --git a/ed25519/ed25519.h b/ed25519/ed25519.h index 56bac15..22fb0fa 100644 --- a/ed25519/ed25519.h +++ b/ed25519/ed25519.h @@ -33,6 +33,7 @@ static const ge_cached ge_eightpoint = { 11267669, -24569594, 14624995 } }; +inline static void ge_initeightpoint() {} #endif #ifdef ED25519_amd64_51_30k @@ -68,6 +69,7 @@ static const ge25519_pniels ge_eightpoint = { // t2d {{ 1700965895112270, 372560131616985, 329575203620664, 756160485635107, 981466775886086 }}, }; +inline static void ge_initeightpoint() {} #endif #ifdef ED25519_amd64_64_24k @@ -103,4 +105,108 @@ static const ge25519_pniels ge_eightpoint = { // t2d {{ 9713713562319586894U, 4328467261753610859U, 8262494979546083277U, 4020087914029409631U }}, }; +inline static void ge_initeightpoint() {} +#endif + +#ifdef ED25519_donna +#define ED25519_CUSTOMRANDOM +#define ED25519_CUSTOMHASH +#include +#include "ed25519-donna/ed25519-donna.h" + +static int ed25519_seckey_expand(unsigned char *sk,const unsigned char *seed) +{ + crypto_hash_sha512(sk,seed,32); + sk[0] &= 248; + sk[31] &= 127; + sk[31] |= 64; + + return 0; +} + +static int ed25519_seckey(unsigned char *sk) +{ + unsigned char seed[32]; + + randombytes(seed,32); + return ed25519_seckey_expand(sk,seed); +} + +static int ed25519_pubkey(unsigned char *pk,const unsigned char *sk) +{ + bignum256modm a; + ge25519 ALIGN(16) A; + + expand256_modm(a,sk,32); + ge25519_scalarmult_base_niels(&A,ge25519_niels_base_multiples,a); + ge25519_pack(pk,&A); + + return 0; +} + + +static int ed25519_keypair(unsigned char *pk,unsigned char *sk) +{ + ed25519_seckey(sk); + ed25519_pubkey(pk,sk); + + return 0; +} +// hacky, but works for current stuff in main.c +#define ge_p1p1 ge25519_p1p1 ALIGN(16) +#define ge_p3 ge25519 ALIGN(16) +#define ge_cached ge25519_pniels ALIGN(16) + +#define ge_p1p1_to_p3 ge25519_p1p1_to_full +#define ge_p3_tobytes ge25519_pack + +DONNA_INLINE static void ge_add(ge25519_p1p1 *r,const ge25519 *p,const ge25519_pniels *q) +{ + ge25519_pnielsadd_p1p1(r,p,q,0); +} + +DONNA_INLINE static void ge_scalarmult_base(ge25519 *A,const unsigned char *sk) +{ + bignum256modm ALIGN(16) a; + expand256_modm(a,sk,32); + ge25519_scalarmult_base_niels(A,ge25519_niels_base_multiples,a); +} + +static ge25519_pniels ALIGN(16) ge_eightpoint; +// portable representation of (basepoint * 8) +static u8 fe_ysubx[32] = { + 0xE0,0xC3,0x64,0xC7,0xDC,0xAD,0x36,0x5E, + 0x25,0xAA,0x86,0xC8,0xC7,0x85,0x5F,0x07, + 0x67,0x65,0x1C,0x3D,0x99,0xDD,0x26,0x55, + 0x9C,0xB5,0x71,0x1E,0x1D,0xC4,0xC8,0x71, +}; +static u8 fe_xaddy[32] = { + 0x9C,0xFD,0xE3,0xC2,0x2A,0x15,0x34,0x1B, + 0x3B,0xE7,0x62,0xAB,0x56,0xFA,0xDF,0xE7, + 0xCF,0xBE,0xB5,0x8D,0x83,0x8A,0x1D,0xA5, + 0xAD,0x3E,0x42,0x42,0xC9,0x4F,0x1B,0x09, +}; +static u8 fe_z[32] = { + 0x77,0xAA,0x7F,0x85,0x02,0x8E,0xF5,0xD9, + 0x52,0xFE,0x8F,0xE6,0x8A,0x52,0x21,0x4A, + 0xCB,0x8D,0x1C,0x05,0x7D,0xAD,0x4A,0x1B, + 0xC6,0x7B,0x23,0x9D,0x4C,0x3F,0xD6,0x02, +}; +static u8 fe_t2d[32] = { + 0x4E,0x06,0xF4,0xFB,0x04,0x0B,0xCE,0x86, + 0x6B,0x52,0xBB,0x96,0x0A,0xCE,0x11,0x3C, + 0xCD,0xEF,0x4A,0x46,0x68,0x47,0xAA,0x72, + 0x5F,0x65,0x90,0x91,0xA8,0x38,0xCA,0x37, +}; + +// initialize from packed representation +static void ge_initeightpoint() +{ + memset(&ge_eightpoint,0,sizeof(ge_eightpoint)); + curve25519_expand(ge_eightpoint.ysubx,fe_ysubx); + curve25519_expand(ge_eightpoint.xaddy,fe_xaddy); + curve25519_expand(ge_eightpoint.z,fe_z); + curve25519_expand(ge_eightpoint.t2d,fe_t2d); +} + #endif diff --git a/main.c b/main.c index 3af6df4..95d444e 100644 --- a/main.c +++ b/main.c @@ -13,8 +13,8 @@ #include "likely.h" #include "vec.h" #include "base32.h" -#include "ed25519/ed25519.h" #include "keccak.h" +#include "ed25519/ed25519.h" // additional leading zero is added by C static const char * const pkprefix = "== ed25519v1-public: type0 ==\0\0"; @@ -553,6 +553,7 @@ int main(int argc,char **argv) #endif int tret; + ge_initeightpoint(); filters_init(); fout = stdout; -- 2.11.4.GIT