блок

В январе 1977 году правительство Соединенных Штатов приняло продукцион­ный шифр, разработанный фирмой IBM, в качестве официального стандарта для несекретных сведений. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), получил широкое распространение в промышленности для защиты информации. В своем исходном виде он уже боль­ше не является надежным, но в модифицированном виде все еще полезен. Сейчас мы объясним принципы его работы.

Схема DES-шифра показана на рис. 8.6, а. Открытый текст шифруется блоками по 64 бита, в результате чего на выходе получаются 64-битные блоки зашифро­ванного текста. Алгоритм, использующий 56-разрядный ключ, состоит из 19 от­дельных этапов. На первом этапе выполняется независимая перестановка 64 раз­рядов открытого текста. Последний представляет собой обратную перестановку. Предпоследний этап меняет местами левые и правые 32 разряда. Остальные 16 эта­пов функционально идентичны, но управляются разными функциями входного ключа. Алгоритм был разработан так, чтобы дешифрация выполнялась тем же ключом, что и шифрование. Это обеспечивает соответствие алгоритма принципу симметричных ключей. Этапы при расшифровке просто выполняются в обрат­ном порядке.

Операция, выполняемая на одном из промежуточных этапов, показана на рис. 8.6, 6. На каждом этапе из двух порций по 32 разряда на входе формируются две порции по 32 разряда на выходе. Правая половина входа просто копируется в левые разряды выхода. Правые 32 выходных разряда представляют собой сум­му по модулю 2 левой части входа и функции правой части входа и ключа данно­го этапа Kv Вся сложность шифра заключается в этой функции.

Функция состоит из четырех последовательно выполняемых шагов. Сначала из 32 разрядов правой части Rhl с помощью фиксированной перестановки и дуб­лирования формируется 48-разрядное число Е. На втором шаге число Е и ключ Kt складываются по модулю 2. Затем выход разделяется на восемь групп по шесть разрядов, каждая из которых преобразуется независимым S-блоком в 4-раз­рядные группы. Наконец, эти 8 • 4 разряда пропускаются через Р-блок.

