69886

СТАНДАРТ ШИФРОВАНИЯ ДАННЫХ DES

Лабораторная работа

Информатика, кибернетика и программирование

DES шифрует открытый текст разбитый на блоки по 64 бита на выходе также блоки по 64 бита с помощью ключа длиной 56 битов из которого на основе перестановок и сдвигов по специальному фиксированному алгоритму производятся раундовые ключи.

Русский

2014-10-12

600.5 KB

3 чел.

PAGE   \* MERGEFORMAT 2

Лабораторная работа № 8

Тема: СТАНДАРТ ШИФРОВАНИЯ ДАННЫХ DES

Цель работы – изучить структуру алгоритма шифрования DES, на практике осуществить формирование подключей, зашифрование и расшифрование блока данных алгоритмом DES с укороченным количеством циклов.

Краткие теоретические сведения.

Федеральный стандарт шифрования данных  принят в США в ноябре 1976 года. В стандарт входит описание «блочного шифра типа Файстеля», а также различных режимов его работы, как составной части нескольких процедур криптографического преобразования данных. Обычно под аббревиатурой  понимается именнно «блочный шифр», который в стандарте соответствует процедуре шифрования в режиме  (Elecnronic Codebook Mode). Название вызвано тем, что любой «блочный шифр» является шифром простой замены и в этом отношении подобен кодовой таблице.

DES шифрует открытый текст, разбитый на блоки по 64 бита (на выходе также блоки по 64 бита) с помощью ключа длиной 56 битов, из которого на основе перестановок и сдвигов по специальному фиксированному алгоритму производятся раундовые ключи. Мощность множества открытых ключей DES равняется (), но реальная криптостойкость оценивается несколько меньшей величиной.

В основе алгоритма DES лежит сеть Фейстеля, чья цикловая (раундовая) функция  обрабатывает 32-разрядные слова (половину блока) и использует в качестве параметра 48-разрядный подключ.

Преобразование блока открытого текста в блок шифртекста продолжается два этапа.

Этап 1. Построение раундовых ключей, в процессе которого выбирается исходный ключ  из случайных 56 битов. 56 битов – это 8 7-битовых ASCII символов, т. е. пароль не может быть больше чем 8 букв. Если использовать лишь буквы и цифры, то количество возможных вариантов ключа будет гораздо меньше максимально возможных .

Восемь битов в позициях 8, 16, 32, 64 добавляются в ключ так, чтобы каждый байт содержал нечётное число единиц. С помощью этой операции можно обнаружить ошибки во время обмена и хранения ключей. 56 битов ключа разбиваются на два блока по 28 битов  и  и подвергаются перестановке по таблице:

Таб.1. Преобразование  (Permuted Choice 1) – перестановка ключа.

57

49

41

33

25

17

9

632

55

47

39

31

23

15

1

58

50

42

34

26

18

7

62

54

46

38

30

22

10

2

59

51

43

35

27

14

6

61

53

45

37

29

19

11

3

60

52

44

36

21

13

5

28

20

12

4

Каждые последующие блоки и  ключа, , получают из предыдущих блоков и в результате циклического сдвига:

Таб.2. Соответствие сдвигов номерам циклов .

№ цикла

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

Сдвиг вправо (Р)

0

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1

Раундовый ключ , , получается из битов блока и  выбором некоторых их 48-ми координат по таблице:

Таб.3. Преобразование  (Permuted Choice 2) – сжимающая перестановка

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

Таким образом, на первом этапе из одного ключа размером 56 битов строится ключевая таблица из 16-ти ключей , , длина каждого из которых 48 битов.

Процедура формирования подключей показана на рисунке 1.

Рис 1. Формирование подключей.

Этап 2. Блок  открытого текста после начальной перестановки по таблице

Таб.4 Преобразование  (initial permutation)– начальная перестановка

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

разбивается на два полублока левый  и правый  длиной по 32 бита. Эти блоки рассматриваются как 32-мерные двоичные векторы. После этого выполняется 16 раундов идентичных операций (функция ), в которых исходные данные комбинируются с ключом. Аргументами функции  являются блоки  по 32 бита и раундовые ключи  по 48 битов.

В каждом раунде сначала 32-битовый блок расширяется до блока  длиной 48 битов по таблице:

Таб.5. Преобразование  – расширяющая перестановка.

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

Выбор битов по таблицам 1, 3-5 из соответствующих блоков производится следующим образом. Таблица рассматривается как последовательность ее строк, записанных друг за другом, начиная с первой строки. Биты блока данных соответствующей длины нумеруются слева направо, начиная с единицы. Каждый элемент  таблицы рассматривается как номер бита  в блоке данных. Преобразование заключается в замене всех элементов  на биты .

Блок  покоординатно складывается по модулю 2 с 48 битами раундового ключа  и делится на 8 последовательных 6-битовых векторов :

