Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 26 из 78

4,
1,
14,
8,
13,
6,
2,
11,
15,
12,
9,
7,
3,
10,
5,
0,
15,
12,
8,
2,
4,
9,
1,
7,
5,
11,
3,
14,
10,
0,
6,
13,
S-блок 2:
15,
1,
8,
14,
6,
11,
3,
4,
9,
7,
2,
13,
12,
0,
5,
10,
3,
13,
4,
7,
15,
2,
8,
14,
12,
0,
1,
10,
6,
9,
11,
5,
0,
14,
7,
11,
10,
4,
13,
1,
5,
8,
12,
6,
9,
3,
2,
15,
13,
8,
10,
1,
3,
15,
4,
2,
11,
6,
7,
12,
0,
5,
14,
9,
S-блок 3:
10,
0,
9,
14,
6,
3,
15,
5,
1,
13,
12,
7,
11,
4,
2,
8,
13,
7,
0,
9,
3,
4,
6,
10,
2,
8,
5,
14,
12,
11,
15,
1,
13,
6,
4,
9,
8,
15,
3,
0,
11,
1,
2,
12,
5,
10,
14,
7,
1,
10,
13,
0,
6,
9,
8,
7,
4,
15,
14,
3,
11,
5,
2,
12,
S-блок 4:
7,
13,
14,
3,
0,
6,
9,
10,
1,
2,
8,
5,
11,
12,
4,
15,
13,
8,
11,
5,
6.
15,
0,
3,
4,
7,
2,
12,
1,
10,
14,
9,
10,
6,
9,
0,
12,
11,
7,
13,
15,
1,
3,
14,
5,
2,
8,
4,
3,
15,
0,
6,
10,
1,
13,
8,
9,
4,
5,
11,
12,
7,
2,
14,
S-блок 5:
2,
12,
4,
1,
7,
10,
11,
6,
8,
5,
3,
15,
13,
0,
14,
9,
14,
11,
2,
12,
4,
7,
13,
1,
5,
0,
15,
10,
3,
9,
8,
6,
4,
2,
1,
11,
10,
13,
7,
8,
15,
9,
12,
5,
6,
3,
0,
14,
11,
8,
12,
7,
1,
14,
2,
13,
6,
15,
0,
9,
10,
4,
5,
3,
S-блок 6:
12,
1,
10,
15,
9,
2,
6,
8,
0,
13,
3,
4,
14,
7,
5,
11,
10,
15,
4,
2,
7,
12,
9,
5,
6,
1,
13,
14,
0,
11,
3,
8,
9,
14,
15,
5,
2,
8,
12,
3,
7,
0,
4,
10,
1,
13,
11,
6,
4,
3,
2,
12,
9,
5,
15,
10,
11,
14,
1,
7,
6,
0,
8,
13,
S-блок 7:
4,
11,
2,
14,
15,
0,
8,
13,
3,
12,
9,
7,
5,
10,
6,
1,
13,
0,
11,
7,
4,
9,
1,
10,
14,
3,
5,
12,
2,
15,
8,
6,
1,
4,
11,
13,
12,
3,
7,
14,
10,
15,
6,
8,
0,
5,
9,
2,
6,
11,
13,
8,
1,
4,
10,
7,
9,
5,
0,
15,
14,
2,
3,
12,
S-блок 8:
13,
2,
8,
4,
6,
15,
11,
1,
10,
9,
3,
14,
5,
0,
12,
7,
1,
15,
13,
8,
10,
3,
7,
4,
12,
5,
6,
11,
0,
14,
9,
2,
7,
11,
4,
1,
9,
12,
14,
2,
0,
6,
10,
13,
15,
3,
5,
8,
2,
1,
14,
7,
4,
10,
8,
13,
15,
12,
9,
0,
3,
5,
6,
11
Входные биты особым образом определяют элемент S-блока. Рассмотрим 6-битовый вход S-блока: b
1
, b
2
, b
3
,
b
4
, b
5
и b
6
. Биты b
1
и b
6
объединяются, образуя 2-битовое число от 0 до 3, соответствующее строке таблицы.
Средние 4 бита, с b
2
по b
5
, объединяются, образуя 4-битовое число от 0 до 15, соответствующее столбцу табл и- цы.

Например, пусть на вход шестого S-блока (т.е., биты функции XOR с 31 по 36) попадает 110011. Первый и последний бит, объединяясь, образуют 11, что соответствует строке 3 шестого S-блока. Средние 4 бита образ у- ют 1001, что соответствует столбцу 9 того же S-блока. Элемент S-блока 6, находящийся на пересечении строки
3 и столбца 9, - это 14. (Не забывайте, что строки и столбцы нумеруются с 0, а не с 1.) Вместо 110011 подста в- ляется 1110.
Конечно же, намного легче реализовать S-блоки программно в виде массивов с 64 элементами. Для этого потребуется переупорядочить элементы, что не является трудной задачей. (Изменить индексы, не изменяя пор я- док элементов, недостаточно. S-блоки спроектированы очень тщательно.) Однако такой способ описания S- блоков помогает понять, как они работают. Каждый S-блок можно рассматривать как функцию подстановки 4- битового элемента: b
2
по b
5
являются входом, а некоторое 4-битовое число - результатом. Биты b
1
и b
6
опреде- ляются соседними блоками, они определяют одну из четырех функций подстановки, возможных в данном S- блоке.
Подстановка с помощью S-блоков является ключевым этапом DES. Другие действия алгоритма линейны и легко поддаются анализу. S-блоки нелинейны, и именно они в большей степени, чем все остальное, обеспеч и- вают безопасность DES.
В результате этого этапа подстановки получаются восемь 4-битовых блоков, которые вновь объединяются в единый 32-битовый блок. Этот блок поступает на вход следующего этапа - перестановки с помощью P-блоков.
Перестановка с помощью P-блоков
32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с P-блоком. Эта п е- рестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Позиции, в которые перемещаются биты, показаны в 5-й. Например, бит 21 перемещается в позицию 4, а бит 4 - в позицию
31.
Табл. 12-7.
Перестановка с помощью P-блоков
16,
7,
20,
21,
29,
12,
28,
17,
1,
15,
23,
26,
5,
18,
31,
10,
2,
8,
24,
14,
32,
27,
3,
9,
19,
13,
30,
6,
22,
11,
4,
25
Наконец, результат перестановки с помощью P-блока объединяется посредством XOR с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следу ю- щий этап.
Заключительная перестановка
Заключительная перестановка является обратной по отношению к начальной перестановки и описана в 4-й.
Обратите внимание, что левая и правая половины не меняются местами после последнего этапа DES, вместо этого объединенный блок R
16
L
16
используется как вход заключительной перестановки. В этом нет ничего ос о- бенного, перестановка половинок с последующим циклическим сдвигом привела бы к точно такому же резул ь- тату. Это сделано для того, чтобы алгоритм можно было использовать как для шифрования, так и для дешифр и- рования.
Табл. 12-8.
Заключительная перестановка
40,
8,
48,
16,
56,
24,
64,
32,
39,
7,
47,
15,
55,
23,
63,
31,
38,
6,
46,
14,
54,
22,
62,
30,
37,
5,
45,
13,
53,
21,
61,
29,
36,
4,
44,
12,
52,
20,
60,
28,
35,
3,
43,
11,
51,
19,
59,
27,
34,
2,
42,
10,
50,
18,
58,
26,
33,
1,
41,
9,
49,
17,
57,
25
Дешифрирование DES
После всех подстановок, перестановок, операций XOR и циклических сдвигов можно подумать, что алг о- ритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, различные компоненты DES были подобраны так, чтобы выполнялось очень полезное свойство: для шифрования и деши ф-