На каждом из 16 этапов используются различные функции исходного ключа. Перед началом работы алгоритма к ключу применяется 56-разрядная переста­новка. Перед каждым этапом ключ разделяется на две группы по 28 разрядов, каж­
дая из которых вращается влево на число разрядов, зависящее от номера этапа. Ключ К{ получается из результата этой операции при помощи еще одной пере­становки 56 разрядов. На каждом этапе из 56 разрядов ключа выбираются 48 раз­рядов, которые также переставляются местами.

 

L,-

64-разрядный открытый текст j j | У Ц У У

1-1

illlllll UUUU

Стандарт шифрования данных DES" title="Стандарт шифрования данных DES" border=0 width=194 height=197 src="http://s55.radikal.ru/i147/1007/25/e1da771fc25d.png">

ы *

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

У V У У У У У

Итерация 1

У У У У У У У У

Итерация 2

Итерация 16

У У У X У У

Перестановка 32 битов

у у у у у у уу

Инверсная перестановка

 

ttfттттУ

32 бита L,

32 бита Я/

64-разрядный зашифрованный текст а

 

Рис. 8.6. Стандарт шифрования данных DES: общий вид (а); детализация одного из этапов (б)

Иногда для повышения надежности DES используется метод, называемый побелкой. Он заключается в том, что перед передачей шифра каждый блок от­крытого текста складывается по модулю 2 с произвольным 64-битным ключом, затем отправляется в устройство DES, после чего получившийся шифр склады­вается по модулю 2 со вторым 64-битным ключом. На приемном конце побелка легко устраняется путем выполнения обратных операций (это возможно, если у получателя есть два побелочных ключа). Поскольку применение этого метода увеличивает длину ключа, полный перебор в пространстве значений ключа ста­новится еще более длительным. Обратите внимание: для побелки каждого блока применяется один и тот же ключ (то есть для каждого сообщения имеется толь­ко один побелочный ключ).

Стандарт шифрования данных DES был полон противоречий с самого мо­мента его создания. Он основывался на шифре Люцифер (Lucifer), разработан­ном и запатентованном корпорацией IBM, с той разницей, что IBM использова­ла 128-разрядный, а не 56-разрядный ключ. Когда федеральное правительство

Соединенных Штатов пожелало стандартизировать какой-то шифр для несек­ретного применения, оно «пригласило» IBM на «обсуждение» этого вопроса с Агентством национальной безопасности, NSA (National Security Agency), являю­щимся самым крупным в мире работодателем в области математики и крипто­анализа. Агентство национальной безопасности США настолько секретно, что существует даже такая популярная шутка:

Вопрос: Что означает аббревиатура NSA?

Ответ: No Such Agency — такого агентства нет.

После этих обсуждений корпорация IBM уменьшила длину ключа со 128 до 56 бит и решила держать в секрете процедуру разработки стандарта DES. Мно­гие полагали, что длина ключа была уменьшена, чтобы гарантировать, что NSA сможет взломать DES, но организациям с более низким финансированием это будет не по силам. Вероятно, цель засекречивания проекта состояла в сокрытии потайного хода, позволяющего Агентству национальной безопасности еще легче взламывать шифр DES. Когда сотрудник этого управления предложил Институ­ту инженеров по электротехнике и электронике (IEEE) отменить планирую­щуюся конференцию по криптографии, ощущения комфорта это не прибавило. Агентство национальной безопасности всегда препятствовало всему.

В 1977 году ученые Стэнфордского университета, занимающиеся исследова­ниями в области криптографии, Диффи (Diffie) и Хеллман (Hellman), разрабо­тали машину для взлома кода DES и оценили стоимость ее создания в 20 млн долларов. По небольшому участку открытого текста и соответствующего ему за­шифрованному тексту эта машина путем полного перебора 256 вариантов за один день могла найти 56-разрядный ключ. На сегодняшний день такая машина могла бы стоить около 1 млн долларов.

вый блок складывается по модулю 2 со случайным вектором инициализации, IV (Initialization Vector), передаваемым вместе с зашифрованным текстом.

Ро Р1 Рг Рз 1111

Режим шифрованной обратной связи" title="Режим шифрованной обратной связи" border=0 width=279 height=77 src="http://s16.radikal.ru/i190/1007/20/aab6e803acc1.jpg"> Со С1 Сг С з а

Однако у метода сцепления блоков шифра есть и недостаток, заключающийся в том, что прежде чем может начаться шифрование или дешифрация, должен по­явиться целый 64-битовый блок данных. Для пользователей интерактивных тер­миналов, набирающих строки короче восьми символов и ждущих ответа, такой
метод не подходит. Для побайтового шифрования может применяться режим шифрованной обратной связи с использованием (тройного) DES, как показано на рис. 8.11. Для стандарта AES идея остается той же самой, только используется 128-разрядный сдвиговый регистр. На рисунке мы видим состояние шифрующей машины после того, как байты с 0 по 9 уже зашифрованы и посланы. Когда при­бывает десятый байт открытого текста, как показано на рис. 8.11, а, алгоритм DES обрабатывает 64-разрядный сдвиговый регистр, чтобы произвести 64-раз- рядный зашифрованный блок. Самый левый байт этого зашифрованного текста извлекается и складывается по модулю 2 с Р10. Этот байт передается по линии. Затем сдвиговый регистр сдвигается влево на 8 разрядов. При этом байт С2 извле­кается с левого конца регистра, а байт С10 вставляется в него на освободившееся место справа от С9. Обратите внимание на то, что содержимое сдвигового регист­ра зависит от всей предыстории открытого текста, так что повторяющиеся фраг­менты исходного текста будут кодироваться каждый раз по-разному. Как и для метода сцепленных блоков шифра, для начала шифрования этим методом требу­ется вектор инициализации.

 

64-разрядный сдвиговый регистр С2 Сз с4 с5 С6 С7 С8 С9 64-разрядный сдвиговый регистр Сг Сз С4 С5 С6 С7 Cg С9

Шифратор

Шифратор Выбор левого байта

Ключ •

Ключ

I

Выбор левого байта

 

--------------- С10

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

а                                                                                                 б

Рис. 8.11. Режим шифрованной обратной связи (а); обратная связь по выходу (б)

При использовании режима шифрованной обратной связи дешифрация ана­логична шифрованию. В частности, содержимое сдвигового регистра шифрует­ся, а не дешифруется, поэтому байт, который складывается по модулю 2 с Ci0 для получения Pw равен тому байту, который складывается по модулю 2 с PlQ для получения С10. Пока содержимое двух сдвиговых регистров идентично, де­шифрация выполняется корректно. Это показано на рис. 8.11, б.

>1*0

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

Шифры, основанные на методе подстановки, сохраняют порядок символов, но подменяют их. Шифры, использующие метод перестановки, меняют порядок следования символов, но не изменяют сами символы. На рис. 8.2 показан простой перестановочный шифр с колоночной перестановкой. Ключом к шифру служит слово или фраза, не содержащая повторяющихся букв. В данном примере в каче­стве ключа используется слово MEGABUCK. Цель ключа — пронумеровать ко­лонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т. д. Открытый текст записывается горизонтально в строках. Шифрованный текст читается по колонкам, начиная с колонки с млад­шей ключевой буквой.

 

м	Е	G	А	В	у	С	К
7	4	5	1	2	8	3	6
Р	1	е	а	s	е	t	г
а	п	s	f	е	г	0	п
е	m	1	1	1	i	о	п
d	о	1	1	а	г	S	t
0	m	У	s	w	i	S	S
b	а	п	к	а	с	с	О
u	п	t	s	i	X	t	W
О	t	W	о	а	b	с	d

Открытый текст

pleasetransferonemilliondollarsto myswissbankaccountsixtwotwo

Зашифрованный текст

AFLLSKSOSELAWAIATOOSSCTCLNMOMANT ESILYNTWRNNTSOWDPAEDOBUOERIRICXB

 

Рис. 8.2. Перестановочный шифр

Чтобы взломать перестановочный шифр, криптоаналитик должен вначале по­нять, что он имеет дело именно с перестановочным шифром. Если взглянуть на частоту символов Е, Т, А, 0,1, N и т. д., легко заметить, что их частоты соответст­вуют нормальным частотам открытого текста. В таком случае очевидно, что этот шифр является перестановочным, так как каждая буква в таком шифре пред­ставляет сама себя.

Затем нужно угадать число колонок. Во многих случаях по контексту сооб­щения можно угадать слово или фразу. Например, предположим, что криптоана­литик подозревает, что где-то в сообщении должно встретиться словосочетание milliondollars. Обратите внимание, что в результате того, что эти слова присутст­вуют в исходном тексте, в шифрованном тексте встречаются биграммы МО, IL, LL, LA, IR и OS. Символ О следует за символом М (то есть они стоят рядом по вертикали в колонке 4), так как они разделены в предполагаемой фразе дистан­цией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вме­сто перечисленных выше биграмм встречались бы следующие: MD, Ю, LL, LL, IA, OR и NS. Таким образом, для каждой длины ключа в шифрованном тексте об­разуется различный набор биграмм. Перебрав различные варианты, криптоана­литик часто довольно легко может определить длину ключа.

Остается узнать только порядок колонок. Если число колонок k невелико, мож­но перебрать все k(k - 1) возможных комбинаций пар соседних колонок, сравнивая частоты образующихся биграмм со статистическими характеристиками англий­ского языка. Пара с лучшим соответствием считается правильно позициониро­ванной. Затем все оставшиеся колонки по очереди проверяются в сочетании с уже найденной парой. Колонка, в которой биграммы и триграммы дают макси­мальное совпадение со статистикой, предполагается правильной. Весь процесс повторяется, пока не будет восстановлен порядок всех колонок. Есть шанс, что на данном этапе текст уже будет распознаваемым (например, если вместо слова million мы увидим milloin, то сразу станет ясно, где сделана ошибка).

Некоторые перестановочные шифры принимают блок фиксированной длины на входе и выдают блок фиксированной длины на выходе. Такие шифры полно­стью определяются списком, сообщающим порядок, в котором символы попада­ют в выходной блок. Например, шифр на рис. 8.2 можно рассматривать в виде шифра с 64-символьным блоком. Его выход описывается последовательностью

чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13....... 62. Другими словами, четвертая входная

буква, а, первой появится на выходе, за ней последует двенадцатая, /, и т. д.