Композиции шифров
Недовольство использованием в одном из криптоалгоритмов 64-битового
блока шифрования привело к созданию Джоаной Дэймен алгоритма под названием
ММВ (Modular Multiplication-based Block cipher - модулярный
мультипликативный блочный шифр). В основе ММВ лежит смешивание операций
различных алгебраических групп. ММВ - итеративный алгоритм, главным образом
состоящий из линейных действий (XOR и использование ключа) и параллельного
применения четырех крупных обратимых нелинейных подстановок. Эти
подстановки определяются с помощью умножения по модулю 232-1 с постоянными
множителями. В итоге появляется алгоритм, использующий 128-битовый ключ и
128-битовый блок.
Алгоритм ММВ оперирует 32-битовыми подблоками текста (х0, х1, х2, x3)
и 32-битовыми подблоками ключа (k0, k1, k2, k3). Это упрощает реализацию
алгоритма на современных 32-битовых процессорах. Чередуясь с операцией
XOR, шесть раз используется нелинейная функция f. Вот этот алгоритм (все
операции с индексами выполняются по модулю 4):
xi = xi ( ki для i = 0..3
f(х0, х1, х2, x3)
xi = xi ( ki+1 для i = 0..3
f(х0, х1, х2, x3)
xi = xi ( ki+2 для i = 0..3
f(х0, х1, х2, x3)
xi = xi ( ki для i = 0..3
f(х0, х1, х2, x3)
xi = xi ( ki+1 для i = 0..3
f(х0, х1, х2, x3)
xi = xi ( ki+2 для i = 0..3
f(х0, х1, х2, x3)
Функция f исполняется в три шага:
1. xi = сi * xi для i = 0..3 (Если на входе умножения одни единицы, то
на выходе - тоже одни единицы).
2. Если младший значащий бит х0 = 1, то x0 = х0 ( С. Если младший
значащий байт х3 = 0, то х3 = х3 ( С.
3. xi = хi-1 ( xi ( хi+1 для i = 0..3.
Все операции с индексами выполняются по модулю 4. Операция умножения
на шаге 1 выполняется по модулю 232-1. Специальный случай для данного
алгоритма: если второй операнд равен 232-1, результат тоже равен 232-1. В
алгоритме используются следующие константы:
С = 2ааааааа
c0 = 025f1cdb
c1 = 2*c0
с2=23 *с0
с3=27 *с0
Константа С - «простейшая» константа без круговой симметрии, высоким
троичным весом и нулевым младшим значащим битом. У константы с0 есть другие
особые характеристики. Константы c1, с2 и с3 - сдвинутые версии с0, и
служат для предотвращения атак, основанных на симметрии.
Расшифрование выполняется в обратном порядке, Этапы 2 и 3 инверсны им
самим. На этапе 1 вместо сi используется сi-1 . Значение с0-1 = 0dad4694 .
1. Стойкость алгоритма ММВ
Схема алгоритма ММВ обеспечивает на каждом раунде значительное и
независимое от ключа рассеивание. ММВ изначально проектировался в расчете
на отсутствие слабых ключей.
ММВ – это уже мертвый алгоритм. Это утверждение справедливо по многим
причинам, хотя криптоанализ ММВ и не был опубликован. Во-первых, алгоритм
проектировался без учета требования устойчивости к линейному криптоанализу.
Устойчивость к дифференциальному криптоанализу обеспечил выбор
мультипликативных множителей, но о существовании линейного криптоанализа
авторы не знали.
Во-вторых, Эли Бихам реализовал эффективную атаку с подобранным
ключом, использующую тот факт, что все раунды идентичны, а развертка ключа
– просто циклический сдвиг на 32 бита. В третьих, несмотря на эффективность
программной реализации ММВ, аппаратное исполнение менее эффективно по
сравнению с DES.
Дэймен предлагает желающим улучшить алгоритм ММВ сначала
проанализировать умножение по модулю с помощью линейного криптоанализа и
подобрать новый множитель, а затем сделать константу С различной на каждом
раунде. Затем улучшить развертку ключа, добавляя к ключам раундов константы
с целью устранения смещения. Однако сам он не стал заниматься этим, а
разработал алгоритм 3-Way.
3.7. Алгоритм Blowfish
Blowfish - это алгоритм, разработанный Брюсом Шнайером специально для
реализации на больших микропроцессорах. Алгоритм Blowfish не запатентован.
При проектировании алгоритма Blowfish Шнайер пытался удовлетворить
следующим критериям:
V Скорость. Программа, реализующая алгоритм Blowfish на 32-битовых
микропроцессорах, шифрует данные со скоростью 26 тактов на байт.
V Компактность. Для исполнения программной реализации алгоритма Blowfish
достаточно 5 Кбайт памяти.
V Простота. В алгоритме Blowfish используются только простые операции:
сложение, XOR и подстановка из таблицы по 32-битовому операнду. Анализ
его схемы несложен, что снижает риск ошибок реализации алгоритма.
V Настраиваемая стойкость. Длина ключа Blowfish переменна и может
достигать 448 бит.
Алгоритм Blowfish оптимизирован для применения в системах, не
практикующих частой смены ключей, например, в линиях связи и программах
автоматического шифрования файлов. При реализации на 32-битовых
микропроцессорах с большим размером кэша данных, например, процессорах
Pentium и PowerPC, алгоритм Blowfish заметно быстрее DES. Алгоритм Blowfish
не годится для применения в случаях, где требуется частая смена ключей,
например, в коммутаторах пакетов, или в качестве однонаправленной хэш-
функции. Большие требования к памяти не позволяют использовать этот
алгоритм в смарт-картах.
3.7.1. Описание алгоритма Blowfish
Blowfish представляет собой 64-битовый блочный алгоритм шифрования с
ключом переменной длины. Алгоритм состоит из двух частей: расширения ключа
и шифрования данных. Расширение ключа преобразует ключ длиной до 448 битов
в несколько массивов подключей общим размером 4168 байт.
Шифрование данных заключается в последовательном исполнении простой
функции 16 раз. На каждом раунде выполняются зависимая от ключа
перестановка и зависимая от ключа и данных подстановка. Используются только
операции сложения и XOR над 32-битовыми словами. Единственные
дополнительные операции каждого раунда - четыре взятия данных из
индексированного массива.
В алгоритме Blowfish используется множество подключей. Эти подключи
должны быть вычислены до начала зашифрования или расшифрования данных.
[pic]
Рис 3. Алгоритм Blowfish
Р-массив состоит из восемнадцати 32-битовых подключей:
Р1,Р2,...,Р18
Каждый из четырех 32-битовых S-блоков содержит 256 элементов:
S1,0, S1,1,…, S1,255
S2,0, S2,2,…, S2,255
S3,0, S3,3,…, S3,255
S4,0, S4,4,…, S4,255
Алгоритм Blowfish представляет собой сеть Файстеля, состоящей из 16
раундов. На вход подается 64-битовый элемент данных х. Для зашифрования
данных:
Разбить х на две 32-битовых половины: xL, xR
Для i от 1 до 16:
xL = xL ( Pi
xR = F (xL) ( xR
Переставить xL и xR
Переставить xL и xR (отнять последнюю перестановку)
xR = xR ( P17
xL = xL ( P18
Объединить xL и xR
[pic]
Рис. 4. Функция F
Функция F рассчитывается следующим образом ( Рис. 4.):
Разделить xL на четыре 8-битовых фрагмента: а, b, с и d
F(xL) = ((S1,a + S2,bmod232)( S3,c) + S4,dmod232
Расшифрование выполняется точно так же, как и зашифрование, но
Р1,Р2,...,Р18 используются в обратном порядке.
В реализациях Blowfish, в которых требуется очень высокая скорость,
цикл должен быть развернут, а все ключи храниться в кэше.
Подключи рассчитываются с помощью самого алгоритма Blowfish. Вот
какова точная последовательность действий.
1. Сначала Р-массив, а затем четыре S-блока по порядку инициализируются
фиксированной строкой. Эта строка состоит из шестнадцатеричных цифр ?.
2. Выполняется операция XOR над Р1 с первыми 32 битами ключа, XOR над Р2
со вторыми 32 битами ключа, и т.д. для всех битов ключа (вплоть до
Р18). Операция XOR выполняется циклически над битами ключа до тех пор,
пока весь Р-массив не будет инициализирован.
3. Используя подключи, полученные на этапах 1 и 2, алгоритм Blowfish
шифрует строку из одних нулей.
4. Р1 и Р2 заменяются результатом этапа 3.
5. Результат этапа 3 шифруется с помощью алгоритма Blowfish и
модифицированных подключей.
6. Р3 и Р4 заменяются результатом этапа 5.
7. Далее по ходу процесса все элементы Р-массива, а затем все четыре S-
блока по порядку заменяются выходом постоянно меняющегося алгоритма
Blowfish.
Всего для генерации всех необходимых подключей требуется 521 итерация.
Приложения могут сохранять подключи - нет необходимости выполнять процесс
их получения многократно.
3.7.2. Стойкость алгоритма Blowfish
Серж Воденэ (Serge Vaudenay) исследовал алгоритм Blowfish с известными
S-блоками и r раундами. Как оказалось, дифференциальный криптоанализ может
восстановить Р-массив с помощью 28r+1 подобранных открытых текстов. Для
некоторых слабых ключей, которые генерируют плохие S-блоки (вероятность
выбора такого ключа составляет 1/214), эта же атака восстанавливает Р-
массив с помощью всего 24г+1 подобранных открытых текстов. При неизвестных
S-блоках эта атака может обнаружить использование слабого ключа, но не
может восстановить сам ключ (и также S-блоки и Р-массив). Эта атака
эффективна только против вариантов с уменьшенным числом раундов и
совершенно безнадежна против 16-раундового алгоритма Blowfish. Разумеется,
важно и открытие слабых ключей, хотя они, вероятно, использоваться не
будут. Слабым называют ключ, для которого два элемента данного S-блока
идентичны. До вып
| |  скачать работу |
Композиции шифров |