рирования используется один и тот же алгоритм.
DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единс т- венное отличие состоит в том, что ключи должны использоваться в обратном порядке. То есть, если на этапах шифрования использовались ключи K
1
, K
2
, K
3
, ..., K
16
, то ключами дешифрирования будут K
16
, K
15
, K
14
, ..., K
1
Алгоритм, который создает ключ для каждого этапа, также цикличен. Ключ сдвигается направо, а число поз и- ций сдвига равно 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1.
Режимы DES
FIPS PUB 81 определяет четыре режима работы: ECB, CBC, OFB и CFB (см. главу 9) [1143]. Банковские стандарты ANSI определяют для шифрования ECB и CBC, а для проверки подлинности - CBC и n-битовый CFB
[52].
В мире программного обеспечения сертификация обычно не важна. Из-за своей простоты в большинстве существующих коммерческих программ используется ECB, хотя этот режим наиболее чувствителен к вскр ы- тию. CBC используется редко несмотря на то, что он лишь незначительно сложнее, чем ECB, и обеспечивает большую безопасность.
Аппаратные и программные реализации DES
Об эффективных аппаратных и программных реализациях алгоритма много писалось [997, 81, 533, 534, 437,
738, 1573, 176, 271, 1572]. Утверждается, что самой быстрой является микросхема DES, разработанная в Digital
Equipment Corporation [512]. Она поддерживает режимы ECB и CBC и основана на вентильной матрице GaAs,
состоящей из 50000 транзисторов. Данные могут зашифровываться и дешифрироваться со скоростью 1 гигабит в секунду, обрабатывая 16.8 миллионов блоков в секунду. Это впечатляет. Параметры ряда коммерческих ми к- росхем DES приведены в 3-й. Кажущиеся противоречия между тактовой частотой и скоростью обработки да н- ных обусловлены конвейеризацией внутри микросхемы, в которой может быть реализовано несколько раб о- тающих параллельно DES-механизмов.
Наиболее выдающейся микросхемой DES является 6868 VLSI (ранее называвшаяся "Gatekeeper'' - Вратарь).
Она не только может выполнять шифрование DES за 8 тактов (лабораторные прототипы могут делать это за 4
такта), но также выполнять троекратный DES в режиме ECB за 25 тактов, а троекратный DES в режимах OFB
или CBC - за 35 актов. Мне это кажется невозможным, но уверяю вас, она именно так и работает.
Программная реализация DES на мэйнфрейме IBM 3090 может выполнить 32000 шифрований DES в секу н- ду. На других платформах скорость ниже, но все равно достаточно велика. В 2-й [603, 793] приведены действи- тельные результаты и оценки для различных ми кропроцессоров Intel и Motorola.
Табл. 12-9.
Коммерческие микросхемы DES
Производитель
Микросхема
Год
Тактовая частота
Скорость данных
Доступность
AMD
Am9518 1981 3 МГц l.3 Мбайт/с
Н
AMD
Am9568
?
4 МГц l.5 Мбайт/с
Н
AMD
AmZ8068 1982 4 МГц l.7 Мбайт/с
Н
AT&T
T7000A
1985
?
l.9 Мбайт/с
Н
CE-Infosys
SuperCrypt
CE99C003 1992 20 МГц
12.5 Мбайт/с
Д
CE-Infosys
SuperCrypt
CE99C003A
1994 30 МГц
20.0 Мбайт/с
Д
Cryptech
Cry12C102 1989 20 МГц
2.8 Мбайт/с
Д
Newbridge
CA20C03A
1991 25 МГц
3.85 Мбайт/с
Д
Newbridge
CA20C03W
1992 8 МГц
0.64 Мбайт/с
Д
Newbridge
CA95C68/18/0 9
1993 33 МГц
14.67 Мбайт/с
Д
Pijnenburg
PCC100
?
?
2.5 Мбайт/с
Д
Semaphore
Communications
Roadrunner284
?
40 МГц
35.5 Мбайт/с
Д

VLSI Technology
VM007 1993 32 МГц
200.0 Мбайт/с
Д
VLSI Technology
VM009 1993 33 МГц
14.0
Д
VLSI Technology
6868 1995 32 МГц
64.0 Мбайт/с
Д
Western Digital
WD2001/2002 1984 3 МГц
0.23 Мбайт/с
Н
Табл. 12-10.
Скорости DES на различных микропроцессорах и компьютерах
Процессор
Скорость (в МГц)
Блоки DES (в с)
8088 4.7 370 68000 7.6 900 80286 6
1100 68020 16 3500 68030 16 3900 80386 25 5000 68030 50 10000 68040 25 16000 68040 40 23000 80486 66 43000
Sun ELC26000
HyperSparc
32000
RS6000-350 53000
Sparc 10/52 84000
DEC Alpha 4000/610 154000
HP9000/887 125 196,000 12.3 Безопасность DES
Люди давно интересуются безопасностью DES [458]. Было много рассуждений о длине ключа, количестве итераций и схеме S-блоков. S-блоки были наиболее таинственными - какие-то константы, без видимого объя с- нения для чего и зачем они нужны. Хотя IBM утверждала, что работа алгоритма была результатом 17 человеко- лет интенсивного криптоанализа, некоторые люди опасались, что NSA вставило в алгоритм лазейку, которая позволит агентству легко дешифрировать перехваченные соо бщения.
Комитет по разведке Сената США чрезвычайно тщательно расследовал этот вопрос в 1978 году. Результаты работы комитета были засекречены, но в открытых итогах этого расследования с NSA были сняты все обвин е- ния в неуместном вмешательстве в проектирование алгоритма [1552]. "Было сказано, что NSA убедило IBM в достаточности более короткого ключа, косвенно помогло разработать структуры S-блоков и подтвердило, что в окончательном варианте DES, с учетом всех знаний NSA, отсутствовали статистические или математические бреши " [435]. Однако, так как правительство не опубликовало подробности расследования, многих людей уб е- дить не удалось.
Тачмен (Tuchman) и Майер (Meyer), разработавшие DES криптографы IBM, заявили, что NSA не изменяло проект [841]:
Их основным подходом был поиск сильных подстановок, перестановок и функций планирования ключей. . . . IBM по просьбе NSA засекретило информацию, касающуюся критериев выбора. ... "NSA сообщило нам, что мы самостоятельно зан о- во открыли ряд секретов, используемых для создания их собственных алгоритмов", - об ъясняет Тачмен.
Позже в одной из статей Тачмен писал: "Алгоритм DES был полностью разработан внутри IBM ее сотру д- никами. NSA не продиктовало ни единой связи!" Тачмен подтвердил это утверждение в своем докладе по ист о- рии DES на Национальной конференции по компьютерной безопасности (National Computer Security Conference)

в 1992 году.
С другой стороны, Копперсмит писал [373, 374]: "Агентство национальной безопасности (NSA) также пом о- гало IBM техническими советами." А Конхейм (Konheim) утверждал: "Мы послали S-блоки в Вашингтон. Они вернулись полностью переработанными. Мы проверили их, и они прошли нашу проверку." На этот факт и сс ы- лаются как на доказательство, что NSA вставило лазейку в DES. По вопросу о каком-либо преднамеренном о с- лаблении DES NSA заявило [363]:
Относительно Стандарта шифрования данных (DES) мы считаем, что ответ на ваш вопрос о роли NSA в разработке DES
содержится в опубликованных итогах расследования Комитета Сената по разведке, проведенного в 1978 году. В сообщении
Комитета указывается, что NSA никоим образом не искажало алгоритм, и что безопасность, предоставляемая DES для несе к- ретных данных, с целью защиты которых он и был разработан, была более чем адекватна в течение по крайней мере 5-10 лет.
Короче говоря, NSA не вносило и не пыталось вносить никаких ослаблений в алгоритм DES.
Тогда почему они изменили S-блоки? Может быть, чтобы гарантировать, что лазейка не будет встроена в
DES самой IBM. У NSA не было причин доверять исследователям IBM, и оно могло решить, что не до конца исполнит свой долг, если не обеспечит отсутствие лазеек в DES. Задание S-блоков и могло быть одним из сп о- собов гарантировать это.
Совсем недавно новые результаты криптоанализа прояснили этот вопрос, который в течение многих лет был предметом спекуляций.
Слабые ключи
Из-за того, что первоначальный ключ изменяется при получении подключа для каждого этапа алгоритма,
определенные первоначальные ключи являются слабыми [721, 427]. Вспомните, первоначальное значение расщепляется на две половины, каждая из которых сдвигается независимо. Если все биты каждой половины равны 0 или 1, то для всех этапов алгоритма используется один и тот же ключ. Это может произойти, если ключ состоит из одних 1, из одних 0, или если одна половина ключа состоит из одних 1, а другая - из одних 0. Кроме того, у два слабых ключа обладают другими свойствами, снижающими их безопасность [427].
Четыре слабых ключа показаны в шестнадцатиричном виде в 1-й. (Не забывайте, что каждый восьмой бит - это бит четности.)
Табл. 12-11.
Слабые ключи DES
Значение слабого ключа (с битами четности)
Действительный ключ
0101 0101 0101 0101 0000000 0000000 1F1F
1F1F
0E0E
0E0E
0000000 FFFFFFF
E0E0
E0E0
F1F1
F1F1
FFFFFFF 0000000
FEFE
FEFE
FEFE
FEFE
FFFFFFF FFFFFFF
Кроме того, некоторые пары ключей при шифровании переводят открытый текст в идентичный шифротекст.
Иными словами, один из ключей пары может расшифровать сообщения, зашифрованные другим ключом пары.
Это происходит из-за метода, используемого DES для генерации подключей - вместо 16 различных подключей эти ключи генерируют только два различных подключа. В алгоритме каждый из этих подключей используется восемь раз. Эти ключи, называемые полуслабыми ключами, в шестнадцатиричном виде приведены в 0-й.
Табл. 12-12.
Полуслабые пары ключей DES
01FE
01FE
01FE
01FE
и
FE01
FE01
FE01
FE01 1FE0 1FE0 0EF1 0EF1
и
E01F
E01F
F10E
F10E
01E0 01E0 01F1 01F1
и
E001
E001
F101
F101 1FFE
1EEE
0EFE
0EFE
и
FE1F
FE1F
FE0E
FE0E
011F
011F
010E
010E
и
1F01 1F01 0E01 0E01
E0FE
E0FE
F1FE
F1FE
и
FEE0
FEE0
FEE1
FEE1
Ряд ключей генерирует только четыре подключа, каждый из которых четыре раза используется в алгоритме.

Эти возможно слабые ключи перечислены в -1-й.
Табл. 12-13.
Возможно слабые ключи DES
1F
1F
01 01 0E
0E
01 01
E0 01 01
E0
F1 01 01
F1 01 1F
1F
01 01 0E
0E
01
FE
1F
01
E0
FE
0E
01
F1 1F
01 01 1F
0E
01 01 0E
FE
01 1F
E0
FE
01 0E
F1 01 01 1F
1F
01 01 0E
0E
E0 1F
1F
E0
F1 0E
0E
F1
E0
E0 01 01
F1
F1 01 01
FE
01 01
FE
FE
01 01
FE
FE
FE
01 01
FE
FE
01 01
E0 1F
01
FE
F1 0E
01
FE
FE
E0 1F
01
FE
F1 0E
01
E0 01 1F
FE
F1 01 0E
FE
E0
FE
1F
01
F1
FE
0E
01
FE
1F
1F
FE
FE
0E
0E
FE
FE
E0 01 1F
FE
F1 01 0E
1F
FE
01
E0 0E
FE
01
F1
E0
FE
01 1F
F1
FE
01 0E
01
FE
1F
E0 01
FE
0E
F1
E0
E0 1F
1F
F1
F1 0E
0E
1F
E0 01
FE
0E
F1 01
FE
FE
FE
1F
1F
FE
FE
0E
0E
01
E0 1F
FE
01
F1 0E
FE
FE
1F
E0 01
FE
0E
F1 01 01 01
E0
E0 01 01
F1
F1
E0 1F
FE
01
F1 0E
FE
01 1F
1F
E0
E0 0E
0E
F1
F1
FE
01
E0 1F
FE
01
F1 0E
1F
01
FE
E0 0E
01
FE
F1
E0 01
FE
1F
F1 01
FE
0E
01 1F
FE
E0 01 0E
FE
F1 01
E0
E0 01 01
F1
F1 01 1F
01
E0
FE
0E
01
F1
FE
1F
FE
E0 01 0E
FE
F0 01 01 1F
E0
FE
01 0E
F1
FE
1F
E0
FE
01 0E
F1
FE
01 01 01
FE
FE
01 01
FE
FE
01
FE
FE
01 01
FE
FE
01 1F
1F
FE
FE
0E
0E
FE
FE
1F
E0
E0 1F
0E
F1
F1 0E
FE
FE
E0
E0
FE
FE
F1
F1 01
FE
E0 1F
01
FE
F1 0E
E0
FE
FE
E0
F1
FE
FE
F1 01
E0
FE
1F
01
F1
FE
0E
FE
E0
E0
FE
FE
F1
F1
FE
1F
FE
FE
1F
0E
FE
FE
0E
E0
E0
FE
FE
F1
F1
FE
FE
Прежде, чем порицать DES слабые ключи, обратите внимание на то, что эти 64 ключа - это крошечная часть полного набора из 72057594037927936 возможных ключей. Если вы выбираете ключ случайно, вероятность выбрать один из слабых ключей пренебрежимо мала. Если вы настоящий параноик, можете всегда проверять "на слабость" сгенерированный ключ. Некоторые думают, что нечего и беспокоиться на этот счет. Другие у т- верждают, что проверка очень легка, почему бы ее и не в ыполнить.
Дальнейший анализ слабых и полуслабых ключей приведен в [1116]. Других слабых ключей в процессе и с- следований найдено не было.
Ключи-дополнения
Выполним побитное дополнение ключа, заменяя все 0 на 1 и все 1 - на 0. Теперь, если блок открытого текста зашифрован оригинальным ключом, то дополнение ключа при шифровании превратит дополнение блока о т- крытого текста в дополнение блока шифротекста. Если x' обозначает дополнение x, то следующее верно:
E
K
(P) = C
E
K'
(P') = C'
В этом нет ничего таинственного. На каждом этапе после перестановки с расширением подключи подверг а- ются операции XOR с правой половиной. Прямым следствием этого факта и является приведенное свойство комплиментарности.
Это означает, что при выполнении вскрытия DES с выбранным открытым текстом нужно проверять только половину возможных ключей: 2 55
вместо 2 56
[1080]. Эли Бихам (Eli Biham) и Ади Шамир показали [172], что существует вскрытие с известным открытым текстом, имеющее ту же сложность, для которого нужно не меньше
2 33
известных открытых текстов.
Остается вопросом, является ли такое свойство слабостью, так как в большинстве сообщений нет компл и- ментарных блоков открытого текста (для случайного открытого текста шансы "против" чрезвычайно велики), а пользователей можно предупредить не пользоваться дополняющими.
Алгебраическая структура
Все возможные 64-битовые блоки открытого текста можно отобразить на 64-битовые блоки шифротекста

2 64
! Различными способами. Алгоритм DES, используя 56-битовый ключ, предоставляет нам 2 56
(приблизительно 10 17
) таких отображений. Использование многократного шифрования на первый взгляд позв о- ляет значительно увеличить долю возможных отображений. Но это правильно только, если действие DES не обладает определенной алгебраической структурой.
Если бы DES был замкнутым, то для любых K
1
и K
2
всегда существовало бы такое K
3
, что
E E P
E P
K
K
K
2 1
3
(
( ))
( )
=
Другими словами, операция шифрования DES образовала бы группу, и шифрование набора блоков открыт о- го текста последовательно с помощью K1 и K2 было бы идентично шифрованию блоков ключом K3. Что еще хуже, DES был бы чувствителен к вскрытию "встреча посередине" с известным открытым текстом, для которого потребовалось бы только 2 28
этапов [807].
Если бы DES был чистым, то для любых K
1
, K
2
и K
3
всегда существовало бы такое K
4
, что
E
E
E
P
E
P
K
K
K
K
3 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.

Количество этапов
Почему 16 этапов? Почему не 32? После пяти этапов каждый бит шифротекста является функцией всех б и- тов открытого текста и всех битов ключа [1078, 1080], а после восьми этапов шифротекст по сути представляет собой случайную функцию всех битов открытого текста и всех битов ключа [880]. (Это называется лавинным эффектом.) Так почему не остановиться после восьми этапов?
В течение многих лет версии DES с уменьшенным числом этапов успешно вскрывались. DES с тремя и ч е- тырьмя этапами был легко взломан в 1982 году [49]. DES с шестью этапами пал несколькими годами позже
[336]. Дифференциальный криптоанализ Бихама и Шамира объяснил и это: DES с любым количеством этапов,
меньшим 16, может быть взломан с помощью вскрытия с известным открытым текстом быстрее, чем с пом о- щью вскрытия грубой силой. Конечно грубый взлом является более вероятным способом вскрытия, но интер е- сен тот факт, что алгоритм содержит ровно 16 этапов.
Проектирование S-блоков
Помимо уменьшения длины ключа NSA также обвиняют в изменении содержания S-блоков. Настаивая на подтверждении схемы S-блоков, NSA заявило, что детали алгоритма являются "чувствительными" и не могут быть опубликованы. Многие криптографы подозревали, что разработанные в NSA S-блоки содержат лазейку,
позволяющую NSA легко выполнять криптоанализ алгоритма.
С момента появления алгоритма для анализа схемы и работы S-блоков были предприняты значительные усилия. В середине 70-х Lexar Corporation [961, 721] и Bell Laboratories [1120] исследовали работу S-блоков. Ни одно из исследований не обнаружило никаких слабостей, хотя оба исследования обнаружили непонятный сво й- ства. S-блоки имеют больше свойств, общих с линейным преобразованием, чем можно было ожидать при их формировании случайным образом. Команда Bell Laboratories констатировала, что S-блоки могут содержать скрытые лазейки, а доклад Lexar завершался следующей фразой:
В DES были найдены структуры, несомненно вставленные для повышения устойчивости системы к определенным типам вскрытия. Также были найдены структуры, кот орые, по видимому, ослабили систему.
С другой стороны этот доклад также содержал следующее предупреждение:
... проблема [поиска структур в S-блоках] усложняется из-за способности человеческого сознания находить в случайных данных структуры, которые в действител ьности вовсе не являются структурами.
На втором симпозиуме по DES Агентство национальной безопасности раскрыло ряд критериев проектиров а- ния S-блоков [229]. Но это не смогло снять всех подозрений, и спор продолжился [228, 422, 714, 1506, 1551].
В литературе про S-блоки писались удивительные вещи. Последние три бита результата четвертого S-блока могут быть получены тем же способом, что и первые, при помощи дополнения некоторых из входных битов
[436, 438]. Различные, но тщательно подобранные входные данные для S-блоков могут давать одинаковый р е- зультат [436]. Можно получить результат одного этапа DES, меняя биты только в трех соседних S-блоках [487].
Шамир заметил, что элементы S-блоков, казалось, были несколько неустойчивы, но не собирался использовать эту неустойчивость для вскрытия [1423]. (Он упомянул об особенности пятого S-блока, но только спустя восемь лет линейный криптоанализ воспользовался этой особенностью.) Другие исследователи показали, что для пол у- чения S-блоков с наблюдаемыми характеристиками могли использоваться общеизвестные принципы проект и- рования [266).
Дополнительные результаты
Были предприняты и другие попытки криптоанализировать DES. Один из криптографов искал закономерн о- сти, используя спектральные тесты [559]. Другие анализировали последовательность линейных множителей, но их вскрытие потерпело неудачу после восьми этапов [1297, 336, 531]. Неопубликованное вскрытие, выполне н- ное в 1987 году Дональдом Дэвисом (Donald Davies), использовало способ, с помощью которого перестановка с расширением повторяет биты в соседних S-блоках, это вскрытие также оказалось бесполезным после восьми этапов [172, 429].
12.4 Дифференциальный и линейный криптоанализ
Дифференциальный криптоанализ
В 1990 году Эли Бихам и Ади Шамир ввели понятие дифференциального криптоанализа [167, 168, 171,
172]. Это был новый, ранее неизвестный метод криптоанализа. Используя этот метод, Бихам и Шамир нашли способ вскрытия DES с использованием выбранного открытого текста, который был эффективнее вскрытия гр у- бой силой.
Дифференциальный криптоанализ работает с парами шифротекстов, открытые тексты которых содержат определенные отличия. Метод анализирует эволюцию этих отличий в процессе прохождения открытых текстов

через этапы DES при шифровании одним и тем же ключом.
Просто выберем пару открытых текстов с фиксированным различием. Можно выбрать два открытых текста случайным образом, лишь бы они отличались друг от друга определенным образом, криптоаналитику даже не нужно знать их значений. (Для DES термин "различие" определяется с помощью XOR. Для других алгоритмов этот термин может определяться по другому.) Затем, используя различия в получившихся шифротекстах, пр и- своим различные вероятности различным ключам. В процессе дальнейшего анализа следующих пар шифроте к- стов один из ключей станет наиболее вероятным. Это и есть правильный ключ.
Подробности гораздо сложнее. На 7-й представлена функция одного этапа DES. Представьте себе пару вх о- дов, X и X', с различием ?X. Выходы, Y и Y' известны, следовательно, известно и различие между ними ?Y. Из- вестны и перестановка с расширением, и P-блок, поэтому известны ?A и ?C. B и B' неизвестны, но их разность
?B известна и равна ?A. (При рассмотрении различия XOR K
i с A и A' нейтрализуются.) Пока все просто. Фокус вот в чем: для любого заданного ?A не все значения ?C равновероятны. Комбинация ?A и ?C позволяет пред- положить значения битов для A XOR K
i и A' XOR K
i
. Так как A и A' известны, это дает нам информацию о K
i
,Y
,C
,B
,A
,X
Y
P
S-блок
K
i
E
E(X)
X
Рис. 12-5. Функция этапа DES.
Взглянем на последний этап DES. (При дифференциальном криптоанализе начальная и заключительная п е- рестановки игнорируются. Они не влияют на вскрытие, только затрудняя объяснение.) Если мы сможем опред е- лить K
16
, то мы получим 48 битов ключа. (Не забывайте, на каждом этапе подключ состоит из 48 битов 56- битового ключа.) Оставшиеся 8 битов мы можем получить грубым взломом. K
16
даст нам дифференциальный криптоанализ.
Определенные различия пар открытых текстов обладают высокой вероятностью вызвать определенные ра з- личия получаемых шифротекстов. Эти различия называются характеристиками. Характеристики распростра- няются на определенное количество этапов и по существу определяют прохождение этих этапов. Существуют входное различие, различие на каждом этапе и выходное различие - с определенной вероятностью.
Эти характеристики можно найти, создав таблицу, строки которой представляют возможные входы XOR
(XOR двух различных наборов входных битов), столбцы - возможные результаты XOR, а элементы - сколько раз конкретный результат XOR встречается для заданного входа XOR. Такую таблицу можно сгенерировать для каждого из восьми S-блоков DES.
Например, на 6-йa показана характеристика одного этапа. Входное различие слева равно L, оно может быть произвольным. Входное различие справа равно 0. (У двух входов одинаковая правая половина, поэтому их ра з- личие - 0.) Так как на входе функции этапа нет никаких различий, то нет различий и на выходе функции этапа.
Следовательно, выходное различие левой части - L ? 0 = L, а выходное различие правой части - 0. Это трив и- альная характеристика, она истинна с вероятностью 1.

На 6-йб показана менее очевидная характеристика. Снова, различие L левых частей произвольно. Входное различие правых частей равно 0x60000000, два входа отличаются только первым и третьим битами. С вероя т- ностью 14/64 различие на выходе функции этапа равно L ? 0x00808200. Это означает, что выходное различие левых половин равно L ? 0x00808200, а выходное различие правых половин - 0x60000000 (с вероятностью
14/64)
? = L ? 0
? = L
K
i f
? = 0
? = 0
? = 0
? = 0
? = L ? 0
? = L
K
i f
? = X
? = Y
? = X
С вероятностью 14/64
(b)
С вероятностью 1
(a)
X = 0x60000000
Y = 0x00808200
? = X
Рис. 12-6. Характеристики DES.
Различные характеристики можно объединять. Также, при условии, что этапы независимы, вероятности м о- гут перемножаться. На 5-й объединяются две ранее описанных характеристики. Входное различие слева равно
0x00808200, а справа - 0x60000000. В конце первого этапа входное различие и результат функции этапа нейтр а- лизуют друг друга, и выходное различие равно 0. Это различие поступает на вход второго этапа, окончательное выходное различие слева равно 0x60000000, а справа - 0. Вероятность этой двухэтапной характерист ики - 14/64.
? = Y
? = Y
K
i f
? = 0
? = 0
? = X
? = X
K
i+1
f
? = X
? = Y
? = X
С вероятностью 14/64
(b)
X = 0x60000000
Y = 0x00808200
? = X
Рис. 12-7. Двухэтапная характеристика DES.
Пара открытых текстов, соответствующих характеристике, называется правильной парой, а пара открытых текстов, несоответствующих характеристике - неправильной парой. Правильная пара подсказывает правильный ключ этапа (для последнего этапа характеристики), неправильная пара - случайный ключ этапа.
Чтобы найти правильный ключ этапа, нужно просто собрать достаточное количество предположений. Один

из подключей будет встречаться чаще, чем все остальные. Фактически, правильный подключ возникнет из всех случайный возможных подключей.
Итак, дифференциальное основное вскрытие n-этапного DES дает 48-битовый подключ, используемый на этапе n, а оставшиеся 8 битов ключа получаются с помощью грубого взлома.
Но ряд заметных проблем все же остается. Во первых, пока вы не перейдете через некоторое пороговое зн а- чение, вероятность успеха пренебрежимо мала. То есть, пока не будет накоплено достаточное количество да н- ных, выделить правильный подключ из шума невозможно. Кроме того, такое вскрытие не практично. Для хр а- нения вероятностей 2 48
возможных ключей необходимо использовать счетчики, и к тому же для вскрытия п о- требуется слишком много данных.
Бихам и Шамир предложили свой способ вскрытия. Вместо использования 15-этапной характеристики 16- этапного DES, они использовали 13-этапную характеристику и ряд приемов для получения последних нескол ь- ких этапов. Более короткая характеристика с большей вероятностью будет работать лучше. Они также испол ь- зовали некоторые сложные математические приемы для получения вероятных 56-битовых ключей, которые и проверялись немедленно, таким образом устранялась потребность в счетчиках. Такое вскрытие достигает усп е- ха, как только находится правильная пара. Это позволяет избежать порогового эффекта и получить линейную зависимость для вероятности успеха. Если у вас в 1000 раз меньше пар, то вероятность успеха в 1000 раз мен ь- ше. Это звучит ужасно, но это намного лучше, чем порог. Всегда есть некоторая вероятность немедленной уд а- чи.
Результаты являются весьма интересными. В -2-й проведен обзор лучших дифференциальных вскрытий DES
с различным количеством этапов [172]. Первый столбец содержит количество этапов. Элементы следующих двух столбца представляют собой количество выбранных или известных открытых текстов, которые должны быть проверены для вскрытия, а четвертый столбец содержит количество действительно проанализированных открытых текстов. В последнем столбце приведена сложность анализа, после обнаружения требуемой пары.
Табл. 12-14. Вскрытие с помощью дифференциального криптоанализа
Количество этапов
Выбранные открытые тексты
Известные открытые тексты
Проанализированные открытые тексты
Сложность анализа
8 2
14 2
38 4
29 9
2 24 2
44 2
2 32
†
10 2
24 2
43 2
14 2
15 11 2
31 2
47 2
2 32
†
12 2
31 2
47 2
21 2
21 13 2
39 2
52 2
2 32
†
14 2
39 2
51 2
29 2
29 15 2
47 2
56 27 2
37 16 2
47 2
55 2
36 2
37
† Сложность анализа для этих вариантов может быть значительно уменьшена за счет использования примерно в четыре раза большего количество открытых текстов и метода группировок.
Наилучшее вскрытие полного 16-этапного DES требует 2 47
выбранных открытых текстов. Можно преобраз о- вать его к вскрытию с известным открытым текстом, но для него потребуется уже 2 55
известных открытых тек- стов. При анализе потребуется 2 37
операций DES.
Дифференциальный криптоанализ эффективен против DES и аналогичных алгоритмов с постоянными S- блоками. Эффективность вскрытие сильно зависит от структуры S-блоков, блоки DES по счастливой случайн о- сти были оптимизированы против дифференциального криптоанализа. Для всех режимов работы DES - ECB,
CBC, CFB и OFB - вскрытие с дифференциальным криптоанализом имеет одинаковую сложность [172].
Устойчивость DES может быть повышена путем увеличения количества этапов. Дифференциальный кри п- тоанализ с выбранным открытым текстом для DES с 17 или 18 этапами потребует столько же времени, сколько нужно для вскрытия грубой силой [160]. При 19 и более этапах дифференциальный криптоанализ становится невозможным, так как для него потребуется более, чем 2 64
выбранных открытых текстов - не забудьте, DES и с- пользует блоки размером 64 битов, поэтому для него существует только 2 64
возможных открытых текстов. (В
общем случае, вы можете доказать устойчивость алгоритма к дифференциальному криптоанализу, показав, что количество открытых текстов, необходимых для выполнения вскрытия, превышает количество возможных о т- крытых текстов.)

Нужно отметить ряд важных моментов. Во первых, это вскрытие в значительной степени теоретическое. О г- ромные требования к времени и объему данных, необходимых для выполнения вскрытия с помощью дифф е- ренциального криптоанализа, находятся почти для всех вне пределов досягаемости. Чтобы получить нужные данные для выполнения такого вскрытия полного DES, вам придется почти три года шифровать поток выбра н- ных шифротекстов 1.5 Мегабит/с. Во вторых, это в первую очередь вскрытие с выбранным открытым текстом.
Оно может быть преобразовано к вскрытию с известным открытым текстом, но вам придется просмотреть все пары "открытый текст/шифротекст" в поисках полезных. В случае полного 16-этапного DES это делает вскр ы- тие чуть менее эффективным по сравнению с грубой силой (вскрытие дифференциальным криптоанализом тр е- бует 2 55.1
операций, а вскрытие грубой силой - 2 55
). Таким образом, правильно реализованный DES сохраняет устойчивость к дифференциальному криптоанализу.
Почему DES так устойчив к дифференциальному криптоанализу? Почему S-блоки оптимизированы так, что усложняют такое вскрытие насколько возможно? Почему используется ровно столько, а не больше этапов? П о- тому что создатели DES знали о дифференциальном анализе. Дон Копперсмит из IBM недавно писал [373, 374]:
При проектировании использовались преимущества определенных криптоаналитических методов, особенно метода "дифференциального криптоанализа", который не был опубликован в открытой литературе. После дискуссий с NSA было р е- шено, что раскрытие процесса проектирования раскроет и метод дифференциального криптоанализа, мощь которого может быть использована против многих шифров. Это, в свою очередь, сократило бы преимущество Соединенных Штатов перед другими странами в области криптографии.
Ади Шамир откликнулся, предложив Копперсмиту признаться, что с тех пор ему не удалось найти эффе к- тивного способа вскрытия DES. Копперсмит предпочел отмолчат ься [1426].
Криптоанализ со связанными ключами
В 9-й показано количество битов, на которые циклически смещается ключ DES на каждом этапе: на 2 бита на каждом этапе, кроме этапов 1, 2, 9 и 16, когда ключ сдвигается на 1 бит. Почему?
Криптоанализ со связанными ключами похож на дифференциальный криптоанализ, но он изучает разл и- чие между ключами. Вскрытие отличается от любого из ранее рассмотренных: криптоаналитик выбирает связь между парой ключей, но сами ключи остаются ему неизвестны. Данные шифруются обоими ключами. В вар и- анте с известным открытым текстом криптоаналитику известны открытый текст и шифротекст данных, шифр о- ванных двумя ключами. В варианте с выбранным открытым текстом криптоаналитик пытается выбрать откр ы- тый текст, зашифрованный двумя ключами.
Модифицированный DES, в котором ключ сдвигается на два бита после каждого этапа, менее безопасен.
Криптоанализ со связанными ключами может взломать такой вариант алгоритма, использовав только 2 17
вы- бранных открытых текстов для выбранных ключей или 2 33
известных открытых текстов для выбранных ключей
[158, 163].
Такое вскрытие также не реализуемо на практике, но оно интересно по трем причинам. Во первых, это пе р- вая попытка криптоаналитического вскрытия алгоритма генерации подключей в DES. Во вторых, это вскрытие не зависит от количества этапов криптографического алгоритма, он одинаково эффективен против DES с 16, 32
или 1000 этапами. И в третьих, DES невосприимчив к такому вскрытию. Изменение количества битов циклич е- ского сдвига мешает криптоанализу со связанными ключами.
Линейный криптоанализ
Линейный криптоанализ представляет собой другой тип криптоаналитического вскрытия, изобретенный
Мицуру Мацуи (Mitsuru Matsui) [1016, 1015, 1017]. Это вскрытие использует линейные приближения для оп и- сания работы блочного шифра (в данном случае DES.)
Это означает, что если вы выполните операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над результатами, вы получите бит, который представляет собой
XOR некоторых битов ключа. Это называется линейным приближением, которое может быть верным с некот о- рой вероятностью p. Если p ? 1/2, то это смещение можно использовать. Используйте собранные открытые те к- сты и связанные шифротексты для предположения о значениях битов ключа. Чем больше у вас данных, тем вернее предположение. Чем больше смещение, тем б ыстрее вскрытие увенчается успехом.
Как определить хорошее линейное приближение для DES? Найдите хорошие одноэтапные линейные пр и- ближения и объедините их. (Начальная и заключительная перестановки снова игнорируются, так как они не влияют на вскрытие.) Взгляните на S-блоки. У них 6 входных битов и 4 выходных. Входные биты можно объ е- динить с помощью операции XOR 63 способами (2 6
- 1), а выходные биты - 15 способами. Теперь для каждого
S-блока можно оценить вероятность того, что для случайно выбранного входа входная комбинация XOR равна некоторой выходной комбинации XOR. Если существует комбинация с достаточно большим смещением, то л и- нейный криптоанализ может сработать.
Если линейные приближения не смещены, то они будут выполняться для 32 из 64 возможных входов. Я и з-

бавлю вас от длительного изучения таблиц, наиболее смещенным S-блоком является пятый S-блок. Действ и- тельно, для 12 входов второй входной бит равен XOR всех четырех выходных битов. Это соответствует вероя т- ности 3/16 или смещению 5/16, что является самым большим смещением для всех S-блоков. (Шамир писал об этом в [1423], но не смог найти способа использовать.)
На 4-й показано, как воспользоваться этим для вскрытия функции этапа DES. b26 - это входной бит S-блока
5. (Я нумерую биты слева направо от 1 до 64. Мацуи игнорирует это принятое для DES соглашение и нумерует свои биты справа налево и от 0 до 63. Этого хватит, чтобы свести вас с ума.) c
17
, c
18
, c
19
, c
20
- это 4 выходных бита S-блока 5. Мы можем проследить b
26
в обратном направлении от входа в S-блок. Для получения b
26
бит объединяется с помощью XOR с битом подключа K
i,26
. А бит X
17
проходит через подстановку с расширением,
чтобы превратиться в a
26
. После S-блока 4 выходных бита проходят через P-блок, превращаясь в четыре выхо д- ных бита функции этапа: Y
3
, Y
8
, Y
14
и Y
25
. Это означает, что с вероятностью 1/2 - 5/6:
X
17
? Y
3
? Y
8
? Y
14
? Y
25
= K
i,26
c
17
,c
18
,c
19
, c
20
b
26
a
26
Y
3
, Y
8
, Y
14
, Y
25
K
i,26
X
17
Y
P
S-блок
K
i
E
E(X)
X
Рис. 12-8. 1-этапное линейное приближение для DES.
Способ, которым можно объединить линейные приближения для различных этапов, похож на тот, который обсуждался для дифференциального криптоанализа. На 3-й показано 3-этапное линейное приближение с вер о- ятностью 1/2+0.0061. Качество отдельных приближений различно: последнее очень хорошо, первое достаточно хорошо, а среднее - плохо. Но вместе эти три 1-этапных приближения дают очень хорошее трехэтапное пр и- ближение.

B
B
B
K
i,26
K
i-1,26
f
3 17 17 17 17
f
С вероятностью 1/2+6.1*10
-3 17
A
17
K
i+1,26 17
A
f
17
B=[8, 14, 25]
A=[3, 8, 14, 25]
A
Рис. 12-9. 3-этапное линейное приближение DES.
Базовое вскрытие должно использовать наилучшее линейное приближение для 16-этапного DES. Для него требуется 2 47
известных открытых блоков, а результатом вскрытия является 1 бит ключа. Это не очень полезно.
Если вы поменяете местами открытый текст и шифротекст и используете дешифрирование вместе с шифров а- нием, вы сможете получить 2 бита. Это все еще не очень полезно.
Существует ряд тонкостей. Используйте 14-этапное линейное приближение для этапов с 2 по 15. Попробуем угадать 6 битов подключа для S-блока 5 первого и последнего этапов (всего, таким образом, 12 битов ключа).
Для эффективности выполняем линейный криптоанализ параллельно 2 12
раз и выбираем правильный вариант,
основываясь на вероятностях. Это раскрывает 12 битов и b
26
, а поменяв местами открытый текст и шифротекст мы получим еще 13 битов. Для получения оставшихся 30 битов используйте исчерпывающий поиск. Существ у- ют и друге приемы, но описанный является основным.
При вскрытии таким образом полного 16 этапного DES ключ будет раскрыт в среднем с помощью 2 43
из- вестных открытых текстов. Программная реализации этого вскрытия, работая на 12 рабочих станциях HP9735,
раскрыла ключ DES за 50 дней [1019]. В момент написания этой книги это наиболее эффективный способ вскрытия DES.
Линейный криптоанализ сильно зависит от структуры S-блоков, оказалось, что S-блоки DES не оптимизир о- ваны против такого способа вскрытия. Действительно, смещение в S-блоках, выбранных для DES, находится между 9 и 16 процентами, что не обеспечивает надежной защиты против линейного криптоанализа [1018]. С о- гласно Дону Копперсмиту [373, 374] устойчивость к линейному криптоанализу "не входило в число критериев проектирования DES". Либо разработчикам не было известно о линейном криптоанализе, либо при проектир о- вании они отдали преимущество устойчив ости против известного им еще более мощного средства вскрытия.
Линейный криптоанализ новее, чем дифференциальный, и в ближайшее время возможно дальнейшее пр о- движение в этом направлении. Некоторые идеи выдвинуты в [1270, 811], но не ясно, можно ли их эффективно применить против полного DES. Однако они очень хорошо работают против вариантов с уменьшенным числом этапов.

Дальнейшие направления
Был предпринят ряд попыток расширить концепцию дифференциального криптоанализа на дифференциалы более высоких порядков [702, 161, 927, 858, 860]. Ларс Кнудсен (Lars Knudsen) использует нечто, называемое частичными дифференциалами для вскрытия 6-этапного DES. Этот метод требует 32 выбранных открытых те к- ста и 20000 шифрований [860]. Но этот метод слишком нов, чтобы можно было утверждать, что он облегчит вскрытие полного 16-этапного DES.
Другим способом вскрытия является дифференциально-линейный криптоанализ - объединение дифференц и- ального и линейного криптоанализа. Сьюзен Лангфорд (Susan Langford) и Хеллман предлагают вскрытие
8-этапного DES, которое раскрывает 10 битов ключа с вероятностью успеха 80 процентов, используя 512 в ы- бранных открытых текстов, и с вероятностью успеха 95 процентов, используя 768 выбранных открытых текстов
[938]. После вскрытия необходим поиск грубой силой в оставшемся пространстве ключей (2 46
возможных клю- чей). Хотя по времени это вскрытие сравнимо с предыдущими способами, для него требуется намного меньше открытых текстов. Однако расширение этого метода на большее количество этапов легким не кажется.
Но этот метод нов, и работа продолжается. В ближайшие годы возможны заметные успехи. Может быть у с- пеха добьется сочетание этого вскрытия с дифференциальным криптоанализом более высоких порядков. Кто знает?
12.5 Реальные критерии проектирования
После появления публикаций о дифференциальном криптоанализе IBM раскрыла критерии проектирования
S-блоков и P-блока [373, 374]. Критериями проектирования S-блоков являлись:
— У каждого S-блока 6 входных битов и 4 выходных бита. (Это самый большой размер, который мог быть реализован в одной микросхеме по технологии 1974 года.)
— Ни один выходной бит S-блока не должен быть слишком близок к линейной функции входных битов.
— Если зафиксировать крайние левый и правый биты S-блока, изменяя 4 средних бита, то каждый возмо ж- ный 4-битовый результат получается только один раз.
— Если два входа S-блока отличаются только одним битом, результаты должны отличаться по крайней мере на 2 бита.
— Если два входа S-блока отличаются только двумя центральными битами, результаты должны отличаться по крайней мере на 2 бита.
— Если два входа S-блока отличаются двумя первыми битами, а последние их последние 2 бита совпадают,
результаты не должны быть одинаковыми.
— Для любого ненулевого 6-битового отличия между входами, не более, чем 8 из 32 пар входов могут пр и- водить на выходе к одинаковому различию.
— Аналогичный предыдущему критерий, но для случая трех активных S-блоков.
Критериями проектирования P-блока являлись:
— 4 выходных бита каждого S-блока на этапе i распределены так, чтобы 2 из них влияют на средние биты
S-блоков на этапе i + 1, а другие 2 бита влияют на п оследние биты.
— 4 выходных бита каждого S-блока влияют на шесть различных S-блоков, никакие 2 не влияют на один и тот же S-блок.
— Если выходной бит одного S-блока влияет на средние биты другого S-блока, то выходной бит этого др у- гого S-блока не может влиять на средние биты первого S-блока.
Эта работа продолжала обсуждение критериев. Сегодня совсем нетрудно генерировать S-блоки, но в начале
70-х это было нелегкой задачей. Тачмен говорил, что программы, готовившие S-блоки, работали месяцами.
12.6 Варианты DES
Многократный DES
В ряде реализаций DES используется трехкратный DES (см. 2-й) [55]. Так как DES е является группой, п о- лученный шифротекст гораздо сложнее вскрыть, используя исчерпывающий поиск: 2 112
попыток вместо 2 56
Подробности можно найти в разделе 15.2.

DES
-1
DES
K
1
DES
DES
-1
K
2
DES
-1
DES
Шифротекст
Открытый текст
Дешифрирование
Шифрование
K
3
Рис. 12-10. Трехкратный DES.
DES с независимыми подключами
Другой возможностью является использование различных подключей на каждом этапе, не создавая их из одного 56-битового ключа [851]. Так как на каждом из 16 этапов используется 48 битов ключа, то длина ключа для такого варианта составит 768 битов. Такой вариант резко увеличивает сложность вскрытия алгоритма гр у- бой силой, сложность такого вскрытия составит 2 768
Однако возможно использование вскрытия "встреча посередине" (см. раздел 15.1). Сложность такого вскр ы- тия уменьшается до 2 384
, что, тем не менее, вполне достаточно для обеспечения любой мыслимой безопасн ости.
Хотя независимые подключи мешают линейному криптоанализу, этот вариант чувствителен к дифференц и- альному криптоанализу и может быть вскрыт с помощью 2 61
выбранных открытых текстов (см. -3-й) [167, 172].
По видимому, никакая модификация распределения ключей не сможет н амного усилить DES.
DESX
DESX - это вариант DES, разработанный RSA Data Security, Inc., и включенный в 1986 году в программу обеспечения безопасности электронной почты MailSafe, а в 1987 году в набор BSAFE. DESX использует метод,
называемый отбеливанием (см. раздел 15.6), для маскировки входов и выходов DES. Кроме 56-битового ключа
DES в DESX используется дополнительный 64-битовый ключ отбеливания. Эти 64 бита используются для в ы- полнения операции XOR с блоком открытого текста перед первым этапом DES. Дополнительные 64 бита, я в- ляющиеся результатом применения однонаправленной функции к полному 120-битовому ключу DESX, испол ь- зуются для выполнения XOR с шифротекстом, полученным в результате последнего этапа [155]. По сравнению с DES отбеливание значительно повышает устойчивость DESX к вскрытию грубой силой, вскрытие требует
(2 120
)/n операций при n известных открытых текстах. Также повышается устойчивость к дифференциальному и линейному криптоанализу, для вскрытия потребуется 2 61
выбранных и 2 60
известных открытых текстов, соот- ветственно [1338].
CRYPT(3)
CRYPT(3) представляет собой вариант DES, используемый в системах UNIX. Он в основном используется в качестве однонаправленной функции для паролей, но иногда может быть использован и для шифрования. Ра з- личие между CRYPT(3) и DES состоит в том, что в CRYPT(3) включена независимая от ключа перестановка с расширением с 2 12
вариантами. Это сделано для того, чтобы для создания аппаратного устройства вскрытия паролей нельзя было использовать промышленные микросхемы DES.
Обобщенный DES
Обобщенный DES (Generalized DES, GDES) был спроектирован для ускорения DES и повышения устойч и- вости алгоритма [1381, 1382]. Общий размер блока увеличился, а количество вычислений осталось неизме н- ным.
На 1-й показана поблочная диаграмма GDES. GDES работает с блоками открытого текста переменной дл и- ны. Блоки шифрования делятся на q 32-битовых подблоков, точное число которых зависит от полного размера блока (который по идее может меняться, но фиксирован для конкретной реализации). В общем случае q равно размеру блока, деленному на 32.

B
0
(3)
B
0
(2)
B
0
(1)
B
0
(q)
B
0
(q-1)
Открытый текст
F
B
1
(3)
B
1
(2)
B
1
(1)
B
1
(q)
B
1
(q-1)
F
B
2
(3)
B
2
(2)
B
2
(1)
K
1
B
2
(q)
B
2
(q-1)
K
2
F
B
n-1
(3)
B
n-1
(2)
B
n-1
(1)
B
n-1
(q)
B
n-1
(q-1)
K
i
F
K
n
B
n
(3)
B
n
(2)
B
n
(1)
B
n
(q)
B
n
(q-1)
Шифротекст
Рис. 12-11. GDES.
Функция f для каждого этапа рассчитывается один раз для крайнего правого блока. Результат при помощи операции XOR объединяется со всеми остальными частям, которые затем циклически смещаются направо.
GDES использует переменное число этапов n. В последний этап внесено незначительное изменение, чтобы пр о- цессы шифрования и дешифрирования отличались только порядком подключей (точно также, как в DES). Де й- ствительно, если q = 2 и n = 16, то описанный алгоритм превращается в DES.
Бихам и Шамир [167, 168] показали, что дифференциальный криптоанализ вскрывает GDES с q = 8 и n = 16
с помощью всего шести выбранных открытых текстов. При использовании независимых подключей требуется
16 выбранных открытых текстов. GDES с q = 8 и n = 22 вскрывается с помощью всего 48 выбранных открытых текстов, а для вскрытия GDES с q = 8 и n = 31 требуется всего 500000 выбранных открытых текстов. Даже
GDES с q = 8 и n = 64 слабее, чем DES - для его вскрытия нужно только 249 выбранных открытых текстов.
Действительно, любая более быстрая, чем DES, схема GDES является также и менее безопасной (см. -3-й).
Недавно появился еще один вариант этой схемы [1591]. Возможно он не более безопасен, чем оригинальный
GDES. Общем случае любой вариант DES с большими блоками, который быстрее DES, скорее всего менее безопасен по сравнению с DES.
DES с измененными S-блоками
Другие модификации DES связаны с S-блоками. В некоторых проектах используется переменный порядок
S-блоков. Другие разработчики меняют содержание самих S -блоков. Бихам и Шамир показали [170,172], что построение S-блоков и даже их порядок оптимальны с точки зрения устойчивости к дифференциальному кри п- тоанализу:
Изменение порядка восьми S-блоков DES (без изменения их значений) также значительно ослабляет DES: DES с 16 эт а- пами и конкретным измененным порядком вскрывается примерно за 2 38
шагов. ... Доказано, что DES со случайными S- блоками вскрыть очень легко. Даже минимальное изменение одного из элементов S_блоков DES может снизить устойч и-

вость DES к вскрытию.
S-блоки DES не были оптимизированы против линейного криптоанализа. Существуют и лучшие S-блоки,
чем предлагаемые в DES, но бездумная замена S-блоков новыми - не самая лучшая идея.
В -3-й [167, 169] перечислены некоторые модификации DES и количество выбранных открытых текстов,
нужное для выполнения дифференциального криптоанализа. В таблицу не включена одна из модификаций, об ъ- единяющая левую и правую половины с помощью сложения по модулю 24 вместо XOR, ее в 2 17
раз труднее вскрыть, чем DES [689].
RDES
RDES - это модификация, в которой в конце каждого этапа обмениваются местами правая и левая половины с использованием зависимой от ключа перестановки [893]. Обмены местами фиксированы и зависят только от ключа. Это означает, что может быть 15 обменов, зависимых от ключа, и 2 15
возможных вариантов, а также что эта модификация не устойчива по отношению к дифференциальному криптоанализу [816, 894, 112]. У RDES
большое количество слабых ключей. Действительно, почти каждый ключ слабее, чем типичный ключ DES. И с- пользовать эту модификацию нельзя.
Лучшей является идея выполнять обмен местами только в пределах правой половины и в начале каждого этапа. Другой хорошей идеей является выполнение обмена в зависимости от входных данных, а не как статич е- ской функции ключа. Существует множество возможных вариантов [813, 815]. В RDES-1 используется завис я- щая от данных перестановка 16-битовых слов в начале каждого этапа. В RDES-2 применяется зависящая от данных перестановка байтов в начале каждого этапа после 16-битовых перестановок, аналогичных RDES-1.
Развитием этой идеи является RDES-4, и т.д. RDES-1 устойчив и к дифференциальному [815], и к линейному криптоанализу [1136]. По видимому, RDES-2 и последующие варианты достаточно хороши.
Табл. 12-15.
Вскрытия вариантов DES с помощью дифференциального криптоанализа
Изменение работы
Количество выбранных открытых текстов
Полный DES (без изменений)
2 47
P-перестановка
Не может усилить
Тождественная перестановка
2 19
Порядок S-блоков
2 38
Замена XOR сложениями
2 39
, 2 31
S-блоки
Случайные
2 18
- 2 20
Случайные перестановки
2 33
- 2 41
Одноэлементные
2 33
Однородные таблицы
2 26
Удаление E-расширения
2 26
Порядок E-расширения и XOR
подключа
2 44
GDES (ширина q=8)
16 этапов
6, 16 64 этапа
2 49
(независимый ключ)
s n
DES
Группа корейских исследователей под руководством Кванджо Кима (Kwangjo Kim) попыталась найти набор
S-блоков, оптимально устойчивых и против дифференциального, и против линейного криптоанализа. Их первая попытка, известная как s
2
DES, представленная в [834], оказалась, как было показано в [855, 858], менее усто й- чивой, чем DES, против дифференциального криптоанализа. Следующий вариант, s
3
DES, был представлен в
[839] и оказался менее устойчив, чем DES, к линейному криптоанализу [856, 1491, 1527, 858, 838]. Бихам пре д-

ложил незначительно изменить алгоритм, чтобы сделать s
3
DES безопасным по отношению и к дифференциал ь- ному, и к линейному криптоанализу [165]. Исследователи вернулись к своим компьютерам и разработали улу ч- шенную технику проектирования S-блоков [835, 837]. Они предложили s
4
DES [836], а затем s
5
DES [838, 944].
В -4-й приведены для s3DES (с обращенными S -блоками 1 и 2), которые безопасны по отношению к обоим видам криптоанализа. Использование этого варианта вместе с трехкратным DES наверняка помешает крипто а- нализу.
DES с S-блоками, зависящими от ключа
Линейный и дифференциальный криптоанализ работают только, если аналитику известно строение S-блоков.
Если S-блоки зависят от ключа и выбираются криптографически сильным методом, то линейный и диффере н- циальный криптоанализ значительно усложнятся. Хотя надо помнить, что даже у хранящихся в секрете случа й- но созданных S-блоков очень плохие дифференциальные и линейные характеристики.
Табл. 12-16.
S-блоки s3DES (с обращенными S-блоками 1 и 2)
S-блок 1:
13 14 0
3 10 4
7 9
11 8
12 6
1 15 2
5 8
2 11 13 4
1 14 7
5 15 0
3 10 6
9 12 14 9
3 10 0
7 13 4
8 5
6 15 11 12 1
2 1
4 14 7
11 13 8
2 6
3 5
10 12 0
15 9
S-блок 2:
15 8
3 14 4
2 9
5 0
11 10 1
13 7
6 12 6
15 9
5 3
12 10 0
13 8
4 11 14 2
1 7
9 14 5
8 2,
4 15 3
10 7
6 13 1
11 12 0
10 5
3 15 12 9
0 6
1 2
8 4
11 14 7
13
S-блок 3:
13 3
11 5
14 8
0 6
4 15 1
12 7
2 10 9
4 13 1
8 7
2 14 11 15 10 12 3
9 5
0 6
6 5
8 11 13 14 3
0 9
2 4
1 10 7
15 12 1
11 7
2 8
13 4
14 6
12 10 15 3
0 9
5
S-блок 4:
9 0
7 11 12,
5 10 6
15 3
1 14 2
8 4
13 5
10 12 6
0 15 3
9 8
13 11 1
7 2
14 4
10 7
9 12 5
0 6
11 3
14 4
2 8
13 15 1
3 9
15 0
6 10 5
12 14 2
1 7
13 4
8 11
S-блок 5:
5 15 9
10 0
3 14 4
2 12 7
1 13 6
8 11 6
9 3
15 5
12 0
10 8
7 13 4
2 11 14 1
15 0
10 9
3 5
4 14 8
11 1
7 6
12 13 2
12 5
0 6
15 10 9
3 7
2 14 11 8
1 4
13
S-блок 6:
4 3
7 10 9
0 14 13 15 5
12 6
2 11 1
8 14 13 11 4
2 7
1 8
9 10 5
3 15 0
12 6
13 0
10 9
4 3
7 14 1
15 6
12 8
5 11 2
1 7
4 14 11 8
13 2
10 12 3
5 6
15 0
9

S-блок 7:
4 10 15 12 2
9 1
6 11 5
0 3
7 14 13 8
10 15 6
0 5
3 12 9
1 8
11 13 14 4
7 2
2 12 9
6 15 10 4
1 5
11 3
0 8
7 14 13 12 6
3 9
0 5
10 15 2
13 4
14 7
11 1
8
S-блок 8:
13 10 0
7 3
9 14 4
2 15 12 1
5 6
11 8
2 7
13 1
4 14 11 8
15 12 6
10 9
5 0
3 4
13 14 0
9 3
7 10 1
8 2
11 15 5
12 6
8 11 7
14 2
4 13 1
6 5
9 0
12 15 3
10
Вот как можно использовать 48 дополнительных битов ключа для создания S-блоков, устойчивых как к л и- нейному, так и к дифференциальному криптоанализу [165].
(1) Изменить порядок S-блоков DES: 24673158.
(2) Выбрать 16 из оставшихся битов ключа. Если первый бит 1, обменять местами первые и последние два ряда S-блока 1. Если второй бит 1, обменять местами первые и последние восемь столбцов S-блока 1. П о- вторить то же самое для третьего и четвертого битов и S-блока 2. Повторить то же самое для S-блоков с 3
по 8.
(3) Взять оставшиеся 32 бита ключа. Выполнить XOR первых четырех битов с каждым элементом S-блока 1,
XOR следующих четырех битов с каждым элементом S-блока 2, и так далее.
Сложность вскрытия такой системы с помощью дифференциального криптоанализа составит 251, с пом о- щью линейного криптоанализа - 2 53
. Сложность исчерпывающего перебора составит 2102.
Что хорошо в этом варианте DES так это то, что он может быть реализован в существующей аппаратуре.
Различные поставщики микросхем DES продают микросхемы DES с возможностью загрузки S-блоков. Можно реализовать любой способ генерации S-блоков вне микросхемы и затем загрузить их в нее. Для дифференц и- ального и линейного криптоанализа нужно так много известных или выбранных открытых текстов, что эти сп о- собы вскрытия становятся неосуществимыми. Вскрытие грубой силой также трудно себе представить, не пом о- жет никакое увеличение скорости.