Часть III Криптографические алгоритмы

Часть III Криптографические алгоритмы

Глава 11 Математические основы

11.1 Теория информации

Современная теория информации впервые была опубликована в 1948 году Клодом Э. Шенноном (Claude Elmwood Shannon) [1431, 1432]. (Его работы были переизданы в IEEE Press [1433].) С математической точки зрения эта тема хорошо рассмотрена в [593]. В этой главе я только схем атично излагаю основные идеи.

Энтропия и неопределенность

0 - Воскресенье 1 -Понедельник  

Норма языка

г =H(M)/N где N - это длина сообщения. При больших N норма обычного английского языка… R = log2 L

Табл. 11-1.

Расстояния уникальности текста ASCII,

Зашифрованного алгоритмами с различной длиной ключа

  5.9 8.2 9.4 11.8 18.8 37.6 … Шеннон определил криптосистему с бесконечным расстоянием уникальности, как…

Практическое использование теории информации

Путаница и диффузия

Путаницамаскирует связь между открытым текстом и шифротекстом. Она затрудняет попытки найти в шифротексте избыточность и статистические… Диффузиярассеивает избыточность открытого текста, распространяя ее по всему… Потоковые шифры используют только путаницу, хотя ряд схем с обратной связью добавляют диффузию. Блочные алгоритмы…

Табл. 11-2 Время выполнения для различных классов алгоритмов

Кл^с Сложность Количество операций для _и=10⁶ Время при 10⁶ операций в секунду

 

Постоянные	0(1)
Линейные	0(и)
Квадратичные	0(п2)
Кубические	0(п3)
Экспоненциальные	0(2")

10*

10¹²

ю¹⁸ ю³⁰

1мкс

1с

11.6 дня

32000 лет

В 10³⁰¹⁰⁰⁶ раз больше, чем время существования вселенной

При условии, что единицей времени для нашего компьютера является микросекунда, компьютер может в ы-полнить постоянный алгоритм за микросекунду, линейный - за секунду, а квадратичный - за 11.6 дня. Выполн е-ние кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция кот о-рого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.

Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскр ы-тия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если п - длина ключа, то сложность вскрытия грубой силой равна 0(2 "). В разделе 12.3 рассматривается дискуссия об использовании для DES 56-битового ключа вместо 112-битового. Сложность вскрытия грубой силой при 56-битовом ключе составляет 2⁵⁶, а при 112-битовом ключе - 2¹¹². В первом случае вскрытие возможно, а во вто-ром - нет.

Сложность проблем

Проблемы, которые можно решить с помощью алгоритмов с полиномиальным временем, называются р е-шаемыми, потому что для разумных входных данных обычно… Что еще хуже, Алан Тьюринг доказал, что некоторые проблемы принципиально… Проблемы можно разбить на классы в соответствии со сложностью их решения. Самые важные классы и их предполагаемые…

Арифметика вычетов

(10 + 13) mod 12 = 23 mod 12 = 11 mod 12 Другим способом записать это является утверждение об эквивалентности 23 и И по… 10 + 13 = 11 (mod 12)

Простые числа

Евангелос Кранакис (Evangelos Kranakis) написал отличную книгу по теории чисел, простым числам и их применению в криптографии [896]. Паула Рибенбойм…

Наибольший общий делитель

НОД(а,и)=1 Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500… Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида.Эвк-лид описал этот…

Обратные значения по модулю

4*х = 1 (mod 7) Это уравнение эквивалентно обнаружению х и к, таких что 4х = 1к + 1

Квадратичные вычеты

х2 = a (mod/;), для некоторых х Не все значения а соответствуют этому требованию. Чтобы а было квадратичным… I2 = 1 = 1 (mod 7)

Символ Лежандра

Ца,р) = 0, если а делится на р. Ца,р) = 1, если а - квадратичный вычет по модулю р. Ца,р) = -1, если а не является квадратичным вычетом по модулю р.

Символ Якоби

Определение 1: J(a,n) определен, только если п нечетно. Определение 2: J(0,h) = 0. Определение 3: Если п - простое число, то символ Якоби ](а,п) = 0, если а делится на п.

Целые числа Блюма

Если р и q - два простых числа, конгруэнтных 3 по модулю 4, то п = рд иногда называют целым числом Блюма.Если п - это целое число Блюма, у каждого квадратичного вычета ровно четыре квадратных корня, один из которых также является квадратом - это главный квадратный корень. Например, главный квадратный корень 139 mod 437 - это 24. Остальные три корня - это 185, 252 и 413.

Генераторы

Иными словами, g является примитивомпо отношению к р. Например, если р = И, то 2 - это генератор по модулю И: 210 = 1024 = 1 (mod И) 2!= 2 = 2 (mod И)

V V

