Curve25519, EdDSA и Poly1305: Три обделенных вниманием криптопримитива
Есть такой очень хороший товарищ по имени 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 году.Испольуется такая вот кривая:
которая эквивалентна кривой для 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#, например.
Надеюсь, после этой статьи у вас появится желание узнать об этих примитивах побольше и использовать их в ваших приложениях.
