POLY1305-AES
POLY1305-AES — код аутентификации сообщения (англ. MAC) ,разработанный  . Является комбинацией POLY-1305 и AES-128 , и как любой код аутенфикации, POLY1305-AES можно использовать для проверки целостности данных и подлинности сообщения.

Poly1305-AES вычисляет 16-байтовый аутентификатор сообщения любой длины, используя 16-байтовый одноразовый номер (уникальный номер сообщения) и 32-байтовый секретный ключ.

AES используется для шифрования одноразового номера, чтобы получить уникальную (и секретную) 128-битную строку, но при желании AES-128 можно заменить любой другой функцией c гарантией безопасности, например ChaCha20.

Обзор

Аргументы POLY1305-AES 
Poly1305-AES получает на вход 
 Сообщение произвольной длины 
 16-байтовый ключ 
 16-байтовый дополнительный ключ 
 16-байтовое однократно используемое число .
и вычисляет 16-байтовый аутентификатор .

Ключ  представляет собой 128-битное целое число r с прямым порядком байтов от младшего к старшему (англ. little-endian ), т.е.
. При этом ключ  должен соответствовать определённым требованиям: у , ,  и  первые 4 из 8 битов должны быть равны 0, а у ,  и   последние 2 бита должны быть равны 0. Таким образом  может принять  различных значений

Алгоритм 
 Poly1305 разбивает сообщение  на фрагменты длиной 16 байт.
 К каждому 16-байтовому фрагмент сообщения добавляется единица до 17 байт для использования в качестве коэффициента полинома. Если последний фрагмент сообщения размером от 1 до 15 байт, то  к фрагменту добавляется единица, а дальше до 17 байт всё заполняется нулями. Коэффициенты  полинома  , где  вычисляются по формуле:.Если  не делится нацело на 16, то используют формулу:
 Полином вычисляется в точке  по модулю  и складывается с 16-байтной зашифрованной строкой , полученной на выходе , где  -однократно используемое число.
	Берём остаток от деления на  и закодируем его, получив хэш длиной 16 байт.

Выбор стуктурных элементов при разработке алогритма 
Изначально для деления по модулю рассматривались простые числа больше  (128 битов – длина фрагмента сообщения). Для простоты вычислений было решено выбрать простое число .

Причин, по которым алгоритм использует однократно используемое число  несколько:
Во-первых, вероятность взлома протоколов, не использующих такие числа  можно выразить формулой: , где  количество сообщений,  – количество попыток взлома,  -максимальная длина сообщения. А с однократно используемым числом вероятность будет такая: .
Во-вторых, одноразовые номера позволяют проводить выполнение алгоритма AES-128 параллельно с другими операциями Poly1305-AES, что уменьшает общее время вычисления аутентификатора. В-третьих, большинство протоколов так или иначе имеют такие одноразовые номера для более безопасного шифрования.

Длина дополнительного ключа  была ограничена 16-ю байтами для ускорения вычислений. При этом возможен ключ длинее для усиления безопасности, но текущая вероятность взлома достаточно низкая, чтобы считать алгоритм при текущей длине ключа безопасным. Но при увеличении длины ключа, общее время вычисления будет слишком долгим, что лишит POLY1305-AES преимущества перед другими алгоритмами.
Так же для ключа был выбран прямой порядок байтов, вместо обратного (англ. Big-endian), так как он экономит время на самых популярных процессорах.

Алгоритм POLY1305, написанный на псевдокоде

Криптостойкость 
Принято считать, что безопасность POLY1305-AES гарантирована, если можно гарантировать безопасность алгоритма AES.
Если у злоумышленника есть  зашифрованных сообщений и он совершает D попыток взлома сообщений длиной не больше  байтов,  - вероятность взлома AES, то вероятность взлома POLY1305-AES будет

Рассмотрим случай, когда сообщения представляют из себя пакеты длиной до 1536 байт, злоумышленник имеет  сообщений зашифрованных POLY1305-AES и совершает  попыток взломать, а вероятность взлома   . В таком случае вероятность, что злоумышленник не сможет взломать  код аутентификации послания .
Для сравнения, при таких параметрах можно легко взломать другие 16-байтные MAC, например CBC-AES, HMAC-MD5 и DMAC-A.

Скорость 
Poly1305-AES можно вычислять с чрезвычайно высокой скоростью, например для AMD Athlon требуется менее 3.1n + 780 циклов для сообщения длиной n байт. Даниэль Дж. Бернштейн опубликовал исходный код  на SPARC, AIX, macOS, Pentium Pro/II/III/M и Athlon. А также эталонную реализацию алгоритма на C, C++, Python и Perl.

Иплементация 
Ниже представлен список криптографических библиотек, в которых есть реализация Poly1305:
 Botan
 Bouncy Castle
 Crypto++
 Libgcrypt
 NaCl
 Nettle
 OpenSSL
 LibreSSL
 wolfCrypt
 GnuTLS
 mbed TLS
 MatrixSSL

Примечания

Ссылки 
 POLY1305-AES Домашняя страница
 Имплементация POLY1305-AES на C
 Таблицы скорости Poly1305-AES

См. также 

Криптография
Аутентификация

Обнаружение и устранение ошибок
Потоковые шифры