Curve25519, EdDSA, and Poly1305: Three cryptoprimitives neglected

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

Curve25519

This is an elliptic curve and a set of parameters for it selected in such a way as to provide a higher response speed (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 of 2 ²⁵⁵ - 19 (which gave the name to the scheme) and with a base point x = 9. The scheme uses compressed points (only X coordinates), thus allowing you to use Montgomery's Ladder , which multiplies the 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 scheme so good from a programmer's point of view?



It is very simple and fast. To generate a new key pair, we feed to the scheme any 32 random bytes, which 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 exactly it is 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, its special case, Ed25519, as you can guess, is also a fast and reinforced version of the digital signature on elliptic curves. The Schnorr scheme is used for Edwards's “Twisted Curve” , invented, by the way, by the same Daniel Bernstein in 2007.



Such a curve is used:





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 you want. It counts a 16-byte (128-bit) MAC using a 256-bit AES key, which is split into two of 128 bits (k, r) and a salt (nonce).

It breaks the message into blocks of 16 bytes each and works with them as with the coefficients of a polynomial in r modulo a prime number 2 ¹³⁰ −5



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



That is why it, along with the ChaCha20 stream cipher, uses Google instead of RC4, as well as it is included in OpenSSH, which now does not need to depend on OpenSSL



The reference implementation of all this is in the NaCl library on C, but there are ports on java and c # , for example.



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