Data Encryption Standard (DES)

1

Data Encryption Standard (DES)
Data Encryption Standard (DES) дълго време е бил един от най-често използваните алгоритми за шифриране
на данни. Разработен от IBM® по заявка на NSA в периода 1970–1977 година този стандарт се явява един от
основополагащите за модерните симетрични криптографски системи. Проектирането на DES е на база на друг
симетричен криптографски алгоритъм, наречен Lucifer
1
. Важно е да се отбележи, че в момента DES се счита като
криптографски ненадежден поради малката дължина на ключовете, която е само 56 бита, както и разработените
специализирани устройства, които успяват да направят напълно успешна атака, насочена към ключа само за 22
часа и 15 минути. Въпреки, че интервал от време от 22 часа може да ни се струва дълъг, той е незначителен от
гледна точка на предполаганото време за разбиване на ключа по метода на грубата сила. Още от 1998 година DES
се измества от 3DES – симетричен алгоритъм, който използва 3 различни ключа и 3 последователни операции с
DES.
Функционално DES разделя данните на 64 битови блокове, които участват в процеса на шифроване, а
използваният алгоритъм се базира на множество етапи на пермутация и заместване на битове, които комбинират
данни и т.нар. етапен ключ, генериран на база на посочения ключ. Както вече няколко пъти споменахме, DES е
симетричен алгоритъм, което означава, че функциите за шифриране и дешифриране, използват един и същи ключ,
но се прилага различна подредба на етапните ключове. DES ключовете са с фиксирана дължина от 64 бита, като от
тях 56 формират ключа, а останалите 8 се използват за проверка по четност (Parity). Възможно е да се използват и
по-слаби 40 битове ключове, но тяхното приложение е било много рядко, дори по времето, когато DES е бил
прилаган в действителни системи. На фиг. 1.24 е показана обобщена функционална схема на DES. X – 64 битов блок
(открит текст)
К – 56 битов ключ
Y – 64 битов блок
(шифриран текст)
DES
Първоначална
пермутация
Шифриране
Етап 1
X
...
Шифриране
Етап 16
Последна
пермутация
Y
k1
k16
K

Фиг. 1.24 Обобщен принцип на работа на симетричния криптографски алгоритъм DES
Операциите шифриране и дешифриране при DES се различават по последователността на използването на
ключовете, а структурата се явява мрежа на Фейстел
2
. Ще разгледаме подробно този алгоритъм за да се обедите,
че въпреки използваните голям брой операции като пермутация, преместване, XOR и др., принципа на работа е

1
Алгоритъмът Lucifer е разработен от Хорст Фейстел (Horst Feistel) и негови колеги от IBM.
2
https://en.wikipedia.org/wiki/Feistel_cipher

2

сравнително лесен и праволинеен. Ако считате, че тази информация не би ви била полезна или ако показаните
схеми и описаните формули ви смущават спокойно можете да прескочите следващите няколко страници от
книгата.
Първите етапи на действието шифриране с DES са показани на фигура 1.25. Числата над стрелките
обозначават броя на използваните битове, а всеки отделен блок ще разгледаме поетапно.
Многократно ще използваме и термина „пермутация“, с който се нарича всяка подредена съвкупност от n
естествени числа, в която дадено число да се среща само веднъж. При DES се прилагат таблици, еднозначно
посочващи промяната на позицията на битовете в блока или резултата от текущата операция. Входен блок
X=x1, x2, , x64
Начална пермутация
IP(X)
Ключ K
56 Бита за ключ и 8 бита за проверка
PC-1
6464
56
32
f
32
L1 R1
L0 R0
48
k1
ЕТАП
1
56
32
Трансформация 1
XOR

Фиг. 1.25 Първоначални етапи при шифриране на данни с DES
Първата стъпка е да се отдели 64 битов блок от открития текст, който се подава към първоначалната
пермутация, обозначена с IP(X). Пермутацията размества битовете в блока като използва следното заместване:
Таблица 1.5 Първоначална пермутация IP при DES
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
Действието на IP(X) може да се опише като по-битова транспозиция - бит 1 от блока се премества на
позиция 40, бит 2 – на позиция 8 и т.н. След като се премине през този етап резултатният блок се разделя на две
половини, наречени L0 и R0. Дясната R0 се подава като входни данни на функцията f, която е описана на фиг. 1.26 и
която е една от най-важните съставни части на DES.

3
Ri-1
Разширение
E(Ri-1)
32
48
ki
48
48
32
32
Пермутация P
S1 S2 S3 S4 S5 S6
6 6 6 6 6 6
4 4 4 4 4 4
S7 S8
6
4
6
4

