Практическое использование теории информации - раздел Компьютеры, Часть III Криптографические алгоритмы Хотя Эти Понятия Имеют Большое Теоретическое Значение, Реальный Криптоанализ ...
Все темы данного раздела:
Энтропия и неопределенность
Теория информации определяет количество информациив сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения ра
Норма языка
Для данного языка норма языкаравна
г =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. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение бло
Алгебраическая структура
Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста
264! Различными способами. Алгоритм DES, используя 56-битовый ключ, предост
Количество этапов
Почему 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], представляет собой способ превратить однонаправленные хэш-функции в
Безопасность шифров, основанных на однонаправленных хэш-функциях
Хотя эти конструкции и могут быть безопасными, они зависят от используемой однонаправленной хэш-функции. Хорошая однонаправленная хэш-функция не обязательно дает безопасный алгоритм шифрования. Сущ
Новости и инфо для студентов