14.3.5. Стандарт шифрования данных

Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.3.5. Стандарт шифрования данных

В 1977 году Национальное бюро стандартов США (National Bureau of Standards) приняло модифицированную систему LUCIFER в качестве Национального стандарта шифрования данных (Data Encryption Standard — DES) [9]. Как показано на рис. 14.10, с точки зрения системы ввода-вывода DES может считаться блочной системой шифрования с алфавитом в 264 символа. Входной блок из 64 бит, который является в этом алфавите символом открытого текста, заменяется новым символом шифрованного текста. На рис. 14.11 в виде блочной диаграммы показаны функции системы. Алгоритм шифрования начинается с начальной перестановки 64 бит открытого текста, описанной в таблице начальной перестановки (табл. 14.1). Таблица начальной перестановки читается слева направо и сверху вниз, так что после перестановки биты x1, х2, ..., х64 превращаются в х58, x50, ..., х7. После этой начальной перестановки начинается основная часть алгоритма шифрования, состоящая из 16 итераций, которые используют стандартный блок, показанный на рис. 14.12. Для преобразования 64 бит входных данных в 64 бит выходных, определенных как 32 бит левой половины и 32 бит правой, стандартный блок использует 48 бит ключа. Выход каждого стандартного блока становится входом следующего стандартного блока. Входные 32 бит правой половины (Ri-1) без изменений подаются на выход и становятся 32 бит левой половины (Li). Эти Ri-1 бит с помощью таблицы расширения (табл. 14.2) также расширяются и преобразуются в 48 бит, после чего суммируются по модулю 2 с 48 бит ключа. Как и в случае таблицы начальной перестановки, таблица расширения читается слева направо и сверху вниз.

Рис. 14.10. Стандарт шифрования данных (DES) в виде блочной системы шифрования

Рис. 14.11. Стандарт шифрования данных

Рис. 14.12. Стандартный компоновочный блок

Данная таблица отображает биты

Таблица 14.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

Таблица 14.2. Таблица выбора бит

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

12

23

24

25

24

25

26

27

28

29

28

29

30

31

32

1

Ri-1 = x1, x2, …, x32

в биты

(Ri-1)E = x32, …, x1, x2, …, x32, x1. (14.22)

Отметим, что биты, обозначенные в первом и последнем столбцах таблицы расширения, — это те битовые разряды, которые дважды использовались для расширения из 32 до 48 бит.

Далее (Ri-1)E суммируется по модулю 2 с i-м ключом, выбор которого описывается позднее, а результат разделяется на восемь 6-битовых блоков.

B1, B2, …, B8

Иными словами,

(Ri-1)E Ki = B1, B2, …, B8 (14.23)

Каждый из восьми 6-битовых блоков Bj используется как вход функции S-блока, возвращающей 4-битовый блок Sj(Bj)). Таким образом, входные 48 бит с помощью функции S-блока преобразуются в 32 бит. Функция отображения S-блока Sj определена в табл. 14.3. Преобразование Вj=b1, b2, b3, b4, b5, b6, выполняется следующим образом. Нужная строка — это b1b6, а нужный столбец — b2b3b4b5. Например, если b1= 110001, то преобразование Si возвращает значение из строки 3, столбца 8, т.е. число 5 (в двоичной записи 0101). 32-битовый блок, полученный на выходе S-блока, переставляется с использованием таблицы перестановки (табл. 14.4). Как и другие таблицы, Р-таблица читается слева направо и сверху вниз, так что в результате перестановки битов х1, х2,..., х32 получаем х16, х7,..., х25. 32-битовый выход Р-таблицы суммируется по модулю 2 с 32 бит левой половины (Li-1), образуя выходные 32 бит правой половины (Ri).

Таблица 14.3. Функции выбора S-блока

Столбец

Строка

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

S1

3

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

 

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

S2

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

 

2

13

6

4

9

8

15

3

0

11

1

2

12

5

10

14

7

S3

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

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

S4

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

 

2

4

2

1

11

10

13

7

8

15

9

12

5

6

3

0

14

S5

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

 

2

9

14

15

5

2

8

12

3

7

0

4

10

1

13

11

6

S6

3

4

3

2

12

9

5

15

0

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

 

2

1

4

11

13

12

3

7

14

10

15

6

8

0

5

9

2

S7

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

 

2

7

11

4

1

9

12

14

2

0

6

10

13

15

3

5

8

S8

3

2

1

14

7

4

10

8

13

15

12

9

0

3

5

6

11

 

Таблица 14.4. Таблица перестановки

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

Алгоритм стандартного блока может быть представлен следующим образом.

Li = Ri-1 (14.24)

Ri = Li-1f (Ri-1,Ki) (14.25)

Здесь f (Ri-1,Ki) обозначает функциональное соотношение, включающее описанные выше расширение, преобразование в S-блоке и перестановку. После 16 итераций в таких стандартных блоках данные размещаются согласно окончательной обратной перестановке, описанной в табл. 14.5, где, как и ранее, выходные биты читаются слева направо и сверху вниз.

Таблица 14.5. Окончательная перестановка

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

Для дешифрования применяется тот же алгоритм, но ключевая последовательность, используемая в стандартном блоке, берется в обратном порядке. Отметим, что значение f(Ri-1, Ki), которое может быть также выражено через выход i-ro блока как f(Li, Ki), делает процесс дешифрования возможным.









© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.
E-mail: formyneeds@yandex.ru