Xreferat.com » Рефераты по информатике и программированию » Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

Содержание


Постановка задачи

Теоретический материал

Исходные данные

Скриншоты работы программы

Выводы

Постановка задачи


Реализовать алгоритм DES и 4 режима шифрования. Шифрование реализовать для любой длины сообщения и любой длины ключа до 56 бит включительно.

Зашифровать сообщения длиной 1 МБ, 10 МБ, 20 МБ и ключом 5,6,7 байт. Для каждого режима, длины сообщения и ключа замерять время и скорость зашифрования

В режимах шифрования DES OFB и CFB размер блока шифрования брать равным порядковому номеру в списке группы

Реализовать алгоритм RSA. Сгенерировать 3 пары открытый/закрытый ключей. Брать файлы размером 20 Кб, 50 Кб, 100 Кб, 500 Кб, 1 МБ.

Каждый файл шифровать с 3 парами ключей. Посчитать время зашифрования/расшифрования и среднюю скорость шифрования/расшифрования для каждой пары ключей и каждого файла.

Программа должна предусматривать сохранение зашифрованного и расшифрованного файла на диск, а также вывод на экран скорости и времени шифрования.


Примечание.

Исходный текст брать произвольный, используя символы из Алфавита (Алфавит брать из Таблицы 1, согласно Вашего варианта)

Ваш вариант=(Номер в списке группы) mod 23

Буквам поставить в соотвествие числа [0..мощность_алфавита-1] (например букве а->0, б->1, в->2 итд.)

Таблица 1.

№

п/п

A

B

Алфавит

15

2000

5000

Цифры, спецсимвол(@) и строчные буквы русского алфавита


Теоретический материал


Шифр RSA

Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.

В криптосистеме RSA открытый ключ КA, секретный ключ КB, сообщение М и криптограмма С принадлежат множеству целых чисел


ZN={0,1,2,...,N-1} (1)


где N - модуль:


N = P*Q. (2)


Здесь Р и Q - случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете.

Множество ZN с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ КA выбирают случайным образом так, чтобы выполнялись условия:

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

(3)

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования, (4)


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрованиягде - функция Эйлера, указывающая количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрованияУсловие (4) означает, что открытый ключ КA и функция Эйлера

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ K B, такой, что


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрованияKB * К A = 1 ( mod ( ) (5)


или


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования. Заметим, что K B и N должны быть взаимно простыми.

Открытый ключ К A используют для шифрования данных, а секретный ключ K B -для расшифрования.

Преобразование шифрования определяет криптограмму С через пару (открытый ключ КA, сообщение М) в соответствии со следующей формулой:

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

(6)


Обращение функции Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования, т.е. определение значения М по известным значениям С, К A и N, практически не осуществимо при N > 2512.

Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, используя пару (секретный ключ K B, криптограмма С) по следующей формуле:

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

 (7)


Процесс расшифрования можно записать так:


DB (ЕА (М)) = М. (8)


Подставляя в (8) значения (6) и (7), получаем:


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


Или


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования(9)


Величина Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрованияиграет важную роль в теореме Эйлера, которая утверждает, что если НОД (х,N)=1, то


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

или в несколько более общей форме


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования(10)


Сопоставляя выражения (9) и (10), получаем Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

или, что то же самое, Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования.

Именно поэтому для вычисления секретного ключа KB используют соотношение (5).

Таким образом, если криптограмму


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


возвести в степень K B, то в результате восстанавливается исходный открытый текст М, так как


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


Таким образом, получатель В, который создает криптосистему, защищает два параметра: секретный ключ K B и пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ К А .

Противнику известны лишь значения К А и N. Если бы он смог разложить число N на множители Р и Q, то он узнал бы "потайной ход" - тройку чисел {Р,Q, К A }, вычислил значение функции Эйлера


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


и определил значение секретного ключа K B.

Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных Р и Q составляют не менее 100 десятичных знаков).

Алгоритм шифрования и расшифрования в криптосистеме RSA

Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Как отмечалось выше, криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.

1. Пользователь В выбирает два произвольных больших простых числа Р и Q.

2. Пользователь В вычисляет значение модуля N=Р*Q.

3. Пользователь В вычисляет функцию Эйлера (8):


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


4. Выбирает случайным образом значение открытого ключа К A с учетом выполнения условий:


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


5. Пользователь В вычисляет значение секретного ключа kB, используя расширенный алгоритм Евклида при решении сравнения


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


6. Пользователь В пересылает пользователю А пару чисел (N, К A) по незащищенному каналу.

Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие шаги.

7. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа


Мi=0,1,2,...,N-1 .


8. Пользователь А шифрует текст, представленный в виде последовательности чисел М, по формуле


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования


9. Пользователь А отправляет криптограмму C1, С2, С3,...,Ci, ... пользователю В.

10. Пользователь В расшифровывает принятую криптограмму C1, С2, С3,...,Ci, ..., используя секретный ключ kB, по формуле


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования.


В результате будет получена последовательность чисел Mi, которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей К A и К B.


Шифр DES

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

