Программирование - это просто
Advertisement
Главная arrow Статьи arrow Разные статьи по программированию arrow Алгоритмы шифрования. Алгоритм DES.
15.06.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Алгоритмы шифрования. Алгоритм DES. Печать E-mail
Автор megabax   
04.08.2014 г.
В этой статье будет пошагово описано создание на Delphi приложение

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

Как я уже говорил на прошлом уроке, алгоритм шифрования DES -  это стандарт шифрования данных, который был разработан еще в 1974 году компанией IBM. Шифрование происходит на основе ключа длиной 64 бита, из которых 56 приходятся непосредственно на шифрование, а 8 бит - это системные  разряды.

Алгоритм использует комбинацию нелинейных (S-блоки) и линейных (перестановки E, IP, IP-1) преобразований. Для DES рекомендовано несколько режимов:

  • режим электронной кодовой книги (ECB — Electronic Code Book),
  • режим сцепления блоков (СВС — Cipher Block Chaining),
  • режим обратной связи по шифротексту (CFB — Cipher Feed Back),
  • режим обратной связи по выходу (OFB — Output Feed Back).

Разберем эти режимы более подробно.

Режим электронной кодовой книги заключается в том, что каждый блок открытого текста заменяется блоком шифротекста. Еще этот метод называется методом простой замены. Недостаток ECB, в сравнении c другими режимами шифрования — сохранение статистических особенностей открытого текста. Например, если зашифровать таким методом картинку, то даже в зашифрованном виде сохраниться контру этой картинки.

