kursovik (663822), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Поскольку S-блоки Khufu зависят от ключа и секретны, алгоритм устойчив к дифференциальному криптоанализу. Известна дифференциальная атака на 16-раундовый Khufu, которая восстанавливает ключ с помощью 2³¹ подобранных открытых текстов, однако этот метод не удалось расширить на большее число раундов. Если принять, что лучший метод взлома Khufu - лобовое вскрытие, стойкость алгоритма впечатляет. 512-би-овый ключ обеспечивает сложность вскрытия 2⁵¹² - это огромное число в любом случае.

3.5.2. Алгоритм Khafre

Khafre - это вторая криптосистема, предложенная Мерклом. (Khufu (Хуфу) и Khafre (Хафр) - имена египетских фараонов). Конструкция этого алгоритма близка Khufu, однако он спроектирован для приложений, где невозможны предварительные вычисления. S-блоки не зависят от ключа. Вместо этого в Khafre используются фиксированные S-блоки. Блок шифрования подвергается операции XOR с ключом не только перед первым раундом и после последнего, но и после каждых восьми раундов шифрования.

Меркл предполагал, что в алгоритме Khafre следует использовать 64- или 128-битовые ключи и что в этом алгоритме понадобится большее число раундов, чем в Khufu. Это, наряду с тем, что каждый раунд Khafre сложнее раунда Khufu, делает Khafre менее скоростным. Зато алгоритму Khafre не нужны никакие предварительные расчеты, что ускорит шифрование небольших порций данных.

В 1990 году Бихам и Шамир применили свой метод дифференциального криптоанализа к алгоритму Khafre. Им удалось взломать 16-раундовый Khafre атакой с подобранным открытым текстом, используя около 1500 различных шифрований. На их персональном компьютере это заняло около часа. Преобразование этой атаки в атаку с известным открытым текстом потребует около 2³⁸ шифрований. Алгоритм Khafre с 24 раундами можно взломать с помощью атаки с подобранным открытым текстом за 2⁵³ шифрования, а с помощью атаки с известным открытым текстом – за 2⁵⁹ шифрования.

Алгоритмы Khufu и Khafre запатентованы. Исходный код этих алгоритмов приведен в патенте.

3.6. Алгоритм ММВ

Недовольство использованием в одном из криптоалгоритмов 64-битового блока шифрования привело к созданию Джоаной Дэймен алгоритма под названием ММВ (Modular Multiplication-based Block cipher - модулярный мультипликативный блочный шифр). В основе ММВ лежит смешивание операций различных алгебраических групп. ММВ - итеративный алгоритм, главным образом состоящий из линейных действий (XOR и использование ключа) и параллельного применения четырех крупных обратимых нелинейных подстановок. Эти подстановки определяются с помощью умножения по модулю 2³²-1 с постоянными множителями. В итоге появляется алгоритм, использующий 128-битовый ключ и 128-битовый блок.

Алгоритм ММВ оперирует 32-битовыми подблоками текста (х₀, х₁, х₂, x₃) и 32-битовыми подблоками ключа (k₀, k₁, k₂, k₃). Это упрощает реализацию алгоритма на современных 32-битовых процессорах. Чередуясь с операцией XOR, шесть раз используется нелинейная функция f. Вот этот алгоритм (все операции с индексами выполняются по модулю 4):

x_i = x_i  k_i для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i  k_i+1 для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i  k_i+2 для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i  k_i для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i  k_i+1 для i = 0..3

f(х₀, х₁, х₂, x₃)

x_i = x_i  k_i+2 для i = 0..3

f(х₀, х₁, х₂, x₃)

Функция f исполняется в три шага:

1. x_i = с_i * x_i для i = 0..3 (Если на входе умножения одни единицы, то на выходе - тоже одни единицы).

2. Если младший значащий бит х₀ = 1, то x₀ = х₀  С. Если младший значащий байт х₃ = 0, то х₃ = х₃  С.

3. x_i = х_i-1  x_i  х_i+1 для i = 0..3.

Все операции с индексами выполняются по модулю 4. Операция умножения на шаге 1 выполняется по модулю 2³²-1. Специальный случай для данного алгоритма: если второй операнд равен 2³²-1, результат тоже равен 2³²-1. В алгоритме используются следующие константы:

С = 2ааааааа

c₀ = 025f1cdb

c₁ = 2*c₀

с₂=2³ *с₀

с₃=2⁷ *с₀

Константа С - «простейшая» константа без круговой симметрии, высоким троичным весом и нулевым младшим значащим битом. У константы с₀ есть другие особые характеристики. Константы c₁, с₂ и с₃ - сдвинутые версии с₀, и служат для предотвращения атак, основанных на симметрии.

Расшифрование выполняется в обратном порядке, Этапы 2 и 3 инверсны им самим. На этапе 1 вместо с_i используется с_i^-1 . Значение с₀^-1 = 0dad4694 .

1. Стойкость алгоритма ММВ

Схема алгоритма ММВ обеспечивает на каждом раунде значительное и независимое от ключа рассеивание. ММВ изначально проектировался в расчете на отсутствие слабых ключей.

ММВ – это уже мертвый алгоритм. Это утверждение справедливо по многим причинам, хотя криптоанализ ММВ и не был опубликован. Во-первых, алгоритм проектировался без учета требования устойчивости к линейному криптоанализу. Устойчивость к дифференциальному криптоанализу обеспечил выбор мультипликативных множителей, но о существовании линейного криптоанализа авторы не знали.

