Алгоритм FROG

Алгоритм FROG был создан в 1998 г. тремя специалистами компании Tecnologia Apropriada (ТесАрго) из небольшого латиноамериканского государства Коста-Рика (неизвестного ранее своими разработками в области криптографии): Дианелосом Георгоудисом (Dianelos Georgoudis), Дамианом Леру (Damian Leroux) и Билли Симоном Чавесом (Billy Simon Chaves).

Основные характеристики и структура алгоритма
Как известно, конкурс AES устанавливал для алгоритмов — участников конкурса обязательность поддержки 128-битного размера блока шифруемых данных, а также 128-, 192- и 256-битных ключей шифрования. Однако, разработчики алгоритма FROG предложили несравнимо более широкий набор значений этих параметров.

Независимо от размера ключа и блока, шифрование выполняется в 8 раундов. В каждом раунде над каждым байтом шифруемого блока (для определенности также будем считать, что блоки имеют размер 16 байтов).

Значение текущего байта складывается по модулю 2 со значением того же байта 1-й части ключа раунда (процедура расширения ключа описана далее). Вторая часть ключа раунда представляет собой таблицу перестановок. Из данной таблицы выбирается байт, порядковый номер которого равен значению, вычисленному на первом шаге. Значение выбранного байта замещает значение текущего байта шифруемого блока данных.

Значение следующего байта перекладывается по модулю 2 со значением, выбранным на шаге 2. Полученный результат замещает старое значение байта шифруемого блока данных.

Третья часть ключа раунда представляет собой таблицу индексов. Значение i-ro байта таблицы индексов определяет еще один модифицируемый байт шифруемого блока данных, который изменяется полностью аналогично байту (т. е. складывается по модулю 2 со значением, полученным на шаге 2). Процедура расширения ключа
1. Путем «размножения» ключа шифрования (т. е. значение ключа шифрования повторяется необходимое количество раз, а ключ шифрования этого алгоритма, как было сказано выше, имеет размер от 5 до 125 байтов) вырабатывается первый 2304-байтный временный массив данных. Байты последней из «размноженных» копий ключа, выходящие за границу требуемого 2304-байтного массива (например, последний 71 байт 125-байтного ключа — ключа максимального размера), отбрасываются.

2. Аналогичным «размножением» 251-байтного фрагмента мастер-ключа формируется второй 2304-байтный временный массив данных. Мастер-ключ представляет собой специально подобранную константу размером 251 байт.

Путем применения операции сложения по модулю 2 к соответствующим битам двух массивов, выработанных на шагах 1 и 2, получается временный расширенный ключ.

Форматирование ключа, полученного на шаге 3 (т. е. его разбиение на 8 отрезков— по числу раундов— размером 16 + 256 + 16 байтов, а также дополнительная обработка, которая будет описана далее), дает предварительный расширенный ключ алгоритма.

Предварительный расширенный ключ используется для зашифровывания 2304-байтного массива, заполненного нулями. Шифрование выполняется в режиме сцепления блоков шифра, где в качестве вектора инициализации (IV) используются первые 16 байтов исходного ключа шифрования, самый первый из которых еще и складывается по модулю 2 с числом, равным размеру ключа шифрования в байтах (это необходимо для получения различных IV для ключей разного размера, но с совпадающими первыми 16 байтами). Результат операции— расширенный ключ, заполненный псевдослучайной информацией. Аналогично шагу 4, выполняется форматирование расширенного ключа для получения восьми ключей раундов с необходимой структурой.

Форматирование ключа
Шаги 4 и 6 алгоритма расширения ключа представляют собой форматирование 2304-байтной псевдослучайной последовательности с целью получения 8 ключей раундов. Если 1-я часть ключа раунда, используемая для сложения по модулю 2, может иметь абсолютно случайную структуру, то корректная таблица перестановок должна состоять из 256 неповторяющихся значений от 0 до 255, а к 16-байтной таблице индексов, кроме того, предъявляются дополнительные требования.

Достоинства и недостатки алгоритма
Несомненно, FROG является одним из самых оригинальных из современных алгоритмов шифрования. Как и многие другие алгоритмы, например AES (Rijndael) или SAFER+, FROG является байт-ориентированным. Однако, в отличие от объяснимых и объясненных авторами Rijndael и SAFER+ преобразований, примененных в этих алгоритмах, авторы алгоритма FROG ограничились пояснением, что такая необычная структура раунда выбрана с целью обеспечить максимально быстрое рассеивание входных данных (т. е. обеспечение влияния каждого бита шифруемых данных на каждый бит шифртекста в пределах блока). К сожалению, алгоритм FROG был признан одним из наиболее слабых участников конкурса AES; в нем было найдено множество недостатков, в частности:
довольно большая часть множества возможных ключей алгоритма оказалась слабой (благодаря очень сложной процедуре расширения ключа) к различным видам атак;
алгоритм оказался весьма медленным, причем даже по сравнению с алгоритмами, известными до конкурса AES, например, Blowfish и RC5;
алгоритм FROG оказался очень требовательным к оперативной памяти — ему необходимо около 2500 байтов в случае, если ключи раундов сформированы заранее, а для работы полнофункционального алгоритма, включающего процедуру расширения ключа, необходимо около 5000 байтов; эти требования очень велики (особенно в сравнении с другими алгоритмами — участниками конкурса AES) для реализации данного алгоритма в смарт-картах.

Таким образом, алгоритм FROG не вышел в финал конкурса AES.