Фиг. 1.26 Функция f при DES
Входните данни за f са 32 бита, които по същество са Ri-1 – дясната половина на пермутацията от
предходната стъпка на алгоритъма. Те се разширяват до 48 бита чрез функцията E(Ri-1), която ще дефинираме след
малко и чиято основна цел е да увеличи дифузията в данните. Получените резултатни 48 бита се подават към XOR
с 48 битов ключ ki. Резултатът (48 бита) се разделя на 8 части, всяка една от тях включваща по 6 бита, които се
използват за вход при т.нар. “S-box” замествания, които водят до 8 части по 4 бита или сумарно – 32 бита.
Последната операция от функцията f е да се пресметне пермутацията, наречена P.
Функцията E (прилагана при f – фиг. 1.26) е сравнително проста и отново извършва действие, подобно на
пермутациите от предходните стъпки, но разширява и резултатните битове, като някои от входните се повтарят
3
.
Таблица 1.6 Функция 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
След като приключат изчисленията, свързани с функцията E се извърша логическа операция XOR с 48 битов
етапен ключ, пресметнат по метод наречен “round key” и към който ще се върнем малко по-късно.
“S-box” заместването е един от най-важните етапи при DES, като при него се използват 6 входни бита, а
резултатът е 4 бита. Използваната функция е нелинейна, което прави алгоритъма сравнително устойчив на
диференциален криптографски анализ. Важно е да се подчертае, че на този етап се използват 8 предварително

3
Поради повторението на стойностите E не може ад се дефинира като математическа пермутация.

4

дефинирани еднозначни таблици за заместване. На фиг. 1.27 е показан пример за работата на S1, с входни битове
101101. РЕД = 3
101101
11
0110 КОЛОНА = 6

Фиг. 1.27 Пример за заместване S1
Битове с номера 0 и 5 дефинират номера на реда (000 (BIN) = 0 (DEC) до 111 (BIN) = 3 (DEC)), а битове 1 до 4
– колоната (0000 (BIN) = 0 (DEC) до 1111(BIN) = 15 (DEC)). След като се определят тези два параметъра се извършва
търсене в една от 8 предварително дефинирани таблици на заместване, като тази за S1 e следната:
Таблица 1.7 “S-box” заместване за S1. Стойностите са в DEC бройна система.
S1 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
2 4 1 14 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
Стойностите в таблицата са в десетична бройна система и всяка една се описва точно с 4 бита. От примерът
се вижда, че трябва да изберем стойността, намираща се на ред 3 и колона 6, която е 1 (DEC). По този начин
резултатът от операцията S1 ще бъде 0001 (BIN). Действието се повтаря аналогично и за останалите “S-box”
трансформации, но се използват различни таблици за заместването на стойността. В таблица 1.8 са описани всички
8 “S-box” замествания.

5

Таблица 1.8 “S-box” замествания при DES (стойностите са в DEC бройна система).
S1
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
2 4 1 14 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
S2
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 15 1 8 14 6 11 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
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
S3
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
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
S4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
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
S5
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
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
S6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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 11 6
3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
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
S8
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
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
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
Последната пермутация P при функцията f е описана в таблица 1.9.

6

Таблица 1.9 Пермутация 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 са 32 бита, които се явяват и окончателните данни от прилагането на функцията f. Те се
подават към логическа операция XOR заедно с Li-1 (виж фиг. 1.25).
Преди да разгледаме и начина за изчисляване на т.нар. “round-key”, нека да опишем и последния етап от
шифрирането с DES, който схематично е показан на фиг. 1.28. ЕТАП
1
6
32
L15 R15
f
32
48
k16
Трансформация 16
L16 R16
32
Последна пермутация
IP
-1
(X)
Криптограма
y=DESk(x)

Фиг. 1.28 Етап 16 при шифриране с DES
Последната пермутация IP
-1
е описана в таблица 1.10.
Таблица 1.10 Пермутация IP
-1

40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 20
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 43 10 50 18 58 26
33 1 41 9 49 17 57 25
Както вече няколко пъти беше споменато, DES използва 56 бита за формиране на ключ и 8 бита за проверка
по четност, които трябва да са дефинирани преди да се стартира процеса на шифриране или дешифриране. В

7

последствие отделните 16 етапа използват 48 битови ключове, които се наричат “round-key” или в условен превод
– етапни ключове. На фиг. 1.29 е показано разпределението на битовете в DES ключ. 64 бита
P
7 бита
1 бит за проверка по четност
P...

Фиг. 1.29 Разпределение на битовете при DES ключа
Основните етапи при трансформациите на ключовете, използване при шифриране на данни с DES са
показани на фиг. 1.30. Ключ К
Пермутация PC-1
64
C0 D0
56
LS1 LS1
28 28
C1 D1
28 28
Пермутация PC-2
5648
k1
Трансформация 1
LS2 LS2
28 28
LS16 LS16
...
C16 D16
28 28
Пермутация PC-2
5648
k16

Фиг. 1.30 Обработка на ключовете при DES за операция шифриране
Битовете за проверка по четност, които показват, дали в предходните 7 бита, броят на 1
те
е четен или
нечетен, след проверка се премахват. Пристъпва се към първата пермутация за обработка на ключа, която е
описана в таблица 1.11. Забележете, че при PC-1 не се използват битов 8, 16, 24, 32, 40, 48 и 64 (проверка по
четност).

8

Таблица 1.11 Пермутация PC-1 при обработка на DES ключ
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
Получените 56 резултатни бита след PC-1 се разделят на две части, наречени C0 и D0. Пристъпва се към
операция преместване на ляво, като стъпката зависи от номера на трансформацията:
 При трансформация 1, 2, 9 и 16 двете части се отместват с 1 бит;
 При останалите етапи