Рассмотрим это на примере. Исходная картинка (Источник: http://commons.wikimedia.org/wiki/File:Tux.jpg?uselang=ru):

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

Картинка в зашифрованном виде (Источник http://commons.wikimedia.org/wiki/File:Tux_ecb.jpg?uselang=ru):

 

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

Картинка, зашифрованная другим методом шифрования (Источник http://commons.wikimedia.org/wiki/File:Tux_secure.jpg?uselang=ru):

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

Режим сцепления блоков. Это более надежный метод, чем режим электронной кодовой книги.  Его суть в том, что каждый блок открытого текста (кроме первого) побитово складывается по модулю 2 (операция XOR) с предыдущим результатом шифрования. Это усовершенствованный режим шифрования по сравнению с ECB: каждый блок открытого текста маскируется соответственно блоком шифротекста, полученном на предыдущем этапе. Однако и у него есть недостатки:

  • возможность определения начала изменения данных при изменении шифротекста

  • возможность переделать открытый текст при перемещении блоков

  • подмена шифротекста с следующим за ней изменением открытого текста

Режим обратной связи по шифротексту. Для шифрования следующего блока открытого текста он складывается по модулю 2 с перешифрованным (блочным шифром) результатом шифрования предыдущего блока. Криптостойкость этого метода  определяется криптостойкостью используемого шифра. Фиксированные блоки открытого текста маскируются блоками шифротекста. Если в режиме СFВ с полноблочной обратной связью имеется два идентичных блока шифротекста, результат шифрования на следующем шаге будет тем же.

Режим обратной связи по выходу. Режим (OFB)[5] обратной связи вывода превращает блочный шифр в синхронный шифрпоток: это генерирует ключевые блоки, которые являются результатом сложения с блоками открытого текста, чтобы получить зашифрованный текст. Так же, как с другими шифрами потока, зеркальное отражение в зашифрованном тексте производит зеркально отраженный бит в открытом тексте в том же самом местоположении. Это свойство позволяет многим кодам с исправлением ошибок функционировать как обычно, даже когда исправление ошибок применено перед кодированием.

Шифр DES является блочным шифром. Входными данными для него служат блок размером n бит и k-битный ключ. На выходе, после применения шифрующего преобразования, получается n-битный зашифрованный блок, причём незначительные различия входных данных как правило приводят к существенному изменению результата. Блочные шифры реализуются путём многократного применения к блокам исходного текста некоторых базовых преобразований.

Шифрование начинается с начальных перестановок, затем идет 16 циклов шифрование, после чего конечные перестановки.

Начальные перестановки определяются следующей таблицей:

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,50 и 42, а последние 23,15 и 7.

Полученные таким образом данные участвую в 16-ти итерационных преобразованиях  Фейстеля. Суть этих преобразований состоит в том, что мы разбиваем  блок данных на две части по 32 бита: L(0) и R(0). Где L(0) - старшие биты, R0 - младшие. Весь блок мы обозначим T(0).

Пусть T(i-1)=L(i-1)R(i-1) - это результат i-1 итерации, тогда результат i-ой итерации T(i)=L(i)R(i) определяется следующим образом:

L(i)=R(i-1)

R(i)=L(i) исключающее ИЛИ f((R(i-1),(k(i))

Где функция f - это функция шифрования. Ее аргументами являются 32-битный вектор R(i-1) и 48-битный ключ k(i), который является результатом преобразования 56- битного ключа k.

Считается функция f по следующему алгоритму:

1. Вычисляется функция расширения E.

2. Производиться функция XOR (исключающее или) с ключом k.

3. Производиться преобразование S, состоящее из 8 преобразований S1, S2,  S3, ... S8.

4. Перестановка P.

И сейчас мы эти шаги рассмотрим более подробно. Функция расширения 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(Ri-1) являются битами 32,1 и 2 вектора Ri-1. Стоит заметить, что некоторые биты дублируются.

Полученный после перестановок вектор E(Ri-1) складывается по модулю 2 (применяется функция XOR) с ключами ki. Затем результат представляется в виде восьми последовательных блоков B1, B2, B3, ... B8. Каждый такой B блок является 6-битным блоком.  

Далее, каждый блок B трансформируется в блок B' с помощью преобразования 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

 

 S1

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

15

1

8

14

6

11

3

4

9

7

2

13

12

0

5

10

 

 S2

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

10

0

9

14

6

3

15

5

1

13

12

7

11

4

2

8

 

S3

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

7

13

14

3

0

6

9

10

1

2

8

5

11

12

4

15

 

S4

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

2

12

4

1

7

10

11

6

8

5

3

15

13

0

14

9

 

 S5

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

12

1

10

15

9

2

6

8

0

13

3

4

14

7

5

11

 

 

S6

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

4

11

2

14

15

0

8

13

3

12

9

7

5

10

6

1

 

 

 S7

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

0

13

2

8

4

6

15

11

1

10

9

3

14

5

0

12

7

 

 

 S8

 

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

Предположим, что B3=101111 и мы ходим найти B'3. Первые и последние разряды являются двоичной записью числа  a, лежит в диапазоне от 0 до 3. Средние 4 разряда представляют число b, лежащее в диапазоне от 0 до 15. Строки таблицы S3 нумеруются от 0 до 3, столбцы от 0 до 15. Пара чисел (а, b) определяет число, находящееся в пересечении строки а и столбца b. Двоичное представление этого числа дает B'3. В нашем случае двоичное значение числа a = 11. Десятичное 3. Для числа b двоичное значение 0111, десятичное 7. Таким образом, нам надо взять число на пересечении строки 3 и столбца 7. Это число 7.

Далее идет перестановка 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-преобразования - это 16,17,20,21.

Ключи тоже получаются хитромудрым способом. Они делаются из исходного ключа k, путем разбиения его на 8 ключей ki. Восемь бит, находящихся в позициях 8, 16, 24, 32, 40, 48, 56, 64 убираются из ключа k таким образом чтобы каждый байт содержал нечетное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. Далее делают перестановку для расширенного ключа (кроме добавляемых битов 8, 16, 24, 32, 40, 48, 56, 64), согласно следующей таблице:

57 49 41 33 25 17 1 9 C0
10 2 59 51 43 35 19 27
63 55 47 39 31 23 7 15 D0
14 6 61 53 45 37 21 29

Эта перестановка определяется двумя блоками C0 и D0 по 28 бит в каждом. Первые три бита C0 это биты 59, 49 и 41 расширенного ключа. А первые три бита блока D0 - это биты 63,55,47 расширенного ключа. Ci, Di получаються из C(i-1), D(i-1) одним или двумя левыми циклическими сдвигами согласно таблице:

i

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

Ключи ki, i=1,...16 состоит из 48 бит, выбранных из битов 56-битного вектора CiDi согласно таблице ниже:

 

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

И завершает шифрование конечная перестановка IP-1. Она действует на T16 согласно следующей таблице

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

При расшифровке данных все действия выполняются в обратном порядке. В 16 циклах расшифрования, в отличие от шифрования c помощью прямого преобразования сетью Фейстеля, здесь используется обратное преобразование сетью Фейстеля. При этом производятся следующие шаги:

R(i-1)=Li

L(i-1)=Ri исключающее ИЛИ f(Li,ki)

Ключи ki, функция f, перестановки IP и IP-1 точно такие же, как и в процессе шифрования.

 

Последнее обновление ( 04.08.2014 г. )
 
Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги