Curve25519, EdDSA и Poly1305: Три обделенных вниманием криптопримитива

041f90078a664603baadb9158e55a60c.jpgЕсть такой очень хороший товарищ по имени Daniel Julius Bernstein. Математик, программист и спец по компьютерной безопасности. Его хэш CubeHash чуть не дотянул до третьего раунда SHA-3, а потоковый шифр Salsa20 попал в шорт лист проекта eStream. А еще он автор культовой в узких кругах криптобиблиотеки NaCl, о трех штуках из которой я бы хотел вкратце рассказать.Curve25519Это эллиптическая кривая и набор параметров к ней подобранных таким образом, чтобы обеспечить более высокое быстродействие и избавиться от некоторых проблем с безопасностью у традиционного ECDH.Кривая используется y2 = x3 + 486662×2 + x. Это — кривая Монтгомери над полем вычетов по модулю простого числа 2255 − 19 (что и дало название схеме) и с базовой точкой x=9. Схема использует точки в сжатой форме (только X координаты), позволяя таким образом использовать «Лестницу Монтгомери», которая делает умножение точек за фиксированное время, избавляя нас от Timing attacks.

Curve25519 используется как обмен ключами по умолчанию в OpenSSH, I2p, Tor, Tox и даже в IOS.

Чем эта схема так хороша с точки зрения программиста?

Она очень простая и быстрая. Чтобы сгенерировать новую ключевую пару, мы подаем на вход схеме 32 случайных байта, из которых получаем 32 байта закрытого ключа и 32 байта открытого. Затем как обычно, обмениваемся открытыми ключами и считаем общий ключ. Насколько именно она быстрее классического ECDH с 256 битными кривыми сказать не возьмусь, зависит от реализации. Мне она нравится за устойчивость к timing attacks.

EdDSA Точнее, ее частный случай, Ed25519, как можно догадаться, тоже убыстренный и усиленный вариант цифровой подписи на эллиптических кривых. Используется схема Шнорра для «Закрученной кривой» Эдвардса, изобретенной, кстати, тем же Даниэлем Бернштайном в 2007 году.Испольуется такая вот кривая:

72d549638a404176a0043c7ca0b94d54.pngкоторая эквивалентна кривой для Curve25519

EdDSA используется, например, в OpenBSD signify tool, чтобы подписывать образы

И так, Curve25519 и Ed25519 — примитивы на эллиптических кривых, оптимизированные по быстродействию и написанные таким образом, чтобы минимизировать или вовсе исключить влияние входных данных на процесс расчета ключей\подписей.

Poly1305 Это MAC (Message authentication code), работающий совместно с AES или любым другим шифром по вашему желанию. Он считает 16 байтный (128 бит) MAC, используя 128 битный ключ AES, дополнительный ключ r и соль (nonce).Он разбивает сообщение на блоки по 16 байт и работает с ними как с коэффициентами полинома в r по модулю простого числа 2130−5Результат получается на 4 байта меньше, чем обычный HMAC-SHA1, не имеет проблем с безопасностью и работает быстрее.

Именно поэтому его вместе с потоковым шифром ChaCha20 использует Google вместо RC4, а так же он включен в OpenSSH, которому теперь не нужно зависеть от OpenSSL

Референсная реализация всего этого в библиотеке NaCl на C, но есть порты на java и c#, например.

Надеюсь, после этой статьи у вас появится желание узнать об этих примитивах побольше и использовать их в ваших приложениях.

© Habrahabr.ru