Алгебраическая структура - раздел Компьютеры, Часть III Криптографические алгоритмы Все Возможные 64-Битовые Блоки Открытого Текста Можно Отобразить На 64-Битовы...
Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста
264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предоставляет нам 2 56 (приблизительно 1017) таких отображений. Использование многократного шифрования на первый взгляд позв о-ляет значительно увеличить долю возможных отображений. Но это правильно только, если действие DES не обладает определенной алгебраической структурой.
Если бы DES был замкнутым,то для любых Кг и К2 всегда существовало бы такое К3, что
ЕК2(ЕК1(Р)) = ЕКз(Р)
Другими словами, операция шифрования DES образовала бы группу, и шифрование набора блоков открыт о-го текста последовательно с помощью К1 и К2 было бы идентично шифрованию блоков ключом КЗ. Что еще хуже, DES был бы чувствителен к вскрытию "встреча посередине" с известным открытым текстом, для которого потребовалось бы только 228 этапов [807].
Если бы DES был чистым,то для любых Ки К2 и К3 всегда существовало бы такое К4, что
ЕКз(ЕК2(ЕК1(Р))) = ЕК4(Р)
Тройное шифрование было бы бесполезным. (Заметьте, что замкнутый шифр обязательно является и чи с-тым, но чистый шифр не обязательно является замкнутым.)
Ряд подсказок можно найти в ранней теоретической работе Дона Копперсмита, но этого недостаточно [377]. Различные криптографы пытались решить эту проблему [588, 427, 431, 527, 723, 789]. В повторяющихся эксп е-риментах собирались "неопровержимые доказательства" того, что DES не является группой [807, 371, 808, 1116, 809], но только в 1992 году криптографам удалось это доказать окончательно [293]. Копперсмит утве р-ждает, что команда IBM знала об этом с самого н ачала.
Длина ключа
В оригинальной заявке фирмы IBM в NBS предполагалось использовать 112-битовый ключ. К тому времени, когда DES стандартом, длина ключа уменьшилась до 56 бит. Многие криптографы настаивали на более дли н-ном ключе. Основным их аргументом было вскрытие грубой силой (см. раздел 7.1).
В 1976 и 1977 гг. Диффи и Хеллман утверждали, что специализированный параллельный компьютер для вскрытия DES, стоящий 20 миллионов долларов, сможет раскрыть ключ за день. В 1981 году Диффи увеличил время поиска до двух дней, а стоимость - до 50 миллионов долларов [491]. Диффи и Хеллман утверждали, что вскрытие в тот момент времени находилось за пределами возможностей любой организации, кроме подобных NSA, но что к 1990 году DES должен полностью утратить свою безопасность [714].
Хеллман [716] продемонстрировал еще один аргумент против малого размера ключа: разменивая объем п а-мяти на время, можно ускорить процесс поиска. Он предложил вычислять и хранить 2 56 возможных результатов шифрования каждым возможным ключом единственного блока открытого текста. Тогда для взлома неизвестн о-го ключа криптоаналитику потребуется только вставить блок открытого текста в шифруемый поток, вскрыть получившийся результат и найти ключ. Хеллман оценил стоимость такого устройства вскрытия в 5 миллионов долларов.
Аргументы за и против существования в каком-нибудь тайном бункере правительственного устройства вскрытия DES продолжают появляться. Многие указывают на то, что среднее время наработки на отказ для микросхем DES никогда не было большим настолько, чтобы обеспечивать работу устройства. В [1278] было показано, что этого возражения более чем достаточно. Другие исследователи предлагают способы еще больше ускорить процесс и уменьшить эффект отказа микросхем.
Между тем, аппаратные реализации DES постепенно приблизились к реализации требования о миллионе шифрований в секунду, предъявляемого специализированной машиной Диффи и Хеллмана. В 1984 году были выпущены микросхемы DES, способные выполнять 256000 шифрования в секунду [533, 534]. К 1987 году были разработаны микросхемы DES, выполняющие 512000 шифрований в секунду, и стало возможным появление варианта, способного проверять свыше миллиона ключей в секунду [738, 1573]. А в 1993 Майкл Винер (Michael Wiener) спроектировал машину стоимостью 1 миллион долларов, которая может выполнить вскрытие DES гр у-бой силой в среднем за 3.5 часа (см. раздел 7.1).
Никто открыто не заявил о создании этой машины, хоте разумно предположить, что кому-то это удалось. Миллион долларов - это не слишком большие деньги для большой и даже не очень большой страны.
В 1990 году два израильских математика, Бихам (Biham) и Шамир, открыли дифференциальный криптоанализ,метод, который позволил оставить в покое вопрос длины ключа. Прежде, чем мы рассмотрим этот метод, вернемся к некоторым другим критическим замечаниям в адрес DES.
Все темы данного раздела:
Энтропия и неопределенность
Теория информации определяет количество информациив сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения ра
Норма языка
Для данного языка норма языкаравна
г =H(M)/N
где N - это длина сообщения. При больших N норма обычного английского яз
Зашифрованного алгоритмами с различной длиной ключа
Длина ключа (в битах) Расстояние уникальности (в символах)
5.9
8.2
Практическое использование теории информации
Хотя эти понятия имеют большое теоретическое значение, реальный криптоанализ использует их достаточно редко. Расстояние уникальности гарантирует ненадежность системы, если оно слишком мало, но его
Путаница и диффузия
Двумя основными методами маскировки избыточности открытого текста сообщения, согласно Шеннону, служат путаница и диффузия [1432].
Путаницамаскирует связь между открытым те
Сложность проблем
Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. (Отличным введением в эту тему являются [600, 211, 1226], см. также [1
Арифметика вычетов
Вы все учили математику вычетов в школе. Иногда ее называли "арифметикой часов". Если Милдред сказ а-ла, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и н
Простые числа
Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2
Наибольший общий делитель
Два числа называются взаимно простыми,если у них нет общих множителей кроме 1. Иными словами, е с-ли наибольший общий делительа и п равен 1. Это записываетс
Обратные значения по модулю
Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:
4*х = 1 (mod 7)
Это уравнение эквивалентно об
Квадратичные вычеты
Если/; - простое число, и а больше 0, но меньше р, то а представляет собой квадратичный вычет по модулю р, если
х2 = a (mod/;), для некоторых
Символ Лежандра
Символ Лежандра, Ца,р), определен, если а - это любое целое число, а р - простое число, большее, чем 2. Он равен 0, 1 или-1.
Ца,р) = 0, если а делится на р.
Символ Якоби
Символ Якоби, ](а,п), представляет собой обобщение символа Лежандра на составные модули, он определ я-ется для любого целого а и любого нечетного целого п. Функция удобна при п
Генераторы
Если р - простое число, и g меньше, чем р, то g называется генераторомпо модулю р, если для каждого числа Ъ от 1 тр - 1 существует
Квадратные корни по модулю п
Если п - произведение двух простых чисел, то возможность вычислить квадратные корни по модулю п вычислительно эквивалентна возможности разложить число п на множители [1283, 35
Solovay-Strassen
Роберт Соловэй (Robert Solovay) и Фолькер Штрассен (Volker Strassen) разработали алгоритм вероятностной проверки простоты числа [1490]. Для проверки простоты числа р этот алгоритм использует
Lehmann
Другой, более простой тест был независимо разработан Леманном (Lehmann) [903]. Вот последовательность действий при проверке простоты числа р:
(1) Выберите случайно число а, м
Rabin-Miller
Повсеместно используемым является простой алгоритм, разработанный Майклом Рабином (Michael Rabin), частично основанным на идеях Гэри Миллера [1093, 1284]. По сути, это упрощенная версия алгоритма,
Практические соображения
В реальных приложениях генерация простых чисел происходит быстро.
(1) Сгенерируйте случайное и-битовое число/;.
(2) Установите старший и младший биты равными 1. (Старший бит гаран
Сильные простые числа
Если п - произведение двух простых чисел, р и q, то может понадобиться использовать в качестве р и q сильные простые числа.Такие простые числа об
Вычисление дискретных логарифмов в конечной группе
Криптографы интересуются дискретными логарифмами следующих трех групп:
— Мультипликативная группа полей простых чисел: G¥(p)
— Мультипликативная группа конечных полей с
Разработка стандарта
В начале 70-х годов невоенные криптографические исследования были крайне редки. В этой области почти не публиковалось исследовательских работ. Большинство людей знали, что для своих коммуникаций во
Принятие стандарта
Американский национальный институт стандартов (American National Standards Institute, ANSI) одобрил DES в качестве стандарта для частного сектора в 1981 году (ANSI X3.92.) [50], назвав его Алгоритм
Проверка и сертификация оборудования DES
Частью стандарта DES является проверка NIST реализаций DES. Эта проверка подтверждает, что реализ а-ция соответствует стандарту. До 1994 года NIST проверял только аппаратные и программно-аппаратные
Заключительная перестановка
Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й. Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, в
Дешифрирование DES
После всех подстановок, перестановок, операций XOR и циклических сдвигов можно подумать, что алг о-ритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, разли
Режимы DES
FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, OFB и CFB (см. главу 9) [1143]. Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности - СВС и n-битовый CF
Аппаратные и программные реализации DES
Об эффективных аппаратных и программных реализациях алгоритма много писалось [997, 81, 533, 534, 437, 738, 1573, 176, 271, 1572]. Утверждается, что самой быстрой является микросхема DES, разработан
Ключи-дополнения
Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение бло
Количество этапов
Почему 16 этапов? Почему не 32? После пяти этапов каждый бит шифротекста является функцией всех б и-тов открытого текста и всех битов ключа [1078, 1080], а после восьми этапов шифротекст по сути пр
Проектирование S-блоков
Помимо уменьшения длины ключа NSA также обвиняют в изменении содержания S-блоков. Настаивая на подтверждении схемы S-блоков, NSA заявило, что детали алгоритма являются "чувствительными" и
Дополнительные результаты
Были предприняты и другие попытки криптоанализировать DES. Один из криптографов искал закономерн о-сти, используя спектральные тесты [559]. Другие анализировали последовательность линейных множител
Дифференциальный криптоанализ
В1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа[167, 168, 171, 172]. Это был новый, ранее неизвестный метод криптоанализа. Используя
Криптоанализ со связанными ключами
В 9-й показано количество битов, на которые циклически смещается ключ DES на каждом этапе: на 2 бита на каждом этапе, кроме этапов 1, 2, 9 и 16, когда ключ сдвигается на 1 бит. Почему?
Линейный криптоанализ
Линейный криптоанализпредставляет собой другой тип криптоаналитического вскрытия, изобретенный Мицуру Мацуи (Mitsura Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные пр
Дальнейшие направления
Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [702, 161, 927, 858, 860]. Ларе Кнудсен (Lars Knudsen) использует нечто, назыв
Многократный DES
В ряде реализаций DES используется трехкратный DES (см. 2-й) [55]. Так как DES e является группой, полученный шифротекст гораздо сложнее вскрыть, используя исчерпывающий поиск: 2 112 по
Обобщенный DES
Обобщенный DES (Generalized DES, GDES) был спроектирован для ускорения DES и повышения устойч и-вости алгоритма [1381, 1382]. Общий размер блока увеличился, а количество вычислений осталось неизме
MADRYGA
В.Е. Мадрига (W. E. Madryga) предложил этот блочный алгоритм в 1984 году [999]. Он может быть эффе к-тивно реализован как программа: в нем нет надоедливых перестановок, и все операции выполняются н
Описание Madryga
Madryga состоит из двух вложенных циклов. Внешний цикл повторяется восемь раз (но это количество м о-жет быть увеличено для повышения) и содержит применение внутреннего цикла к открытому тексту. Вн
Криптоанализ и Madryga
Исследователи из Технического университета в Квинсланде (Queensland University of Technology) [675] и с-следовали Madryga вместе с некоторыми другими блочными шифрами. Они обнаружили, что в этом ал
Описание FEAL
На 10-й представлена блок-схема одного этапа FEAL. В качестве входа процесса шифрования используется 64-битовый блок открытого текста. Сначала блок данных подвергается операции XOR с 64 битами ключ
Криптоанализ FEAL
Успешный криптоанализ FEAL-4, FEAL с четырьмя этапами, был выполнен с помощью вскрытия с выбра н-ными открытыми текстами [201], а позже слабость этого алгоритма была показана в [1132]. Последнее вс
Патенты
FEAL запатентован в Соединенных Штатах [1438], соответствующие патенты приняты к рассмотрению в Англии, Франции и Германии. Желающий лицензировать использование алгоритма должен связаться с Дера п-
REDOC III
REDOC представляет собой упрощенную версию REDOC II, также разработанную Майклом Вудом [1615]. Он работает с 80-битовым блоком. Длина ключа может меняться и достигать 2560 байтов (20480 битов). Алг
Описание LOKI91
Механизм LOKI91 похож на DES (см. Рис. 13-8). Блок данных делится на левую и правую половины и пр о-ходит через 16 этапов, что очень походе на DES. На каждом этапе правая половина сначала подвергае
Криптоанализ LOKI91
Кнудсен предпринял попытку криптоанализа LOKI91 [854, 858], но нашел, что этот алгоритм устойчив к дифференциальному криптоанализу. Однако ему удалось обнаружить, что вскрытие со связанными ключами
Патенты и лицензии
LOKI не запатентован. Кто угодно может реализовать алгоритм и использовать его. Исходный код, прив е-денный в этой книге, написан в Университете Нового Южного Уэльса. При желании использовать эту р
KHUFU и KHAFRE
В 1990 году Ральф Меркл (Ralph Merkle) предложил два алгоритма. В основе их проектирования лежали следующие принципы [1071]:
1. 56-битовый размер ключа DES слишком мал. Так как стоимость у
Патенты
И Khufu, и Khafre запатентованы [1072]. Исходный код этих алгоритмов содержится в патенте. При желании получить лицензию на любой или оба алгоритма следует обратиться к директору по лицензированию
Скорость IDEA
Современные программные реализации IDEA примерно в два раза быстрее, чем DES. На компьютере с i386/33 МГц IDEA шифрует данные со скоростью 880 Кбит/с, а на компьютере с i486/33 МГц - со скоростью 2
Криптоанализ IDEA
Длина ключа IDEA равна 128 битам - более чем в два раза длиннее ключа DES. При условии, что наиболее эффективным является вскрытие грубой силой, для вскрытия ключа потребуется 2 128 (10
Патенты и лицензии
IDEA запатентован в Европе и Соединенных Штатах [1012, 1013]. Патент принадлежит Ascom-Tech AG. Для некоммерческого использования лицензирование не нужно. При заинтересованности в лицензии для ко м
Описание ГОСТ
ГОСТ является 64-битовым алгоритмом с 256-битовым ключом. ГОСТ также использует дополнительный ключ, который рассматривается ниже. В процессе работы алгоритма на 32 этапах последовательно выполняет
Криптоанализ ГОСТ
Вот главные различия между DES и COST.
— DES использует сложную процедуру для генерации подключей из ключей. В ГОСТ эта процедура очень проста.
— В DES 56-битовый ключ, а в ГОСТ -
BLOWFISH
Blowfish - это алгоритм, разработанный лично мной для реализации на больших микропроцессорах [1388, 1389]. Алгоритм незапатентован, и его код на языке С приведен в конце этой книги для широкого пол
Безопасность Blowfish
Серж Воденэ (Serge Vaudenay) исследовал Blowfish с известными S-блоками и г этапами, дифференциал ь-ный криптоанализ может раскрыть Р-массив с помощью 2 8Ж выбранных открытых текстов [15
Описание SAFER K-64
Блок открытого текста делится на восемь байтовых подблоков: Въ В2, . . . , Въ В%. Затем подблоки обрабатываются в ходе г этапов. Наконец подблоки
SAFER K-128
Этот альтернативный способ использования ключа был разработан Министерством внутренних дел Синг а-пура, а затем был встроен Массеем в SAFER [1010]. В этом способе используются два ключа, Ка
Безопасность SAFER K-64
Массей показал, что SAFER K-64 после 6 этапов абсолютно защищен от дифференциального криптоанализа после 8 этапов и достаточно безопасен. Уже после 3 этапов против этого алгоритма становится неэффе
Описание S-Way
Этот алгоритм описать несложно. Для шифрования блока открытого текста х: For i = 0 to n - 1
х = х XOR Ki х = theta (х) х = pi - 1 (х) х = gamma (x) х = pi - 2
Сети Фейстела
Большинство блочных алгоритмов являются сетями Фейстела(Felstel networks). Эта идея датируется началом 70-х годов [552, 553]. Возьмите блок длиной п и разделите его на две
Простые соотношения
DES обладает следующим свойством: если Е^Р) = С, то ЕК{РГ) = С, где Р', С" и К' - побитовые дополнения Р,СиК. Это свойство вдвое уменьш
Групповая структура
При изучении алгоритма возникает вопрос, не образует ли он группу. Элементами группы являются блоки шифротекста для каждого возможного ключа, а групповой операцией является композиция. Изучение гру
Устойчивость к дифференциальному и линейному криптоанализу
Исследование дифференциального и линейного криптоанализа значительно прояснило теорию проектиров а-ния хорошего блочного шифра. Авторы IDEA ввели понятие дифференциалов,обобщение о
Проектирование S-блоков
Сила большинства сетей Фейстела - и особенно их устойчивость к дифференциальному и линейному кри п-тоанализу - непосредственно связана с их S-блоками. Это явилось причиной потока исследований, что
Проектирование блочного шифра
Проектировать блочный шифр нетрудно. Если вы рассматривает 64-битовый блочный шифр как перестано в-ку 64-битовых чисел, ясно, что почти все эти перестановки безопасны. Трудность состоит в проектиро
Luby-Rackoff
Майкл Любы (Michael Luby) и Чарльз Ракофф (Charles Rackoff) показали, что Каш не является безопасным [992]. Рассмотрим два одноблочных сообщения: АВ и АС. Если криптоаналитику известн
Шифр краткого содержания сообщения
Шифр краткого содержания coo6nieHM(Message Digest Cipher, M DC), изобретенный Питером Гутманном (Peter Cutmann) [676], представляет собой способ превратить однонаправленные хэш-функции в
Безопасность шифров, основанных на однонаправленных хэш-функциях
Хотя эти конструкции и могут быть безопасными, они зависят от используемой однонаправленной хэш-функции. Хорошая однонаправленная хэш-функция не обязательно дает безопасный алгоритм шифрования. Сущ
Новости и инфо для студентов