.

Далее каждый из векторов , , трансформируется в 4-битовый вектор  с помощью так называемого -бокса (-box) – таблицы из четырёх строк и 16 столбцов. Каждый вектор , , попадает в свой бокс ,.

Таб.6. Таблицы -боксов для .

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

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

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

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

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

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

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

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

Это – главный этап алгоритма, потому что -боксы нелинейны и более чем другие операции придают системе  криптостойкости. Принципы построения -боксов:

  •  каждая строка -бокса – некоторая перестановка множества ;
  •  -боксы не должны быть линейными или аффинными преобразованиями исходных данных;
  •  изменение одного бита исходных данных в -боксе должно вызывать изменения по крайней мере двух битов на выходе из бокса;
  •  если на вход -бокса сначала подан вектор , а затем вектор , то векторы  и  должны отличаться хотя бы двумя битами.

Механизм действия S-боксов. Преобразование, с помощью которого 48-разрядный блок преобразуется в 32-разрядный состоит в выборке восьми тетрад из 8 таблиц (-боксов) размером 4 на 16. Из каждого -бокса выбирается одна тетрада. Для этого 48-разрядный блок делится последовательно на 8 комбинаций по 6 битов каждая. Первая комбинация (слева) является входом в первый -бокс, вторая – во второй и т.д. При этом, первый и последний биты комбинации задают номер строки, а остальные 4 бита – номер столбца -бокса, на пересечении которых расположена соответствующая тетрада.

Таким образом, результатом действия -боксов являются 8 4-битовых векторов , которые снова объединяются в единый 32-битовый блок. Координаты этого 32-битового блока подвергаются  перестановке в -боксе по таблице:

Таб.7. Преобразование .

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

Все описаны действию и образуют шифровальную функцию DES .

Вектор, полученный с помощью функции DES, покоординатно складывается по модулю 2 с вектором левого блока .

Таким образом -й раунд (-я итерация) алгоритма DES выглядит так:

;

,

где  и  – блоки данных, полученные в -м та ()-м раундах соответственно,  – 48 битовый ключ -го раунда, .

После 16-го раунда DES правый и левый блоки уже не меняются местами, а объединяются в блок  и подвергаются финальной перестановке, которая является обратной к начальной, по таблице:

Таб.8 Преобразование  – финальная перестановка

40

08

48

16

56

24

64

32

39

07

47

15

55

23

63

31

38

06

46

14

54

22

62

30

37

05

45

13

53

21

61

29

36

04

44

12

52

20

60

28

35

03

43

11

51

19

59

27

34

02

42

10

50

18

58

26

33

01

41

09

49

17

57

25

Финальная перестановка завершает алгоритм.

Общая схема алгоритма изображена на рис. 2.

Рис.2. Блок-схема работы алгоритма .

Криптограмму, полученную с помощью шифра , дешифруют теми же раундовыми ключами , но в обратном порядке: . Алгоритм генерации ключей также должен быть обратным – сдвиг вправо, количество битов сдвига определяется справа налево.

Другие режимы использования алгоритма шифрования DES.

Режим сцепления блоков шифртекста (CBC, Ciрher Block Chaining Mode). Суть этого режима состоит в том, что сообщение разбивается на блоки по 64 бит, и их последовательность зашифровывается. Перед зашифрованием (в режиме ECB), блок открытого текста поразрядно складывается с предыдущим блоком шифртекста. Для зашифрования первого блока шифртекста требуется уникальный для сообщения блок (вектор инициализации, IV). Последний не является секретным. Данный режим не позволяет накапливаться ошибкам при передаче, поскольку ошибка при передаче приведет к потере только двух блоков исходного текста. Существуют также режим шифрования с обратной связью (CFB, Cipher Feedback) и режим шифрования с внешней обратной связью (OFB, Output Feedback). Рассмотрение этих режимов выходит за рамки данной лабораторной работы.

Порядок выполнения работы.

  1.  Изучить краткие теоретические сведения о стандарте шифрования DES.
  2.  Получить последовательность всех шестнадцати подключей, выбрав ключ шифрования.

Варианты ключа шифрования:

1

12345670

11

05764132

21

37601452

2

23456701

12

57641320

22

76014523

3

34567012

13

76413205

23

60145237

4

45670123

14

64132057

24

01452376

5

56701234

15

41320576

25

13207654

6

67012345

16

02315467

26

32076541

7

70123456

17

14523760

27

20765413

8

03214765

18

45237601

28

07654132

9

13205764

19

52376014

29

76541320

10

32057641

20

23760145

30

65413207

  1.  Выбрать входной блок информации – 64 бита и зашифровать его вручную, используя один (первый) цикл алгоритма DES.
  2.  Убедиться в правильности зашифрования с помощью расшифрования.
  3.  Составить отчет, приобщив полученные результаты.

