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

стр. 10
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

Биты входного блока Т (64 бита) переставляются в соответствии с матрицей IP: бит 58 вход-
ного блока Т становится битом 1, бит 50 – битом 2 и т.д. Эту перестановку можно описать выражени-
ем Т0 = IP(T). Полученная последовательность битов Т0 разделяется на две последовательности: L0
– левые или старшие биты, R0 – правые или младшие биты, каждая из которых содер-жит 32 бита.
Затем выполняется итеративный процесс шифрования, состоящий из 16 шагов (циклов).
Пусть Тi – результат i-й итерации:
Т i = L i R i,
где Li = t1 t2 ... t32 (первые 32 бита); Ri = t33 t34 ... t64 (последние 32 бита). Тогда результат i-й итерации
описывается следующими формулами:
Li = Ri–1, i = 1, 2, ..., 16;
Ri = Li–1 ? f (Ri–1, Ki), i = 1, 2, ..., 16.
Функция f называется функцией шифрования. Ее аргументами являются последовательность
Ri–1, получаемая на предыдущем шаге итерации, и 48-битовый ключ Кi, который является результа-
том преобразования 64-битового ключа шифра К. (Подробнее функция шифрования f и алгоритм
получения ключа Кi описаны ниже.)
На последнем шаге итерации получают последовательности R16 и L16 (без перестановки мес-
тами), которые конкатенируются в 64-битовую последовательность R16 L16.
По окончании шифрования осуществляется восстановление позиций битов с помощью
матрицы обратной перестановки IP–1 (табл.3.2).
Таблица 3.2
–1
Матрица обратной перестановки IP
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


Пример того, как соотносятся элементы первой строки матрицы IP–1 с элементами матрицы IP
приведен в табл. 3.3.
Таблица 3.3
Связь элементов матриц
–1
Элемент матрицы IP Элемент матрицы IP

40 01
8 02
48 03
16 04
56 05
... ...

Процесс расшифрования данных является инверсным по отношению к процессу шифрования.
Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые
данные сначала переставляются в соответствии с матрицей IP–1, а затем над последовательностью
битов R16L16 выполняются те же действия, что и в процессе шифрования, но в обратном порядке.
Итеративный процесс расшифрования может быть описан следующими формулами:
Ri–1 = Li, i = 1, 2, ..., 16;
Li–1 = Ri ? f (Li, Ki), i = 1, 2, ..., 16.


3
Таким образом, для процесса расшифрования с переставленным входным блоком R16L16 на
первой итерации используется ключ К16, на второй итерации – К15 и т.д. На 16-й итерации использу-
ется ключ К1. На последнем шаге итерации будут получены последовательности L0 и R0, которые кон-
катенируются в 64-битовую последовательность L0R0. Затем в этой последовательности 64 бита пе-
реставляются в соответствии с матрицей IP. Результат такого преобразования – исходная последо-
вательность битов (расшифрованное 64-битовое значение).
Теперь рассмотрим, что скрывается под преобразованием, обозначенным буквой f. Схема
вычисления функции шифрования f (Ri–1,Ki) показана на рис. 3.3.
Ri–1 (32 бита)

Е
Расширитель

48 бит

Кi (48 бит)



S1 S2 S3 S4 S5 S6 S7 S8



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

32 бита

f (Ri–1,Кi)
Рис.3.3. Схема вычисления функции шифрования f

Для вычисления значения функции f используются:
• функция Е (расширение 32 бит до 48);
• функция S1, S2, ..., S8 (преобразование 6-битового числа в 4-битовое);
• функция Р (перестановка битов в 32-битовой последователь-
ности).
Приведем определения этих функций.
Аргументами функции шифрования f являются Ri–1 (32 бита) и Ki (48 бит). Результат функции
Е (Ri–1) есть 48-битовое число. Функция расширения Е, выполняющая расширение 32 бит до 48 (при-
нимает блок из 32 бит и порождает блок из 48 бит), определяется табл. 3.4.
В соответствии с табл. 3.4 первые три бита E (Ri–1) – это биты 32, 1 и 2, а последние – 31, 32, 1. Полу-
ченный результат (обозначим его E(Ri–1)) складывается по модулю 2 (операция XOR)
Таблица 3.4
Функция расширения E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1

с текущим значением ключа Кi и затем разбивается на восемь 6-битовых блоков В1, В2, ..., В8:
Е (Ri–1) ? Кi = В1 В2 ... В8.
Далее каждый из этих блоков используется как номер элемента в функциях-матрицах S1, S2,
..., S8, содержащих 4-битовые значения (табл. 3.5).
Следует отметить, что выбор элемента в матрице Sj осуществляется достаточно оригиналь-
ным образом. Пусть на вxод матрицы Sj поступает 6-битовый блок Bj = b1 b2 b3 b4 b5 b6, тогда двух-
битовое число b1 b6 указывает номер строки матрицы, а четырехбитовое число b2 b3 b4 b5 – номер
столбца. Например, если на вход матрицы S1 поступает 6-битовый блок В1= b1 b2 b3 b4 b5 b6 =
= 100110, то 2-битовое число b1 b6 = 10(2) = 2(10) указывает строку с номером 2 матрицы S1, а 4-
битовое число b2 b3 b4 b5=0011(2)=3(10) указывает столбец с номером 3 матрицы S1. Это означает, что


