Information Security
Cryptography
Programming
15 January 2015

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

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

Curve25519


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

Кривая используется y2 = x3 + 486662x2 + x. Это — кривая Монтгомери над полем вычетов по модулю простого числа 2255 − 19 (что и дало название схеме) и с базовой точкой x=9. Схема использует точки в сжатой форме (только X координаты), позволяя таким образом использовать "Лестницу Монтгомери", которая делает умножение точек за фиксированное время, избавляя нас от Timing attacks.

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

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

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

EdDSA


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

Испольуется такая вот кривая:


которая эквивалентна кривой для Curve25519

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

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

Poly1305


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

Результат получается на 4 байта меньше, чем обычный HMAC-SHA1, не имеет проблем с безопасностью и работает быстрее.

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

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

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

+31
27.6k 119
Comments 8