Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии
.pdfЬпочные системы шифрования
Рис. 27
211
/лава 8
В приводимом ниже описании алгоритма ОЕ8 использованы следующие обозначения:
Ци К( — левая и правая половины 64-битного блока
АА ;
® — операция побитового сложения векторов-блоков по модулю 2;
к{ — 48-битовые ключи;
/ — функция шифрования;
1Р — начальная перестановка степени 64.
При зашифровании очередного блока Т (см. рис. 27) его биты подвергаются начальной перестановке 1Р согласно табл. 9.
Т аб л и ц а 9. Начальная перестановка 1Р
58 |
50 |
42 |
34 |
26 |
18 |
10 |
2 |
60 |
52 |
44 |
36 |
28 |
20 |
12 |
4 |
62 |
54 |
46 |
38 |
30 |
22 |
14 |
6 |
64 |
56 |
48 |
40 |
32 |
24 |
16 |
8 |
57 |
49 |
41 |
33 |
25 |
17 |
9 |
1 |
59 |
51 |
43 |
35 |
27 |
19 |
11 |
3 |
61 |
53 |
45 |
37 |
29 |
21 |
13 |
5 |
63 |
55 |
47 |
39 |
31 |
23 |
15 |
7 |
При этом бит 58 блока Т становится битом 1 , бит 50 — битом 2 и т. д. Полученный после перестановки блок 1Р(Т)
разделяется на две половины: Ь0, состоящую из 32 старших бит, и К0, состоящую из 32 младших бит.
Затем выполняется итеративный процесс шифрования, состоящий из 16 циклов преобразования Фейстеля. Пусть
Тг_х = Д _ 1Т?/_1 — результат (;-1 )-й итерации.
Тогда результат /-й итерации 7 ] = ! ^ определяется формулами
212
ьлочные системы шифрования |
|
|
\Ь |
- |
(2) |
1 |
= 1 М © / ( Д ^ Д Д |
|
|Д |
1=1,16. |
|
Функция / |
называется функцией шифрования. Ее аргумен |
|
тами являются 32-битовый вектор |
К1_] и 48-битовый ключ |
к1, который является результатом преобразования 56битового ключа шифра к . Результатом последней итерации является блок Т[6 = Д 6Д 6. По окончании шифрования осу
ществляется восстановление п о з и ц и й битов применением к
г ,6 обратной перестановки 1Р 1.
При расшифровании данных все действия выполняются в обратном порядке, при этом вместо соотношений (2) следу
ет использовать соотношения |
|
|^|-1 |
= А» |
{ /_ , |
=Д , 0 / ( 1 ,Д ,), / = 16Л, |
пользуясь которыми можно “спуститься” от Ьхь |
И У?16 К 1 0 И Л о . |
||
Схема |
вычисления значения функции |
шифрования |
|
/ ( Д ч ,кг) |
изображенана рис 28. |
|
|
Для вычисления значения функции |
/ |
используются: |
функция расширения Е ; преобразование 5 , составленное из
восьми преобразований 8 -блоков |
8 ], 8 2 *—> |
переста |
||
новка Р . Аргументами функции / |
являются вектор Д_, |
(32 |
||
бита) и вектор к1 |
(48 бит). Функция Е “расширяет” |
32- |
||
битовый вектор Д ч |
до 48-битового вектора Е(К {_Х) путем |
дублирования некоторых битов вектора Км , при этом порядок следования битов в ^(Д _! ) указан в табл. 10.
213
( лава Ь
у
е |
А; (4 8 бит) |
|
&
N(
Перестановка битов Р
\/
ЛЪ -1*д
(32 бита)
Рис. 28
Таблица 10
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 |
214
Ьлочные системы шифрования
Первые три бита в |
Е |
— это соответственно биты 32, 1 |
|
и 2 вектора |
, а |
последние три бита — это соответственно |
биты 31, 32, 1 вектора К{_}.
Полученный результат складывается побитно по моду лю 2 с текущим значением ключа кг и затем представляется
в виде восьми последовательных 6-битовых блоков |
: |
|
Е ( = |
В 1...В$. |
|
Далее каждый из блоков |
трансформируется в 4-бито- |
*
вый блок В^ с помощью подходящей таблицы ^5^блока В},
список которых приведен в табл. 1 1 . |
"—— |
|
Преобразование блока |
В в В } осуществляется сле |
|
дующим образом. Пусть, например, |
В2 равен 111010. Пер |
|
вый и последний разряды |
В2 являются двоичной записью |
числа а , 0 < а < 3 . Аналогично средние 4 разряда представ ляют число Ъ9 0 < 6 < 15 . В нашем примере а = 2, Ь = 13.
Строки и столбцы таблицы В2 пронумерованы числами
а и Ь . Таким образом, пара (а, Ь) однозначно определяет число, находящееся на пересечении строки с номером а и столбца с номером Ъ . В данном случае это число равно 3.
Записывая его в двоичной форме, получаем В2, равный 0 0 1 1 .
Значение |
теперь |
получается применением |
|
перестановки битов |
Р 9 заданной таблицей к результирую- |
||
|
> |
> |
> |
щему 32-битовому блоку В\ |
В2 ... В^. |
215
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
I лава 8 |
|
Таблица 11 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
0 |
1 |
Н О М Е Р |
|
7 |
С Т О Л Б П А |
14 |
15 |
|
|||||||||
|
|
2 |
3 |
4 |
5 |
6 |
8 |
9 |
10 |
11 |
12 |
13 |
|
||||||
н |
0 |
14 4 13 1 2 15 И 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 |
|
|
о |
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 И 3 14 10 0 6 13 |
|
||||||||||||||||
м |
0 |
15 1 8 14 6 И 3 4 9 |
7 2 |
|
13 12 0 5 10 |
|
|||||||||||||
|
1 |
3 |
13 |
4 |
7 |
15 |
2 |
8 |
14 |
12 |
0 |
1 |
10 |
6 |
9 |
11 |
5 |
3 ? |
|
Е |
2 |
0 14 7 И 10 4 13 1 5 8 12 6 9 3 2 15 |
|
||||||||||||||||
|
3 |
13 8 10 1 |
3 15 4 2 И 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 |
8. |
|
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 И 5 6 |
15 .0 3 4 7 2 12 1 10 14 9 8 4 |
|||||||||||||||||
|
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 И 2 12 4 7 13 1 5 0 15 10 |
3 9 8 6 8, |
|||||||||||||||||
|
2 |
4 |
2 |
1 |
11 |
10 |
13 |
7 |
8 |
15 |
9 |
12 |
5 |
6 |
3 |
0 |
14 |
|
|
О |
3 |
И 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 |
Зб |
|
|
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 |
87 |
|
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 |
8« |
|
2 |
7 И 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 |
|
216
Ьлочные системы шифрования
Таблица 12
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 |
На каждой итерации используется текущее значение ключа к1 (48 бит), получаемое из исходного ключа к сле дующим образом.
Сначала пользователи выбирают сам ключ к , содержа щий 56 случайных значащих битов. Восемь битов, находя щихся в позициях 8,16,...,64, добавляются в ключ таким об разом, чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Значащие 56 бит ключа подвергаются пе рестановке, приведенной в табл. 13.
Таблица 13
57 |
49 |
41 |
33 |
25 |
17 |
9 |
1 |
58 |
50 |
42 |
34 |
26 |
18 |
10 |
2 |
59 |
51 |
43 |
35 |
27 |
19 |
11 |
3 |
60 |
52 |
44 |
36 |
63 |
55 |
47 |
39 |
31 |
23 |
15 |
7 |
62 |
54 |
46 |
38 |
30 |
22 |
14 |
6 |
61 |
53 |
45 |
37 |
29 |
21 |
13 |
5 |
28 |
20 |
12 |
4 |
217
I лава 8
Эта перестановка определяется двумя блоками С0 и О0
по 28 бит в каждом (они занимают соответственно верхнюю и нижнюю половины таблицы). Так, первые три бита в С0 есть
соответственно 57, 49, |
41 биты ключа. Затем |
индуктивно |
определяются блоки С, |
и Д , / = 1,16. |
|
Если уже определены С;_, и Д _ 1, то С, и Ц |
получают |
ся из них одним или двумя левыми циклическими сдвигами согласно табл. 14.
Таблица 14
г |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 15 16 |
Число сдвигов |
1 |
1 |
2 |
2 |
2 2 2 2 1 |
2 |
2 |
2 2 2 2 1 |
||||||
Теперь определим ключи к19 1 < / < |
16. |
Ключ к{ состоит |
||||||||||||
из 48 битов, выбираемых из битов блока С Д |
согласно таб |
лице 15. Первыми тремя битами в к{ являются биты 14, 17, 11 из блока С Д . Отметим, что 8 из 56 бит (с номерами 9, 18,
22, 25, 35, 38, 43, 54) из С Д |
отсутствуют в к, . |
||||
Таблица 15 |
|
|
|
|
|
14 |
17 |
И |
24 |
1 |
5 |
3 |
28 |
15 |
6 |
21 |
10 |
23 |
19 |
12 |
4 |
26 |
8 |
16 |
7 |
27 |
20 |
13 |
2 |
41 |
52 |
31 |
37 |
47 |
55 |
30 |
40 |
51 |
45 |
33 |
48 |
44 |
49 |
39 |
56 |
34 |
53 |
46 |
42 |
50 |
36 |
29 |
32 |
218
Ьлочные системы шифрования
Сделаем несколько замечаний.
Нелинейность преобразований, осуществляемых ОЕ8, определяется только 5-блоками. Их выбор не имеет достаточ но обстоятельного обоснования. Высказывались мнения о том, что 5-блоки имеют некоторую “лазейку”, позволяющую осуществлять контроль за шифрованной перепиской. Офици альная же версия такова. В 1976 г. АНБ заявило, что выбор 5-блоков определен следующими требованиями:
—каждая строка табличного задания каждого 5-блока должна являться перестановкой множества (0,1,..., 15};
—5-блоки не должны являться линейными или аффин ными функциями своих входов;
—изменение одного бита входа 5-блока должно приво дить к изменению по крайней мере двух битов выхода;
— для каждого 5-блока и любого входа х значение 5(х)
и 5(х ® (О,ОД,1,0,0)) должны различаться по крайней мере
двумя битами.
Криптоанализ БЕ8 приводит ко многим нелинейным сис темам уравнений. Дело в том, что каждый бит блока шифр текста является функцией от всех битов блока открытого тек ста и ключа. Известные аналитические методы вскрытия ОЕ8 не дают существенного выигрыша по сравнению с полным
перебором всего множества из 2 56 ключей. К недостаткам алгоритма ЭЕ8 относится небольшое (по современным мер кам) число ключей, что дает возможность их полного перебо ра на быстродействующей вычислительной технике за реаль ное время.
Официально ЭЕ8 являлся стандартом шифрования дан ных до 31 декабря 1998 г. В 1997 г. был объявлен конкурс на новый стандарт, который был назван АЕ8 (Айуапсес! Епсгур- 1юп 81апс1агс1). 2 октября 2000 г. Национальный институт стандартов и технологий (НИСТ) США объявил победителя “конкурса АЕ8”. Однако для того, чтобы этот алгоритм завое вал мировое признание, необходимы серьезные исследования его свойств специалистами различных стран.
219
I лава 8
Стандарт шифрования данных ГОСТ 28147-89
В России установлен единый алгоритм криптографиче ского преобразования данных для систем обработки инфор мации в сетях ЭВМ, отдельных вычислительных комплексах и ЭВМ. Он определяется ГОСТом 28147-89. Этот алгоритм предназначен для аппаратной и программной реализации, удовлетворяет необходимым криптографическим требовани ям и не накладывает ограничений на степень секретности защищаемой информации. Алгоритм реализует шифрование 64-битовых блоков данных с помощью 256-битового ключа.
Схема алгоритма шифрования представлена на рис. 29.
N. г
КЗУ |
|
|
Х 0(К 0) |
ш |
см. |
Х,(К ,)
Х2(К 2)
Х 3(К 3) |
3. з7 |
з5 3. |
Х4(К 4)
Х5(К ,)
Хб(К б) |
..... |
1г |
Х 7(К 7) |
Г4 |
1 |
|
32 |
У
см.
Рис. 29
На приведенной схеме:
Лг,, N 2— 32-разрядные накопители;
220