Curve25519, EdDSA, and Poly1305: Three Attempted Crypto Primitives

There is such a very good friend by the name of Daniel Julius Bernstein . Mathematician, programmer and computer security specialist. His hash CubeHash almost reached the third round of SHA-3, and the stream cipher Salsa20 hit the shortlist of the eStream project. He is also the author of the cult NaCl crypto library in narrow circles , about three of which I would like to briefly tell you.

Curve25519

This is an elliptical curve and a set of parameters for it selected in such a way as to provide higher performance (on average, 20-25%) and get rid of some security problems with traditional ECDH.

The curve is used y ² = x ³ + 486662x ² + x. This is the Montgomery curve over the residue field modulo a prime number 2 ²⁵⁵ - 19 (which gave the name to the scheme) and with a base point x = 9. The scheme uses points in a compressed form (only X coordinates), thus allowing the use of the " Montgomery Ladder ", which does the multiplication of points in a fixed time, saving us from Timing attacks.

Curve25519 is used as the default key exchange in OpenSSH, I2p, Tor, Tox and even in IOS.

Why is this circuit so good from the point of view of the programmer?

She is very simple and fast. To generate a new key pair, we send to the input circuit any 32 random bytes that will be the private key. From them we get 32 ​​bytes of the public key. Then, as usual, we exchange public keys and consider the common one. How much faster than the classic ECDH with 256-bit curves I can’t say, depends on the implementation. I like it for its resistance to timing attacks and for the ability to use any 32-byte arrays as private keys.

Eddsa

More precisely, her special case, Ed25519, as you might guess, is also an accelerated and enhanced version of the digital signature on elliptic curves. Schnorr's scheme is used for Edwards' Twisted Curve , invented, by the way, by the same Daniel Bernstein in 2007.

This curve is used here:


which is equivalent to the curve for Curve25519

EdDSA is used, for example, in the OpenBSD signify tool to sign images.

And so, Curve25519 and Ed25519 are primitives on elliptic curves, optimized for speed and written in such a way as to minimize or completely eliminate the influence of input data on the process of calculating keys / signatures.

Poly1305

This is a MAC (Message authentication code) that works in conjunction with AES or any other cipher of your choice. It counts a 16 byte (128 bit) MAC using a 256 bit AES key, which is split into two 128 bits (k, r) and salt (nonce).
It breaks the message into blocks of 16 bytes and works with them as polynomial coefficients in r modulo a prime number 2 ¹³⁰ −5

The result is 4 bytes less than the usual HMAC-SHA1, has no security problems and is faster.

That is why it is used by Google instead of RC4 together with the ChaCha20 stream cipher , and it is also included in OpenSSH, which now does not need to depend on OpenSSL. The

reference implementation of all this in the NaCl library in C, but there are ports in java and c #, eg.

I hope that after this article you will have a desire to learn more about these primitives and use them in your applications.