4
в матрице S1 блок В1 = 100110 выбирает элемент на пересечении строки с номером 2 и столбца с
номером 3, т.е. элемент 8(10) =
=1000(2). Совокупность 6-битовых блоков В1, В2,..., В8 обеспечивает выбор четырехбитового элемента
в каждой из матриц S1, S2, ..., S8.
В результате получаем S1(В1) S2(В2) S3(В3) ... S8(В8), т.е. 32-битовый блок (поскольку матрицы
Sj содержат 4-битовые элементы). Этот 32-битовый блок преобразуется с помощью функции пере-
становки битов Р (табл.3.6).
Таким образом, функция шифрования
f (Ri–1, Ki) = P(S1(B1), ..., S8(B8)).
Как нетрудно заметить, на каждой итерации используется новое значение ключа Кi (длиной 48
бит). Новое значение ключа Кi вычисляется из начального ключа К (рис.3.4). Ключ К представляет
собой 64-битовый блок с 8 битами контроля по четности, расположенными в позициях 8, 16, 24, 32,
40, 48, 56, 64. Для удаления контрольных битов и подготовки ключа к работе используется функция G
первоначальной подготовки ключа (табл. 3.7).
Таблица 3.5
Функции преобразования S1, S2, ..., S8
Номер столбца
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 S1
2 4 1 4 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
0 15 1 8 14 6 11 34972 13 12 0 5 10
1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 S2
2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 S3
2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
Н3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
о0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
м1 13 8 11 5 6 15 03472 12 1 10 14 9 S4
е2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
р3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 S5
с2 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
т3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3
р0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
о1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 S6
к2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 1 6
и3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 S7
2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
0 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 S8
2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11




5
Ключ К

Функция G


С0 (28 бит) D0 (28 бит)

Сдвиг влево Сдвиг влево

С1 D1 К1
Функция
H
Сдвиг влево Сдвиг влево

С2 D2 К2
Функция
H
Сдвиг влево Сдвиг влево



С16 D16
К16
Функция
H


Рис.3.4. Схема алгоритма вычисления ключей Ki

Табл. 3.7 разделена на две части. Результат преобразования G(K) разбивается на две поло-
вины С0 и D0 по 28 бит каждая. Первые четыре строки матрицы G определяют, как выбираются

Таблица 3.6 Таблица 3.7
Функция P перестановки Функция G первоначальной подготовки
битов ключа (переставленная выборка 1)
16 7 20 21 57 49 41 33 25 17 9
29 12 28 17 1 58 50 42 34 26 18
1 15 23 26 10 2 59 51 43 35 27
5 18 31 10 19 11 3 60 52 44 36
2 8 24 14 63 55 47 39 31 23 15
32 27 3 9 7 62 54 46 38 30 22
19 13 30 6 14 6 61 53 45 37 29
22 11 4 25 21 13 5 28 20 12 4


биты последовательности С0 (первым битом С0 будет бит 57 ключа шифра, затем бит 49 и т.д., а
последними битами – биты 44 и 36 ключа).
Следующие четыре строки матрицы G определяют, как выбираются биты последовательно-
сти D0 (т.е. последовательность D0 будет состоять из битов 63, 55, 47, ...,12, 4 ключа шифра).
Как видно из табл. 3.7, для генерации последовательностей С0 и D0 не используются биты 8,
16, 24, 32, 40, 48, 56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для дру-
гих целей (например, для контроля по четности). Таким образом, в действительности ключ шифра
является 56-битовым.
После определения С0 и D0 рекурсивно определяются Сi и Di, i = 1, 2, ..., 16. Для этого при-
меняются операции циклического сдвига влево на один или два бита в зависимости от номера шага
итерации, как показано в табл. 3.8.
Операции сдвига выполняются для последовательностей Сi и Di независимо. Например, по-
следовательность С3 получается посредством циклического сдвига влево на две позиции последова-
тельности С2, а последовательность D3 – посредством сдвига влево на две позиции последователь-
ности D2, С16 и D16 получаются из С15 и D15 посредством сдвига влево на одну позицию.




6
Таблица 3.8
Таблица сдвигов si для вычисления ключа
Количество si сдвигов влево,
Количество si сдвигов влево,
Номер итерации Номер итерации
бит
бит


1 1 9 1
2 1 10 2
3 2 11 2
4 2 12 2
5 2 13 2
6 2 14 2
7 2 15 2
8 2 16 1


Ключ Кi, определяемый на каждом шаге итерации, есть результат выбора конкретных битов из
56-битовой последовательности Сi Di и их перестановки. Другими словами, ключ Кi=H(Сi Di), где
функция H определяется матрицей, завершающей обработку ключа (табл. 3.9).
Таблица 3.9
Функция H завершающей обработки ключа
(переставленная выборка 2)

14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8

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

стр. 10
(из 48 стр.)

ОГЛАВЛЕНИЕ

Следующая >>