Процесс шифрования заключается в начальной перестановке битов 64-битового блока, шестнадцати циклах шифрования и, наконец, обратной перестановки битов (рис.1).


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

Рис.1. Обобщенная схема шифрования в алгоритме DES


Необходимо сразу же отметить, что ВСЕ таблицы, приведенные в данной статье, являются СТАНДАРТНЫМИ, а следовательно должны включаться в вашу реализацию алгоритма в неизменном виде. Все перестановки и коды в таблицах подобраны разработчиками таким образом, чтобы максимально затруднить процесс расшифровки путем подбора ключа. Структура алгоритма DES приведена на рис.2.

Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

Рис.2. Структура алгоритма шифрования DES


Пусть из файла считан очередной 8-байтовый блок T, который преобразуется с помощью матрицы начальной перестановки IP (табл.1) следующим образом: бит 58 блока T становится битом 1, бит 50 - битом 2 и т.д., что даст в результате: T(0) = IP(T).

Полученная последовательность битов T(0) разделяется на две последовательности по 32 бита каждая: L(0) - левые или старшие биты, R(0) - правые или младшие биты.


Таблица 1: Матрица начальной перестановки IP

58 50 42 34 26 18 10 02

60 52 44 36 28 20 12 04

62 54 46 38 30 22 14 06

64 56 48 40 32 24 16 08

57 49 41 33 25 17 09 01

59 51 43 35 27 19 11 03

61 53 45 37 29 21 13 05

63 55 47 39 31 23 15 07


Затем выполняется шифрование, состоящее из 16 итераций. Результат i-й итерации описывается следующими формулами:


L(i) = R(i-1)

R(i) = L(i-1) xor f(R(i-1), K(i)) ,


где xor - операция ИСКЛЮЧАЮЩЕЕ ИЛИ.

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

На 16-й итерации получают последовательности R(16) и L(16) (без перестановки), которые конкатенируют в 64-битовую последовательность R(16)L(16).

Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP-1 (табл.2).


Таблица 2: Матрица обратной перестановки IP-1

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


Матрицы IP-1 и IP соотносятся следующим образом: значение 1-го элемента матрицы IP-1 равно 40, а значение 40-го элемента матрицы IP равно 1, значение 2-го элемента матрицы IP-1 равно 8, а значение 8-го элемента матрицы IP равно 2 и т.д.

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

Итеративный процесс расшифрования может быть описан следующими формулами:

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

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


На 16-й итерации получают последовательности L(0) и R(0), которые конкатенируют в 64-битовую последовательность L(0)R(0).

Затем позиции битов этой последовательности переставляют в соответствии с матрицей IP. Результат такой перестановки - исходная 64-битовая последовательность.

Теперь рассмотрим функцию шифрования f(R(i-1),K(i)). Схематически она показана на рис. 3.


Использование современных симметрических (DES) и асимметрических (RSA) алгоритмов шифрования

Рис.3. Вычисление функции f(R(i-1), K(i))


Для вычисления значения функции f используются следующие функции-матрицы:

Е - расширение 32-битовой последовательности до 48-битовой,

S1, S2, ... , S8 - преобразование 6-битового блока в 4-битовый,

Р - перестановка бит в 32-битовой последовательности.

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


Таблица 3:Функция расширения E

32 01 02 03 04 05

04 05 06 07 08 09

08 09 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 01


Результат функции Е(R(i-1)) есть 48-битовая последовательность, которая складывается по модулю 2 (операция xor) с 48-битовым ключом К(i). Получается 48-битовая последовательность, которая разбивается на восемь 6-битовых блоков B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). То есть:


E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .


Функции S1, S2, ... , S8 определяются табл.4.

Таблица 4

Функции преобразования S1, S2, ..., S8


Номер столбца

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15


Н

о

м

е

р


с

т

р

о

к

и

0

1

2

3

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

S1


0

1

2

3

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

S2


0

1

2

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

S3


0

1

2

3

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

S4


0

1

2

3

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

S5


0

1

2

3

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

S6


0

1

2

3

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

S7


0

1

2

3

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

S8


К табл.4. требуются дополнительные пояснения. Пусть на вход функции-матрицы Sj поступает 6-битовый блок B(j) = b1b2b3b4b5b6, тогда двухбитовое число b1b6 указывает номер строки матрицы, а b2b3b4b5 - номер столбца. Результатом Sj(B(j)) будет 4-битовый элемент, расположенный на пересечении указанных строки и столбца.

Например, В(1)=011011. Тогда S1(В(1)) расположен на пересечении строки 1 и столбца 13. В столбце 13 строки 1 задано значение 5. Значит, S1(011011)=0101.

Применив операцию выбора к каждому из 6-битовых блоков B(1), B(2), ..., B(8), получаем 32-битовую последовательность S1(B(1))S2(B(2))S3(B(3))...S8(B(8)).

Наконец, для получения результата функции шифрования надо переставить биты этой последовательности. Для этого применяется функция перестановки P (табл.5). Во входной последовательности биты перестанавливаются так, чтобы бит 16 стал битом 1, а бит 7 - битом 2 и т.д.


Таблица 5:Функция перестановки P

16 07

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: