<< Предыдущая

стр. 20
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

бит за прием. Однако они высоко эффективны с точки зрения
аппаратной реализации.
Блочные шифры удобны как для программных, так и для аппа­
ратных средств, но они не допускают такой высокой скорости
обработки информации, как поточные.
Аппаратные средства функционируют быстрее, чем программ­
ное обеспечение, но этот выигрыш происходит за счет сниже­
ния гибкости.


5.2. Шифр Феистеля и DES
Шифр DES — вариант базисного шифра Феистеля (см. рис. 5.4),
названного по имени Г. Феистеля, работавшего в фирме IBM и вы­
полнившего некоторые из самых ранних невоенных исследований в
области алгоритмов шифрования. Интересная особенность шифра
Феистеля заключается в том, что функция раунда обратима вне за­
висимости от свойств функции F (см. рис. 5.4). Чтобы в этом убе­
диться, обратимся к формулам. Каждый раунд шифрования осуще­
ствляется по правилу
k = Гг-1, Гг = h-i е F{ki, n-i).

Следовательно, расшифрование происходит за счет преобразований:
Ti—i =• li^ Н—1 ^^ ^г Ф -^ \"^г5 н)"


блок открытого текста \ 1о \ го \


п-1 1 ^-1 1
Sраундов
/ТТЛ*-ki
/ +
* *
Li, \п\

Ltis
БЛОК ШИФРОТЕКСТА \ Ls \

Р и с . 5.4. Основные операции пхифра Феистеля

Выписанные формулы показывают, что мы несколько упростили
первоначальный проект, поскольку
- в качестве F можно выбрать любую функцию и получить ши-
фруюш;ую функцию, которая будет обраш;аться при помош;и
секретного ключа;
Глава 5. Симметричные шифры

- одну и ту же микросхему можно использовать как р^ля шифро­
вания, так и д^ля расшифрования. Нам необходимо лишь про­
следить за порядками подключен, которые в этих процессах
обратны друг другу.
Конечно, А^ля создания криптостойкого шифра нам все eni;e надо
позаботиться о том,
- как генерировать подключи,
- сколько должно быть раундов,
- как определить функцию F,
Работа над DES была начата в начале 1970-ых годов группой со­
трудников IBM^ в которую входил и Фейстель. Отправной точкой
проекта послужил более ранний шифр — «Люцифер», как называли
его в IBM, Было известно, что управление национальной безопас­
ности {NSA) внесло изменения в проект. Долгое время специалисты
в области секретности считали, что изменения состояли в исполь­
зовании ловушки в функции F. Однако теперь считается, что они
были направлены на повьппение безопасности шифра. В частности,
эти модификации укрепили сопротивляемость шифра дифференци­
альному криптоанализу — технике, с которой гражданские иссле­
дователи не были знакомы до 1980-ых годов.
В документах национального института стандартизации США
(ANSI) криптосистема DES называется алгоритмом шифрования
данных (DEA)^ а международная организация по стандартизации,
ссылаясь на шифр DES^ пользуется аббревиатурой DEA-1. Этот
алгоритм являлся мировым стандартом на протяжении более чем
двадцати лет и утвердился как первый доступный всем желаюш;им
официальный алгоритм. Поэтому его стоит отметить как важней­
шую веху на пути криптографии от чисто военного использования
к широкомасштабному применению.
Основные черты шифра DES определяются прежде всего тем,
что он — обобш;ение шифра Фейстеля и, кроме того, в нем
- число раундов S равно 16,
- длина блока п — 64 бита,
- размер ключа — 56 битов,
- каждый из подключей fci, /1:2, . . . , fcie насчитывает 48 битов.
Заметим, что для многих современных алгоритмов длина ключа в
56 битов недостаточна. Поэтому в DES зачастую используют три
ключа вместо одного, проводя три итерации стандартного процес­
са. При этом, как легко подсчитать, длина ключа становится равной
5.2. Шифр Фейстелл и DES

168 битам. Такая версия классического шифра называется тройным
DES или 3DES (рис. 5.5). Есть и другой способ модификации DES^
в которой берут два ключа, увеличивая длину основного ключа до
112 битов. Упражнение 5.3.3 посвяп1;ено подробностям этого метода.

Р и с . 5.5. Тройной DES
1 PES 1 - » 1 PES'' 1 -• 1 DES 1

t 1 Т
1 2 3


i i i
PES'' 1
1 PES'' PEs\<-
4-




5.2.1. О б з о р д е й с т в и я хпифра DES
Как уже не раз отмечалось, в первом при­
ближении DES — это шифр Фейстеля с 16 \блок открытого текста]
раундами (рис. 5.6), за исключением того,
что как перед, так и после основных ите­
раций алгоритма Фейстеля осуществляются
некоторые перестановки. Обратите внима­
ние (рис. 5.6) на то, как два блока меняют­
ся местами перед последней перестановкой
алгоритма. Эта замена никак не влияет на
стойкость шифра, и пользователи часто за­
давались вопросом: зачем ее BOo6ni;e делать?
Один из членов творческого коллектива, раз­
работавшего DES^ утверждал, что она об­
легчает микросхемную реализацию процеду­ БЛОК ШИФРОТЕКСТА
ры шифрования.
Ш и ф р DES преобразует открытый текст Р и с . 5.6. Алгоритмы
из 64 битов следующим образом: ^^^ ^ Фейстеля
- производит начальную перестановку (IP);
- расш;епляет блок на левую и правую половины;
- осуш;ествляет 16 раундов с одним и тем же набором операций;
- соединяет половины блока;
- производит конечную перестановку.
Конечная перестановка обратна начальной. Это позволяет ис­
пользовать одно и то же программное обеспечение и «железо» для
двух сторон процесса: шифрования и расшифрования. Разворачива-
Глава 5. Симметричные шифры

