ed25519 from Dan Bernstein et al

For asymmetric cryptography, I use ed25519 from Dan Bernstein et al.  This is a variant of his curve25519 system that is very useful for signatures; the curve has a different shape (Edwards form), and the algorithms are better tuned, since Edwards form has properties that simplifies tuning (it is more regular).

Elliptic Curve Cryptography is a more complicated variant of the discrete logarithm problem than RSA.  The field used here is a curve, and an addition operation is defined that is similar to an addition of points on a clock (where you turn P2 by the angle of the neutral element to P1); the difference from adding two angles in cartesian coordinates is the curve parameter d; that's all.  This operation works uniformly for neutral element, for doubling and for negative elements; the curve is symmetric to both x and y axis.  Adding two points requires several multiplications over the coordinate field, which is a modulo prime field.  This prime is 2^255-19, which gives the name of the curve.

As there is an addition, there is also a scalar multiplication (repeated addition); as the addition is a multiplication over the coordinate field, the scalar multiplication is (from the point of complexity) an exponentiation over the coordinate field.  The inverse problem thus is a generic discrete logarithm problem.  Unlike RSA, there is no designed in shortcut, RSA is also broken if you can factor a large number into two primes.  The factoring into primes is considerably simpler than it was originally expected, which means that RSA security now requires long keys, and longer keys don't result in adequately better security (3000 bits is 128 bit security, but for 256 bits security you need a 15000 bit key - that's a factor of 5).  So far, no shortcut to break ECC has been found (after 20 years!), supposed the parameters of the curve are good.

There are weak curves which have only a small number of points on them.  Fortunately, Dan Bernstein did characterize his curve, so it's known to be strong.  The number of points on the curve l is also a known prime (this number is needed to calculate the modulus for multiplying scalars), it is 2^252 + 27742317777372353535851937790883648493.

I use ed25519 for both Diffie Hellman key exchange and for signatures.  Secret keys are generated by using 256 random bits, with a few of them set to dedicated values to make it mod l.  This means you can use any random number as secret.  For notation, I write the scalar multiplication with the scalar on the left side in parens.  The public key is derived from the secret key

pk=(sk)*base

Diffie Hellman Key Exchange

For Diffie Hellman key exchange, the identity

(sk2)*pk1 = (sk1)*pk2   or

(sk1)*(sk2)*base = (sk2)*(sk1)*base

is used (actually with -pk, as the expansion used from signature generating also negates the public key).  Each side multiplies the other's public key with its own secret key; the resulting product is compressed (only x coordinate), and then used as shared secret.  Dan Bernstein uses a hash function to derive two pseudo-random values out of the secret; I don't do this for the key pair.  The main reason is "nothing up my sleeve", Dan Bernstein doesn't explain why he's doing it, so this thing can't go in.

The ed25519 curve is isomorph to the curve25519 curve, so the cryptography is just as strong.  I prefer to have only one set of primitives for signatures and key exchange, which also allows to use only one secret key for both.  Having only a 32 byte secret key e.g. allows you to write it on a piece of paper, and store it somewhere safe... far away from any electronics, on a medium that lasts for centuries.

Signatures

For signatures, I compute a hash of the message or file using Keccak.  The Keccak state is now used twice, so two copies have to be made.

First, I absorb the secret key, and diffuse the state for another round.  The first 64 bytes of the Keccak state is the pseudo-random number k:=hash(absorb(sk,state)), deterministic for message and secret key.  For ECDSA, this is suggested to be a random number; as Keccak is a PRF, this deterministic pseudo-random number is just as good.  It is guaranteed that for different messages k is different (collision left aside).  Now derive a point r on the curve:

r=(k)*base

Compress r (a point), and append (operator ||) the public key to r, to compute another hash round on the second copy of the Keccak state: z=hash(absorb(r||pk,state)).  Then compute the second parameter of the signature, (s)=(z*sk+k) (this is a scalar, i.e. mod l).  The signature consists of r, s, and takes a mere 64 bytes.

For verification, the receiver computes z again (same as above: hash the message into Keccak state, and absorb r||pk, followed by another hash round), and then computes

r⩵(s)*base - (z)*pk = (z*sk)*base + (k)*base - (z)*(sk)*base

As (z*sk)*base=(z)*(sk)*base, the remainder is (k)*base.  If this equals to the r part of the signature, the signature is valid.

Signing a message is considerably faster than verifying it, because the most expensive function for signing is the (k)*base scalar product; it's only 10% slower than generating a keypair.  This is accelerated with a precomputed table.  Verifying is about as expensive as a Diffie Hellman key exchange, because here the dominant timing is (z)*pk.  There is also some precomputation, but it takes about three times as long in total.

Ephemeral Key Exchange

For key exchange, I use my own variant of ephemeral key exchange: First, each side generates a random keypair, and exchanges the public keys.  The shared secret (sk2)*pk1=(sk1)*pk2 is now used to encrypt and exchange the constant public keys of both sides, hiding important metadata from evesdroppers.  Another shared secret (skb)*pka=(ska)*pkb is generated, and concatenated to the first shared secret; this plus a random and unique initialization vector is the starting point to generate per-block keys.  The advantage over a signature as used in standard ECDHE is both time (no signing needed, and verification is slightly more expensive than key exchange), and data transmitted - only the public key needs to go to the other side.

Repository

To implement the necessary changes (add scalar multiplication with "constant" execution time, i.e. no secret dependent operation), I cloned floodberry's ed25519-donna code, so you need a

git clone https://github.com/forthy42/ed25519-donna.git -b bernd

and to compile&install it, just run ./ed25519-lib (will ssh into root to install).  To install 32 bit libaries on a 64 bit system, run

env BITS="" ./ed25519-libs -m32