Требования к отчету.

В отчете должны быть приведены:

  1.  выбранный ключ;
  2.  последовательность подключей на всех шестнадцати циклах;
  3.  открытый блок сообщения;
  4.  зашифрованный блок сообщения;
  5.  промежуточные результаты, возникшие в процессе зашифрования;


 

А также другие работы, которые могут Вас заинтересовать

45491. Моделирование случайных чисел с заданным 34.5 KB
  Для этого непрерывный закон распределения вероятности события дискретизируем. hi высота iого столбца fx распределение вероятности показывает насколько вероятно некоторое событие. Если точка в пересечении этих двух координат лежит ниже кривой плотности вероятности то событие X произошло иначе нет. Метод взятия обратной функции Допустим задан интегральный закон распределения вероятности где fx функция плотности вероятности.
45492. Оценка точности модели 76 KB
  Преобразование Фурье Преобразование Фурье Модель сигнала Способ основывается на том что в любом сигнале присутствуют гармонические составляющие. Сумма гармоник с соответствующими весами составляет модель сигнала. Пусть задан сигнал: Определяем время рассмотрения сигнала: если сигнал периодический то время рассмотрения равно периоду p сигнала; b если сигнал непериодический то периодом сигнала считается все время его рассмотрения. Отметим важную особенность данного способа представления вместо всего сигнала во всех его подробностях...
45493. Регрессионные модели 85.5 KB
  Линейная одномерная модель: y =0 1 x Ei = Yi 0 1 Xi i = 1n где n число снятых экспериментально точек. Ошибки всех точек i от 1 до n следует сложить. Найдем значение sigm по формуле: Если в интервал Yэ Yт Yэ попадает 67 точек и более то выдвинутая нами гипотеза принимается. Если требуется большая уверенность в результате то используют дополнительное условие: в интервал Yэ 2 Yт Yэ 2 должны попасть 95 экспериментальных точек.
45494. Методы построения датчиков случайных чисел 75.5 KB
  Генератор случайных чисел ГСЧ Основа метода МонтеКарло ГСЧ равномерно распределенных в интервале 01. Такая последовательность чисел должна обладать математическим ожиданием и дисперсией Если окажется что случайные числа должны быть распределены в другом интервале то преобразование имеет вид: ГСЧ ррb x:= b r Пример: x:= 313r r:=0 x:=3r:=1 x:=10r:=0. ГСЧ порождает случайный поток событий с равномерным законом распределения. ГСЧ делятся на: физические; табличные; алгоритмические.
45495. Общие принципы построения моделирующих алгоритмов 47.5 KB
  Общие принципы построения моделирующих алгоритмов Проблема при составлении алгоритмов на последовательной машине состоит в том что при моделировании необходимо отслеживать множество параллельных процессов во времени. Основные методы Принцип Принцип особых состояний Принцип последовательной проводки заявок Принцип параллельной работы объектов Принцип Определение состояния системы в фиксированные моменты времени: t t t2 Особенности: самый универсальный и простой метод описывает широкий класс объектов Недостатки: самый...
45496. Иерархия протоколов 304 KB
  Информационная совместимость – это правила передачи информации от одного узла к другому. Для того чтобы передать информацию от одного узла другому используют как минимум три уровня: физический; канальный; сетевой; На физическом уровне описаны характеристики передающей среды Основной задачей канального уровня является преобразование физической среды в канал передачи данных а так же выявление ошибок и деление информации на кадры. Кадр – единица измерения для передачи информации для сетей. Первые четыре уровня обеспечивают...
45497. Теоретические основы передачи данных 378.5 KB
  Ограничения на пропускную способность передачи данных.5c ∑ n sin2pnft∑ bncos2pnft f – частота nbn – амплитуды nой гармоники t – время передачи сигнала gt – определенное ограничение на пропускную способность. При этом скорость передачи информации зависит от способа кодирования и скорости изменения кодирования.
45498. Магистрали 261 KB
  Основное достижение – это применение одного канала для передачи сигналов между различными источниками и приемниками. Основано на разделении передачи сигналов от разных источников по различным несущим частотам. Это связано с тем что пропускная способность составляет 25000 Гц и за счет этого в оптических каналах скорость передачи на порядок выше. Это связано с тем что после получения канала с аналоговой петли скорость передачи данных может быть увеличена в несколько раз поэтому для цифровых каналов связи применяется метод мультиплексирования...
45499. Коммутация 466 KB
  Для систем передачи используются три способа коммутации: коммутация сообщений; коммутация каналов; коммутация пакетов. При использовании коммутации каналов снижаются накладные расходы на передачу информации. При коммутации пакетов все сообщения разделяются на определенные пакеты. В отличие от коммутации каналов абонент не может монополизировать линию.