Алгоритм SAFER+
Этот алгоритм был предложен калифорнийской корпорацией Cylink
как один из кандидатов на принятие в качестве нового стандарта шифрования AES. Он является примером шифра, не использующего структуру сети Фейстела. Шифр работает с блоками длиной 128 бит и с ключами длиной 128, 192 или 256 бит, в соответствии с требованиями NIST к новому стандарту. Процедуры шифрования и расшифрования представляют собой последовательность итераций, число которых зависит от длины ключа и равно 8, 12 и 16 соответственно. При шифровании после (а при расшифровании – перед) всех итераций производится еще одно подмешивание подключа.
Каждая итерация состоит из четырех слоев – подмешивания первого подключа, нелинейной обратимой замены, подмешивания второго подключа и линейного перемешивания. При этом используются только байтовые операции, что делает этот шифр особенно привлекательным для реализации на микропроцессорах малой разрядности.
Слои подмешивания первого и второго подключа имеют сходную структуру. На i?й итерации используются два подключа K2i?1 и K2i длиной по 128 бит. При добавлении первого подключа байты 1, 4, 5, 8, 9, 12, 13 и 16 текстового блока складываются с соответствующими байтами подключа поразрядно по модулю 2, а байты 2, 3, 6, 7, 10, 11, 14 и 15 складываются с байтами подключа по модулю 256. Второй подключ в конце итерации добавляется аналогично, только те байты, которые складывались поразрядно, теперь складываются по модулю 256, и наоборот.
Слой нелинейной замены устроен следующим образом. Значение x байта j преобразуется в 45x (mod 257) для байтов с номерами j = 1, 4, 5, 8, 9, 12, 13 и 16. При этом если x
= 128, то 45128 (mod 257) = 256 представляется нулем. Значения байтов с номерами j = 2, 3, 6, 7, 10, 11, 14 и 15 преобразуются в log45(x), при этом если x = 0, то log45(0) представляется числом 128. Нетрудно заметить, что эти операции являются обратимыми (в действительности, они обратны друг другу). Производить вычисления экспонент и логарифмов при шифровании и расшифровании не обязательно – можно заранее вычислить таблицы замены (всего для их хранения потребуется 512 байтов) и использовать их при работе.
Линейное перемешивание представляет собой умножение текстового блока справа на специальную невырожденную матрицу M. При этом все операции выполняются побайтно по модулю 256.
Подмешивание подключа K2r+1
производится так же, как и подмешивание первого подключа в каждой итерации.
При расшифровании вначале подмешивается подключ K2r+1, при этом операция сложения по модулю 256 заменяется на вычитание. Затем выполняются итерации расшифрования.
i-я итерация расшифрования выполняет преобразование, обратное к r-i+1-й итерации шифрования (r – число итераций) и также содержит 4 слоя. Вначале текстовый блок умножается на матрицу, обратную к матрице шифрования
Затем подмешивается подключ K2r?2i+2, так же, как и второй подключ в итерации шифрования, только сложение с ключом по модулю 256 заменяется вычитанием.
После этого производится обратная нелинейная замена, т.е. те байты, которые при шифровании возводились в степень, логарифмируются, и наоборот.
И, наконец, подмешивается подключ K2r?2i+1
(с учетом тех же замечаний, что относились к подмешиванию подключа K2r?2i+2).
Для завершения описания алгоритма осталось указать, как из ключа пользователя получаются подключи для итераций.
При обработке ключа пользователя применяются так называемые слова смещения B2, B3, ..., B33
длиной по 16 байт, которые вычисляются по формулам:
где Bi,j – j-й байт i-го слова смещения (j = 1…16). При этом значение Bi,j=256 представляется нулем. Слова смещения являются константами и могут быть вычислены заранее.
Для длины ключа в 128 бит используются только слова B2, … B17, для ключа в 192 бита используются слова смещения B2,…,B25, а для ключа в 256 бит используются все слова.
Генерация подключей осуществляется по следующему алгоритму:
В качестве первого подключа используются первые шестнадцать байтов пользовательского ключа. Далее пользовательский ключ записывается в ключевой регистр размером на один байт больше длины ключа. После этого все байты ключа суммируются поразрядно по модулю 2 и результат записывается в дополнительный байт регистра. После чего для получения требуемых подключей повторяется итеративная процедура, заключающаяся в следующем:
1. Содержимое каждого байта в регистре циклически сдвигается влево на 3 позиции;
2. Производится выборка 16 байт из регистра. При этом для получения подключа Ki
выбираются идущие подряд байты регистра, начиная с i-го (если достигнут конец регистра, то оставшиеся байты выбираются с его начала);
3. Выбранные байты складываются с соответствующими байтами слова смещения Bi
по модулю 256. Результат сложения и является подключом Ki.
