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

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

ОГЛАВЛЕНИЕ

Следующая >>

8
32 27 3 9
13 30
19 6
22 4
11 25

5.2.1.4- S-блок. Содержимое восьми S-блоков алгоритма пред­
ставлено в табл. 5.5. Напомним, что каждый из них представляет
собой таблицу из 4 строк и 16 столбцов.

5.2.2. Разворачивание ключа в DES
Разворачивание ключа работает с 56-битовым ключом, который пред­
ставлен строкой из 64 знаков, включающей в себя контрольные би-
5,2. Шифр Фейстелл и DES 137

ты, следящие за четностью. Каждый восьмой бит этой строки, т. е.
стоящий на позициях 8, 16, . . . , 64, отвечает за то, чтобы каждый
байт ключа состоял из нечетного числа битов.

Таблица 5.5. S-блоки
S-блок 1. 14 4 13 1 2 15 11 8 3 10 б 12 5 9 О 7
О 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 О
15 12 8 2 4 9 1 7 5 11 3 14 10 О 6 13

S-блок 2 15 1 8 14 б 11 3 4 9 7 2 13 12 О 5 10
3 13 4 7 15 2 8 14 12 О 1 10 б 9 11 5
О 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 б 7 12 О 5 14 9

S-блок 3 10 О 9 14 б 3 15 5 1 13 12 7 11 4 2 8
13 7 О9 3 4 б 10 2 8 5 14 12 11 15 1
13 б 49 8 15 3 О 11 1 2 12 5 10 14 7
1 10 13 О б 9 8 7 4 15 14 3 11 5 2 12

S-блок 4 7 13 14 3 О б 9 10 1 2 8 5 11 12 4 15
2 12 1 10 14 9
13 8 11 5 б 15 О 3 4 7
10 б 9 О 12 11 7 13 15 1 3 14 5 2 8 4
3 15 О б 10 1 13 8 9 4 5 11 12 7 2 14

S-блок 5 2 12 4 1 7 10 11 б 8 5 3 15 13 О 14 9
14 11 2 12 4 7 13 1 5 О 15 10 3 9 8 б
4 2 1 11 10 13 7 8 15 9 12 5 б 3 О 14
11 8 12 7 1 14 2 13 б 15 О 9 10 4 5 3

12 1 10 15 9 2 б 8 0 13 3 4 14 7 5 11
S-блок б
14
4 2 12 1 13 0 11
7 9 5 б 38
10 15
1
14 2 12 4
8 7 0 Иб
9 15 5 3 10 13
14
4 2 12 11 1 б
9 5 10 7 0 8 13
3 15
2 14 12
cS-блок 7 4 11 15 0 8 13 9 7 5 б1
3 10
4 14
11 1 12 2
7 9 10 3 5 15 8б
13 0
14 92
4 12 7 10 15 б 8 0
1 11 13 3 5
3 12
4 14 2
11 8 1 10 7 5 0
б 13 9 15
13 2 8 4 б 15 11 1 10 9 3 14 5 0 12 7
S-блок 8
1 15 13 8 10 3 7 4 12 5 б 11 0 14 9 2
7 И 4 1 9 12 14 2 0 б 10 13 15 3 5 8
4 10 8 13 15 12

При разворачивании ключа сначала, согласно перестановке из
табл. 5.6, перемешиваются его биты. Эта перестановка имеет 64 вхо-
Глава 5. Симметричные шифры

да и 56 выходов. Таким образом, после ее применения, в частности,
отбрасываются контрольные биты.
Т а б л и ц а 5.6. Перестановка РС-1
57 49 41 33 25 17 9
1 42 34
50
58 26 18
2
10 51 43 27
59 35
11 52 44
19 3 60 36
63 55 47 39 31 23 15
62 54 22
7 46 38 30
14 6 61 53 45 37 29
21 12 4
13 5 28 20

Результат этой перестановки, называемой в литературе P C - i ,
делится на две половины (по 28 битов в каждой). Левая часть обо­
значается через Со, а правая — через DQ. Теперь р^ля каждого ра­
унда с номером г вычисляется
d = Ci-i<^pi, Di = Di^i<^pi,
где x<^pi обозначает циклический сдвиг битовой строки х влево на
Рг позиций. Для раундов с номером i = 1,2,3,9 и 16 имеем р^ = 1, а
для остальных — pi = 2.
Наконец, две части Ci и Di соединяются вместе и подаются на
вход следующей перестановки, называемой PC-2 (табл. 5.7), выхо­
дом которой и будет 48-битовый подключ г-го раунда.
Т а б л и ц а 5.7. Перестановка PC-2
14 17 11 24 1 5
21
3 28 15 6 10
12 4
23 19 26 8
2
7
16 27 20 13
41 52 31 37 47 55
30 40 51 45 33 48
44 34
49 39 56 53
42 32
46 50 36 29


3. Rijndael
Победитель конкурса AES^ объявленный в конце 2000 года, алго­
ритм Rijndael^ был разработан двумя бельгийскими криптографа­
ми: Дименом (Daemen) и Рийменом (Rijmen). Эта криптосистема,
относясь к блочным шифрам, имеет много общего с DES^ хотя и
5.3. Rijndael

