tanenbaum_seti_all.pages (525408), страница 226
Текст из файла (страница 226)
8.8. а[ага га[0] гх[1] га[2] гк[3] та[4] гк[8] га[Е] га[7] гь[8] та[9] гк[10] Ключи итераций Рис. З.В. Создание массивов згаге и гК Перед началом основного цикла вычислений производится еше одно действие: гх[О] поразрядно складывается по модулю 2 с массивом агате. Другими словами, каждый из 16 байт в массиве агате заменяется суммой по модулю 2 от него самого и соответствующего байта в гь [О]. Только после этого начинается главное развлечение. В цикле проводятся 10 итераций, в каждой из которых массив зтате подвергается преобразованию. Каждый раунд (итерация) состоит из четырех шагов.
На шаге 1 в зтате производится посимвольная подстановка. Каждый байт по очереди используется в качестве индекса для Б-блока, заменяющего его значение на соответствующую запись Б-бло- Алгоритмы с симметричным криптографическим ключом 841 ка. На этом шаге получается прямой моноалфавнтный подстаиовочный шифр, В отличие от 1)ЕЯ, где используются несколько Б-блоков, в Щпбае1 8-блок всего олин.
На шаге 2 каждая из четырех строк поворачивается влево. Строка 0 поворачивается на 0 байт (то есть не изменяется), строка 1 — на 1 байт, строка 2 — на 2 байта, а строка 3 — на 3 байта. Смысл заключается в разбрасывании данных вокруг блока. Это аналогично перестановкам, показанным на рис.
8.5. На шаге 3 происходит независимое перемешивание всех колонок. Делается это с помощью операции матричного умножения, в результате которого каждая новая колонка оказывается равной произвелению старой колонки на постоянную матрицу. При этом умножение выполняется с использованием конечного поля 1алуа, СЕ(2к). Несмотря на то, что все это кажется довольно сложным, алгоритм устроен так, что каждый элемент матрицы вычисляется посредством всего лишь двух обращений к таблице и трех суммирований по модулю 2 (Оаешеп и Ецшеп, 2002, приложение Е). Наконец, на шаге 4 ключ данной итерации складывается по модулю 2 с массивом эгаге.
Благодаря обратимости всех действий расшифровка может быть выполнена с помощью такого же алгоритма, но с обратным порядком следования всех шагов. Однако есть одна хитрость, которая позволяет заниматься расшифровкой, используя алгоритм шифрования с измененными таблицами. Данный алгоритм обладает не только очень высокой защищенностью, но и очень высокой скоростью, Хорошая программная реализация иа машине с частотой 2 ГГц может шифровать данные со скоростью 700 Мбит/с. Такой скорости достаточно лля шифрации видео в формате МРЕС-2 в реальном масштабе времени. Аппаратные реализации работают еще быстрее.
Режимы шифрования Несмотря на всю свою сложность, АЕБ (или 1)ЕБ, или любой другой блочный код) представляет собой, по сути дела, моноалфавитный подстановочный шифр с большими длинами символов (в АЕ3 используются 128-битные символы, в 0ЕБ— 64-битные).
Для любого отрывка открытого текста шифр при прогоне через один и тот же шифрующий блок будет получаться всегда одинаковым. Скажем, если вы будете 100 раз пытаться зашифровать текст аЬсйеЯИ, задавая всякий раз один и тот же ключ для алгоритма 1)Е5, вы получите 100 одинаковых копий шифра. Взломщик может попытаться использовать этот недостаток при попытке расшифровки текста. Режим электронного шифроблокнота Чтобы понять, каким образом это свойство моноалфавитного подстановочного шифра может быть использовано для частичного взлома шифра, мы рассмотрим (тройное) кодирование по стандарту ЭЕ8 только лишь потому, что изображать 84-разрядные блоки проще, чем 128-разрядные. Надо иметь при этом в виду, что АЕБ сталкивается с теми же самыми проблемами.
Самый очевидный способ ко- а42 Глава 8. Безопасность в сетях дирования длинного сообщения заключается в разбиении его на отдельные блоки по 8 байт (64 бита) с последующим кодированием этих блоков по очереди одним и тем же ключом. Последний блок при необходимости можно дополнить до 64 бит, Такой метод называется режимом электронного шифроблокнота, по аналогии со старомодными шифроблокнотами, содержавшими слова и соответствующие им шифры (обычно это были пятизначные десятичные числа).
На рис. 8.9 показано начало компьютерного файла, в котором перечислены поощрительные премии сотрудникам компании. Этот файл состоит из последовательных 32-разрядных записей, по одной иа сотрудника, следующего формата: 16 байт на имя, 8 байт на должность и 8 байт на премию. Каждый из шестнадцати 8-байтовых блоков (пронумерованных от 0 до 15) кодируется шифром ПЕ8. Имя Должность Премия Б~ — — > В В Рис. В.в. Открытый текст файла, зашифрованного в виде! б ОЕБ-блоков Лесли только что поругалась с боссом и не рассчитывает на большую премию. Ким, напротив, — любимица босса, что всем известно. Лесли может получить доступ к файлу после того как он будет зашифрован, по до того как он будет отослан в банк.
Может ли Лесли исправить ситуацию, имея доступ только к зашифрованному файлуу В данном случае это очень просто. Все, что нужно сделать Лесли, — это скопировать зашифрованный блок 12 (содержащий премию Ким) и заменить им блок 4 (содержащий премию Лесли). Даже не зная содержимого блока 12, Лесли может рассчитывать на значительно более веселое Рождество. (Скопировать зашифрованный блок 8 тоже можно, но вероятность, что это будет обнаружено, выше; кроме того, Лесли, в общем-то, не жадная). Режим сцепления блоков шифра Чтобы противостоять атакам подобного типа, все блочные шифры можно модернизировать таким образом, чтобы замена одного блока вызывала повреждение других блоков открытого текста после их расшифровки, превращая эти блоки (начиная с модифицированного места) в мусор. Олин из таких способов — сцепление блоков шифра.
При этом методе, показанном на рис, 8Л0, каждый блок от- крытого текста перед зашифровкой складывается по модулю 2 с предыдущим уже зашифрованным блоком. При этом одинаковым блокам открытого текста уже не соответствуют одинаковые блоки зашифрованного текста. Таким образом, шифр перестает быть большим моноалфавитным подстановочным шифром. Пер- Алгоритмы с симметричным криптографическим ключом В4З вый блок складывается по модулю 2 со случайным вектором инициализации, 1У (1п(т(а1!гас(оп 'тгестог), передаваемыч вместе с зашифрованным текстом. Рв Рз Рг Рз Вектор инициализации ифрвтор Со Сз Сг Сз Са Сз Сг Сз Дешифратор Вектор инициализации Сложение Ро Рз Рг Рз по модулю 2 б Рис.
8.10. Сцепление зашифрованных блоков; шифрование (а), дешифрация (б) Рассмотрим работу сцепления блоков шифра на примере рис. 8.10. Начнем с вычисления С, = Е(Р, ХОтт Лг), Затем мы вычислим С, = Е(Р, ХОРк Сз) и т. л. Расшифровка производится цо формуле Р, = 1'т" ХОК 0(Сз), и т. д. Обратите внимание на то, что блок 1 является функцией всех блоков открытого текста с 0 по г — 1, поэтому один и тот же исходный блок текста преобразуется в разные зашифрованные блоки в зависимости от их расположения.
При использовании такого способа шифрования преобразование, произведенное Лесли, приведет к появлению двух блоков чепухи, начиная с поля премии Лесли. Для сообразительного офицера службы безопасности эта странность может послужить подсказкой в последующем расследовании. Сцепление блоков шифра также обладает тем достоинством, что усложняет криптоанализ, так как одни и те же блоки открытого текста преобразуются в разные зашифрованные блоки. Именно по этой причине и применяется описанный метод. Режим шифрованной обратной связи Однако у метода сцепления блоков шифра есть и недостаток.
заключающийся в том, что прежде чем может начаться шифрование или дешифрация, должен появиться целый 64-битовый блок данных. Для пользователей интерактивных терминалов, набирающих строки короче восьми символов и ждущих ответа, такой 844 Глава 8. Безопасность в сетях метод не подходит. Для побайтового шифрования может применяться режим шифрованной обратной связи с использованием (тройиого) ПЕЗ, как показано на рис. 8,11. Для стандарта АЕЕ идея остается той же самой, только используется 128.разрядный сдвиговый регистр. На рисунке мы видим состояние шифруюшей машины после того, как байты с 0 по 9 уже зашифрованы и посланы.
Когда прибывает десятый байт открытого текста, как показано на рис. 8.11, а, алгоритм )ЗЕЕ обрабатывает 64-разрядный сдвиговый регистр, чтобы произвести 64-разрядный зашифрованный блок, Самый левый байт этого зашифрованного текста извлекается и складывается по модулю 2 с Рнг Этот байт передается по линии. Затем сдвиговый регистр сдвигается влево на 8 разрядов, При этом байт С, извлекается с левого конца регистра, а байт С„вставляется в него на освободившееся место справа от Си Обратите внимание на то, что содержимое сдвигового регистра зависит от всей предыстории открытого текста, так что повторяюшиеся фрагменты исходного текста будут кодироваться каждый раз по-разному. Как и для метода сцепленных блоков шифра, для начала шифрования этим методом требуется вектор инициализации. 64-разрядный сдвиговый регистр 64-разрядный сдвиговый регистр Ого лежание по модулю 2 Ргс Рис.
8.11. Режим шифрованной обратной связи (а); обратная связь по выходу (б) При использовании режима шифрованной обратной связи дешифрация аналогична шифрованию. В частности, содержимое сдвигового регистра нгифруеглся, а не деши4руется, поэтому байт, который складывается по модулю 2 с С„ длЯ полУчениЯ Рнн Равен томУ байтУ, котоРый складываетси по модУлю 2 с Р„ для получения С„, Пока содержимое двух сдвиговых регистров идентично, дешифрация выполняется корректно. Это показано на рис. 8.11, б. Проблемы с режимом шифрованной обратной связи начинаются, когда при перелаче шифрованного таким способом текста один бит случайно инвертируется. При этом испорченными окажутся 8 байтов, расшифровываемые в то время, когда поврежденный байт находится в сдвиговом регистре.
Когда поврежденный байт покинет сдвиговый регистр, на выходе опять станет расшифровывать- Алгоритмы с симметричным криптографическим ключом 845 ся правильный открытый текст. Таким образом, результат инверсии одного бита оказывается относительно локализованным и не портит всего остатка сооб шения, Режим группового шифра Тем не менее, существуют приложения, в которых один испорченный при передаче бит приводит к порче 64 бит открытого текста, а это многовато. Для таких приложений существует четвертый вариант, называемый режимом группового (потокового) шифра.
Суть его заключается в том, что выходной блок получается шифрацией вектора инициализации с использованием ключа. Затем этот выходной блок снова шифруется с использованием ключа, в результате чего получается второй выходной блок. Для получения третьего блока шифруется второй блок, и т. д. Последовательность (произвольной длины) выходных блоков, называемая ключевым потоком, воспринимается как одноразовый блокнот и складывается по модулю 2 с открытым текстом. В результате получается шифрованный текст, как показано на рис. 8.12, а. Обратите внимание; вектор инициализации используется только на первом шаге.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
