## Artifact fd20167dc6f8496a07dd0970e7d341ef56598b3e:

- File wiki/ed25519.md — part of check-in [385b2a8aa4] at 2019-03-09 12:11:20 on branch trunk — Markdown edits (user: bernd size: 6944)

# 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 for the DHE, i.e. no secret dependent operation), I cloned floodberry's ed25519-donna code and added autoconf stuff for build process, so you need a

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

and to compile&install it, just run ```
./autogen.sh && make && sudo make
install
```

. To install 32 bit libaries on a 64 bit system, run `autogen.sh`

with `CC="gcc -m32"`