не является непосредственным обобщением шифра Фейстеля. Для
обеспечения криптостойкости алгоритм Rijndael включает в себя
повторяющиеся раунды, каждый из которых состоит из замен, пе­
рестановок и прибавления ключа. Кроме того, Rijndael использу­
ет сильную математическую структуру: большинство его операций
основаны на арифметике поля F28. Однако, в отличие от DES^ ши­
фрование и расшифрование в этом алгоритме — процедуры разные.
Напомним, что элементы поля F28 хранятся в памяти компьюте­
ра в виде 8-битовых векторов (или байтов), представляющих дво­
ичные многочлены. Например, байт '83/г' в шестнадцатиричной си­
стеме^ соответствует двоичному числу
'1000ООПЬ', т. к. '83/г' ^ 8 • 16 + 3 = 131
в десятичной системе. Этот набор двоичных разрядов можно полу­
чить непосредственно из байта '83/i' = ^80h^ Н- '03/г^ заметив, что
цифра 8 шестнадцатиричной системы, стоящая во втором разряде
представляет число 8-16 = 8-2^. Само число 8 = 2^ в двоичной систе­
ме записывается в виде последовательности 1000 двоичных знаков.
Значит, число '80/г' = 2^ • 2^ в двоичной системе счисления выгля­
дит как '1000 00006'. Осталось к этой строке битов прибавить запись
числа 3 в двоичной системе, т.е. ООН. Заметьте, что при этом до­
статочно к числу 8 (1000) в двоичной системе приписать число 3
(ООН). Указанная последовательность битов соответствует много­
члену Х^ -\- X -\-1 над полем F2. Таким образом, можно сказать, что
шестнадцатиричное число '83/г' представляет тот же многочлен.
Арифметические операции в поле F28 соответствуют операциям
над двоичными многочленами из F2[X] по модулю неприводимого
полинома
т{Х) = Х^ + Х^ + Х^ + X + 1.
В алгоритме Rijndael 32-битовые слова отождествляются с много­
членами степени 3 из F28[X]. Отождествление делается в формате
«перевертыш», т.е. старший (наиболее значимый) бит соответству­
ет младшему коэффициенту многочлена. Так, например, слово
ao||ai||a2||a3

^Российское представление чисел в шестнадцатиричной системе. Цифры: пер­
вые десять цифр от О до 9 представляются стандартно, цифры от 10 до 15
замещаются буквами A,B,C,D,E,F. Для перевода десятичного числа в шестна­
дцатиричную систему, переведем его сначала в двоичную, затем разделим на
блоки по 4 цифры и каждый блок заменим шестнадцатиричной цифрой. Напри­
мер, 'ОНО 1100 1111 Ь' = 'eCFh'
Глава 5. Симметричные шифры

соответствует многочлену
азХ^ -h а2Х'^ + aiX + ао.
Арифметика в алгоритме совпадает с арифметическими действи­
ями в кольце многочленов F28[X] по модулю многочлена М{Х) =
= Х^ + 1. Заметим, что многочлен М{Х) = {X -{- 1)^ приводим,
и, следовательно, арифметические действия в алгоритме отличны
от операций поля, в частности, бывают пары ненулевых элементов,
произведение которых равно 0.
Rijndael — настраиваемый блочный алгоритм, который может
работать с блоками из 128, 192 или 256 битов. Для каждой комби­
нации блока и размера ключа определено свое количество раундов.
В целях упрощения обсуждения мы рассмотрим самый простой и,
вероятно, наиболее часто используемый вариант алгоритма, при ко­
тором блоки, как и ключ, состоят из 128 битов. В этом случае в
алгоритме выполняется 10 раундов. С данного момента мы будем
иметь дело лишь с этой простой версией.
Rijndael оперирует с внутренней байтовой матрицей размера
4 x 4 , называемой матрицей состояний:

^ 50,0 50,1 50,2 50,3 ^

51,2
51,0 51,3
^1,1
52,1 52,2
52,0 52,3

^53,0 53,1 53,2 53,3/

которую обычно записывают как вектор 32-битовых слов. Каждое
слово в векторе представляет столбец матрицы. Подключи также
хранятся в виде матрицы 4 x 4 :

/k 0,0 fco,l ^0,2 ^0,3
h,o ^1,1 ^1,2 A:i,3
Ki
^2,0 ^2,1 ^2,2 ^2,3




5.3.1. Операции алгоритма Rijndael
Раундовая функция в Rijndael действует с использованием четырех
операций, которые мы сейчас опишем.
5.3.1.1. SubBytes. В алгоритме есть два типа S-блоков. Один
тип применяется при шифровании, а другой — при расшифровании.
5.3. Rijndael

Каждый из них обратен другому. S-блоки в алгоритме DES отби­
рались из большого числа себе подобных так, чтобы предотвратить
взлом шифра с помош;ью дифференциального криптоанализа. В Ri­
jndael S-блоки имеют прозрачную математическую структуру, что
позволяет формально анализировать устойчивость шифра к диффе­
ренциальному и линейному анализам. Эта математическая структу­
ра не только повышает сопротивляемость дифференциальному ана­
лизу, но и убеждает пользователя, что в алгоритм не закрался не­
досмотр.
S-блоки поочередно обрабатывают строки матрицы состояний
5 = [^7, . . . , So], воспринимая их как элементы поля F28. Их работа
состоит из двух шагов.
1. Вычисляется мультипликативный обратный к элементу s G F28
и записывается как новый байт х = [xj^ ... ^ хо]. Т1о соглаше­
нию, элемент [О, . . . , 0], не имеющий обратного, остается неиз­
менным.
2. Битовый вектор х с помош;ью линейного преобразования над
полем F2 переводится в вектор у:

/ 1 0 0 0 1 1 1 1^ f Хо ^
( Уо^
110 00 111 XI
У1
1110 00 11
У2 Х2

11110 001 хз
2/3
111110 00
У4 Х4

0 111110 0 Х^
У5
00 111110
2/6 Хб

10 0 0 1 1 1 1 1^
^ \^7 )
\У7 )

служащий выходом S-блока. Действия S-блока на стадии расшифро­

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

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

ОГЛАВЛЕНИЕ

Следующая >>