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

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

Содержание

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

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

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

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

Выводы

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

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

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

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

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

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

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

Примечание.

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

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

3.        Буквам поставить в соотвествие числа [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 выбирают случайным образом так, чтобы выполнялисьусловия:

/>

(3)

/>, (4)

/>где — функция Эйлера, указывающая количествоположительных целых чисел в интервале от 1 до N, которыевзаимно просты сN.

/>

Условие (4)означает, что открытый ключ КA и функция Эйлера /> должны быть взаимно простыми.

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

/>KB * КA = 1 ( mod () (5)

или

/>

Это можноосуществить, так как получатель В знает пару простых чисел (P,Q) и может легконайти />. Заметим, что KB и N должны быть взаимно простыми.

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

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

/>

(6)

Обращениефункции />, т.е. определениезначения М по известным значениям С, КAи N, практически не осуществимо при N > 2512.

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

/>

 (7)

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

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

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

/>

Или

/>(9)

Величина />играет важную роль в теореме Эйлера, которая утверждает, что еслиНОД (х,N)=1, то

/>

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

/>(10)

Сопоставляявыражения (9) и (10), получаем />

или, что тоже самое, />.

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

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

/>

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

/>

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

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

/>

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

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

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

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

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

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

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

/>

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

/>

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

/>

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

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

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

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

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

/>

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

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

/>.

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

Шифр DES

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

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

/>

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

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

/>

Рис.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) выполняются те же действия, чтои в процессе шифрования, но в обратном порядке.

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