ние ключа дает 16 подключен по 48 битов каждый, выделяя их из
56-битного основного ключа.
Сейчас мы опишем действие функции F. В каждом раунде алго­
ритма DES оно состоит из шести шагов:
- Перестановка с расширением. Правая половина из 32 битов
растягивается до 48 битов и перемешивается. Это помогает
рассеиванию связи между входными битами и выходными. Пе­
рестановка с расширением (отличная от начальной) выбирает­
ся так, чтобы один входной бит воздействовал на две замены
через S-блоки, о которых речь пойдет ниже. Это помогает рас­
пространять зависимости и создает лавинный эффект (малое
различие между двумя наборами входных данных превраш;а-
ется в большое на выходе).
- Слоэюение с подключом. К строке из 48 битов, полученной
после перестановки с расширением, и подключу (его длина то­
же 48 битов) применяется операция исключаюш;его ИЛИ, т. е.
каждая пара соответствуюп];их битов складывается по моду­
лю 2. Заметим, что подключ используется только в этом месте
алгоритма.
- Расщепление, Результат предыдуш;его шага расщепляется на
6 частей по 8 битов в каждом.
- S-блок. Каждый 6-битовый кусок передается в один из восьми
S-блоков (блоков подстановки), где он превраш;ается в набор
из 4 битов. S-блоки — нелинейные компоненты алгоритма DES
и именно они дают основной вклад в криптостойкость шифра.
Каждый S-блок представляет собой поисковую таблицу из че­
тырех строк и шестнадцати столбцов. Шесть входяш,их в S-
блок битов определяют, какую строку и какой столбец необхо­
димо использовать ^\ля замены. Первый и шестой бит задают
номер строки, а остальные — номер столбца. Выход S-блока
— значение соответствуюп1;ей ячейки таблицы.
- Р-блок. На этот момент у нас есть восемь групп 4-битовых
элементов, которые комбинируются здесь в 32-битовую строку
и перемешиваются, формируя выход функции F.
Структура функции F алгоритма DES схематически изображена
на рис. 5.7.
Сейчас мы подробно расскажем о тех шагах, которые мы пока
полностью не раскрыли.
5.2. Шифр Фейстелл и DES 135


перестановка
с расширением




12345678901234567890123456789012


Рис. 5.7. Структура функции F алгоритма DES
5.2.1.1. Начальная перестановка, IP. Начальная перестанов­
ка алгоритма DES определяется таблицей 5.1. Эту и все другие та­
блицы, изображающие перестановки, следует читать слева направо
и сверху вниз. Так, число 58, расположенное в первой строке и пер­
вом столбце таблицы, означает, что IP перемещает пятьдесят вось­
мой бит входных данных на первое место. Аналогично, согласно
этой таблице, второй бит перемещается в позицию 50, и т. д.
Таблица 5.1. Начальная перестановка
34
42
58 26 2
50 18 10
52 44
60 36 28 12 4
20
62 54 14
46 38 30 22 6
64 32 24
56 48 40 16 8
41
57 49 33 25 1
17 9
59 35 27
51 43 11
19 3
21
61 53 45 37 29 13 5
63 55 47 39 31 23 15 7
Обратная перестановка задается таблицей 5.2.
5.2.1.2. Перестановка с расширением Е. Перестановка Е так­
же представляется таблицей (таб. 5.3). Каждая строка в ней соот­
ветствует битам, входящим в соответствующий S-блок на следую­
щем шаге. Обратите внимание, как биты, нумерующие строку од­
ного S-блока (первый и последний бит каждой строки), влияют на
выбор столбца другого S-блока.
36 Глава 5, Симметричные шифры


Таблица 5.2. Перестановка, обратная к начальной
40 8 48 16 56 24 64 32
15
7 47 55
39 23 63 31
14 54 22 62
38 6 46 30
21
13 53
37 5 45 61 29
44 12 52
4
36 20 60 28
3 43 11 51
35 19 59 27
2 42
34 10 50 18 58 26
41
1 9 49 17 57
33 25

;стаLHOB ка с расширением
32 1 2 3 4 5
4567 8 9
12
8 9 10 11 13
12 13 14 15 16 17
21
16 17 18 19 20
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1


5.2.1.3. Перестановка в Р-блоке, Р. Эта перестановка пре­
вращает 8 групп 4-битовых элементов на выходе из S-блоков, в 32-
битовую строку, соединяя и перемешивая их, как показано в табл. 5.4.
Таблица 5.4. Перестановка в Р-блоке
7 21
16 20
12
29 28 17
1 15 23 26
5 18 31 10
2 24 14

<< Предыдущая

стр. 20
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>