_е(1.923+0(1))(1п(п))Л(1п((1п(и)))/з

В 1970 году большой новостью стало разложение на множители 41-разрядного трудного числа [1123]. ("Трудным" является такое число, у которого нет маленьких множителей, и которое не обладает специальной формой, позволяющей упростить процесс.) Десять лет спустя разложение в два раз более длинного числа заняло лишь несколько часов на компьютере Cray [440].

В 1988 году Карл Померанс (Carl Pomerance), используя обычные СБИС, спроектировал устройство для ра з-ложения на множители [1259]. Размер числа, которое можно было разложить, зависел только от размеров ус т-ройства, которое так и не было построено.

В 1993 году с помощью квадратичного решета было разложено на множители 120-разрядное трудное число. Расчет, потребовавший 825 mips-лет, был выполнен за три месяца реального времени [463]. Другие результаты приведены в [504].

Сегодня для разложения на множители используются компьютерные сети [302, 955]. Для разложения 116_разрядного числа Аржат Ленстра (Arjen Lenstra) и Марк Манасс (Mark Manasse) в течение нескольких м е-сяцев использовали свободное время массива компьютеров, разбросанных по всему миру, - 400 mips-лет.

В марте 1994 года с помощью двойной вариации множественного полиномиального QS [66] командой м а-тематиков под руководством Ленстры было разложено на множители 129-разрядное (428-битовое) число. В ы-числения выполнялись добровольцами в Internet - в течение восьми месяцев трудились 600 человек и 1600 ко м-пьютеров, возможно, самый большой в истории многопроцессорный конгломерат. Трудоемкость вычислений была в диапазоне от 4000 до 6000 mips-лет. Компьютеры соединялись по электронной почте, передавая свои результаты в центральное хранилище, где выполнялся окончательный анализ. В этих вычислениях использов а-лись QS и теория пятилетней давности, NFS мог бы ускорить выполнение расчетов раз в десять [949]. В соо т-ветствии с [66]: "Мы делаем вывод, что широко используемые 512-битовые модули RSA могут быть вскрыты организацией, готовой потратить несколько миллионов долларов и подождать несколько месяцев." По оценкам авторов разложение 512-битового числа в 100 раз более трудоемко при использовании той же техники и только в 10 сложнее при использовании NFS и современной техники [949].

С целью развития искусства разложения на множители RSA Data Security, Inc. в марте 1991 года объявило о

программе RSA Factoring Challenge (состязание RSA по разложению на множители) [532]. Состязание состоит в разложении на множители ряда трудных чисел, каждое из которых является произведением двух простых чисел примерно одинакового размера. Каждое простое число было выбрано конгруэнтным 2 по модулю 3. Всего было предложено 42 числа, по одному числу в диапазоне от 100 до 500 разрядов с шагом 10 разрядов (плюс одно д о-полнительное, 129-разрядное число). К моменту написания этой книги RSA-100, RSA-110, RSA-120, и RSA-129 были разложены на множители, все с помощью QS. Следующим (с помощью NFS) может быть RSA-130, или чемпионы по разложению на множители сразу возьмутся за RSA -140.

Данная область развивается быстро. Технику разложения на множители трудно экстраполировать, так как невозможно предсказать развитие математической теории. До открытия NFS многие считали, что любой метод разложения на множители не может асимптотически быть быстрее QS. Они были неправы.

Предстоящее развитие NFS, по видимому, будет происходить в форме уменьшения константы: 1.923. Для ряда чисел специальной формы, таких как числа Ферма, константа приближается к 1.5 [955, 954]. Если бы для трудных чисел, используемых в сегодняшней криптографии, константу тоже можно было снизить до этого уровня, то 1024-битовые числа раскладывались бы на множители уже сегодня. Одним из способов уменьшить константу является обнаружение лучших способов представления чисел как полиномов с маленькими коэфф и-циентами. Пока еще проблема не изучалась достаточно эффективно, но возможно решающий успех уже близок [949].

Последние результаты программы RSA Factoring Challenge можно узнать, отправив запрос по электронной почте по адресу challenge-info@rsa.com.

Квадратные корни по модулю п

11.5 Генерация простого числа Для алгоритмов с открытыми ключами нужны простые числа. Их нужно множество для… Если каждому понадобится свое простое число, не иссякнет ли у нас запас? Нет. В действительности сущее т-вует…

Solovay-Strassen

(1) Выберите случайно число а, меньшее/;. (2) Если НОД(а,/;) (1, тор не проходит проверку и является составным. (3) Вычислите; = а(р-)12 mod/;.

Lehmann

(1) Выберите случайно число а, меньшее/;. (2) Вычислите арА'2 mod/;. (3) Если арА'2 Ф 1 или -1 (mod p), то р не является простым.

Rabin-Miller

Выберите для проверки случайное число р. Вычислите Ъ - число делений/; - 1 на 2 (т.е., 2Ь - это наибольшая степень числа 2, на которое делится р -… (1) Выберите случайное число а, меньшее/;. (2) Установите; = 0 и z = am mod/;.

Практические соображения

(1) Сгенерируйте случайное и-битовое число/;. (2) Установите старший и младший биты равными 1. (Старший бит гарантирует… (3) Убедитесь, что р не делится на небольшие простые числа: 3, 5, 7, 11, и т.д. Во многих реализациях пров е-ряется…

Сильные простые числа

Наибольший общий делитель p -lnq -l должен быть небольшим. Hp -l,nq -l должны иметь среди своих множителей большие простые числа,… Hp' -l,nq' -l должны иметь среди своих множителей большие простые числа.

Вычисление дискретных логарифмов в конечной группе

— Мультипликативная группа полей простых чисел: G¥(p) — Мультипликативная группа конечных полей степеней 2: GF(2") — Группы эллиптической кривой над конечными полями F: EC(F)

V V

_е(1+0(1))(1п(п))Л(1п((1п(и)))Л

Решето числового поля быстрее, оценка его эвристического времени выполнения:

V V

_е(1.923+0(1))(1п(п))Л(1п((1п(и)))/з

Стивен Полиг (Stephen Pohlig) и Мартин Хеллман нашли способ быстрого вычисления дискретных лог а-рифмов в GF(p) при условии, что р - 1 раскладывается на малые простые множители [1253]. По этой причине в криптографии используются только такие поля, для которых р - 1 обладает хотя бы одним большим простым множителем. Другой алгоритм [14] вычисляет дискретных логарифм со скоростью, сравнимой с разложением на множители, он был расширен на поля вида GF(/) [716]. Этот алгоритм был подвергнут критике в [727] по ряду теоретических моментов. В других статьях [1588] можно увидеть, насколько на самом деле трудна пр о-блема в целом.

Вычисление дискретных логарифмов тесно связано с разложением на множители. Если вы можете решить проблему дискретного логарифма, то вы можете и разложить на множители. (Истинность обратного никогда не была доказана.) В настоящее время существует три метода вычисления дискретных логарифмов в поле простого числа [370, 934, 648]: линейное решето, схема целых чисел Гаусса и решето числового поля.

Предварительное, объемное вычисление для поля должно быть выполнено только один раз. Затем, быстро можно вычислять отдельные логарифмы. Это может серьезно уменьшить безопасность систем, основанных на таких полях. Важно, чтобы различные приложения использовали различные поля простых чисел. Хотя нескол ь-ко пользователей одного приложения могут применять общее поле.

В мире расширенных полей исследователями не игнорируются и GF(2 "). Алгоритм был предложен в [727]. Алгоритм Копперсмита (Coppersmith) позволяет за приемлемое время находить дискретные логарифмы в таких полях как GF(2¹²⁷) и делает принципиально возможным их поиск в полях порядка GF(2⁴⁰⁰) [368]. В его основе лежит [180]. У этого алгоритма очень велика стадия предварительных вычислений, но во всем остальном он хорош и эффективен. Реализация менее эффективной версии этого же алгоритма после семи часов предвар и-тельных вычислений тратила на нахождение каждого дискретного логарифма в поле GF(2 ¹²⁷) лишь несколько

секунд [ИЗО, 180]. (Это конкретное поле, когда-то использовавшееся в некоторых криптосистемах [142, 1631, 1632], не является безопасным.) Обзор некоторых из этих результатов можно найти в [1189, 1039].

Позднее были выполнены предварительные вычисления для полей GF(2 ²²⁷), GF(2³¹³) и GF(2⁴⁰¹), удалось зна­чительно продвинуться и для поля GF(2⁵⁰³). Эти вычисления проводились на nCube-2, массивном параллельном компьютере с 1024 процессорами [649, 650]. Вычисление дискретных логарифмов в поле GF(2 ⁵⁹³) все еще нахо­дится за пределами возможного.

Как и для нахождения дискретных логарифмов в поле простого числа, для вычисления дискретных лог а-рифмов в полиномиальном поле также требуется один раз выполнить предварительные вычисления. Тахер Эль-Джамаль (Taher EIGamal) [520] приводит алгоритм вычисления дискретных логарифмов в поле GF( р²).

Глава 12 Стандарт шифрования данных DES (Data Encryption Standard)

12.1 Введение

Стандарт шифрования данных DES (Data Encryption Standard), который ANSI называет Алгоритмом ши ф-рования данных DEA (Data Encryption Algorithm), a ISO - DEA-1, за 20 лет стал мировым стандартом. Хотя на нем и появился налет старости, он весьма прилично выдержал годы криптоанализа и все еще остается безопа с-ным по отношению ко всем врагам, кроме, возможно, самых могущественных.

Разработка стандарта

Покупатели не знали, что они покупают. Многие небольшие компании изготавливали и продавали крипт о-графическое оборудование, преимущественно… Влияние соответствующего изменения ключей и принципов работы на реальную мощь… В1972 году Национальное бюро стандартов (National Bureau of Standards, NBS), теперь называющееся Н а-циональным…

Принятие стандарта

Две другие группы внутри ANSI, представляющие банковские операции при розничной и оптовой торговле, разработали свои стандарты на основе DES.… Рабочая группа ANSI по безопасности финансовых организаций при розничной… Рабочая группа ANSI по безопасности финансовых организаций при оптовой торговле разработала свой со б-ственный набор…

Проверка и сертификация оборудования DES

NIST также разработал программу сертификации устройств проверки подлинности на соответствие ANSI Х9.9 и FIPS ИЗ. На март 1995 года было… В стандарте DES было оговорено, что он будет пересматриваться каждые пять лет.… NBS и NSA пересмотрели стандарт. В этот раз NSA было задействовано в большей степени. Благодаря по д-писанной Рейганом…

Г

Сдвиг Сдвиг

Перестановка со сжатием

1____ [

Ключ

Рис. 12-2. Один этап DES.

Если Bt - это результат г-ой итерации, Ц и R_t - левая и правая половины В„ К, - 48-битовый ключ для этапа i, a f - это функция, выполняющие все подстановки, перестановки и XOR с ключом, то этап можно представить как:

U = Ri-!

Д,-= Z,,-.! © f№__b £,■)

Начальная перестановка

Начальная перестановка выполняется еще до этапа 1, при этом входной блок переставляется, как показано в 11-й. Эту и все другие таблицы этой главы надо читать слева направо и сверху вниз. Например, начальная пер е-становка перемещает бит 58 в битовую позицию 1, бит 50 - в битовую позицию 2, бит 42 - в битовую позицию 3, и так далее.

Табл. 12-1. Начальная перестановка

58, 50^ 42^ Н 26, 1Л 10, 2, 60^ 52^ 44^36^ 28^ 20, Y2, <Г

62, 54, 46, 38, 30, 22, 14, 6, 64, 56, 48, 40, 32, 24, 16, 8,

57, 49, 41, 33, 25, 17, 9, 1, 59, 51, 43, 35, 27, 19, И, 3,

61, 53, 45, 37, 29, 21, 13, 5, 63, 55, 47, 39, 31, 23, 15, 7

Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES. (Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки да н-ных открытого текста и шифротекста в микросхему DES. Не забывайте, что DES появился раньше 16- и 32-битовых микропроцессорных шин.) Так как программная реализация этой многобитовой перестановки нелегка (в отличие от тривиальной аппаратной), во многих программных реализациях DES начальная и заключител ь-ные перестановки не используются. Хотя такой новый алгоритм не менее безопасен, чем DES, он не соответс т-вует стандарту DES и, поэтому, не может называться DES.

Преобразования ключа

Сначала 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита, как показано в 10-й. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый

подключ.Эти подключи, К„ определяются следующим образом.

Табл. 12-2. Перестановка ключа

57^ 49^ 4, 33^ 25^ П, 9, 1^ 58^ 50^ 42^ 34, 26^ 18^

10, 2, 59, 51, 43, 35, 27, 19, И, 3, 60, 52, 44,36,

63, 55, 47, 39, 31, 23, 15, 7, 62, 54, 46, 38, 30, 22,

14, 6, 61, 53, 45, 37, 29, 21, 13, 5, 28, 20, 12, 4

Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвиг а-ются налево на один или два бита в зависимости от этапа. Этот сдвиг показан в 9-й.

Табл. 12-3. Число битов сдвига ключа в зависимости от этапа

Этап I 2 3 4 5 6 7 8 9 10 П 12 13 14 15 16

Число 1122222212222221

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием.Ее результатом является набор из 48 битов. Перестановка со сжатием (также называемая переставленным выбором) определена в 8-й. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбр а-сывается.

Табл. 12-4. Перестановка со сжатием

4, П, П, 2Д 1^ 5^ 3, 28^ 1Д 6, 2й Щ

23, 19, И, 4,26, 8, 16, 7, 27, 20, 13, 2,

41, 52, 31, 37, 47, 55, 30, 40,51, 45, 33, 48,

44,49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32

Из-за сдвига для каждого подключа используется отличное подмножество битов ключа. Каждый бит испол ь-зуется приблизительно в 14 из 16 подключей, хотя не все биты используются в точности одинаковое число раз.

Перестановка с расширением

Эта операция расширяет правую половину данных, R„ от 32 до 48 битов. Так как при этом не просто повто­ряются определенные биты, но и изменяется их порядок, эта операция называется перестановкой с расшире-нием.У нее две задачи: привести размер правой половины в соответствие с ключом для операции XOR и пол у-чить более длинный результат, который можно будет сжать в ходе операции подстановки. Однако главный криптографический смысл совсем в другом. За счет влияния одного бита на две подстановки быстрее возрастает зависимость битов результата от битов исходных данных. Это называется лавинным эффектом.DES спроек­тирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита о т-крытого текста и каждого бита ключа.

Перестановка с расширением показана на 9-й. Иногда она называется E-блоком(от expansion). Для каждого 4-битового входного блока первый и четвертый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким поз и-циям исходных данных. Например, бит входного блока в позиции 3 переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока.

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16

^х

Nd

v__ у_

У___ У-__ У

У___ У-__ У-

У__ у_

123 4 56789 10 1112131415 16 1718192021 22 2324

Рис. 12-3. Перестановка с расширением.

Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок.

Табл. 12-5. Перестановка с расширением

 

32,	1,	2,	з,	4,	5,	4,	5,	6,	7,	8,	9,
8,	9,	10,	И,	12.,	13,	12,	13,	14,	15,	16,	17,
16,	17,	18,	19,	20,	21,	20,	21,	22,	23,	24,	25,
24,	25,	26,	27,	28,	29,	28,	29,	30,	31,	32,

Подстановка с помощьюS-блоков

После объединения сжатого блока с расширенным блоком с помощью XOR над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки,или S-блоках(от substitution). У каждого S-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. (Для восьми S-блоков DES потребуется 256 байтов памяти.) 48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком: первый подблок - S-блоком 1, вт о-рой - S-блоком 2, и так далее. См. 8-й.

46-битовый вход

32-битовый выход

Рис. 12-4. Подстановка - S-блоки.

Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4-битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение. Все восемь S-блоков показаны в 6-й.

 

						Табл. 12-6. S-блоки
S-блок 1:
14, 4,	13,	1,	2,	15,	И,	8, 3,	10,	6,	12.,	5,	9,	0,	7,
0, 15,	7,	4,	14,	2,	13,	1, Ю,	6,	12.,	И,	9,	5,	з,	8,

4, 1,	14,	8,	13,	6,	2,	И,	15,	12,	9,	7,	з,	10,	5,	0,
15, 12,	8,	2,	4,	9,	1,	7,	5,	И,	з,	14,	10,	о,	6,	13,
S-блок 2:
15, 1,	8,	14,	6,	И,	з,	4,	9,	7,	2,	13,	12,	о,	5,	10,
3, 13,	4,	7,	15,	2,	8,	14,	12,	0,	1,	10,	6,	9,	И,	5,
0, 14,	7,	И,	10,	4,	13,	1,	5,	8,	12,	6,	9,	з,	2,	15,
13, 8,	10,	1,	з,	15,	4,	2,	И,	6,	7,	12,	0,	5,	14,	9,
S-блок 3:
10, 0,	9,	14,	6,	з,	15,	5,	1,	13,	12,	7,	И,	4,	2,	8,
13, 7,	0,	9,	з,	4,	6,	10,	2,	8,	5,	14,	12,	И,	15,	1,
13, 6,	4,	9,	8,	15,	з,	0,	И,	1,	2,	12,	5,	10,	14,	7,
1, 10,	13,	0,	6,	9,	8,	7,	4,	15,	14,	з,	И,	5,	2,	12,
S-блок 4:
7, 13,	14,	з,	о,	6,	9,	10,	1,	2,	8,	5,	И,	12,	4,	15,
13, 8,	И,	5,	6.	15,	0,	з,	4,	7,	2,	12,	1,	10,	14,	9,
10, 6,	9,	0,	12,	И,	7,	13,	15,	1,	з,	14,	5,	2,	8,	4,
3, 15,	0,	6,	10,	1,	13,	8,	9,	4,	5,	И,	12,	7,	2,	14,
S-блок 5:
2, 12,	4,	1,	7,	10,	И,	6,	8,	5,	з,	15,	13,	0,	14,	9,
14, И,	2,	12,	4,	7,	13,	1,	5,	0,	15,	10,	з,	9,	8,	6,
4, 2,	1,	И,	10,	13,	7,	8,	15,	9,	12,	5,	6,	з,	0,	14,
И, 8,	12,	7,	1,	14,	2,	13,	6,	15,	0,	9,	10,	4,	5,	з,
S-блок 6:
12, 1,	10,	15,	9,	2,	6,	8,	0,	13,	з,	4,	14,	7,	5,	И,
10, 15,	4,	2,	7,	12,	9,	5,	6,	1,	13,	14,	0,	И,	з,	8,
9, 14,	15,	5,	2,	8,	12,	з,	7,	0,	4,	10,	1,	13,	И,	6,
4, 3,	2,	12,	9,	5,	15,	10,	И,	14,	1,	7,	6,	о,	8,	13,
S-блок 7:
4, И,	2,	14,	15,	0,	8,	13,	з,	12,	9,	7,	5,	10,	6,	1,
13, 0,	И,	7,	4,	9,	1,	10,	14,	з,	5,	12,	2,	15,	8,	6,
1, 4,	И,	13,	12,	з,	7,	14,	10,	15,	6,	8,	0,	5,	9,	2,
6, И,	13,	8,	1,	4,	10,	7,	9,	5,	0,	15,	14,	2,	з,	12,
S-блок 8:
13, 2,	8,	4,	6,	15,	И,	1,	10,	9,	з,	14,	5,	0,	12,	7,
1, 15,	13,	8,	10,	з,	7,	4,	12,	5,	6,	И,	0,	14,	9,	2,
7, И,	4,	1,	9,	12,	14,	2,	0,	6,	10,	13,	15,	з,	5,	8,
2, 1,	14,	7,	4,	10,	8,	13,	15,	12,	9,	0,	з,	5,	6,	И

Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: Ъ_ъ Ъ₂, Ъ_ъ, Ь₄, Ь₅ и Ь₆. Биты Ъ_х и Ь₆ объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы. Средние 4 бита, с Ь₂ по Ь₅, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу табл и-

цы.

Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют И, что соответствует строке 3 шестого S-блока. Средние 4 бита образ у-ют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся на пересечении строки 3 и столбца 9, - это 14. (Не забывайте, что строки и столбцы нумеруются с 0, а не с 1.) Вместо 110011 подста в-ляется 1110.

Конечно же, намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы, что не является трудной задачей. (Изменить индексы, не изменяя пор я-док элементов, недостаточно. S-блоки спроектированы очень тщательно.) Однако такой способ описания S-блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4-битового элемента: Ь₂ по ^являются входом, а некоторое 4-битовое число - результатом. Биты Ъ_г и Ь₆ опреде­ляются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S-блоке.

Подстановка с помощью S-блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко поддаются анализу. S-блоки нелинейны, и именно они в большей степени, чем все остальное, обеспеч и-вают безопасность DES.

В результате этого этапа подстановки получаются восемь 4-битовых блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью Р-блоков.

Перестановка с помощью Р-блоков

32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с Р-блоком. Эта п е-рестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Позиции, в которые перемещаются биты, показаны в 5-й. Например, бит 21 перемещается в позицию 4, а бит 4 - в позицию 31.

Табл. 12-7. Перестановка с помощью P-блоков

16, Т, 20^ 2й 29^ 2, 28^ П, 1^ 5, 23^ 26^ 5^ 18^ Ъ, W,

2, 8, 24, 14, 32, 27, 3, 9, 19, 13, 30, 6, 22, И, 4,25

Наконец, результат перестановки с помощью Р-блока объединяется посредством XOR с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следу то­щий этап.

Заключительная перестановка

Табл. 12-8. Заключительная перестановка

40, 8^ 48^ 6, 56^ 24^ М, 32^ 39^ Т, 47^ 1Д 55^ 23^ 63^ зТ7

38, 6, 46, 14, 54, 22, 62, 30, 37, 5, 45, 13, 53, 21, 61, 29,

36, 4, 44,12, 52, 20, 60, 28, 35, 3, 43, И, 51, 19, 59, 27,

34, 2, 42, 10, 50, 18, 58, 26, 33, 1, 41, 9, 49, 17, 57, 25

Дешифрирование DES

рирования используется один и тот же алгоритм. DES позволяет использовать для шифрования или дешифрирования блока одну и ту…

Режимы DES

[52]. В мире программного обеспечения сертификация обычно не важна. Из-за своей…

Аппаратные и программные реализации DES

Наиболее выдающейся микросхемой DES является 6868 VLSI (ранее называвшаяся "Gatekeeper" - Вратарь). Она не только может выполнять… Программная реализация DES на мэйнфрейме IBM 3090 может выполнить 32000…

Табл. 12-9. Коммерческие микросхемы DES

 

Производитель	Микросхема	Год	Тактовая частота	Скорость данных	Доступность
AMD	Am9518		3 МГц	1.3 Мбайт/с	Н
AMD	Am9568	?	4 МГц	1.5 Мбайт/с	Н
AMD	AmZ8068		4 МГц	1.7 Мбайт/с	Н
AT&T	T7000A		?	1.9 Мбайт/с	Н
CE-Infosys	SuperCrypt CE99C003		20 МГц	12.5 Мбайт/с	д
CE-Infosys	SuperCrypt CE99C003A		30 МГц	20.0 Мбайт/с	д
Cryptech	Cryl2C102		20 МГц	2.8 Мбайт/с	д
Newbridge	CA20C03A		25 МГц	3.85 Мбайт/с	д
Newbridge	CA20C03W		8 МГц	0.64 Мбайт/с	д
Newbridge	CA95C68/18/0		33 МГц	14.67 Мбайт/с	д
Pijnenburg	PCC100	?	?	2.5 Мбайт/с	д
Semaphore	Roadranner284	?	40 МГц	35.5 Мбайт/с	д
Communications

VLSI Technology	VM007		32 МГц	200.0 Мбайт/с	Д
VLSI Technology	VM009		33 МГц	14.0	д
VLSI Technology			32 МГц	64.0 Мбайт/с	д
Western Digital	WD2001/2002		3 МГц	0.23 Мбайт/с	н

Табл. 12-10. Скорости DES на различных микропроцессорах и компьютерах

Процессор

 

Скорость (в МГц)	Блоки DES (в с)
4.7
7.6

Sun ELC26000
HyperSparc 32000

RS6000-350 53000

Sparc 10/52 84000

DEC Alpha 4000/610 154000

HP9000/887 125 196,000

12.3 Безопасность DES

Люди давно интересуются безопасностью DES [458]. Было много рассуждений о длине ключа, количестве итераций и схеме S-блоков. S-блоки были наиболее таинственными - какие-то константы, без видимого объя с-нения для чего и зачем они нужны. Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко-лет интенсивного криптоанализа, некоторые люди опасались, что NSA вставило в алгоритм лазейку, которая позволит агентству легко дешифрировать перехваченные соо бщения.

Комитет по разведке Сената США чрезвычайно тщательно расследовал этот вопрос в 1978 году. Результаты работы комитета были засекречены, но в открытых итогах этого расследования с NSA были сняты все обвин е-ния в неуместном вмешательстве в проектирование алгоритма [1552]. "Было сказано, что NSA убедило IBM в достаточности более короткого ключа, косвенно помогло разработать структуры S-блоков и подтвердило, что в окончательном варианте DES, с учетом всех знаний NSA, отсутствовали статистические или математические бреши " [435]. Однако, так как правительство не опубликовало подробности расследования, многих людей уб е-дить не удалось.

Тачмен (Tuchman) и Майер (Meyer), разработавшие DES криптографы IBM, заявили, что NSA не изменяло проект [841]:

Их основным подходом был поиск сильных подстановок, перестановок и функций планирования ключей. . . . IBM по просьбе NSA засекретило информацию, касающуюся критериев выбора. ... "NSA сообщило нам, что мы самостоятельно зан о-во открыли ряд секретов, используемых для создания их собственных алгоритмов", - об ъясняет Тачмен.

Позже в одной из статей Тачмен писал: "Алгоритм DES был полностью разработан внутри IBM ее сотру д-никами. NSA не продиктовало ни единой связи!" Тачмен подтвердил это утверждение в своем докладе по ист о-рии DES на Национальной конференции по компьютерной безопасности (National Computer Security Conference)

в 1992 году.

С другой стороны, Копперсмит писал [373, 374]: "Агентство национальной безопасности (NSA) также пом о-гало IBM техническими советами." А Конхейм (Konheim) утверждал: "Мы послали S-блоки в Вашингтон. Они вернулись полностью переработанными. Мы проверили их, и они прошли нашу проверку." На этот факт и ее бе­леются как на доказательство, что NSA вставило лазейку в DES. По вопросу о каком-либо преднамеренном о с-лаблении DES NSA заявило [363]:

Относительно Стандарта шифрования данных (DES) мы считаем, что ответ на ваш вопрос о роли NSA в разработке DES содержится в опубликованных итогах расследования Комитета Сената по разведке, проведенного в 1978 году. В сообщении Комитета указывается, что NSA никоим образом не искажало алгоритм, и что безопасность, предоставляемая DES для несе к-ретных данных, с целью защиты которых он и был разработан, была более чем адекватна в течение по крайней мере 5-10 лет. Короче говоря, NSA не вносило и не пыталось вносить никаких ослаблений в алгоритм DES.

Тогда почему они изменили S-блоки? Может быть, чтобы гарантировать, что лазейка не будет встроена в DES самой IBM. У NSA не было причин доверять исследователям IBM, и оно могло решить, что не до конца исполнит свой долг, если не обеспечит отсутствие лазеек в DES. Задание S-блоков и могло быть одним из сп о-собов гарантировать это.

Совсем недавно новые результаты криптоанализа прояснили этот вопрос, который в течение многих лет был предметом спекуляций.

Слабые ключи

Из-за того, что первоначальный ключ изменяется при получении подключа для каждого этапа алгоритма, определенные первоначальные ключи являются слабыми[721, 427]. Вспомните, первоначальное значение расщепляется на две половины, каждая из которых сдвигается независимо. Если все биты каждой половины равны 0 или 1, то для всех этапов алгоритма используется один и тот же ключ. Это может произойти, если ключ состоит из одних 1, из одних 0, или если одна половина ключа состоит из одних 1, а другая - из одних 0. Кроме того, у два слабых ключа обладают другими свойствами, снижающими их безопасность [427].

Четыре слабых ключа показаны в шестнадцатиричном виде в 1-й. (Не забывайте, что каждый восьмой бит -это бит четности.)

Табл. 12-11. Слабые ключи DES

0101 1F1F E0E0 FEFE

Значение слабого ключа (с битами четности) Действительный ключ

0101 0101 0101 0000000 0000000

IF IF 0E0E 0E0E 0000000 FFFFFFF

E0E0 F1F1 F1F1 FFFFFFF 0000000

FEFE FEFE FEFE FFFFFFF FFFFFFF

Кроме того, некоторые пары ключей при шифровании переводят открытый текст в идентичный шифротекст. Иными словами, один из ключей пары может расшифровать сообщения, зашифрованные другим ключом пары. Это происходит из-за метода, используемого DES для генерации подключей - вместо 16 различных подключей эти ключи генерируют только два различных подключа. В алгоритме каждый из этих подключей используется восемь раз. Эти ключи, называемые полуслабыми ключами,в шестнадцатиричном виде приведены в 0-й.

Табл. 12-12. Полуслабые пары ключей DES

01FE 1FE0 01Е0 1FFE 011F E0FE

 

01FE	01FE	01FE	и	FE01	FE01	FE01	FE01
1FE0	0EF1	0EF1	и	E01F	E01F	F10E	F10E
01Е0	01F1	01F1	и	Е001	Е001	F101	F101
IEEE	0EFE	0EFE	и	FE1F	FE1F	FE0E	FE0E
011F	010Е	010E	и	1F01	1F01	0Е01	0Е01
E0FE	FIFE	FIFE	и	FEE0	FEE0	FEE1	FEE1

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

Эти возможно слабые ключиперечислены в -1-й.

Табл. 12-13. Возможно слабые ключи DES

 

IF

IF

OE

OE

EO

EO

Fl

Fl

IF

IF

OE

OE

FE

IF

EO

FE

OE

Fl

IF

IF

OE

OE

FE

IF

EO

FE

OE

Fl

IF

IF

OE

OE

EO

IF

IF

EO

Fl

OE

OE

Fl

Е0

EO

Fl

Fl

FE

FE

FE

FE

FE

FE

FE

FE

EO

IF

FE

Fl

OE

FE

FE

EO

IF

FE

Fl

OE

EO

IF

FE

Fl

OE

FE

Е0

FE

IF

Fl

FE

OE

FE

IF

IF

FE

FE

OE

OE

FE

FE

EO

IF

FE

Fl

OE

IF

FE

EO

OE

FE

Fl

Е0

FE

IF

Fl

FE

OE

FE

IF

EO

FE

OE

Fl

ЕО

EO

IF

IF

Fl

Fl

OE

OE

IF

EO

FE

OE

Fl

FE

FE

FE

IF

IF

FE

FE

OE

OE

EO

IF

FE

Fl

OE

FE

FE

IF

EO

FE

OE

Fl

EO

EO

Fl

Fl

ЕО

IF

FE

Fl

OE

FE

IF

IF

EO

EO

OE

OE

Fl

Fl

FE

EO

IF

FE

Fl

OE

IF

FE

EO

OE

FE

Fl

ЕО

FE

IF

Fl

FE

OE

IF

FE

EO

OE

FE

Fl

EO

EO

Fl

Fl

IF

EO

FE

OE

Fl

FE

IF

FE

EO

OE

FE

FO

IF

EO

FE

OE

Fl

FE

IF

EO

FE

OE

Fl

FE

FE

FE

FE

FE

FE

FE

FE

FE

IF

IF

FE

FE

OE

OE

FE

FE

IF

EO

EO

IF

OE

Fl

Fl

OE

FE

FE

EO

EO

FE

FE

Fl

Fl

FE

EO

IF

FE

Fl

OE

EO

FE

FE

EO

Fl

FE

FE

Fl

EO

FE

IF

Fl

FE

OE

FE

EO

EO

FE

FE

Fl

Fl

FE

IF

FE

FE

IF

OE

FE

FE

OE

EO

EO

FE

FE

Fl

Fl

FE

FE

Прежде, чем порицать DES слабые ключи, обратите внимание на то, что эти 64 ключа - это крошечная часть полного набора из 72057594037927936 возможных ключей. Если вы выбираете ключ случайно, вероятность выбрать один из слабых ключей пренебрежимо мала. Если вы настоящий параноик, можете всегда проверять "на слабость" сгенерированный ключ. Некоторые думают, что нечего и беспокоиться на этот счет. Другие у т-верждают, что проверка очень легка, почему бы ее и не в ыполнить.

Дальнейший анализ слабых и полуслабых ключей приведен в [1116]. Других слабых ключей в процессе и с-следований найдено не было.

Ключи-дополнения

Ек{Р) = С EK{F) = С" В этом нет ничего таинственного. На каждом этапе после перестановки с расширением подключи подверг а-ются операции XOR…

Алгебраическая структура

264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предоставляет нам 2 56 (приблизительно 1017) таких отображений. Использование… Если бы DES был замкнутым,то для любых Кг и К2 всегда существовало бы такое… ЕК2(ЕК1(Р)) = ЕКз(Р)

Количество этапов

В течение многих лет версии DES с уменьшенным числом этапов успешно вскрывались. DES с тремя и ч е-тырьмя этапами был легко взломан в 1982 году…

Проектирование S-блоков

С момента появления алгоритма для анализа схемы и работы S-блоков были предприняты значительные усилия. В середине 70-х Lexar Corporation [961, 721]… В DES были найдены структуры, несомненно вставленные для повышения… С другой стороны этот доклад также содержал следующее предупреждение:

Дополнительные результаты

12.4 Дифференциальный и линейный криптоанализ

Дифференциальный криптоанализ

Дифференциальный криптоанализ работает с парами шифротекстов,открытые тексты которых содержат определенные отличия. Метод анализирует эволюцию этих… через этапы DES при шифровании одним и тем же ключом. Просто выберем пару открытых текстов с фиксированным различием. Можно выбрать два открытых текста случайным образом,…

Рис. 12-5. Функция этапа DES.

Взглянем на последний этап DES. (При дифференциальном криптоанализе начальная и заключительная п е-рестановки игнорируются. Они не влияют на вскрытие, только затрудняя объяснение.) Если мы сможем опред е-лить К₁₆, то мы получим 48 битов ключа. (Не забывайте, на каждом этапе подключ состоит из 48 битов 56-битового ключа.) Оставшиеся 8 битов мы можем получить грубым взломом. К₁₆ даст нам дифференциальный криптоанализ.

Определенные различия пар открытых текстов обладают высокой вероятностью вызвать определенные ра з-личия получаемых шифротекстов. Эти различия называются характеристиками.Характеристики распростра­няются на определенное количество этапов и по существу определяют прохождение этих этапов. Существуют входное различие, различие на каждом этапе и выходное различие - с определенной вероятностью.

Эти характеристики можно найти, создав таблицу, строки которой представляют возможные входы XOR (XOR двух различных наборов входных битов), столбцы - возможные результаты XOR, а элементы - сколько раз конкретный результат XOR встречается для заданного входа XOR. Такую таблицу можно сгенерировать для каждого из восьми S-блоков DES.

Например, на 6-йа показана характеристика одного этапа. Входное различие слева равно L, оно может быть произвольным. Входное различие справа равно 0. (У двух входов одинаковая правая половина, поэтому их ра з-личие - 0.) Так как на входе функции этапа нет никаких различий, то нет различий и на выходе функции этапа. Следовательно, выходное различие левой части - L © 0 = L, а выходное различие правой части - 0. Это трив и-альная характеристика, она истинна с вероятностью 1.

На 6-йб показана менее очевидная характеристика. Снова, различие L левых частей произвольно. Входное различие правых частей равно 0x60000000, два входа отличаются только первым и третьим битами. С вероя т-ностью 14/64 различие на выходе функции этапа равно L © 0x00808200. Это означает, что выходное различие левых половин равно L © 0x00808200, а выходное различие правых половин - 0x60000000 (с вероятностью 14/64)

A = L

К,

Т ___ I___

ДХ------ / <*--------

А = 0--------- А = 0

A = L®0

_д = 0

_д = 0

A = L

т

А = У

тА = /-©0

/

К,

А = Х

А = Х

А = Х

Х= 0x60000000 У = 0x00808200

С вероятностью (а)

С вероятностью 14/64 (Ь)

Рис. 12-6. Характеристики DES.

Различные характеристики можно объединять. Также, при условии, что этапы независимы, вероятности м о-гут перемножаться. На 5-й объединяются две ранее описанных характеристики. Входное различие слева равно 0x00808200, а справа - 0x60000000. В конце первого этапа входное различие и результат функции этапа нейтр а-лизуют друг друга, и выходное различие равно 0. Это различие поступает на вход второго этапа, окончательное выходное различие слева равно 0x60000000, а справа - 0. Вероятность этой двухэтапной характерист ики - 14/64.

A= Y т Ф

К,

<*-------- / +--------------

А= У--------- А=Х

А = Х

А = Х

А = Х

*----------------- / ■*--------------------------------

_д = 0--------- д = 0

А = Х

A = Y

Х= 0x60000000 У = 0x00808200

С вероятностью 14/64 (Ь)

Рис. 12-7. Двухэтапная характеристика DES.

Пара открытых текстов, соответствующих характеристике, называется правильной парой, а пара открытых текстов, несоответствующих характеристике - неправильной парой. Правильная пара подсказывает правильный ключ этапа (для последнего этапа характеристики), неправильная пара - случайный ключ этапа.

Чтобы найти правильный ключ этапа, нужно просто собрать достаточное количество предположений. Один

из подключен будет встречаться чаще, чем все остальные. Фактически, правильный подключ возникнет из всех случайный возможных подключей.

Итак, дифференциальное основное вскрытие п-этапного DES дает 48-битовый подключ, используемый на этапе п, а оставшиеся 8 битов ключа получаются с помощью грубого взлома.

Но ряд заметных проблем все же остается. Во первых, пока вы не перейдете через некоторое пороговое зн а-чение, вероятность успеха пренебрежимо мала. То есть, пока не будет накоплено достаточное количество да н-ных, выделить правильный подключ из шума невозможно. Кроме того, такое вскрытие не практично. Для хр а-нения вероятностей 2⁴⁸ возможных ключей необходимо использовать счетчики, и к тому же для вскрытия п о-требуется слишком много данных.

Бихам и Шамир предложили свой способ вскрытия. Вместо использования 15-этапной характеристики 16-этапного DES, они использовали 13-этапную характеристику и ряд приемов для получения последних нескол ь-ких этапов. Более короткая характеристика с большей вероятностью будет работать лучше. Они также испол ь-зовали некоторые сложные математические приемы для получения вероятных 56-битовых ключей, которые и проверялись немедленно, таким образом устранялась потребность в счетчиках. Такое вскрытие достигает yen e-ха, как только находится правильная пара. Это позволяет избежать порогового эффекта и получить линейную зависимость для вероятности успеха. Если у вас в 1000 раз меньше пар, то вероятность успеха в 1000 раз мен ь-ше. Это звучит ужасно, но это намного лучше, чем порог. Всегда есть некоторая вероятность немедленной уд а-чи.

Результаты являются весьма интересными. В -2-й проведен обзор лучших дифференциальных вскрытий DES с различным количеством этапов [172]. Первый столбец содержит количество этапов. Элементы следующих двух столбца представляют собой количество выбранных или известных открытых текстов, которые должны быть проверены для вскрытия, а четвертый столбец содержит количество действительно проанализированных открытых текстов. В последнем столбце приведена сложность анализа, после обнаружения требуемой пары.

Табл. 12-14. Вскрытие с помощью дифференциального криптоанализа

Количество Выбранные открытые Известные открытые Проанализированные Сложность

 

этапов	тексты	тексты	открытые тексты	анализа
		^38
		^44		232f
	?24	?43	?14	?15
И	?31	?47		232f
	?31	?47	?21	?21
	?39	?52		232f
	?39	?51	?29	?29
	?47	^56		?37
	?47	?55	^36	?37

t Сложность анализа для этих вариантов может быть значительно уменьшена за счет использования примерно в четыре раза большего количество открытых текстов и метода группировок.

Наилучшее вскрытие полного 16-этапного DES требует 2⁴⁷ выбранных открытых текстов. Можно преобразо­вать его к вскрытию с известным открытым текстом, но для него потребуется уже 2 ⁵⁵ известных открытых тек­стов. При анализе потребуется 2³⁷ операций DES.

Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными S-блоками. Эффективность вскрытие сильно зависит от структуры S-блоков, блоки DES по счастливой случайн о-сти были оптимизированы против дифференциального криптоанализа. Для всех режимов работы DES - ЕСВ, СВС, CFB и OFB - вскрытие с дифференциальным криптоанализом имеет одинаковую сложность [172].

Устойчивость DES может быть повышена путем увеличения количества этапов. Дифференциальный кри п-тоанализ с выбранным открытым текстом для DES с 17 или 18 этапами потребует столько же времени, сколько нужно для вскрытия грубой силой [160]. При 19 и более этапах дифференциальный криптоанализ становится невозможным, так как для него потребуется более, чем 2 ^м выбранных открытых текстов - не забудьте, DES ис­пользует блоки размером 64 битов, поэтому для него существует только 2 ^м возможных открытых текстов. (В общем случае, вы можете доказать устойчивость алгоритма к дифференциальному криптоанализу, показав, что количество открытых текстов, необходимых для выполнения вскрытия, превышает количество возможных о т-крытых текстов.)

Нужно отметить ряд важных моментов. Во первых, это вскрытие в значительной степени теоретическое. О г-ромные требования к времени и объему данных, необходимых для выполнения вскрытия с помощью дифф е-ренциального криптоанализа, находятся почти для всех вне пределов досягаемости. Чтобы получить нужные данные для выполнения такого вскрытия полного DES, вам придется почти три года шифровать поток выбра н-ных шифротекстов 1.5 Мегабит/с. Во вторых, это в первую очередь вскрытие с выбранным открытым текстом. Оно может быть преобразовано к вскрытию с известным открытым текстом, но вам придется просмотреть все пары "открытый текст/шифротекст" в поисках полезных. В случае полного 16-этапного DES это делает вскр ы-тие чуть менее эффективным по сравнению с грубой силой (вскрытие дифференциальным криптоанализом тр е-бует 2^55Л операций, а вскрытие грубой силой - 2⁵⁵). Таким образом, правильно реализованный DES сохраняет устойчивость к дифференциальному криптоанализу.

Почему DES так устойчив к дифференциальному криптоанализу? Почему S-блоки оптимизированы так, что усложняют такое вскрытие насколько возможно? Почему используется ровно столько, а не больше этапов? П о-тому что создатели DES знали о дифференциальном анализе. Дон Копперсмит из IBM недавно писал [373, 374]:

При проектировании использовались преимущества определенных криптоаналитических методов, особенно метода "дифференциального криптоанализа", который не был опубликован в открытой литературе. После дискуссий с NSA было р е-шено, что раскрытие процесса проектирования раскроет и метод дифференциального криптоанализа, мощь которого может быть использована против многих шифров. Это, в свою очередь, сократило бы преимущество Соединенных Штатов перед другими странами в области криптографии.

Ади Шамир откликнулся, предложив Копперсмиту признаться, что с тех пор ему не удалось найти эффе к-тивного способа вскрытия DES. Копперсмит предпочел отмолчат ься [1426].

Криптоанализ со связанными ключами

Криптоанализ со связанными ключамипохож на дифференциальный криптоанализ, но он изучает разл и-чие между ключами. Вскрытие отличается от любого из… Модифицированный DES, в котором ключ сдвигается на два бита после каждого… Такое вскрытие также не реализуемо на практике, но оно интересно по трем причинам. Во первых, это пе р-вая попытка…

Линейный криптоанализ

Это означает, что если вы выполните операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над… Как определить хорошее линейное приближение для DES? Найдите хорошие… Если линейные приближения не смещены, то они будут выполняться для 32 из 64 возможных входов. Я и з-

Рис. 12-8. 1-этапное линейное приближение для DES.

Способ, которым можно объединить линейные приближения для различных этапов, похож на тот, который обсуждался для дифференциального криптоанализа. На 3-й показано 3-этапное линейное приближение с веро­ятностью 1/2+0.0061. Качество отдельных приближений различно: последнее очень хорошо, первое достаточно хорошо, а среднее - плохо. Но вместе эти три 1-этапных приближения дают очень хорошее трехэтапное пр и-ближение.

A

Км ,26

к,+1,26

К/,26

A

Л=[3,8, 14, 25] В=[8,14, 25]

С вероятностью 1/2+6.1*10^-3

Рис. 12-9. 3-этапное линейное приближение DES.

Базовое вскрытие должно использовать наилучшее линейное приближение для 16-этапного DES. Для него требуется 2⁴⁷ известных открытых блоков, а результатом вскрытия является 1 бит ключа. Это не очень полезно. Если вы поменяете местами открытый текст и шифротекст и используете дешифрирование вместе с шифров а-нием, вы сможете получить 2 бита. Это все еще не очень полезно.

Существует ряд тонкостей. Используйте 14-этапное линейное приближение для этапов с 2 по 15. Попробуем угадать 6 битов подключа для S-блока 5 первого и последнего этапов (всего, таким образом, 12 битов ключа). Для эффективности выполняем линейный криптоанализ параллельно 2 ^п раз и выбираем правильный вариант, основываясь на вероятностях. Это раскрывает 12 битов и Ь₂₆, а поменяв местами открытый текст и шифротекст мы получим еще 13 битов. Для получения оставшихся 30 битов используйте исчерпывающий поиск. Существ у-ют и друге приемы, но описанный является основным.

При вскрытии таким образом полного 16 этапного DES ключ будет раскрыт в среднем с помощью 2 ⁴³ из­вестных открытых текстов. Программная реализации этого вскрытия, работая на 12 рабочих станциях НР9735, раскрыла ключ DES за 50 дней [1019]. В момент написания этой книги это наиболее эффективный способ вскрытия DES.

Линейный криптоанализ сильно зависит от структуры S-блоков, оказалось, что S-блоки DES не оптимизир о-ваны против такого способа вскрытия. Действительно, смещение в S-блоках, выбранных для DES, находится между 9 и 16 процентами, что не обеспечивает надежной защиты против линейного криптоанализа [1018]. С о-гласно Дону Копперсмиту [373, 374] устойчивость к линейному криптоанализу "не входило в число критериев проектирования DES". Либо разработчикам не было известно о линейном криптоанализе, либо при проектир о-вании они отдали преимущество устойчивости против известного им еще более мощного средства вскрытия.

Линейный криптоанализ новее, чем дифференциальный, и в ближайшее время возможно дальнейшее пр о-движение в этом направлении. Некоторые идеи выдвинуты в [1270, 811], но не ясно, можно ли их эффективно применить против полного DES. Однако они очень хорошо работают против вариантов с уменьшенным числом этапов.

Дальнейшие направления

Другим способом вскрытия является дифференциально-линейный криптоанализ - объединение дифференц и-ального и линейного криптоанализа. Сьюзен Лангфорд… Но этот метод нов, и работа продолжается. В ближайшие годы возможны заметные… 12.5 Реальные критерии проектирования

Многократный DES

Шифрование           …   =5  

Рис. 12-10. Трехкратный DES.

DES с независимыми подключами

Другой возможностью является использование различных подключен на каждом этапе, не создавая их из одного 56-битового ключа [851]. Так как на каждом из 16 этапов используется 48 битов ключа, то длина ключа для такого варианта составит 768 битов. Такой вариант резко увеличивает сложность вскрытия алгоритма гр у-бой силой, сложность такого вскрытия составит 2⁷⁶⁸.

Однако возможно использование вскрытия "встреча посередине" (см. раздел 15.1). Сложность такого вскр ы-тия уменьшается до 2³⁸⁴, что, тем не менее, вполне достаточно для обеспечения любой мыслимой безопасн ости.

Хотя независимые подключи мешают линейному криптоанализу, этот вариант чувствителен к дифференц и-альному криптоанализу и может быть вскрыт с помощью 2⁶¹ выбранных открытых текстов (см. -3-й) [167, 172]. По видимому, никакая модификация распределения ключей не сможет н амного усилить DES.

DESX

DESX - это вариант DES, разработанный RSA Data Security, Inc., и включенный в 1986 году в программу обеспечения безопасности электронной почты MailSafe, а в 1987 году в набор BSAFE. DESX использует метод, называемый отбеливанием (см. раздел 15.6), для маскировки входов и выходов DES. Кроме 56-битового ключа DES в DESX используется дополнительный 64-битовый ключ отбеливания. Эти 64 бита используются для в ы-полнения операции XOR с блоком открытого текста перед первым этапом DES. Дополнительные 64 бита, я в-ляющиеся результатом применения однонаправленной функции к полному 120-битовому ключу DESX, испол ь-зуются для выполнения XOR с шифротекстом, полученным в результате последнего этапа [155]. По сравнению с DES отбеливание значительно повышает устойчивость DESX к вскрытию грубой силой, вскрытие требует (2¹²> операций при п известных открытых текстах. Также повышается устойчивость к дифференциальному и линейному криптоанализу, для вскрытия потребуется 2⁶¹ выбранных и 2⁶⁰ известных открытых текстов, соот­ветственно [1338].

CRYPT(3)

CRYPT(3) представляет собой вариант DES, используемый в системах UNIX. Он в основном используется в качестве однонаправленной функции для паролей, но иногда может быть использован и для шифрования. Ра з-личие между CRYPT(3) и DES состоит в том, что в CRYPT(3) включена независимая от ключа перестановка с расширением с 2¹² вариантами. Это сделано для того, чтобы для создания аппаратного устройства вскрытия паролей нельзя было использовать промышленные микросхемы DES.

Обобщенный DES

На 1-й показана поблочная диаграмма GDES. GDES работает с блоками открытого текста переменной дл и-ны. Блоки шифрования делятся на q 32-битовых…

К,

к₂

УптпУпУп f !

tt? tb₄ щ У< —^- к,

к_п

 

вГ		еп(2)		еп(3)		вУ]		в>>
	Шифротекст

Рис. 12-11. GDES.

Функция f для каждого этапа рассчитывается один раз для крайнего правого блока. Результат при помощи операции XOR объединяется со всеми остальными частям, которые затем циклически смещаются направо. GDES использует переменное число этапов п. В последний этап внесено незначительное изменение, чтобы пр о-цессы шифрования и дешифрирования отличались только порядком подключей (точно также, как в DES). Де й-ствительно, если q = 2 и п = 16, то описанный алгоритм превращается в DES.

Бихам и Шамир [167, 168] показали, что дифференциальный криптоанализ вскрывает GDES с q = 8 и п = 16 с помощью всего шести выбранных открытых текстов. При использовании независимых подключей требуется 16 выбранных открытых текстов. GDES с# = 8ий = 22 вскрывается с помощью всего 48 выбранных открытых текстов, а для вскрытия GDES с g = 8 и и = 31 требуется всего 500000 выбранных открытых текстов. Даже GDES с# = 8ий = 64 слабее, чем DES - для его вскрытия нужно только 249 выбранных открытых текстов. Действительно, любая более быстрая, чем DES, схема GDES является также и менее безопасной (см. -3-й).

Недавно появился еще один вариант этой схемы [1591]. Возможно он не более безопасен, чем оригинальный GDES. Общем случае любой вариант DES с большими блоками, который быстрее DES, скорее всего менее безопасен по сравнению с DES.

DES с измененными S-блоками

Другие модификации DES связаны с S-блоками. В некоторых проектах используется переменный порядок S-блоков. Другие разработчики меняют содержание самих S-блоков. Бихам и Шамир показали [170,172], что построение S-блоков и даже их порядок оптимальны с точки зрения устойчивости к дифференциальному кри п-тоанализу:

Изменение порядка восьми S-блоков DES (без изменения их значений) также значительно ослабляет DES: DES с 16 эт а-пами и конкретным измененным порядком вскрывается примерно за 2 ³⁸ шагов. ... Доказано, что DES со случайными S-блоками вскрыть очень легко. Даже минимальное изменение одного из элементов S_6jiokob DES может снизить устойч и-

вость DES к вскрытию.

S-блоки DES не были оптимизированы против линейного криптоанализа. Существуют и лучшие S-блоки, чем предлагаемые в DES, но бездумная замена S-блоков новыми - не самая лучшая идея.

В -3-й [167, 169] перечислены некоторые модификации DES и количество выбранных открытых текстов, нужное для выполнения дифференциального криптоанализа. В таблицу не включена одна из модификаций, об ъ-единяющая левую и правую половины с помощью сложения по модулю 24 вместо XOR, ее в 2 ¹⁷ раз труднее вскрыть, чем DES [689].

RDES

RDES - это модификация, в которой в конце каждого этапа обмениваются местами правая и левая половины с использованием зависимой от ключа перестановки [893]. Обмены местами фиксированы и зависят только от ключа. Это означает, что может быть 15 обменов, зависимых от ключа, и 2 ¹⁵ возможных вариантов, а также что эта модификация не устойчива по отношению к дифференциальному криптоанализу [816, 894, 112]. У RDES большое количество слабых ключей. Действительно, почти каждый ключ слабее, чем типичный ключ DES. И с-пользовать эту модификацию нельзя.

Лучшей является идея выполнять обмен местами только в пределах правой половины и в начале каждого этапа. Другой хорошей идеей является выполнение обмена в зависимости от входных данных, а не как статич е-ской функции ключа. Существует множество возможных вариантов [813, 815]. В RDES-1 используется завис я-щая от данных перестановка 16-битовых слов в начале каждого этапа. В RDES-2 применяется зависящая от данных перестановка байтов в начале каждого этапа после 16-битовых перестановок, аналогичных RDES-1. Развитием этой идеи является RDES-4, и т.д. RDES-1 устойчив и к дифференциальному [815], и к линейному криптоанализу [1136]. По видимому, RDES-2 и последующие варианты достаточно хороши.

Табл. 12-15. Вскрытия вариантов DES с помощью дифференциального криптоашлиза

Изменение работы Количество выбранных

открытых текстов

Полный DES (без изменений) Y¹

Р-перестановка Не может усилить

Тождественная перестановка 2¹⁹

Порядок S-блоков 2³⁸

Замена XOR сложениями 2³⁹, 2³¹

S-блоки

218 - 220 233 - 241 ?33 ^44

Случайные

Случайные перестановки

Одноэлементные

Однородные таблицы

Удаление Е-расширения

Порядок Е-расширения и XOR подключа

GDES (ширина q=8)

16 этапов 6, 16

64 этапа 2⁴⁹ (независимый ключ)

FDES

Группа корейских исследователей под руководством Кванджо Кима (Kwangjo Kim) попыталась найти набор S-блоков, оптимально устойчивых и против дифференциального, и против линейного криптоанализа. Их первая попытка, известная как /DES, представленная в [834], оказалась, как было показано в [855, 858], менее усто й-чивой, чем DES, против дифференциального криптоанализа. Следующий вариант, s³DES, был представлен в [839] и оказался менее устойчив, чем DES, к линейному криптоанализу [856, 1491, 1527, 858, 838]. Бихам пре д-

ложил незначительно изменить алгоритм, чтобы сделать ,³DES безопасным по отношению и к дифференциаль­ному, и к линейному криптоанализу [165]. Исследователи вернулись к своим компьютерам и разработали улу ч-шенную технику проектирования S-блоков [835, 837]. Они предложили /DES [836], а затем /DES [838, 944].

В -4-й приведены для s3DES (с обращенными S-блоками 1 и 2), которые безопасны по отношению к обоим видам криптоанализа. Использование этого варианта вместе с трехкратным DES наверняка помешает крипто а-нализу.

DES с S-блоками, зависящимиот ключа

Линейный и дифференциальный криптоанализ работают только, если аналитику известно строение S-блоков. Если S-блоки зависят от ключа и выбираются криптографически сильным методом, то линейный и диффере н-циальный криптоанализ значительно усложнятся. Хотя надо помнить, что даже у хранящихся в секрете случа й-но созданных S-блоков очень плохие дифференциальные и линейные характеристики.

Табл. 12-16. S-блоки S3DES (с обращенными S-блоками 1 и 2)

 

S-блок 1:
13 14							И
8 2	И
14 9											И
			И
S-блок 2:
15 8								И
6 15										И
9 14			2,									И
10 5											И
S-блок З:
13 3	И
4 13						и
		И
1 И
S-блок 4:
		И	12,
5 10									И
10 7						И
3 9														И
S-блок 5:
5 15														И
6 9												И
15 0								И
12 5										И
S-блок 6:
43												И
14 13	И
13 0													И
1 7			И

S-блок 7:

4 10

И

10 15

И

2 12

И

12 6

И

S-блок 8:

13 10

И

И

4 13

И

8 И

Вот как можно использовать 48 дополнительных битов ключа для создания S-блоков, устойчивых как к л и-нейному, так и к дифференциальному криптоанализу [165].

(1) Изменить порядок S-блоков DES: 24673158.

(2) Выбрать 16 из оставшихся битов ключа. Если первый бит 1, обменять местами первые и последние два ряда S-блока 1. Если второй бит 1, обменять местами первые и последние восемь столбцов S-блока По­вторить то же самое для третьего и четвертого битов и S-блока 2. Повторить то же самое для S-блоков с 3 по 8.

(3) Взять оставшиеся 32 бита ключа. Выполнить XOR первых четырех битов с каждым элементом S-блока 1, XOR следующих четырех битов с каждым элементом S-блока 2, и так далее.

Сложность вскрытия такой системы с помощью дифференциального криптоанализа составит 251, с пом о-щью линейного криптоанализа - 2⁵³. Сложность исчерпывающего перебора составит 2102.

Что хорошо в этом варианте DES так это то, что он может быть реализован в существующей аппаратуре. Различные поставщики микросхем DES продают микросхемы DES с возможностью загрузки S-блоков. Можно реализовать любой способ генерации S-блоков вне микросхемы и затем загрузить их в нее. Для дифференц и-ального и линейного криптоанализа нужно так много известных или выбранных открытых текстов, что эти сп о-собы вскрытия становятся неосуществимыми. Вскрытие грубой силой также трудно себе представить, не пом о-жет никакое увеличение скорости.

12.7 Насколько безопасен сегодня DES?

Ответ одновременно и прост, и труден. При простом ответе учитывается только длина ключа (см. раздел 7.1). Машина для вскрытия DES грубой силой, способная найти ключ в среднем за 3.5 часа, в 1993 году стоила 1 миллион долларов [1597, 1598]. DES используется очень широко, и наивно было бы предполагать, что NSA и аналогичные организации в других странах не построили по такому устройству. И не забывайте, что стоимость уменьшается в 5 раз каждые 10 лет. С течением времени DES будет становиться все менее и менее безопасным.

Для трудного ответа нужно попытаться оценить криптоаналитические методы. Дифференциальный крипто а-нализ был известен в NSA задолго до середины 70-х, когда DES впервые стал стандартом. Наивно считать, что с тех пор теоретики NSA ничего не делали, почти наверняка они разработали новые криптоаналитические мет о-ды, которые можно использовать против DES. Но фактов у нас нет, одни слухи.

Винн Шварцтау (Winn Schwartau) пишет, что NSA построило огромную параллельную машину для вскр ы-тия DES уже в середине 80-х [1404]. По крайней мере одна такая машина была построена в Harris Corp. С и с-пользованием Cray Y-MP. Предположительно существует ряд алгоритмов, которые на несколько порядков уменьшают сложность вскрытия DES грубой силой. Контекстные алгоритмы, основанные на внутренней работе DES, позволяют отбросить ряд ключей, используя частичные решения. Статистические алгоритмы уменьшают эффективную длину ключа еще сильнее. Другие алгоритмы также проверяют вероятные ключи - слова, печ а-таемые последовательности ASCII, и т.д. (см. раздел 8.1). По слухам NSA может вскрыть DES за время от 3 до 15 минут, в зависимости от того коков будет выполненный объем предварительной обработки. И каждая такая машина стоит порядка 50000 долларов.

Согласно другим слухам, если у NSA есть большое количество открытых текстов и шифротекстов, его эк с-перты могут выполнить некоторые статистические расчеты и затем считать ключ из архива на оптических ди с-ках.

И то, что это только слухи, не дает мне чувство уверенности в DES. Этот алгоритм очень долго был очень большой мишенью. Почти любое изменение DES послужит дополнительной защитой, может быть получивши й-ся шифр и будет менее устойчив к вскрытию, но у NSA может не оказаться средств решения этой конкретной задачи.

Я рекомендую использовать схему Бихама для зависящих от ключа S-блоков. Она может быть легко реал и-зована программно или аппаратно (с помощью микросхем с загружаемыми S-блоками), и не приводит к потере эффективности по сравнению с DES. Эта схема повышает устойчивость алгоритма к вскрытию грубой силой, усложняет дифференциальный и линейный криптоанализ и заставляет NSA столкнуться с алгоритмом, по кра й-ней мере таким же сильным как DES, но другим.

Глава 13 Другие блочные шифры 13.1 LUCIFER

В конце 60-х IBM начала выполнение исследовательской программы по компьютерной криптографии, наз ы-анной Люцифером (Lucifer) и руководимой сначала Хорстом Фейстелем (Horst Feistel), а затем Уолтом Тачм е-ном (Walt Tuchman). Это же название - Lucifer - получил блочный алгоритм, появившийся в результате этой программыв начале 70-х [1482, 1484]. В действительности существует по меньшей мере два различных алг о-ритма с таким именем [552, 1492]. [552] содержит ряд пробелов в спецификации алгоритма. Все это привело к заметной путанице.

Lucifer - это набор перестановок и подстановок, его блоки похожи на блоки DES. В DES результат функции f объединяется с помощью XOR со входом предыдущего этапа, образуя вход следующего этапа. У S-блоков алг о-ритма Lucifer 4-битовые входы и 4-битовые выходы, вход S-блоков представляет собой перетасованный выход 8_блоков предыдущего этапа, входом S-блоков первого этапа является открытый текст. Для выбора использу е-мого S-блока из двух возможных применяется бит ключа. (Lucifer реализует это, как один Т-блок с 9 битами на входе и 8 битами на выходе.) В отличие от DES половины блока между этапами не переставляются и вообще понятие половины блока не используется в алгоритме Lucifer. У этого алгоритма 16 этапов, 128-битовые блоки и более простое, чем в DES, распределение ключей.

Применив дифференциальный криптоанализ к первой реализации Lucifer'a, Бихам и Шамир [170, 172] пок а-зали, что Lucifer с 32-битовыми блоками и 8 этапами может быть взломан с помощью 40 выбранных открытых текстов за 2³⁹ шагов, тот же способ позволит вскрыть Lucifer с 128-битовыми блоками и 8 этапами с помощью 60 выбранных открытых текстов за 2⁵³ шагов. 18-этапный, 128-битовый Lucifer вскрывается дифференциаль­ным криптоанализом с помощью 24 выбранных открытых текстов за 2 ²¹ шагов. Все эти вскрытия использовали сильные S-блоки DES. Применив дифференциальный криптоанализ против второй реализации Lucifer, Бихам и Шамир обнаружили, что S-блоки намного слабее, чем в DES. Дальнейший анализ показал, что более половины возможных ключей не являются безопасными [112]. Криптоанализ со связанными ключами может взломать 128-битовый Lucifer с любым числом этапов с помощью 2³³ выбранных открытых текстов для выбранных клю­чей или 2⁶⁵ известных открытых текстов для выбранных ключей [158]. Вторая реализация Lucifer еще слабее [170, 172, 112].

Некоторые думают, что Lucifer безопаснее, чем DES, из-за большей длины ключа и малого количества опу б-ликованных сведений. Но очевидно, что это не так.

Lucifer является объектом нескольких патентов США: [553, 554, 555, 1483]. Сроки действия всех этих п а-тентов истекли.

MADRYGA

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

Описание Madryga

Итерация внутреннего цикла оперирует с 3-байтовым окном данных, называемым рабочим кадром (см. 12-й). Это окно смещается на 1 байт за итерацию. (При… Текст TL-2

Рис. 13-1. Одна итерация Madryga.

Так как каждый байт данных влияет на два байта слева от себя и на один байт справа, после восьми прох о-дов каждый байт шифротекста зависит от 16 байтов слева и от восьми байтов справа.

При шифровании каждая итерация внутреннего цикла устанавливает рабочий кадр на предпоследний байт открытого текста и циклически перемещает его к байту открытого текста, третьему слева от последнего. Снач а-

ла весь ключ подвергается операции XOR со случайной константой и затем циклически смещается влево на 3 бита. Младшие три бита младшего байта рабочего кадра сохраняются, они определяют вращение остальных двух байтов. Затем для младшего байта рабочего кадра выполняется операция XOR с младшим байтом ключа. Далее объединение двух старших байтов циклически смещается влево на переменное число битов (от 0 до 7). Наконец рабочий кадр смещается вправо на один байт и весь процесс повторяется.

Смысл случайной константы в том, чтобы превратить ключ в псевдослучайную последовательность. Длина константы должна быть равна длине ключа. При обмене данными абоненты должны пользоваться константой одинаковой длины. Для 64-битового ключа Мадрига рекомендует константу 0x0fle2d3c4b5a6978.

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

Криптоанализ и Madryga

Хотя у меня нет сведений о проведении формального анализа этого алгоритма, он не производит впечатл е-ние супернадежного. При поверхностном… Алгоритм состоит только из линейных операций (циклическое смещение и XOR),… В этом нет ничего похожего на мощь S-блоков DES.

Gt;

&

е

о

о

о

/

f

/

f

/

t

ф

-ф

/ ■•

в₄ в₅ в₆ в₇

-ф

•Э

•0

Ф

К4

К₅ Кб

Этапы 3-15

/

Этап 16

Этап 17

Кп

К12

Ki3

K14

е

о

о

о

ф

Gt;

Gt;

#

f

/

f

/

t

/

ф

-Ф

/ ■•

е

^

ф

•е

-э

•0

Къ

Кэ

Кю

 

Во Bi B2 Вз

В₄ В₅ В_в В₇

Рис. 13-2. NewDES.

Функция f выводится из Декларации независимости. Подробности можно найти в [1405].

Скотт показал, что каждый бит блока открытого текста влияет на каждый бит шифротекста уже после 7 эт а-пов. Он также проанализировал функцию f и не нашел каких-либо очевидных проблем. NewDES обладает той же комплиментарностью, что и DES [364]: если Е^Р} = С, то Е_К(Р'} = С. Это уменьшает объем работы, необ­ходимой для вскрытия грубой силой, с 2¹¹⁰ действий до 2^Ш Бихам заметил, что любое изменение полного бай­та, примененное ко всем байтам ключа и данных, также приводит к комплиментарности [160]. Это уменьшает объем грубого вскрытия до 2¹¹² действий.

Это не является критичным, но предложенное Бихамом криптоаналитическое вскрытие со связанными кл ю-чами может вскрыть NewDES с помощью 2³³ выбранных открытых текстов для выбранных ключей за 2⁴⁸ дей­ствий [160]. Хотя такое вскрытие требует много времени и в большой степени является теоретическим, оно п о-казывает, что NewDES слабее, чем DES.

13.4 FEAL

FEAL был предложен Акихиро Шимузу (Akihiro Shimizu) Шоджи Миягучи (Shoji Miyaguchi) из NTT Japan [1435]. В нем используются 64-битовый блок и 64-битовый ключ. Его идея состоит в том, чтобы создать алг о-ритм, подобный DES, но с более сильной функцией этапа. Используя меньше этапов, этот алгоритм мог бы р а-ботать быстрее. К несчастью действительность оказалась далека от целей проекта.

Описание FEAL

тем блок данных расщепляется не левую и правую половины. Объединение левой и правой половин с помощью XOR образует новую правую половину. Левая… 32 бита Lo{Re} Ь {Ri}

Рис. 13-3. Один этап FEAL.

Функция f берет 32 бита данных и 16 битов ключа и смешивает их вместе. Сначала блок данных разбивается на 8-битовые кусочки, которые затем объединяются с помощью XOR и заменяют друг друга. Блок-схема фун к-ции f представлена на 9-й. Две функции S₀h Si определяются следующим образом:

S₀(a,b) = циклический сдвиг влево на два бита ((а + Ъ) mod 256)

Si(a,b) = циклический сдвиг влево на два бита((а + Ъ + 1) mod 256)

Ъ

f_{ab_}

So

I

So

Si

bo

Ф-Ф

e<—ф

a₀

a

a

 

16 битов

a 32 бита

 

Si

a

Рис. 13-4. Функция f.

Тот же алгоритм может быть использован для дешифрирования. Единственным отличием является то, что при дешифрировании порядок использования частей ключа меняется на обратный.

На 8-й представлена блок-схема функции генерации ключа. Сначала 64-битовый ключ делится на две пол о-

вины, к которым применяются операции XOR и функции f_h как показано на схеме. На 7-й показана блок-схема функции/*. Два 32-битовых входа разбиваются на 8-битовые блоки, объединяемые и заменяемые в соответс т-вии со схемой. S₀ и Si определяются, как показано на рисунке. Затем в алгоритме шифрования/дешифрирования используются 16-битовые блоки ключа.

На микропроцессоре 80286/10 МГц ассемблерная реализация FEAL-32 может шифровать данные со скор о-стью 220 Кбит/с. FEAL-64 может шифровать данные со скоростью 120 Кбит/с [1104].

 

 

 

 

 

 

 

 

 

 

 

 

 

32 бита	Блок ключа J64 бита 32 бита
	А0
	'			Во
		г- L
Ко, К,	к р
	А, 1				•
	'			в,
	А	I- L	(Т>«
Кг, К$	Г		kV*
<	^	| _:'
	А7 1	'	D7 А, 32 бита	в7
KU, Ki5 <		■

а₀

X

Рис. 13-5. Обработка ключа в FEAL.

а 32 бита

a

a

~о<

-е«-

«X

Si

So

й 32 бита

 

 

So h©<-х₂

*ф—►

Si

а_и й,. - 8 бит

 

Y

|32 бита

/ф,й)

Y=S₀(X ,X₂)=Rot2((X+X₂) mod 256) Y=Si(Xi,X2)=Rot2((Xi+X₂+1) mod 256) Y: выходные 8 битов, х_ьХ₂ (8 битов): входы Rot2(Y): циклический сдвиг влево на 2 бита 8-битовых данных у

Рис. 13-6. Функция/^.

Криптоанализ FEAL

Шамиром на конференции SECURICOM '89 [1424]. Для вскрытия FEAL-8 с выбранными открытыми текстами потребовалось только 10000 блоков [610], что… Бихам и Шамир применили против FEAL-N дифференциальный криптоанализ, хотя они… Разработчики FEAL определили также модификацию FEAL - FEAL-NX, в которой используется 128-битовый ключ (см. 6-й)…

Рис. 13-7. Обработка ключа в FEAL-NX.

Более того. В [1520] было представлено другое вскрытие FEAL-4, требующее только 1000 известных откр ы-тых текстов, и FEAL-8, для которого нужно только 20000 известных открытых текстов. Другие вскрытия прив е-дены в [1549, 1550]. Наилучшим является выполненное Мицуру Мацуи (Mitsura Matsui) и Атшуиро Ямагиши

(Atshuiro Yamagishi) [1020]. Это было первое применение линейного криптоанализа, и оно позволило вскрыть FEAL-4 с помощью 5 известных открытых текстов, FEAL-6 - с помощью 100 известных открытых текстов, а FEAL-8 - с помощью 2¹⁵ известных открытых текстов. Дальнейшие уточнения можно найти в [64]. Диффере н-циальный криптоанализ позволяет вскрывать FEAL-8, используя только 12 выбранных открытых текстов [62]. Кто бы не изобрел новый метод криптоаналитического вскрытия, кажется, что он всегда сначала пробует его на FEAL.

Патенты

13.5 REDOC REDOC II представляет собой другой блочный алгоритм, разработанный Майклом… REDOC II выполняет все манипуляции - перестановки, подстановки и XOR с ключом - с байтами, этот а л-горитм эффективен…

REDOC III

(1) Создать таблицу ключей из 256 10-байтовых ключей, используя секретный ключ. (2) Создать 2 10-байтовых блока маски М и М2. М представляет собой XOR… (3) Для шифрования 10-байтового блока:

Патенты и лицензии

Обе версии REDOC запатентованы в Соединенных штатах [1614]. Рассматриваются и иностранные патенты. При заинтересованности в REDOC II или REDOC III обращайтесь к Майклу Буду (Michael С. Wood, Delta Computec, Inc., 6647 Old Thompson Rd., Syracuse, NY 13211).

LOKI

LOKI разработан в Австралии и впервые был представлен в 1990 году в качестве возможной альтернативы DES [273]. В нем используются 64-битовый блок и 64-битовый ключ. Общая структура алгоритма и использ о-вания ключа описана в [274, 275], а схема S-блоков - в [1247].

Используя дифференциальный криптоанализ, Бихам и Шамир смогли взломать LOKI с И и менее этапами быстрее, чем грубой силой [170]. Более того, алгоритм обладает 9-битовой комплиментарностью, что уменьш а-ет сложность вскрытия грубой силой в 256 раз [170, 916, 917].

Ларе Кнудсен (Lars Knudsen) показал, что LOKI с 14 и менее этапами чувствителен к дифференциальному криптоанализу [852, 853]. Кроме того, если в LOKI используются альтернативные S-блоки, получающийся шифр вероятно также будет чувствителен к дифференциальному криптоанализу.

LOKI91

В ответ на эти вскрытия разработчики LOKI вернулись за чертежную доску и пересмотрели свой алгоритм. Результатом было появление LOKI91 [272]. (Предыдущая версия LOKI была переименована в LOKI89.)

Чтобы повысить устойчивость алгоритма к дифференциальному криптоанализу и избавиться от комплиме н-тарности, в оригинальный проект были внесены следующие изменения:

1. Алгоритм генерации подключей был изменен так, чтобы половины переставлялись не после каждого, а после каждого второго этапа.

2. Алгоритм генерации подключей был изменен так, чтобы количество позиций циклического сдвига л е-вого подключа было равно то 12, то 13 битам.

3. Были устранены начальная и заключительная операции XOR блока и ключа.

4. Была изменена функция S-блока с целью сгладить XOR профили S-блоков (чтобы повысить их усто й-чивость к дифференциальному криптоанализу), и не допустить, чтобы для какого-то значения выпо л-нялось f(x) = 0, где f - это комбинация Е-, S- и Р-блоков.

Описание LOKI91

Открытый текст /_32 ^^_®_©_(§)_Ф

Рис. 13-8. LOKI91.

Табл. 13-1. Перестановка с расширением

4,

28, 20, 12,

И,

2, 26, 18, 10,

1, 25, 17,

9,

32,

24,

16,

8,

31,

23, 15,

7,

20,

22,

14,

6,

29, 21, 13,

5,

28,

20,

12,

4,

27,

19,

И,

3,

26, 18, 10,

2,

25,

17,

9,

48-битовый результат делится на четыре 12-битовых блока, для каждого из которых выполняется следующая подстановка с использованием S-блока: берется каждый 12-битовый вход, по 2 крайних левых и крайних пр а-вых бита используются для получения номера г, в 8 центральных бит образуют номер с. Результатом S-блока -О - является следующее значение:

0(г,с) = (с + ((г* 17) © Oxff) & Oxff)³¹ mod P_r

P_r приведено в Табл. 13-2.

Табл. 13-2.

Pr

 

г:	1,	2,	з,	4,	5,	6,	7,	8,	9,	10,	И,	12,	13,	14,	15,
Pr-	375,	279,	391,	395,	397,	415,	419,	425,	433,	445,	451,	463,	471,	477,	487,

Затем четыре 8-битовых результата снова объединяются, образуя 32-битовое число, которое подвергается операции перестановки, описанной в Табл. 13-3. Наконец для получения новой левой половины выполняется XOR правой половины с прежней левой половиной, а левая половина становится новой правой половиной. П о-сле 16 этапов для получения окончательного шифротекста снова выполняется XOR блока и ключа.

Табл. 13-3. Перестановка с помощью P-блока

32, 24^ 6, 8^ Ъ, 23, 5, Т, 30^ 22^ 14, 6, 29, ТА, Ъ, ^

28, 20, 12, 4, 27, 19, И, 3, 26, 18, 10, 2, 25, 17, 9, 1

Подключи из ключа выделяются достаточно прямолинейно. 64-битовый ключ разбивается на левую и пр а-вую половины. На каждом этапе подключом является левая половина. Далее она циклически сдвигается влево на 12 или 13 битов, затем после каждых двух этапов левая и правая половины меняются местами. Как и в DES для шифрования и дешифрирования используется один и тот же алгоритм с некоторыми изменениями в испол ь-зовании подключей.

Криптоанализ LOKI91

Другое вскрытие со связанными ключами может вскрыть LOKI91 с помощью 2 32 выбранных открытых тек­стов для выбранных ключей или с помощью 248…

Патенты и лицензии

KHUFU и KHAFRE

1. 56-битовый размер ключа DES слишком мал. Так как стоимость увеличения размера ключа прене б-режимо мала (компьютерная память недорога и… 2. Интенсивное использование перестановок в DES хотя и удобно для аппаратных… 3. S-блоки DES, всего с 64 4-битовыми элементами, слишком малы. Теперь с увеличением памяти должны увеличиться и…

Khufu

Khufu - это 64-битовый блочный шифр. 64-битовый открытый тест сначала разбивается на две 32-битовые половины, L и R. Над обеими половинами и определенными частями ключа выполняется операция XOR. Затем, аналогично DES, результаты проходят через некоторую последовательность этапов. На каждом этапе младший значащий байт L используется в качестве входных данных S-блока. У каждого S-блока 8 входных битов и 32 выходных бита. Далее выбранный в S-блоке 32-битовый элемент подвергается операции XOR с R. Затем L цик­лически сдвигается не несколько из восьми битов, L и R меняются местами, и этап заканчивается. Сам S-блок не является статическим, но меняется каждые восемь этапов. Наконец после последнего этапа над L и R выпол­няется операция XOR с другими частями ключа, и половины объединяются, образуя блок шифротекста.

Хотя части ключа используются для XOR с блоком шифрования в начале и в конце алгоритма, главная цель ключа -генерация S-блоков. Эти S-блоки - секретны, по сути являются они являются частью ключа. Полный размер ключа Khufu равен 512 битам (64 байтам), алгоритм предоставляет способ генерации S-блоков по кл то­чу. Количество этапов алгоритма остается открытым. Меркл упомянул, что 8-этапный Khufu чувствителен к вскрытию с выбранным открытым текстом и рекомендует 16, 24 или 32 этапа [1071]. (Он ограничивает выбор количества этапов числами, кратными восьми.)

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

Khafre

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

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

В 1990 году Бихам и Шамир применили свой метод дифференциального анализа против Khafre [170]. Им удалось взломать 16-этапный Khafre с помощью вскрытия с выбранным открытым текстом после 1500 разли ч-ных шифрований. На их персональном компьютере это заняло около часа. Преобразование этого вскрытия во вскрытие с известным открытым текстом потребует около 238 шифрований. Khafre с 24 этапами может быть вскрыт с помощью вскрытия с выбранным открытым текстом за 253 шифрования, а с помощью вскрытия с и з-вестным открытым текстом - за 259 шифрования.

Патенты

13.8 RC2 RC2 представляет собой алгоритм с переменной длиной ключа, спроектированный… RC2 - это шифр с 64-битовым блоком и переменной длиной ключа, предназначенный заменить DES. В соо т-ветствии с…

IDEA

Первый вариант шифра IDEA, предложенный Ксуеджа Лай (Xuejia Lai) и Джеймсом Масси (James Massey), появился в 1990 году [929]. Он назывался PES (Proposed Encryption Standard, предложенный стандарт шифр о-вания). В следующем году, после демонстрации Бихамом и Шамиром возможностей дифференциального кри п-тоанализа, авторы усилили свой шифр против такого вскрытия и назвали новый алгоритм IPES (Improved Proposed Encryption Standard, улучшенный предложенный стандарт шифрования) [931, 924]. В 1992 году назв а-ние IPES было изменено на IDEA (International Data Encryption Algorithm, международный алгоритм шифров а-ния данных) [925].

IDEA основывается на некоторых впечатляющих теоретических положениях и, хотя криптоанализ добился некоторых успехов в отношении вариантов с уменьшенным количеством этапов, алгоритм все еще кажется сильным. По моему мнению это самый лучший и самый безопасный блочный алгоритм, опубликованный сег о-Дня.

Будущее IDEA пока неясно. Попыток заменить им DES предпринято не было, частично потому, что он зап а-тентован и должен быть лицензирован для коммерческих приложений, и частично потому, что люди пока все еще ждут, наблюдая насколько хорошо поведет себя алгоритм в предстоящие годы криптоанализа. Его сег о-

дняшняя известность объясняется тем, что он является частью PGP (см. раздел 24.12).

Обзор IDEA

IDEA является блочным шифром, он работает с 64-битовыми блоками открытого текста. Длина ключа - 128 битов. Для шифрования и дешифрирования используется один и тот же алгоритм.

Как и другие, уже рассмотренные блочные шифры IDEA использует и запутывание, и рассеяние. Флософия, лежащая в основе проекта, представляет собой "объединение операций из различных алгебраических групп". Смешиваются три алгебраические группы, и все они могут быть легко реализованы как аппаратно, так и пр о-граммно:

— XOR

-Сложение по модулю 2¹⁶

- Умножение по модулю 2¹⁶ + 1. (Это операцию можно рассматривать как S-блок IDEA.)

Все эти операции (а в алгоритме используются только они, перестановки на битовом уровне не применяю т-ся) работают с 16-битовыми подблоками. Этот алгоритм даже эффективнее на 16-битовых процессорах.

Описание IDEA

Схема IDEA представлена на Рис. 13-9. 64-битовый блок данных делится на четыре 16-битовых подблока: Х_и Х₂, Х₃ и Х₄. Эти четыре подблока становятся входными данными для первого этапа алгоритма. Всего в алг о-ритме восемь этапов. На каждом этапе четыре подблока подвергаются операциям XOR, сложениям и умнож е-ниям друг с другом и с шестью 16-битовыми подключами. Между этапами обмениваются местами второй и третий подблоки. Наконец четыре подблока объединяются с четырьмя подключами в окончательном преобраз о-вании. На каждом этапе события происходят в следующей последовательности:

(1) Перемножаются Х и первый подключ.

(2) Складываются Х₂ и второй подключ.

(3) Складываются Х₃ и третий подключ.

(4) Перемножаются Х₄ и четвертый подключ.

(5) Выполняется XOR над результатами этапов (1) и (3).

(6) Выполняется XOR над результатами этапов (2) и (4).

(7) Перемножаются результаты этапа (5) и пятый подключ.

(8) Складываются результаты этапов (6) и (7).

(9) Перемножаются результаты этапа (8) и шестой подключ.

(10) Складываются результаты этапов (7) и (9).

(И) Выполняется XOR над результатами этапов (1) и (9).

(12) Выполняется XOR над результатами этапов (3) и (9).

(13) Выполняется XOR над результатами этапов (1) и (10).

(14) Выполняется XOR над результатами этапов (4) и (10).

Х2

Zl<1L>0Z2 (1L£]

один этап

еще

семь

этап

Х,

Х₃

Х_А

 

( 9 )

Выход

Z/LJ

Z₄

 

У Y₂

Уз

Ya

X : 16-битовый подблок открытого текста

Y, ■ 16-битовый подблок шифротекста

Z/^r) : 16-битовый подблок ключа

Ф : побитовое "исключающее или" (xoR) 16-битовых подблоков

ЕВ: сложение по модулю 2¹⁶ 16-битовых целых

© : умножение по модулю 2¹⁶+1 16-битовых целых при условии,

что нулевой подблок соответствует 2

Рис. 13-9. IDEA.

Выходом этапа являются четыре подблока - результаты действий (И), (12), (13) и (14). Поменяйте местами два внутренних подблока (но не в последнем этапе), и вы получите исходные данные для следующего этапа.

После восьмого этапа выполняется заключительное преобразование:

(1) Перемножаются Х_х и первый подключ.

(2) Складываются Х₂ и второй подключ.

(3) Складываются Х₃ и третий подключ.

(4) Перемножаются Х₄ и четвертый подключ.

Наконец четыре подблока снова соединяются, образуя шифротекст.

Также несложно создавать подключи. Алгоритм использует 52 из них (шесть для каждого из восьми этапов и еще четыре для заключительного преобразования). Сначала 128-битовый ключ делится на восемь 16-битовых подключей. Это первые восемь подключей алгоритма (шесть для первого этапа и два - для второго). Затем ключ циклически сдвигается налево на 25 битов и снова делится на восемь подключей. Первые четыре используются на этапе 2, а оставшиеся четыре - на этапе 3. Ключ циклически сдвигается налево на 25 битов для получения следующих восьми подключей, и так до конца алгоритма.

Дешифрирование выполняется точно также за исключением того, что подключи инвертируются и слегка и з-меняются. Подключи при дешифрировании представляют собой обратные значения ключей шифрования по отношению к операциям либо сложения, либо умножения. (Для IDEA подблоки, состоящие из одних нулей, считаются равными 2¹⁶ = -1 для умножения по модулю 2¹⁶ + 1, следовательно, обратным значением 0 относи­тельно умножения является 0.) Эти вычисления могут занять некоторое время, но их нужно выполнить один раз для каждого ключа дешифрирования. В Табл. 13-4 представлены подключи шифрования и соответствующие

подключи дешифрирования.

Табл. 13-4. Подключи шифрования и дешифрирования IDEA

Этап	Подключи шифрования
	Z,m Z2(1)	z3w	z4w	z5w	z6(1)
	z/2) z2(2)	z/2>	z/2>	Z5p)	z6(2)
	z/3) z2(3)	z/3>	z4®	z5p)	z6(3)
	z/4) z2(4)	z/4>	z/4>	z/4>	z6(4)
	z/5) z2(5)	z3«	z4«	Z5(5)	z6(5)
	Z1(6) Z2(6)	z3(6)	z4®	z5(6)	z6(6)
	z/7) z2(7)	z/7>	z/7>	z/7>	z6(7)
	Zi(8) Z2(8)	z3(8)	z/8>	z/8>	z6(8)
заключительное	z/9> z/9>	z/9>	z/9>
преобразование

Подключи дешифрирования

 

Z (9-и	-z/9>	-z3(9)	z (9)~1	z^	z6(8)
7 С8)-1	-z/8>	-z3(8)	7 (8)-l	z5<7>	z6(7)
z (7-и	-z/7>	-z3(7)	z (7)~1	z5(6)	z6(6)
7 W"1	-z2®	-z3(6)	7 (6)-l	Z5(5)	z6(5)
Z (5-и	-z2«	-Zs(5)	z (5)_1	z5<4>	z6(4)
Z (4)_1	-z/4>	-z/4>	z (4)_1	z5p)	z6(3)
Z (3-и	-z/3>	-z/3>	Z (3)"1	Z5p)	z6(2)
Z (2-и	-z/2>	-z/2>	z (2)_1	z5«	z6(1)
Z (1-и	-z2«	-z3«	z (1)_1

Скорость IDEA

Реализация PES на базе СБИС шифрует данные со скоростью 55 Мбит/с при тактовой частоте 25 МГц [208,398]. Другая СБИС, разработанная ЕТН Zurich и…

Криптоанализ IDEA

Может быть вскрытие грубой силой - не лучший способ вскрытия IDEA. Алгоритм все еще слишком нов, чтобы можно было говорить о каких-то конкретных… один этап еще

Ya

X : 16-битовый подблок открытого текста

Y, ■ 16-битовый подблок шифротекста

Z/^r) : 16-битовый подблок ключа

Ф : побитовое "исключающее или" (xoR) 16-битовых подблоков

ЕВ: сложение по модулю 2¹⁶ 16-битовых целых

© : умножение по модулю 2¹⁶+1 16-битовых целых при условии,

что нулевой подблок соответствует 2

Рис. 13-10. PES.

Вилли Майер (Willi Meier) исследовал три алгебраических операции IDEA и показал, что, хотя они нес о-вместимы, есть случаи, когда эти операции можно упростить так, чтобы в некоторой степени облегчить [1050]. Его вскрытие 2-этапного IDEA оказалось эффективнее вскрытия грубой силой (2 ⁴² операций), но для IDEA с 3 и более этапами эффективность этого вскрытия была ниже вскрытия грубой силой. Безопасность полного 8-этапного IDEA осталась непоколебимой.

Джоан Дэймен (Joan Daemen) открыла класс слабых ключей IDEA [405, 409]. Эти ключи не являются ел а-быми в том смысле, в котором слабы некоторые ключи DES, для которых функция шифрования обратна самой себе. Слабость этих ключей состоит в том, что взломщик может легко определить их с помощью вскрытия с выбранным открытым текстом. Например, слабым является следующий ключ (в шестнадцатиричной записи):

0000,0000,0х00,0000,0000,000х,хххх,х000

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

В любом случае вероятность случайной генерации одного из таких слабых ключей очень мала: 1/2 ⁹⁶. Опас­ность случайно выбрать такой ключ практически не существует. К тому же, несложно модифицировать IDEA так, чтобы исключить наличие слабых ключей - достаточно выполнить XOR каждого подключа с числом OxOdae [409].

Хотя попыток выполнить криптоанализ IDEA было много, мне неизвестно ни об одной успешной.

Режимы работы и варианты IDEA

IDEA может работать в любом из режимов работы блочного шифра, описанных в главе 9. Против двойных реализаций IDEA может быть предпринято то же вскрытие "встреча посередине", что и против DES (см. раздел

15.1). Однако, так как ключ IDEA более чем в два раза длиннее ключа DES, это вскрытие непрактично. Объем нужной для такого вскрытия памяти составит 64*2 ¹²⁸ битов, или 10³⁹ байтов. Может быть во вселенной и доста­точно материи, чтобы построить такое хранилище, но я в этом сомневаюсь.

Если вы учитываете возможность использования параллельной вселенной, используйте утроенную реализ а-цию IDEA (см. раздел 15.2):

C = E_K3(D_K2(E_Ki(P)))

Такая реализация устойчива против вскрытия "встреча посередине".

Кроме того, почему бы вам не реализовать IDEA независимыми подключами, особенно если ваши средства распределения ключей позволяют работать с длинными ключами. Для IDEA нужно всего 52 16-битовых ключа, общей длиной 832 битов. Этот вариант определенно безопасней, но никто не сможет сказать насколько.

В наивной модификации может быть увеличен вдвое размер блока. Алгоритм также прекрасно работал бы с 32-битовыми подблоками вместо 16-битовых и с 256-битовым ключом. Шифрование выполнялось бы быстрее, и безопасность возросла бы в 2³² раза. Или нет? Теория, на которой основан алгоритм, опирается на то, что 2¹⁶+1 является простым числом. А 2³² + 1 простым числом не является. Может быть алгоритм и можно изм е-нить так, чтобы он работал, но его безопасность будет совсем иной. Лай говорит, что заставить работать такой алгоритм будет нелегко [926].

Хотя IDEA кажется намного безопаснее DES, не всегда можно легко заменить один алгоритм другим в с у-ществующем приложении. Если ваша база данных и шаблоны сообщений могут работать с 64-битовым кл ю-чом, реализация 128-битового ключа IDEA может быть возможной.

Для таких приложений создайте 128-битовый ключ, объединив 64-битовый ключ сам с собой. Не забывайте, что эта модификация заметно ослабляет IDEA.

Если вас больше волнует скорость работы, а не безопасность, попробуйте вариант IDEA с меньшим числом этапов. Сегодня лучшее вскрытие IDEA быстрее вскрытия грубой силой только для 2.5 и менее этапов [1050], 4-этапный IDEA будет в два раза быстрее и, насколько мне известно, его безопасность не уменьшится.

Caveat Emptor¹

IDEA - это относительно новый алгоритм, многие вопросы пока остаются открытыми. Образует ли IDEA группу? (Лай думает, что нет [926].) Не существует ли пока не открытых способов вскрытия этого шифра? У IDEA твердая теоретическая основа, но снова и снова казавшиеся безопасными алгоритмы капитулируют перед новыми формами криптоанализа. Ряд групп академических и военных исследователей не опубликовали свои результаты криптоанализа IDEA. Возможно, кто-нибудь уже добился или когда-нибудь добьется успеха.

Патенты и лицензии

13.10 MMB Недовольство использованием в IDEA 64-битового блока шифрования привело к… ММВ оперирует 32-битовыми подблоками текста (х0, хь х2, х3) и 32-битовыми подблоками ключа (к0, ки к2, к3). Это делает…

Глава 14

И еще о блочных шифрах

ГОСТ

ГОСТ - это блочный алгоритм, разработанный в бывшем Советском Союзе [655, 1393]. Название ТОСТ" является сокращением от "Государственный стандарт", нечто похожее на FIPS за исключением того, что это название могут носить стандарты практически любого типа. (Полным названием является "Государственный стандарт Союза ССР", или "Государственный стандарт Союза Советских Социалистических Республик".) Н о-мер данного стандарта - 28147-89. Все эти стандарты утверждаются Государственным комитетом по стандартам Союза ССР.

Я не знаю, использовался ли ГОСТ 28147-89 для засекреченного трафика или только для гражданского шифрования. Замечание в начале стандарта гласит, что алгоритм "удовлетворяет всем криптографическим тр е-бованиям, а степень защищаемой информации не ограничивается". Я слышал утверждения, что этот алгоритм первоначально использовался только для очень важных линий связи, включая секретные военные коммуник а-ции, но у меня нет подтверждений.

Описание ГОСТ

Для шифрования текст сначала разбивается на левую половину L и правую половину R. На этапе i использу­ется подключ Kt. На этапе i алгоритма ГОСТ… U = Rt-i Д,-= Z,,-.! © f№_b £,■)

Rh

►0

Выбор подключа

 

/-М

Rh

Рис. 14-1. Этап ГОСТ.

В этом случае, если на входе S-блока О, то на выходе 7. Если на входе 1, на выходе 10, и т.д. Все восемь S-блоков различны, они фактически являются дополнительным ключевым материалом. S-блоки должны хр а-ниться в секрете.

Выходы всех восьми S-блоков объединяются в 32-битовое слово, затем все слово циклически сдвигается влево на И битов. Наконец результат объединяется с помощью XOR с левой половиной, и получается новая правая половина, а правая половина становится новой левой половиной. Выполните это 32 раза, и все в поря д-

ке.

Генерация подключен проста. 256-битовый ключ разбивается на восемь 32-битовых блоков: к_и к₂, . . .£₈. На каждом этапе используется свой подключ, как показано в Табл. 14-1. Дешифрирование выполняется также, как и шифрование, но инвертируется порядок подключей *,-.

Стандарт ГОСТ не определяет способ генерации S-блоков, говорится только, что блоки должны быть пр е-доставлены каким-то образом [655]. Это породило домыслы о том, что советский производитель может поста в-лять хорошие S-блоки "хорошим" организациям и плохие S-блоки тем организациям, которых производитель собирается надуть. Это вполне может быть так, но неофициальные переговоры с российским производителем микросхем ГОСТ выявили другую альтернативу. Производитель создает перестановки S-блока самостоятельно с помощью генератора случайных чисел.

Табл. 14-1. Использование подключей на различных этапах ГОСТ

Этап: 1 2 3 4 5 6 7 8 9 10 И 12 13 14 15 16

Подключ: 1234567812345678

Этап: 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

Подключ: 1234567887654321

Совсем недавно стал известным набор S-блоков, используемых в приложениях Центрального Банка РФ. Эти S-блоки также используются в однонаправленной хэш-функции ГОСТ (см. раздел 18.11) [657]. Они перечисл е-ны в Табл. 14-2.

Криптоанализ ГОСТ

— DES использует сложную процедуру для генерации подключей из ключей. В ГОСТ эта процедура очень проста. — В DES 56-битовый ключ, а в ГОСТ - 256-битовый. Если добавить секретные… — У S-блоков DES 6-битовые входы и 4-битовые выходы, а у S-блоков ГОСТ 4-битовые входы и выходы. В обоих алгоритмах…

Табл. 14-2. S-блоки ГОСТ

S-блок 1:

4 10 9 2 13 8 0 14 6 И 1 12 7 15 5 3
S-блок 2:

14 И 4 12 6 13 15 10 2 3 8 1 0 7 5 9

S-блок З:

5 8 1 13 10 3 4 2 14 15 12 7 6 0 9 И
S-блок 4:

7 13 10 1 0 8 9 15 14 4 6 12 И 2 5 3

S-блок 5:

6 12 7 1 5 15 13 8 4 10 9 14 0 3 И 2
S-блок 6:

4 И 10 0 7 2 1 13 3 6 8 5 9 12 15 14

S-блок 7:
13 И 4 1 3 15 5 9 0 10 14 7 6 8 2 12

S-блок 8:
1 15 13 0 5 7 10 4 9 2 3 14 6 И 8 12

Если лучшим способом вскрытия ГОСТ является грубая сила, то это очень безопасный алгоритм. ГОСТ и с-пользует 256-битовый ключ, а если учитывать секретные S-блоки, то длина ключа возрастает. ГОСТ, по вид и-мому, более устойчив к дифференциальному и линейному криптоанализу, чем DES. Хотя случайные S-блоки ГОСТ возможно слабее фиксированных S-блоков DES, их секретность увеличивает устойчивость ГОСТ к ди ф-ференциальному и линейному криптоанализу. К тому же, эти способы вскрытия чувствительны к количеству этапов - чем больше этапов, тем труднее вскрытие. ГОСТ использует в два раза больше этапов, чем DES, одно это возможно делает несостоятельными и дифференциальный, и линейный криптоанализ.

Другие части ГОСТ такие же, как в DES, или слабее. ГОСТ не использует существующую в DES перест а-новку с расширением. Удаление этой перестановки из DES ослабляет его из-за уменьшения лавинного эффекта, разумно считать, что отсутствие такой операции в ГОСТ ослабляет этот алгоритм. Сложение, используемое в ГОСТ, не менее безопасно, чем используемая в DES операция XOR.

Самым большим различием представляется использование в ГОСТ циклического сдвига вместо перестано в-ки. Перестановка DES увеличивает лавинный эффект. В ГОСТ изменение одного входного бита влияет на один S-блок одного этапа, который затем влияет на два S-блока следующего этапа, три блока следующего этапа, и т.д.. В ГОСТ потребуется 8 этапов прежде, чем изменение одного входного бита повлияет на каждый бит р е-зультата, алгоритму DES для этого нужно только 5 этапов. Это, конечно же, слабое место. Но не забывайте: ГОСТ состоит из 32 этапов, a DES только из 16.

Разработчики ГОСТ пытались достигнуть равновесия между безопасностью и эффективностью. Они изм е-нили идеологию DES так, чтобы создать алгоритм, который больше подходит для программной реализации. Они, по видимому, менее уверены в безопасности своего алгоритма и попытались скомпенсировать это очень большой длиной ключа, сохранением в секрете S-блоков и удвоением количества итераций. Вопрос, увенчались ли их усилия созданием более безопасного, чем DES, алгоритма, остается открытым.

CAST

CAST был разработан в Канаде Карлайслом Адамсом (Carlisle Adams) и Стаффордом Таваресом (Stafford Tavares) [10, 7]. Они утверждают, что название обусловлено ходом разработки и должно напоминать о вероя т-ностном характере процесса, а не об инициалах авторов. Описываемый алгоритм CAST использует 64-битовый блок и 64-битовый ключ.

CAST имеет знакомую структуру. Алгоритм использует шесть S-блоков с 8-битовым входом и 32-битовым выходом. Работа этих S-блоков сложна и зависит от реализации, подробности можно найти в литературе.

Для шифрования сначала блок открытого текста разбивается на левую и правую половины. Алгоритм сост о-ит из 8 этапов. На каждом этапе правая половина объединяется с частью ключа с помощью функции f, а затем XOR результата и левой половины выполняется для получения новой правой половины. Первоначальная (до этапа) правая половина становится новой левой половиной. После 8 этапов (не переставьте левую и правую п о-ловины после восьмого этапа) две половины объединяются, образуя шифротекст. Функция f проста:

(1) Разбейте 32-битовый вход на четыре 8-битовых части: а, Ъ, с, d.

(2) Разбейте 16-битовый подключ на две 8-битовых половины: e, f.

(3) Подайте а на вход S-блока 1, Ъ - на вход S-блока 2, с - на вход S-блока 3, d - на вход S-блока 4, е - на вход S-блока 5 и/- на вход S-блока 6.

(4) Выполните XOR шести выходов S-блоков, получая 32-битовый результат.

Иначе, 32-битовый вход может быть объединен с помощью XOR с 32 битами ключа, разбит на четыре 8-битовых части, которые обрабатываются S-блоками и затем объединяются с помощью XOR [7]. Безопасность N этапов, организованных таким образом, по видимому, соответствует N + 2 этапам другого варианта.

16-битовые подключи этапов легко получаются из 64-битового ключа. Если к_и к₂, . . .к_н - это 8 байтов клю­ча, то на этапах алгоритма используются следующие подключи:

Этап1:*1,*2

Этап 2: k₃, k₄

Этап 3: к₅, к₆

Этап 4: к_ъ h

Этап 5: к₄, к₃

Этап 6: к_г, к_г

Этап 7: *₈, £₇

Этап 8: к₆, к₅

Сила этого алгоритма заключена в его S-блоках. У CAST нет фиксированных S-блоков, для каждого прил о-жения они конструируются заново. Критерии проектирования описаны в [10], изогнутыми функциями являются столбцы S-блоков, обеспечивающие необходимые свойства S-блоков (см. раздел 14.10). Созданный для данной реализации CAST S-блоков уже больше никогда не меняется. S-блоки зависят от реализации, а не от ключа.

В [10] было показано, что CAST устойчив к дифференциальному криптоанализу, а в [728] - что CAST усто й-чив и к линейному криптоанализу. Неизвестно иного, чем грубая сила, способа вскрыть CAST.

Northern Telecom использует CAST в своем пакете программ Entrust для компьютеров Macintosh, РСира-бочих станций UNIX. Выбранные ими S-блоки не опубликованы. Канадское правительство считает CAST н о-вым стандартом шифрования. Патентная заявка на CAST находится в процессе рассмотрения.

BLOWFISH

1. Скорость. Blowfish шифрует данные на 32-битовых микропроцессорах со скоростью 26 тактов на байт. 2. Компактность. Blowfish может работать менее, чем в 5 Кбайт памяти. 3. Простота. Blowfish использует только простые операции: сложение, XOR и выборка из таблицы по 32-битовому операнду.…

Рис. 14-2. Blowfish.

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

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

Для1= 1по16:

X_L =X_L®P_n

x_R = F(Xi) © x_R

Переставить x_L и x_R (кроме последнего этапа.)

X_R =X_R® Р₁₇ X_L =X_L® Р_п

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

8 битов

 

	8 битов
32 бита
	8 битов
	8 битов

S-блок 1

S-блок2

S-блок з

S-блок4

Е^

Е-

,, 32 бита

------------ ►

Рис. 14-3. Функция F.

Функция F представляет собой следующее (см. Рис. 14-3):

Разделить x_L на четыре 8-битовых части: а, Ь, с и d F(x_L) = ((S_ha + S₂,_b mod 2³²) © S₃,_c)+ S₄,_d mod 2³²

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

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

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

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

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

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

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

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

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

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

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

Безопасность Blowfish

Конечно, важно и раскрытие слабых ключей, даже хотя они скорее всего не будут использоваться. Слабым является ключ, для которого два элемента… вертывание ключа и проверить, нет ли в S-одинаковых элементов. Хотя я не… Мне неизвестно об успешном криптоанализе Blowfish. Для безопасности не реализуйте Blowfish с умен ь-шенным числом…

SAFER

SAFER K-64 означает Secure And Fast Encryption Routine with a Key of 64 bits - Безопасная и быстрая проц е-дура шифрования с 64-битовым ключом [1009]. Этот не являющийся частной собственностью алгоритм, разр а-ботанный Джеймсом Массеем (James Massey) для Cylink Corp., используется в некоторых из продуктов этой компании. Правительство Сингапура собирается использовать этот алгоритм - с 128-битовым ключом [1010] -для широкого спектра приложений. Его использование не ограничено патентом, авторскими правами или др у-гими ограничениями.

Алгоритм работает с 64-битовым блоком и 64-битовым ключом. В отличие от DES он является не сетью Фейстела (см. раздел 14.10), а итеративным блочным шифром: для некоторого количества этапов применяется одна и та же функция. На каждом этапе используются два 64-битовых подключа. Алгоритм оперирует только байтами.

Описание SAFER K-64

На Рис. 14-4 показан один этап SAFER K-64. Сначала над подблоками выполняется либо операция XOR, л и-бо сложени с байтами подключа К2гЛ. Затем… у = 45х mod 257. (Если х = 0, то у = 0.) у = log45 х. (Если х = 0, то у = 0.)

Рис. 14-4. Один этап SAFER.

Это операции в конечном поле GF(257), a 45 - элемент поля, являющийся примитивом. В реализациях SAFER K-64 быстрее выполнять поиск в таблице, чем все время рассчитывать новые результаты.

Затем подблоки либо подвергаются XOR, либо складываются с байтами подключа К_2г. Результат этого дей­ствия проходит через три уровня линейных операций, целью которых является увеличение лавинного эффекта. Каждая операция называется псевдоадамаровым преобразованием (Pseudo-Hadamard Transform, PHT). Если на входе РНТ а_х и а₂, то на выходе:

ii = (2fli + а₂) mod 256

Ъ_г = (_fll + а₂) mod 256

После г этапов выполняется заключительное преобразование. Оно совпадает с преобразованием, являющи м-ся первым действием каждого этапа. Над В_и В,, В₅ и £₈ выполняется XOR с соответствующими байтами по­следнего подключа, а В₂, В₃, В₆ и В₇ складываются с соответствующими байтами последнего подключа. В р е-зультате и получается шифротекст.

Дешифрирование представляет собой обратный процесс: сначала заключительное преобразование (с выч и-танием вместо сложения), затем г инвертированных этапов. Обратное РНТ (Inverse PHT, IPHT) - это:

а_г = (*! - Ъг) mod 256

а₂ = (-*! + 2Ъг) mod 256

Массей рекомендует использовать 6 этапов, но для большей безопасности количество этапов можно увел и-чить.

Генерировать подключи совсем не трудно. Первый подключ, К_и - это просто ключ пользователя. После­дующие ключи генерируются в соответствии со следующей процедурой:

i:,₊₁ = (X,«<30 + c,

Символ "«<" обозначает циклический сдвиг налево. Сдвиг выполняется побайтно, а с, является константой этапа. Если с„ - этоу-ый байт константы г'-го этапа, то можно рассчитать все константы этапов по следующей

формуле

c, = 4545"«9'+'') mod 256) mod 257 mod 257 Обычно эти значения хранятся в таблице.

SAFER K-128

Безопасность SAFER K-64

Кнудсен (Knudsen) обнаружил слабое место в распределении ключей: практически для каждого ключа сущ е-ствует не меньше одного (а иногда даже девять)… SAFER был спроектирован для Cylink, a Cylink были предъявлены различные… 14.5 3-WAY

Описание S-Way

х = х XOR Ki х = theta (х) х = pi - 1 (х) х = gamma (x) х = pi - 2 (х) x = x®Kn+1 х = theta (x) При этом используются следующие функции: — theta(x) - функция линейной подстановки, в основном набор циклических… — pi - 1 (х) и pi - 2 (х) - простые перестановки.

CRAB

Этот алгоритм был разработан Бертом Калиски [Burt Kaliski] и Мэттом Робшоу [Matt Robshaw] из RSA Laboratories [810]. В основе Crab лежит идея использовать методы однонаправленных хэш-функций для созд а-ния быстрого алгоритма шифрования. Следовательно, Crab очень похож на MD5, и в этом разделе предполаг а-ется, что вы знакомы с материалом раздела 18.5.

У Crab очень большой блок: 1024 байта. Так как Crab был представлен скорее как материал для исследов а-ния, а не реальный алгоритм, конкретной процедуры генерации ключей не было предложено. Авторы рассмо т-рели метод, который позволяет превратить 80-битовый ключ в три вспомогательных подключа, хотя алгоритм позволяет легко использовать ключи переменной длины. В Crab используется два набора больших подключей:

Перестановка чисел с 0 до 255: Р₀, Р_и Р₂, ..., Р₂₅₅-

Массив из 2048 32-битовых чисел: S₀, S_u S₂,..., S₂₀₄₁.

Все эти подключи должны быть вычислены до шифрования или дешифрирования. Для шифрования 1024-байтового блока X

(1) Разделите Хна 256 32-битовых подблоков: Х₀, Х_и Х₂, ..., Х₂₅₅.

(2) Переставьте подблоки Хв соответствии с Р.

(3) For r=0 to 3 For g = 0 to 63

A = X(4g) <<< 2r B = X(4g+1) <<< 2r C = X(4g+2) <<< 2r D = X(4g+3) <<< 2r For step s = 0 to 7

A = A © (В + ЦВ, C, D) + Ssnr+sg+s)

TEMP = D

D = C

C = B

B = A«< 5

A = TEMP X(4g) <<< 2r = A X_{4g+_l) <<< 2r = B

X(4^+2) <« 2r = С

Х(4_я+з) <« 2r = D

(4) Снова объединить X₀, X, X₂, ..., X₂₅₅, получая шифротекст.
Функции ЦВ, С, D) аналогичны используемым в MD5:

UB, С, D) = {BaC)w ((­ В) л D)

ЦВ, С, D) = (В л D) v (С л (­ D))

ЦВ, C, D) = B®C®D

ЦВ, C, D) = C®(Bv(­ D))

Дешифрирование представляет собой обратный процесс. Генерирование подключей является непростой з а-дачей. Вот как по 80-битовому ключу К может быть сгенерирован массив перестановок Р.

(1) Проинициализируйте К₀, К, К₂, ..., К₉ 10 байтами К.

(2) For г=10 to 255

K_t = К,_2 © К,.6 © К.л © К,_ло

(3) For г=10 to 255, Р, = i

(4) m=0

(5) For7=0 to 1

For г = 256 to 1 step -1

m = (K₂₅₆,i + K₂₅₇.i) mod i

K2si-i = K25₁_i «< 3

Переставить Р, и Р,_л

S-массив из 2048 32-битовых слов может быть сгенерирован аналогичным образом либо по тому же 80-битовому ключу, либо по другому ключу. Авторы предупреждают, что эти детали должны "рассматриваться только в качестве мотивации, могут быть и другие эффективные схемы, обеспечивающие лучшую безопасность" [810].

Crab был предложен как испытательный стенд для новых идей, а не как рабочий алгоритм. Во многом он использует те же приемы, что и MD5. Бихам заметил, что очень большой блок упрощает криптоанализ алг о-ритма [160]. С другой стороны Crab может позволять эффективно использовать очень большой ключ. В этом случае "упрощение криптоанализа" может ничего не значить.

14.7 SXAL8/MBAL

Это 64-битовый блочный алгоритм из Японии [769]. SXAL8 - это основной алгоритм, a MBAL представляет собой расширенную версию с переменной длиной блока. Так как внутри MBAL выполняется ряд умных дейс т-вий, авторы утверждают, что они могут обеспечить достаточную безопасность за малое число этапов. При длине блока 1024 байта MBAL примерно в 70 раз быстрее, чем DES. К несчастью в [1174] показано, что MBAL чу в-ствителен к дифференциальному криптоанализу, а в [865] - что он чувствителен и к линейному криптоанал изу.

14.8 RC5

RC5 представляет собой блочный фильтр с большим числом параметров: размером блока, размером ключа и количеством этапов. Он был изобретен Роном Ривестом и проанализирован в RSA Laboratories [1324, 1325].

Используется три действия: XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависящие и от ключа, и от данных, представляют собой интересную оп е-рацию.

RC5 использует блок переменной длины, но в приводимом примере мы остановимся на 64-битовом блоке данных. Шифрование использует 2г+2 зависящих от ключа 32-битовых слов - S₀, S_u S₂, ... S_2r+l - где г - число этапов. Эти слова мы сгенерируем позднее. Для шифрования сначала разделим блок открытого текста на два 32-битовых слова: А и В. (RC5 предполагает следующее соглашение по упаковке байтов в слова: первый байт занимает младшие биты регистра А, и т.д.) Затем:

A = A + S₀

B = B + S_X

For i = 1 to r:

A = ((A® B) <« B) + 5*2,

В = ((B ® A) <« A) + S_2l+1 Результат находится в регистрах А и В.

Дешифрирование также просто. Разбейте блок открытого текста на два слова, А и В, а затем: For i = r down to 1:

B = ((B - S_2l+1) >»A)®A

A = ((A - S_2i) >» B)®B

B = B - S_X

A = A - S₀

Символ ">»" обозначает циклический сдвиг направо. Конечно же, все сложения и вычитания выполняются по модулю 2³².

Создание массива ключей более сложно, но также прямолинейно. Сначала, байты ключа копируются в ма с-сив L из с 32-битовых слов, дополняя при необходимости заключительное слово нулями. Затем массив S ини­циализируется при помощи линейного конгруэнтного генератора по модулю 2 ³²:

forJ=lto 2(r +l) - l:

S_l = (S_l.₁ + Q) mod 2³²

Р = 0xb7el5163 и Q = 0х9е3779Ь9, эти константы основываются на двоичном представлении е и phi.

Наконец, подставляем L в S:

i = j = О

А =В = 0

выполнить п раз (где п - максимум 2(г + 1) и с):

A = Si = (Si + A + B)«<l

B = Li = (Li + A + B) <« (А+В)

j = (j+l) mod 2(r +l)

j = (j +l) mod с

По сути, RC5 представляет собой семейство алгоритмов. Только что мы определили RC5 с 32-битовым ел о-вом и 64-битовым блоком, не существуе причин, запрещающих использовать тот же алгоритм с 64-битовым словом и 128-битовым. Для w = 64, Р и Q равны 0xb7el51628aed2a6b и 0x9e3779b97f4a7cl5, соответственно. Ривест обозначил различные реализации RC5 как RC5- wlrlb, где w - это размер слова, г - число этапов, а Ъ -длина ключа в байтах.

RC5 является новым алгоритмом, но RSA Laboratories потрптила достаточно много времени, анализируя его работу с 64-битовым блоком. После 5 этапов статистика выглядит очень хорошо. После 8 этапов каждый бит открытого текста влияет по крайней мере на один циклический сдвиг. Дифференциальное вскрытие требует 2 ²⁴ выбранных открытых текстов для 5 этапов, 2⁴⁵ для 10 этапов, 2⁵³ для 12 этапов и 2⁶⁸ для 15 этапов. Конечно же, существует только 2^м возможных открытых текстов, поэтому такое вскрытие неприменимо против алгоритма с 15 и более этапами. Оценка для линейного криптоанализа показывает, что алгоритм безопасен после 6 этапов. Ривест рекомендует использовать не меньше 12 этапов, а лучше 16 [1325]. Это число может меняться.

RSADSI в настоящее время патентует RC5, а это названия заявлено, как торговая марка. Компания утве р-ждает, что плата за лицензирование будет очень мала, но это лучше проверить.

14.9 Другие блочные алгоритмы

Существует алгоритм, называемый в литературе CRYPTO-MECCANO [301], но он не является безопасным. Четыре японских криптографа на Eurocrypt '91 представили алгоритм, основанный на хаотичных отображениях [687, 688], Бихам выполнил криптоанализ этого алгоритма на той же конференции [157]. Другой алгоритм оп и-рается на подмножества некоторого множества случайных кодов [693]. Существует множество алгоритмов, о с-нованных на теории кодов, исправляющих ошибки: вариант алгоритма МакЭлайса (МсЕНесе) (см. раздел 19.7) [786, 1290], алгоритм Rao-Nam [1292, 733, 1504, 1291, 1056, 1057, 1058, 1293], варианты алгоритма Rao-Nam [464, 749, 1503] и алгоритм Li-Wang [964, 1561] - все они небезопасны. CALC также небезопасен [1109]. Алг о-ритм TEA (Tiny Encryption Algorithm, Крошечный алгоритм шифрования) слишком нов, чтобы его коммент и-ровать [1592]. Другим алгоритмом является Vino [503]. MacGuffm, блочный алгоритм, предложенный Мэттом Блэйзом и мной, также небезопасен [189], он был взломан на той же конференции, на которой он был предл о-жен. BaseKing, похожий по философии на З-way, но использующий 192-битовый блок [385], слишком нов, чт о-бы его комментировать.

Кроме того, существует множество блочных алгоритмов, разработанных вне криптографического сообщес т-ва. Некоторые из них используются различными военными и правительственными организациями. У меня нет данных о таких алгоритмах. Существуют также десятки частных коммерческих алгоритмов. Некоторые из них могут быть хороши, некоторые нет. Если компания предполагает, что опубликование ее алгоритмов не будет служить интересам компании, то лучше согласиться с ней и не использовать эти алгоритмы.

14.10 Теория проектирования блочного шифра

В раздел 11.1 я описывал принципы Шеннона для смешения и рассеяния. Спустя пятьдесят лет после того, как эти принципы были впервые сформулированы, они остаются краеугольным камнем проектирования хор о-

шего блочного шифра.

Смешение служит для маскировки взаимосвязей между открытым текстом, шифротекстом и ключом. По м-ните, как даже незначительная зависимость между этими тремя вещами может быть использована при дифф е-ренциальном и линейном криптоанализе? Хорошее смешение настолько усложняет статистику взаимосвязей, что не работают даже мощные криптографические средства.

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

Для безопасности достаточно одного смешения. Алгоритм, состоящий из единственной зависящей от ключа таблицы соответствия 64 битов открытого текста 64 битам шифротекста был бы достаточно сильным. Проблема в том, что для такой таблицы потребовалось бы слишком много памяти: 1020 байтов. Смысл создания блочного шифра и состоит в создании чего-то похожего на такую таблицу, но предъявляющего к памяти более умеренные требования.

Прием состоит в том, чтобы в одном шифре в различных комбинациях периодически перемежать смешив а-ние (с гораздо меньшими таблицами) и диффузию. Это называется результирующим шифром.Иногда блоч­ный шифр, который включает последовательные перестановки и подстановки, называют сетью перестановок-подстановок(substitution-permutation network), или SP-сетью.

Взгляните снова на функцию f в DES. Перестановка с расширением и Р-блок реализуют диффузию, a S-блоки - смешение. Перестановка с расширением и Р-блок линейны, S-блоки - нелинейны. Каждая операция сама по себе очень проста, но вместе они работают очень хорошо.

На примере DES также можно показать еще несколько принципов проектирования блочного шифра. Первым является идея итеративного блочного шифраПри этом предполагается, что простая функция этапа будет п о-следовательно использована несколько раз. Двухэтапный DES не очень силен, чтобы все биты результата зав и-сели от всех битов ключа и всех битов исходных данных, нужно 5 этапов [1078, 1080]. 16-этапный DES - это сильный алгоритм, 32-этапный DES еще сильнее.

Сети Фейстела

U = Дм К, - это подключ, используемый на /-ом этапе, a f - это произвольная функция… Эту концепцию можно увидеть в DES, Lucifer, FEAL, Khufu, Khafre, LOKI, COST, CAST, Blowfish и других алгоритмах.…

Простые соотношения

Простое соотношениеможно определить как [857]: Если Eg{P) = С, то Ет (g(P,K)) = h(C,K) где/; g и h - простые функции. Под "простыми функциями" я подразумеваю функции, которые вычисляются легко,…

Групповая структура

Полезным, однако, является не вопрос о том, действительно ли алгоритм является группой, а о том, наскол ь-ко он близок к группе. Если не хватает… Целью исследования является оценка пространства ключей для теоретического…

Слабые ключи

В хорошем блочном шифре все ключи одинаково сильны. Обычно нет проблем и при алгоритме с малым количеством слабых ключей, таком как DES. Вероятность случайно выбрать один из них очень мала, такой ключ легко проверить и при необходимости отбросить. Однако, иногда эти слабые ключи могут быть задейс т-вованы, если блочный фильтр используется как однонаправленная хэш-функция (см. раздел 18.11).

Устойчивость к дифференциальному и линейному криптоанализу

Линейный криптоанализ новее, и он все еще совершенствуется. Были определены понятия классификации ключей [1019] и нескольких приближений [811, 812].… Кнудсен добился некоторого успеха, рассматривая некоторые необходимые (но,… Достаточно интересной кажется двойственность дифференциального и линейного криптоанализа. Эта дво й-ственность…

Проектирование S-блоков

S-блок - это просто подстановка: отображение m-битовых входов на n-битовые выходы. Ранее я упоминал об одной большой таблице отображения 64-битовых… обеспечивают безопасность блочного шифра. В общем случае чем S-блоки больше,… В DES восемь различных 6*4-битовых S-блоков. В Khufu и Khafre единственный 8*32-битовый S-блок, в LOKI 12*8-битовый…

Проектирование блочного шифра

Легко можно спроектировать блочный шифр, если вы используете память, достаточную для размещения S-блоков 48*32. Трудно спроектировать небезопасный… 14.11 Использование однонаправленных хэш-функций Сымым простым способом использовать для шифрования однонаправленную хэш-функцию является хэш и-рование предыдущего…

Кат

Этот метод, изобретенный Филом Карном (Phil Каш) и открытый им для свободного использования, создает обратимый алгоритм шифрования из определенных однонаправленных хэш-функций.

Алгоритм работает с 32-байтовыми блоками открытого текста и шифротекста. Длина ключа может быть произвольной, хотя определенные дины ключей более эффективны для конкретных однонаправленных хэш-функций. Для однонаправленных хэш-функций MD4 и MD5 лучше всего подходят 96-байтовые ключи.

Для шифрования сначала разбейте открытый текст на две 16-байтовых половины: Р, и Р_г. Затем разбейте на две 48-байтовых половины ключ: К, и К_г.

Р= Pi , Рг,

к = к,,к_г

Добавьте К,кР,и выполните хэширование однонаправленной хэш-функцией, затем выполните XOR резул ь-тата с Р_г, получая С_г, правую половину шифротекста. Затем, добавьте К_г к С_г выполните хэширование однона­правленной хэш-функцией. Выполните XOR результата с Р,, получая С,. Наконец, объедините С_г и С,, получая шифротекст.

C_r = P_r ® H(P_h К,)

Ci= Pi®H{C_r, K_r)

С = С/, С_г

Для дешифрирования просто инвертируйте процесс. Добавьте К_г к Сг, выполните хэширование и XOR ре­зультата с С/, получая Pi. Добавьте К_г к P_h выполните хэширование и XOR результата с С_г, получая Р_г.

Pi=d® H(C_r, K_r) P_r = C_r®H{P_hKi)

P = Pi, Pr

Общая структура Karn совпадает с структурой множества других блочных алгоритмов, рассмотренных в этом разделе. У алгоритма только два этапа, так как его сложность определяется однонаправленной хэш-функцией. А, так как ключ используется только как вход хэш-функции, он не может быть раскрыт даже при помощи вскрытия с выбранным открытым текстом, если, конечно, безопасна используемая однонаправленная хэш-функция.

Luby-Rackoff

Ее удается избежать при помощи трехэтапного алгоритма шифрования [992,1643,1644]. Он использует три различных хэш-функции: Яь Я2 и Я3. Дальнейшие… (1) Разделите ключ на две половины: К, и Кг. (2) Разделите блок открытого текста на две половины: L0 и R0.

Шифр краткого содержания сообщения

Хэш функции, например MD5 и SHA, используют 512-битовый текстовый блок для преобразования входн о-го значения (128 битов в MD5, и 160 битов в SHA) в… Рассмотрим MDC с SHA. MDC использует 160-битовый блок и 512-битовый ключ.… MDC можно использовать с любой однонаправленной хэш-функцией: MD4, MD5, Snefru, и т.д. Он незап а-тентован и может…

Безопасность шифров, основанных на однонаправленных хэш-функциях

                              … Блок сообщения у Выходное значение