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

в 11:59, , рубрики: Curve25519, Daniel J. Bernstein, Ed25519, EdDSA, Poly1305, информационная безопасность, криптография

Curve25519, EdDSA и Poly1305: Три обделенных вниманием криптопримитива - 1Есть такой очень хороший товарищ по имени Daniel Julius Bernstein. Математик, программист и спец по компьютерной безопасности. Его хэш CubeHash чуть не дотянул до третьего раунда SHA-3, а потоковый шифр Salsa20 попал в шорт лист проекта eStream. А еще он автор культовой в узких кругах криптобиблиотеки NaCl, о трех штуках из которой я бы хотел вкратце рассказать.

Curve25519

Это эллиптическая кривая и набор параметров к ней подобранных таким образом, чтобы обеспечить более высокое быстродействие и избавиться от некоторых проблем с безопасностью у традиционного ECDH.

Кривая используется y2 = x3 + 486662x2 + 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 и Poly1305: Три обделенных вниманием криптопримитива - 2
которая эквивалентна кривой для 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#, например.

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

Автор: Scratch

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js