Implementations of a fast Elliptic-curve Digital Signature Algorithm
C++ C PHP
Latest commit 8757bd4 Mar 16, 2015 @floodyberry Merge pull request #23 from TomMD/master
Fix #22 - make CPP use CUSTOMRANDOM as in README
Permalink
Failed to load latest commit information.
fuzz fuzzer needs to use the reference rng if no openssl (inconsequential … Nov 7, 2013
README.md README.md: Fix "verification" typo Nov 3, 2014
curve25519-donna-32bit.h need double {} on initializer Nov 7, 2013
curve25519-donna-64bit.h convert to packed 24k table for basepoint mults Nov 1, 2013
curve25519-donna-helpers.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
curve25519-donna-sse2.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-32bit-sse2.h optimized sse2 ge25519_scalarmult_base_choose_niels Nov 2, 2013
ed25519-donna-32bit-tables.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-64bit-sse2.h optimized sse2 ge25519_scalarmult_base_choose_niels Nov 2, 2013
ed25519-donna-64bit-tables.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-64bit-x86-32bit.h add ED25519_FORCE_32BIT (useless, just for comparing), which has the … Nov 7, 2013
ed25519-donna-64bit-x86.h full clobber list Nov 4, 2013
ed25519-donna-basepoint-table.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-batchverify.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-impl-base.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-impl-sse2.h use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519-donna-portable-identify.h slightly better uint128_t detection Oct 22, 2013
ed25519-donna-portable.h always embarrassing leaving debug comments in Nov 9, 2013
ed25519-donna.h add ED25519_FORCE_32BIT (useless, just for comparing), which has the … Nov 7, 2013
ed25519-hash-custom.h add a default sha512 impl and the option to use a custom hash function May 16, 2013
ed25519-hash.h add a default sha512 impl and the option to use a custom hash function May 16, 2013
ed25519-randombytes-custom.h use OpenSSL's RAND_bytes as the default rng ed25519_randombytes_unsafe Oct 26, 2013
ed25519-randombytes.h Fix #22 - make CPP use CUSTOMRANDOM as in README Mar 16, 2015
ed25519.c use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
ed25519.h Fix a C++-related syntax error in ed25519.h May 23, 2014
modm-donna-32bit.h 32 bit has enough limbs that branching pays off in the lt/lte check Oct 24, 2013
modm-donna-64bit.h update to exactly match supercop batch verify implementations Oct 24, 2013
regression.h check-in Mar 2, 2012
test-internals.c use ALIGN(x) instead of MM16 for variable alignment Nov 8, 2013
test-ticks.h split ticks off in to test-ticks.h Aug 30, 2012
test.c merge test-batch.c in to test.c Oct 26, 2013

README.md

ed25519 is an Elliptic Curve Digital Signature Algortithm, developed by Dan Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang.

This project provides performant, portable 32-bit & 64-bit implementations. All implementations are of course constant time in regard to secret data.

Performance

SSE2 code and benches have not been updated yet. I will do those next.

Compilers versions are gcc 4.6.3, icc 13.1.1, clang 3.4-1~exp1.

Batch verification time (in parentheses) is the average time per 1 verification in a batch of 64 signatures. Counts are in thousands of cycles.

Note that SSE2 performance may be less impressive on AMD & older CPUs with slower SSE ops!

Visual Studio performance for ge25519_scalarmult_base_niels will lag behind a bit until optimized assembler versions of ge25519_scalarmult_base_choose_niels are made.

E5200 @ 2.5ghz, march=core2
ImplementationSigngcciccclangVerifygcciccclang
ed25519-donna 64bit 100k110k137k327k (144k) 342k (163k) 422k (194k)
amd64-64-24k 102k 355k (158k)
ed25519-donna-sse2 64bit108k111k116k353k (155k) 345k (154k) 360k (161k)
amd64-51-32k 116k 380k (175k)
ed25519-donna-sse2 32bit147k147k156k380k (178k) 381k (173k) 430k (192k)
ed25519-donna 32bit 597k335k380k1693k (720k)1052k (453k)1141k (493k)
E3-1270 @ 3.4ghz, march=corei7-avx
ImplementationSigngcciccclangVerifygcciccclang
amd64-64-24k 68k 225k (104k)
ed25519-donna 64bit 71k 75k 90k226k (105k) 226k (112k) 277k (125k)
amd64-51-32k 72k 218k (107k)
ed25519-donna-sse2 64bit 79k 82k 92k252k (122k) 259k (124k) 282k (131k)
ed25519-donna-sse2 32bit 94k 95k103k296k (146k) 294k (137k) 306k (147k)
ed25519-donna 32bit 525k299k316k1502k (645k)959k (418k) 954k (416k)

Compilation

No configuration is needed if you are compiling against OpenSSL.

Hash Options

If you are not compiling aginst OpenSSL, you will need a hash function.

To use a simple/slow implementation of SHA-512, use -DED25519_REFHASH when compiling ed25519.c. This should never be used except to verify the code works when OpenSSL is not available.

To use a custom hash function, use -DED25519_CUSTOMHASH when compiling ed25519.c and put your custom hash implementation in ed25519-hash-custom.h. The hash must have a 512bit digest and implement

struct ed25519_hash_context;

void ed25519_hash_init(ed25519_hash_context *ctx);
void ed25519_hash_update(ed25519_hash_context *ctx, const uint8_t *in, size_t inlen);
void ed25519_hash_final(ed25519_hash_context *ctx, uint8_t *hash);
void ed25519_hash(uint8_t *hash, const uint8_t *in, size_t inlen);
Random Options

If you are not compiling aginst OpenSSL, you will need a random function for batch verification.

To use a custom random function, use -DED25519_CUSTOMRANDOM when compiling ed25519.c and put your custom hash implementation in ed25519-randombytes-custom.h. The random function must implement:

void ED25519_FN(ed25519_randombytes_unsafe) (void *p, size_t len);

Use -DED25519_TEST when compiling ed25519.c to use a deterministically seeded, non-thread safe CSPRNG variant of Bob Jenkins ISAAC

Minor options

Use -DED25519_INLINE_ASM to disable the use of custom assembler routines and instead rely on portable C.

Use -DED25519_FORCE_32BIT to force the use of 32 bit routines even when compiling for 64 bit.

32-bit
gcc ed25519.c -m32 -O3 -c
64-bit
gcc ed25519.c -m64 -O3 -c
SSE2
gcc ed25519.c -m32 -O3 -c -DED25519_SSE2 -msse2
gcc ed25519.c -m64 -O3 -c -DED25519_SSE2

clang and icc are also supported

Usage

To use the code, link against ed25519.o -mbits and:

#include "ed25519.h"

Add -lssl -lcrypto when using OpenSSL (Some systems don't need -lcrypto? It might be trial and error).

To generate a private key, simply generate 32 bytes from a secure cryptographic source:

ed25519_secret_key sk;
randombytes(sk, sizeof(ed25519_secret_key));

To generate a public key:

ed25519_public_key pk;
ed25519_publickey(sk, pk);

To sign a message:

ed25519_signature sig;
ed25519_sign(message, message_len, sk, pk, signature);

To verify a signature:

int valid = ed25519_sign_open(message, message_len, pk, signature) == 0;

To batch verify signatures:

const unsigned char *mp[num] = {message1, message2..}
size_t ml[num] = {message_len1, message_len2..}
const unsigned char *pkp[num] = {pk1, pk2..}
const unsigned char *sigp[num] = {signature1, signature2..}
int valid[num]

/* valid[i] will be set to 1 if the individual signature was valid, 0 otherwise */
int all_valid = ed25519_sign_open_batch(mp, ml, pkp, sigp, num, valid) == 0;

Note: Batch verification uses ed25519_randombytes_unsafe, implemented in ed25519-randombytes.h, to generate random scalars for the verification code. The default implementation now uses OpenSSLs RAND_bytes.

Unlike the SUPERCOP version, signatures are not appended to messages, and there is no need for padding in front of messages. Additionally, the secret key does not contain a copy of the public key, so it is 32 bytes instead of 64 bytes, and the public key must be provided to the signing function.

Curve25519

Curve25519 public keys can be generated thanks to Adam Langley leveraging Ed25519's precomputed basepoint scalar multiplication.

curved25519_key sk, pk;
randombytes(sk, sizeof(curved25519_key));
curved25519_scalarmult_basepoint(pk, sk);

Note the name is curved25519, a combination of curve and ed25519, to prevent name clashes. Performance is slightly faster than short message ed25519 signing due to both using the same code for the scalar multiply.

Testing

Fuzzing against reference implemenations is now available. See fuzz/README.

Building ed25519.c with -DED25519_TEST and linking with test.c will run basic sanity tests and benchmark each function. test-batch.c has been incorporated in to test.c.

test-internals.c is standalone and built the same way as ed25519.c. It tests the math primitives with extreme values to ensure they function correctly. SSE2 is now supported.

Papers

Available on the Ed25519 website