Во-вторых, Эли Бихам реализовал эффективную атаку с подобранным ключом, использующую тот факт, что все раунды идентичны, а развертка ключа – просто циклический сдвиг на 32 бита. В третьих, несмотря на эффективность программной реализации ММВ, аппаратное исполнение менее эффективно по сравнению с DES.

Дэймен предлагает желающим улучшить алгоритм ММВ сначала проанализировать умножение по модулю с помощью линейного криптоанализа и подобрать новый множитель, а затем сделать константу С различной на каждом раунде. Затем улучшить развертку ключа, добавляя к ключам раундов константы с целью устранения смещения. Однако сам он не стал заниматься этим, а разработал алгоритм 3-Way.

3.7. Алгоритм Blowfish

Blowfish - это алгоритм, разработанный Брюсом Шнайером специально для реализации на больших микропроцессорах. Алгоритм Blowfish не запатентован. При проектировании алгоритма Blowfish Шнайер пытался удовлетворить следующим критериям:

• Скорость. Программа, реализующая алгоритм Blowfish на 32-битовых микропроцессорах, шифрует данные со скоростью 26 тактов на байт.

• Компактность. Для исполнения программной реализации алгоритма Blowfish достаточно 5 Кбайт памяти.

• Простота. В алгоритме Blowfish используются только простые операции: сложение, XOR и подстановка из таблицы по 32-битовому операнду. Анализ его схемы несложен, что снижает риск ошибок реализации алгоритма.

• Настраиваемая стойкость. Длина ключа Blowfish переменна и может достигать 448 бит.

Алгоритм Blowfish оптимизирован для применения в системах, не практикующих частой смены ключей, например, в линиях связи и программах автоматического шифрования файлов. При реализации на 32-битовых микропроцессорах с большим размером кэша данных, например, процессорах Pentium и PowerPC, алгоритм Blowfish заметно быстрее DES. Алгоритм Blowfish не годится для применения в случаях, где требуется частая смена ключей, например, в коммутаторах пакетов, или в качестве однонаправленной хэш-функции. Большие требования к памяти не позволяют использовать этот алгоритм в смарт-картах.

3.7.1. Описание алгоритма Blowfish

Blowfish представляет собой 64-битовый блочный алгоритм шифрования с ключом переменной длины. Алгоритм состоит из двух частей: расширения ключа и шифрования данных. Расширение ключа преобразует ключ длиной до 448 битов в несколько массивов подключей общим размером 4168 байт.

Шифрование данных заключается в последовательном исполнении простой функции 16 раз. На каждом раунде выполняются зависимая от ключа перестановка и зависимая от ключа и данных подстановка. Используются только операции сложения и XOR над 32-битовыми словами. Единственные дополнительные операции каждого раунда - четыре взятия данных из индексированного массива.

В алгоритме Blowfish используется множество подключей. Эти подключи должны быть вычислены до начала зашифрования или расшифрования данных.

Рис 3. Алгоритм Blowfish

Р-массив состоит из восемнадцати 32-битовых подключей:

Р₁,Р₂,...,Р₁₈

Каждый из четырех 32-битовых S-блоков содержит 256 элементов:

S_1,0, S_1,1,…, S_1,255

S_2,0, S_2,2,…, S_2,255

S_3,0, S_3,3,…, S_3,255

S_4,0, S_4,4,…, S_4,255

Алгоритм Blowfish представляет собой сеть Файстеля, состоящей из 16 раундов. На вход подается 64-битовый элемент данных х. Для зашифрования данных:

Разбить х на две 32-битовых половины: x_L, x_R

Для i от 1 до 16:

x_L = x_L  P_i

x_R = F (x_L)  x_R

Переставить x_L и x_R

Переставить x_L и x_R (отнять последнюю перестановку)

x_R = x_R  P₁₇

x_L = x_L  P₁₈

Объединить x_L и x_R

Рис. 4. Функция F

Функция F рассчитывается следующим образом ( Рис. 4.):

Разделить x_L на четыре 8-битовых фрагмента: а, b, с и d

F(x_L) = ((S_1,a + S_2,bmod2³²) S_3,c) + S_4,dmod2³²

Расшифрование выполняется точно так же, как и зашифрование, но Р₁,Р₂,...,Р₁₈ используются в обратном порядке.

В реализациях Blowfish, в которых требуется очень высокая скорость, цикл должен быть развернут, а все ключи храниться в кэше.

Подключи рассчитываются с помощью самого алгоритма Blowfish. Вот какова точная последовательность действий.

1. Сначала Р-массив, а затем четыре S-блока по порядку инициализируются фиксированной строкой. Эта строка состоит из шестнадцатеричных цифр π.

2. Выполняется операция XOR над Р₁ с первыми 32 битами ключа, XOR над Р₂ со вторыми 32 битами ключа, и т.д. для всех битов ключа (вплоть до Р₁₈). Операция XOR выполняется циклически над битами ключа до тех пор, пока весь Р-массив не будет инициализирован.

3. Используя подключи, полученные на этапах 1 и 2, алгоритм Blowfish шифрует строку из одних нулей.

4. Р₁ и Р₂ заменяются результатом этапа 3.

5. Результат этапа 3 шифруется с помощью алгоритма Blowfish и модифицированных подключей.

6. Р₃ и Р₄ заменяются результатом этапа 5.

7. Далее по ходу процесса все элементы Р-массива, а затем все четыре S-блока по порядку заменяются выходом постоянно меняющегося алгоритма Blowfish.

Всего для генерации всех необходимых подключей требуется 521 итерация. Приложения могут сохранять подключи - нет необходимости выполнять процесс их получения многократно.

Характеристики

Список файлов реферата