Скляр Б. Цифровая связь (2003) (1151859), страница 215
Текст из файла (страница 215)
Практическая защищенность Для последовательностей шифрованного текста, размер которых больше расстояния единственности, любая система уравнений (определяющая ключ) может быть решена путем простого перебора всех возможных ключей, пока не будет получено единственное решение. Однако это совершенно непрактично, за исключением применения очень короткого ключа. Например, для ключа, полученного путем перестановки английского алфавита, существует 26! = 4 х 10" возможных пере- 920 становок (в криптографическом смысле это считается малым).
Будем считать, что в результате изнурительных поисков мы нашли правильный ключ, перебрав приблизительно половину возможных комбинаций. Если допустить, что каждая проверка потребует для вычисления 1 мкс, то полное время поиска превысит 1О" лет. Следовательно, если криптоаналитик хочет иметь некоторую надежду на успех, то о "лобовых" методах перебора следует забыть и применять какую-ту иную технологию (например, статистический анализ). 14.3.1. Смешение и диффузия При расшифровке многих систем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов и их комбинаций. Шеннон [51 предложил две концепции шифрования, усложняющие задачу криптоаналитика.
Он назвал эти преобразования "смешение" (сопГцз(оп) и "диффузия" (г)1)Тцз)оп). Смешеиие — это подстановки, которые делают взаимосвязь между ключом и шифрованным текстом как можно более сложной. Это усложняет применение статистического анализа, сужаюшего поиск практического подмножества области ключей. В результате смешения дешифрование даже очень короткой последовательности шифрованного текста требует большого числа ключей. Диффузия — это преобразования, сглаживающие статистические различия между символами и их комбинациями. Примером диффузии 26-буквенного алфавита является преобразование последовательности сообщений М = М„М„...
в новую последовательность сообщений У = Ум 1'н ... с помощью следующего соотношения: У„=~ М„„, по модулю 26. (14.20) 14.3.2. Подстановка Технология шифрования с помощью подстановки, например использование шифра Цезаря и прогрессивного ключа шифрования Тритемиуса, широко используется в головоломках. Такие простые подстановочные шифры дают малую защищенность. Чтобы к подстановочной технологии можно было применить концепцию смешения, требуется более сложное соотношение. На рис. 14.6 изображен пример создания большей подстановочной сложности с помощью использования нелинейного преобразования.
В общем случае в входных битов сначала представляются как один из 2" различных символов (на приведенном рисунке а =2). Затем множество из 2"символов перемешивается так, чтобы каждый символ заменялся другим символом множества. После этого символ снова превращается в лбитовый. 14.3. Практическая защищенность 921 Здесь каждый символ в последовательности рассматривается как число по модулю 26, г — некоторое выбранное целое число и л = 1, 2, .... Новое сообщение 1' будет иметь ту же избыточность, что и исходное сообщение М, но частота появления всех букв в У будет более равномерной, чем в М.
В результате, чтобы статистический анализ принес криптоаналитику какую-либо пользу, ему необходимо перехватить большую последовательность шифрованного текста Можно легко показать, что существует (2")! различные подстановки или связанные с ними возможные модели. Задача криптоаналитика становится вычисли- тельно невозможной для больших п. Пусть и = 128, тогда 2" = 10та и (2")! представляет собой астрономическое число. Видим, что для и= 128 это преобразование с помощью блока подстановки (зпЬ|111иг(оп Ыосй, Я-блок) является сложным (запутывающим). Впрочем, хотя Ю-блок с п = 128 можно считать идеальным, его реализация является невозможной, поскольку она потребует блока с 2п = 10м контактами. п=з п=з 1 Выход Вход 1 Рис. 14.б.
Блок подстановки Чтобы убедиться, что Я-блок, приведенный на рис. 14.6, представляет собой нелинейное преобразование, достаточно использовать теорему о суперпозиции, которая формулируется ниже. Предположим, что С=та+ ТЬ С = Т(а + Ь), (14.21) где а и Ь вЂ” входные элементы, С и С' — выходные элементы, а Т вЂ” преобразование.
Тогда Если Т линейно, С = С" для всех входных элементов. Если Т нелинейно, СФ С. Предположим, а = 001 и Ь = 010; тогда, используя преобразование Т, показанное на рис. 14.6, получим следующее: С= П001) Ю Т(010) = 111 Ю 000 = 111, С = Т(001 Ю 010) = Т(011) = 110. Здесь символ Ю обозначает сложение по модулю 2. Поскольку С;в С', Я-блок является нелинейным.
Глава 14. Шифрование и дешифрование 14.3.3. Перестановка При перестановке (транспозиции) буквы исходного открытого текста в сообщении не заменяются другими буквами алфавита, как в классических шифрах, а просто переставляются. Например, слово "ТН1[х[К" после перестановки может выглядеть как шифрованный текст НКТ[х[1. На рис. 14.7 приведен пример бинарной перестановки данных (линейная операция). Видно, что входные данные просто перемешиваются или переставляются.
Преобразование выполняется с помощью блока перестановки (реппцгаг[оп ыос[г, Р-блок). технология, используемая сама по себе, имеет один основной недостаток: она уязвима по отношению к обманным сообщениям. Обманное сообщение изображено на рис. 14.7. Подача на вход единственной 1 (при остальных О) позволяет обнаружить одну из внутренних связей. Если криптоаналитику необходимо выполнить криптоанализ такой системы с помощью атаки открытого текста, он отправит последовательность таких обманных сообщений, при каждой передаче смещая единственную 1 на одну позицию. Таким образом, обнаруживаются все связи входа и выхода. Данный пример показывает, почему защищенность системы не должна зависеть от ее архитектуры. 1 Выход Вход О Рис.
14.7. Беси пересмаиоехи 14.3.4. Продукционный шифр Для преобразований, включающих значительное число и-символьных сообщений, желательным является применение обеих описанных выше схем (5-блока и Р-блока). Шеннон [5[ предложил использовать продукционный сии((р, или комбинацию преобразований Я- и Р- блоков, которые вместе могут дать более мощную систему шифрования, чем каждый из них в отдельности. Этот подход, выборочно использующий преобразования замещения и перестановки, был использован 1ВМ в системе 1ЛС1ГЕК [7, 8[ и стал основой национального стандарта шифрования данных (Вага Епоургюп 8гапдап5 — [еЕБ) [9[.
На рис. 14.8 изображены такие комбинации Р- и Ю-блоков. Дешифрование выполняется об- 923 14.3. Практическая защищенность ратным прогоном данных, при котором используются преобразования, обратные к преобразованию каждого Ю-блока. Систему, изображенную на рис. 14.8, реализовать довольно трудно, поскольку все В-блоки являются различными', случайно генерируемый ключ неприменим и система не дает возможности повторить одну и ту же последовательность операций. Поэтому в системе ПЗС1ЕЕК 181 использовались два различных типа В-блоков, 51 и Ва, которые могли быль общедоступными. Пример такой системы изображен на рис.
14.9. Входные данные преобразуются с помощью последовательности Я- и Р-блоков, определяемой ключом. В приведенном примере ключ размером 25 бит определяет, какой из двух блоков (51 или Ял) следует выбрать на каждой из 25 позиций схемы. Таким образом, подробности аппарата шифрования могут быть открыты, поскольку защищенность системы обеспечивается ключом.
Риа 14,В. Продукиионнал система шифровании Выжгд вход Заштрихованные блокипютветотвуютоимволам приведенного нижедвоичного ключа Глава 14. Шифрование и дешифрование 924 1 о О о о о о Вюдо О о о о о О О Пример двоичного ключа 1 О 1 О О О 1 О 1 1 1 1 1 О 1 1 О 1 О 1 1 1 О 1 О Рис. 14.2 Индивидуальные возможности, олределлемые ключом О 1 О 1 О О О !Выход 1 1 о 1 о 1 1 Итеративная структура продукционной системы шифрования (рис. 14.9) является типичной для большинства реальных блочных шифров. Сообщения делятся на последовательные блоки по и бит, каждый из которых шифруется одним и тем же ключом. л-битовый блок представляет один из 2" различных символов, допускающих (2")! различные схемы подстановки. Следовательно, чтобы реализация схемы была разумной, подстановочная часть шифрования выполняется параллельно на небольших сегментах блока.
Пример подобной схемы рассмотрен в следующем разделе. 14.3.5. Стандарт шифрования данных В !977 году Национальное бюро стандартов США (Ха11опа1 Впгеап ОГ Бгапбагбз) приняло модифицированную систему 1.(ЗС1ГЕК в качестве Национального стандарта шифрования данных (Рага Епсгурйоп Бгапк)аге) — РЕЗ) [9]. Как показано на рис. 14.10, с точки зрения системы ввода-вывода РЕЯ может считаться блочной системой шифрования с алфавитом в 2еи символа. Входной блок из 64 бит, который является в этом алфавите символом открытого текста, заменяется новым символом шифрованного текста.
На рис. 14.11 в виде блочной диаграммы показаны функции системы. Алгоритм шифрования начинается с начальной перестановки 64 бит открь1того текста, описанной в таблице начальной перестановки (табл. 14.1). Таблица начальной перестановки читается слева направо и сверху вниз, так что после перестановки биты х,, хт ..., х„превращаются в хкв, хпн ..., х,. После этой начальной перестановки начинается основная часть алгоритма шифрования, состоящая из 16 итераций, которые используют стандартный блок, показанный на рис. 14.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
