скрыть

скрыть

  Форум  

Delphi FAQ - Часто задаваемые вопросы

| Базы данных | Графика и Игры | Интернет и Сети | Компоненты и Классы | Мультимедиа |
| ОС и Железо | Программа и Интерфейс | Рабочий стол | Синтаксис | Технологии | Файловая система |



Google  
 

Алгоритм шифрования DES



Алгоритм шифрования данных DES разработан для зашифрования и расшифрования данных разрядностью 64 бит на основе 64-битового ключа. Расшифрование выполняется по тому же ключу, что и зашифрование, но этот процесс является инверсным по отношению к процессу зашифрования данных. При описании алгоритма шифрования используются следующие обозначения. Если L и R - последовательности бит, то через LR будем обозначать конкатенацию последовательностей L и R, т.е. последовательность бит, размерность которой равна сумме размерностей L и R. В этой последовательности биты последовательности R следуют за битами последовательности L. Конкатенация битовых строк является ассоциативной, то есть запись ABCDE, означает, что за битами последовательности A, следуют, биты последовательности B, затем C и т.д. Символом + будем обозначать операцию побитового сложения по модулю 2.

Процесс шифрования.

Процесс шифрования данных поясняется рисунком 1. Сначала 64 бита входной последовательности перестанавливаются в соответствии с таблицей 1. Таким образом, бит 58 входной последовательности становится битом 1, бит 50 – 2 и т.д.

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

Полученная последовательность бит разделяется на две последовательности: L(0) (биты 58, 50, 42, ..., 8) и R(0) (биты 57, 49, 41, ..., 7), каждая из которых содержит 32 бита. Затем выполняется итеративный процесс шифрования, который описывается следующими формулами:

L(i)=R(i-1), i=1,2,...,16.

R(i)=L(i-1) + F(R(i-1),K(i)), i=1,2,...,16.

Функция F называется функцией шифрования. Ее аргументами являются последовательность R, полученная на предыдущем шаге, и 48-битовый ключ K(i), который является результатом функции преобразования 64-битового ключа шифра. Подробно функция шифрования и алгоритм получения ключей K(i) описаны ниже.

На последнем шаге итерации будут получены последовательности L(16) и R(16), которые конкатенируются в 64-х битовую последовательность R(16)L(16). Видно, что в полученной последовательности 64 бита, перестанавливаются в соответствии с таблицей 2. Как легко видеть данная перестановка является обратной по отношению к начальной (см. таблицу 1).

Таблица 2. "Конечная перестановка"

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

Полученная последовательность из 64 бит и будет являться зашифрованной последовательностью.

Рисунок 1.

 

Процесс расшифрования.

Процесс расшифрования данных является инверсным по отношению к процессу шифрования. Все действия должны быть выполнены в обратном порядке. Это означает, что расшифровываемые данные сначала переставляются в соответствии с таблицей 1, а затем над последовательностью бит R(16)L(16) выполняется те же действия, что и в процессе зашифрования, но в обратном порядке. Итеративный процесс расшифрования описан следующими формулами:

R(i-1)=L(i), i =16, 15, ..., 1

L(i-1)=R(i)+F(L(i),K(i)), i=16, 15, ..., 1.

На последнем шаге итерации будут получены последовательности L(0) и R(0), которые конкетанируются в 64 битовую последовательность L(0)R(0). В полученной последовательности 64 бита перестанавливаются в соответствии с таблицей 2. Результат преобразования - исходная последовательность бит (расшифрованное 64-битовое значение).

Функция шифрования.

Функция шифрования F(R,K) схематически показана на рисунке 2. Для вычисления значения функции F используется функция E (расширение 32 бит до 48), функции S(1), S(2),...,S(8) преобразование 6-битового числа в 4-битовое) и функция P (перестановка бит в 32-битовой последовательности). Приведем определения этих функций. Аргументами функции шифрования являются R (32 бита) и K (48 бит). Результат функции E(R) есть 48-битовое число, которое складывается по модулю 2 с числом K. Таким образом, получается 48-битовая последовательность, которая рассматривается, как конкатенация 8 строк длиной по 6 бит (т.е. B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8)). Результат функции S(i)B(i) - 4 битовая последовательность, которую будем обозначать L(i). В результате конкетанации всех 8 полученных последвательностей L(i) имеем 32-битовую последовательность L=L(1)L(2)L(3)L(4)L(5)L(6)L(7)L(8). Наконец, для получения результат функции шифрования надо переставить биты последовательности L. Для этого применяется функция перестановки P(L).

Рисунок 2.

 

Функция расширения Е, выполняющая расширение 32 бит до 48, определяется таблицей 3. В соответствии с этой таблицей первые три бита Е(R) - это биты 32,1 и 2, а последние - 31,32,1.

Таблица 3. "Функция расширения Е"

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

Функция S(i), которая преобразует 6-битовые числа в 4-битовые, определяется в таблицей 4.

Таблица 4. "Функции преобразования S(i)"

S(1)

14

4

13

1

2

15

11

8

3

10

6

12

5

9

0

7

0

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

0

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

S(2)

15

1

8

14

6

11

3

4

9

7

2

13

12

0

5

10

3

13

4

7

15

2

8

14

12

0

1

10

6

9

11

5

0

14

7

11

10

4

13

1

5

8

12

6

9

3

2

15

13

8

10

1

3

15

4

2

11

6

7

12

0

5

14

9

S(3)

10

0

9

14

6

3

15

5

1

13

12

7

11

4

2

8

13

7

0

9

3

4

6

10

2

8

5

14

12

11

15

1

13

6

4

9

8

15

3

0

11

1

2

12

5

10

14

7

1

10

13

0

6

9

8

7

4

15

14

3

11

5

2

12

S(4)

7

13

14

3

0

6

9

10

1

2

8

5

11

12

4

15

13

8

11

5

6

15

0

3

4

7

2

12

1

10

14

9

10

6

9

0

12

11

7

13

15

1

3

14

5

2

8

4

3

15

0

6

10

1

13

8

9

4

5

11

12

7

2

14

S(5)

2

12

4

1

7

10

11

6

8

5

3

15

13

0

14

9

14

11

2

12

4

7

13

1

5

0

15

10

3

9

8

6

4

2

1

11

10

13

7

8

15

9

12

5

6

3

0

14

11

8

12

7

1

14

2

13

6

15

0

9

10

4

5

3

S(6)

12

1

10

15

9

2

6

8

0

13

3

4

14

7

5

11

10

15

4

2

7

12

9

5

6

1

13

14

0

11

3

8

9

14

15

5

2

8

12

3

7

0

4

10

1

13

11

6

4

3

2

12

9

5

15

10

11

14

1

7

6

0

8

13

S(7)

4

11

2

14

15

0

8

13

3

12

9

7

5

10

6

1

13

0

11

7

4

9

1

10

14

3

5

12

2

15

8

6

1

4

11

13

12

3

7

14

10

15

6

8

0

5

9

2

6

11

13

8

1

4

10

7

9

5

0

15

14

2

3

12

S(8)

13

2

8

4

6

15

11

1

10

9

3

14

5

0

12

7

1

15

13

8

10

3

7

4

12

5

6

11

0

14

9

2

7

11

4

1

9

12

14

2

0

6

10

13

15

3

5

8

2

1

14

7

4

10

8

13

15

12

9

0

3

5

6

11

К таблице 4 требуются дополнительные пояснения. Каждая из функций S(i)B(i) преобразет 6-битовый код в 4-битовый выход по следующему алгоритму:

  • первый и последний биты входной последовательности B, определяют номер строки k.
  • второй, третий, четвертый и пятый биты последовательности B задают номер колонки l
  • результат преобразования выбирается из строки k и колонки l.

Предположим, что B=011011. Тогда S(1)(B)=0101. Действительно, k=1, l=13. В колонке 13 строки 1 задано значение 5, которое и является значением функции S(1)(011011).

Функция перестановки бит P(L), также используемая для определения функции шифрования, задается значениями, приведенными в таблице 5. В последовательности L 32 перестанавливается так, чтобы бит 16 стал первым битом, бит 7 - вторым и т.д.

Таблица 5. "Функция перестановки 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

Процесс получения ключей.

Чтобы завершить описание алгоритма шифрования данных, осталось привести алгоритм получение ключей K(i), i=1,2,...,16, размерностью в 48 бит. Ключи K(i) определяются по 64-битовому ключу шифра как это показано на рисунке 3.

Рисунок 3.

В начале над ключом шифра выполняется операция B, которая сводится к выбору определенных бит и их перестановке, как это показано в таблицей 6. Причем, первые четыре строки определяют, как выбираются биты последовательности C(0) (первым битом C(0) будет бит 57 бит ключа шифра, затем бит 49 и т.д., а последними битами биты 44 и 36 ключа шифра), а следующие четыре строки - как выбираются биты последовательности D(0) (т.е. последовательность D(0) будем состоять из битов 63,55,...,12, 4 ключа шифра).

Таблица 6. "Функция перестановки и выбора последовательности B"

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

Как видно из таблицы 6, для генерации последовательностей C(0) и D(0) не используются биты 8,16,25,32,40,48,56 и 64 ключа шифра. Эти биты не влияют на шифрование и могут служить для других целей (например, для контроля по четности). Таким образом, в действительности ключ шифра является 56-битовым. После определения C(0) и D(0) рекурсивно определяются C(i) и D(i), i=1,2,...,16. Для этого применяются операции сдвига влево на один или два бита в зависимости от номера шага итерации, как это показано в таблицей 7. Операции сдвига выполняются для последовательностей C(i) и D(i) независимо. Например, последовательность C(3) получается, посредством сдвига влево на две позиции последовательности C(2), а последовательность D(3) - посредством сдвига влево на две позиции последовательности D(2). Следует иметь в виду, что выполняется циклический сдвиг влево. Например, единичный сдвиг влево последовательности C(i) приведет к тому, что первый бит C(i) станет последним и последовательность бит будет следующая: 2,3,..., 28,1.

Таблица 7. "Функция сдвига Si"

1

1

2

1

3

2

4

2

5

2

6

2

7

2

8

2

9

1

10

2

11

2

12

2

13

2

14

2

15

2

16

1

Ключ K(i), определяемый на каждом шаге итерации, есть результат выбора определенных бит из 56-битовой последовательности C(i)D(i) и их перестановки. Другими словами, K(i) = K(C(i)D(i)), где функция K определяется данными, приведенными в таблицей 8.

Таблица 8. "Функция перестановки и выбора K"

14

17

11

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

Как следует из таблицы 8 первый бит K(i) - это бит 14 последовательности C(i)D(i), второй - бит 17, последний - бит 32.






Copyright © 2004-2016 "Delphi Sources". Delphi World FAQ




Группа ВКонтакте   Ссылка на Twitter   Группа на Facebook