Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

Контрольная работа по "Информатике". 21

НЕКОММЕРЧЕСКОЕ АКЦИОНЕРНОЕ ОБЩЕСТВО АЛМАТИНСКИЙ УНИВЕРСИТЕТ ЭНЕРГЕТИКИ И СВЯЗИ

Кафедра Телекоммуникационных Систем

КУРСОВАЯ РАБОТА

По дисциплине:

«Защита информации в телекоммуникационных системах»

Выполнил: ст. гр. Агаханова Евгения

№ зач.кн. 123070 Проверила: доцент Федулина И.Н.

Алматы, 2013

Содержание

Введение

В данной курсовой работе рассматриваются симметричные и несимметричные системы шифрования. Задание №1 посвящено шифрованию по алгоритму RSA, а также предлагаются расчеты по электронной подписи с использованием хеш-функции.

Задание №2 посвящено асимметричному шифрованию или шифрованию с открытым ключом. Рассматриваются алгоритмы Диффи–Хелмана, Шамира и Эль-Гамаля.

Создание алгоритмов асимметричного шифрования является величайшим и, возможно, единственным революционным достижением в истории криптографии.

Алгоритмы шифрования с открытым ключом разрабатывались для того, чтобы решить две наиболее трудные задачи, возникшие при использовании симметричного шифрования.

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

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

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

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

Задание 1.1

Несимметричное шифрование-дешифрование.

Зашифровать информацию по методу RSA для последующей передачи. Вариант задания определяется последними цифрами номера студенческого билета. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма числа р и q.

Одним из наиболее распространенных методов несимметричного шифрования - дешифрования является метод шифрования с открытым ключом, в котором используется алгоритм RSA.

Алгоритм основан на использовании операции возведения в степень модульной арифметики. Его можно представить в виде следующей последовательности шагов:

Шаг 1. Выбирается два больших простых числа р и q. Простыми называются числа, которые делятся на самих себя и на 1. На практике для обеспечения криптостойкости системы величина этих чисел должна быть длиной не менее двухсот десятичных разрядов.

Шаг 2. Вычисляется открытая компонента ключа n: n = р q.

Шаг 3. Находится функция Эйлера по формуле: f(р q.)=(р-1)(q-1)

Функция Эйлера показывает количество целых положительных чисел от1 до n, которые не имеют ни одного общего делителя, кроме 1.

Шаг 4. Выбирается число е, которое должно взаимно простым со значением функции Эйлера и меньшим, чем f(р q.)

Шаг 5. Определяется число d, удовлетворяющее соотношению

е * d(mod f(р q.))=1. Числа е и n принимаются в качестве открытого ключа.

В качестве секретного ключа используются числа d и n.

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

L ³ log₂(n.+1); Каждый блок рассматривается как целое положительное число X(i), принадлежащее интервалу (0, n-1). Таким образом, исходная информация представляется последовательностью чисел X(i), (i = 1.I). Значение I определяется длиной шифруемой последовательности.

Шаг 7. Зашифрованная информация получается в виде последовательности чисел Y(i)= (Y(i))^e (mod n).

Шаг 8. Для расшифрования информации используется следующая зависимость: Х(i)= (Y(i))^e (mod n).

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

Текст для шифрования: Книга

p = 7

q=11

Вычислим открытую компонента ключа n:

n=7*11=77

Находится функция Эйлера по формуле

Выбирается число е, которое должно быть взаимно простым со значением функции Эйлера и меньшим, чем f(р q.)

Предположим, что е=13.

4.Выберем число d по следующей формуле: е * d(mod f(р q.))=1 d будет равно 37: (d=37).

Числа е и n принимаются в качестве открытого ключа. В качестве секретного ключа используются числа d и n.

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

_L₌₆

Каждый блок рассматривается как целое положительное число X(i), принадлежащее интервалу (0, n-1). Таким образом, исходная информация представляется последовательностью чисел X(i), (i = 1.I).Значение I определяется длиной шифруемой последовательности.

Представим шифруемое сообщение как последовательность чисел в диапазоне от 0 до 32:

Представим шифруемое сообщение как последовательность чисел в

Буквы алфавита	А	Б	В	Г	Д	Е	Ж	З	И	Й	К	Л	М	Н	О	П	Р
Номер буквы	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Буквы алфавита	С	Т	У	Ф	Х	Ц	Ч	Ш	Щ	Ъ	Ы	Ь	Э	Ю	Я
Номер буквы	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32

диапазоне от 0 до 32:

11, 14, 9, 4, 1

Для представления чисел в двоичном виде требуется 6 двоичных разрядов, так как в русском алфавите используются 33 буквы, поэтому исходный текст имеет вид:

К	11	001011
Н	14	001110
И	9	001001
Г	4	000110
А	1	000001

Зашифрованная информация получается в виде последовательности чисел

Зашифруем сообщение, используя открытый ключ {13,77}

Расшифруем полученные данные, используя закрытый ключ {37,77}.

_Вывод:

Данные расшифрованы, сопоставим последовательность <11,14,9,4,1> с последовательностью букв нашего алфавита. Получили слово Книга.

Наиболее популярная криптосистема RSA, разработанная в 1977 году, получила название в честь ее создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана.

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

Задание 1.2. Хеширование и цифровая подпись документов

Используя данные задания 1, получить хеш – код m для сообщения М при помощи хеш – функции Н, взятой из рекомендаций МККТТ Х.509. Вектор инициализации Н₀ выбрать равным нулю.

Вычислить цифровую подпись методом RSA под электронным документом М, используя рассчитанный хеш – код m и секретный ключ d.

Представить схему цифровой подписи с подробным описанием ее функционирования.

Хеш – функцию МККТТ Х.509 запишем следующим образом:

где - вектор инициализации;

- длина блока.

Все блоки делят пополам и к каждой половине прибавляют равноценное количество единиц. С преобразованными таким образом блоками производят интеграционные действия.

Необходимо получить хеш – код сообщения Каримова при помощи хеш функции Х.509 с параметрами p=7, q=11.

Получить значение модуля:

Представить сообщение в виде номеров букв русского алфавита в десятичном и двоичном видах:

К	11	00001011
Н	14	00001110
И	9	00001001
Г	4	00000110
А	1	00000001

Разбить байт пополам, добавив в начало полубайта единицы и получить хешируемые блоки М_i:

M₁	M₂	M₃	M₄	M₅
11110000	11111011	11110000	11111110	11110000
M₆	M₇	M₈	M₉	M₁₀
11111001	11110000	11110110	11110000	11110001

Выполним интеративные шаги:

1 интерация:

M₁	1111 0000

H₀	0000 0000
	1111 0000=240₁₀
	240²mod77=4
H₁	4₁₀= 00000100₂

2 интерация:

M₂	11111011

H₁	00000100
	11111111=255₁₀
	255² mod77=37₁₀
H₂	37₁₀=00100101₂

3 интерация:

M₃	11110000

H₂	00100101
	01010101=85₁₀
	85² mod77=64₁₀
H₃	64₁₀ = 01000000₂

4 интерация:

M₄	11111110

H₃	01000000
	10111110=190₁₀
	190² mod77=64₁₀
H₄	64₁₀ = 01000000₂

5 интерация:

M₅	11110000

H₄	01000000
	10110000=176₁₀
	176² mod77=22
H₅	22₁₀ = 00010110

6 интерация:

M₆	11111001

H₅	00010110
	11101111=239₁₀
	239² mod77=64₁₀
H₆	64₁₀ = 01000000₂

7 интерация:

M₇	11110000

H₆	01000000
	10110000=176₁₀
	176² mod77=22
H₇	22₁₀=00010110

8 интерация:

M₈	11110110

H₇	00010110
	11100000=224₁₀
	224² mod77=39
H₈	49₁₀=00110001

9 интерация:

M₉	1111 0000

H₈	00110001
	11000001=193₁₀
	193² mod77=58
H₉	58₁₀ = 00111010

10 интерация:

M₁₀	11110001

H₉	00111010
	11001011=203₁₀
	203² mod91=14
H₁₀	14₁₀ = 00001110

Вывод:

Таким образом, исходное сообщение «Каримова» имеет хеш – код m=14

Для вычисления цифровой подписи используем следующую формулу:

Пара (M, S) передается получателю как электронный документ М, подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа d.

Получив пару (M, S), получатель вычисляет хеш – код сообщения М двумя способами:

Восстанавливает хеш – код m’, применяя криптографическое преобразование подписи S с использованием открытого ключа e:

Находит результат хеширования принятого сообщения с помощью той же хеш – функции: m=H(M) =14.

При равенстве вычисленных значений m’ и m получатель признает пару (M, S) подлинной.

Задача 2. Шифрование по алгоритму Шамира

Зашифровать сообщение по алгоритму Шамира для трех абонентов, взяв значение сообщения m и значение p из таблицы 2. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j – требуемые для реализации этого алгоритма число р. Выбор данных для других абонентов произвести циклически согласно процедуре (i + 1) и (g + 1).

Последние цифры номера зачетной книжки – (17). Выбираем для трех абонентов (сообщение, p) - (14,51), (16,53), (18,57).

Таблица 2.3 – Исходные данные

I	0	1	2	3	4
Сообщение	12	14	16	18	20
G	0	1	2	3	4
p	29	31	37	41	43

I	5	6	7	8	9
Сообщение	22	24	26	28	30
G	5	6	7	8	9
p	47	49	51	53	57

Перейдем к описанию системы. Пусть есть два абонента А и В, соединенные линией связи. А хочет передать сообщение m абоненту Б так, чтобы никто не узнал его содержание. А выбирает случайное большое простое число р и открыто передает его В. Затем А выбирает два числа с_{А
и}d_A , такие, что

с_Аd_A mod (р - 1) = 1. (2.1)

Эти числа А держит в секрете и передавать не будет. В тоже выбирает два числа с_в d_в, такие, что

с_в<d_в mod (p - 1) = 1, (2.2)

и держит их в секрете.

После этого А передает свое сообщение m, используя трехступенчатый протокол. Если m < р (m рассматривается как число), то сообщение т передается сразу , если же т р, то сообщение представляется в виде m₁, m₂,..., m_t, где все m_i < р, и затем передаются последовательно m₁, m₂,..., m_t. При этом для кодирования каждого m_i лучше выбирать случайно новые пары (c_A,d_A) и (c_B,d_B) — в противном случае надежность системы понижается. В настоящее время такой шифр, как правило, используется для передачи чисел, например, секретных ключей, значения которых меньше р. Таким образом, мы будем рассматривать только случай m < р.

Описание протокола.

Шаг 1. А вычисляет число: Х₁ =m^СА modp (2.3), где m — исходное сообщение, и пересылает х₁к В.

Шаг 2. В, получив х₁, вычисляет число: X₂ = х₁^CB mod p (2.4),

и передает х₂ к А.

Шаг 3. А вычисляет число: X₃ = х₂^dA mod p (2.5),

и передает его В.

Шаг 4. В, получив х₃, вычисляет число X₄ = x₃^dB mod p (2.6).

Утверждение (свойства протокола Шамира).

1) х₄ = m, т.е. в результате реализации протокола от А к В действительно передается исходное сообщение;

2) злоумышленник не может, узнать, какое сообщение было передано.

Доказательство. Вначале заметим, что любое целое число е 0 может быть представлено в виде е = k(р-1)+r, где r = е mod (p-1). Поэтому на основании теоремы Ферма: (2.7).

Справедливость первого пункта утверждения вытекает из следующей цепочки равенств:

(предпоследнее равенство следует из (2.7), а последнее выполняется в силу (2.1) и (2.2)).

Доказательство второго пункта утверждения основано на предположении, что для злоумышленника, пытающегося определить m, не существует стратегии более эффективной, чем следующая. Вначале он вычисляет C_B из (2.4), затем находит d_B и, наконец, вычисляет Х₄ = m по (2.6). Но для осуществления этой стратегии злоумышленник должен решить задачу дискретного логарифмирования (2.4), что практически невозможно при больших р.

Опишем метод нахождения пар c_A,d_A и с_B,d_B, удовлетворяющих (2.1) и (2.2). Достаточно описать только действия для абонента А. так как действия для В совершенно аналогичны. Число с_A выбираем случайно так, чтобы оно было взаимно простым с р-1 (поиск целесообразно вести среди нечетных чисел, так как р - 1 четно), Затем вычисляем d_A с помощью обобщенного алгоритма Евклида.

Теорема Пусть a и b – два целых положительных числа. Тогда существуют целые (не обязательно положительные) числа x и y, такие, что

ax + by = gcd(a, b). (1)

Обобщенный алгоритм Евклида служит для отыскания gcd(a,b) и x,y, удовлетворяющих (1). Введем три строки U=(u₁, u₂, u₃), V=(v₁, v₂, v₃) и Т=(t₁, t₂, t₃). Тогда алгоритм записывается следующим образом.

Решение:

Пусть А хочет передать В сообщение m = 26. А выбирает р = 29,

с_Аd_A mod (р - 1) = 1.

с_А = 3, d_A = 19.

Аналогично, В выбирает параметры

с_вd_в mod (p - 1) = 1

c_B = 11 и d_B = 23. Переходим к протоколу Шамира.

Шаг 1. x₁ = 26³mod 29 =2.

Шаг 2. х₂ = 2¹¹ mod 29 = 18.

ШагЗ. x₃= 18¹⁹ mod 29 =288.

Шаг 4. х₄ = 288²³ mod 29 = 26.

Таким образом, В получил передаваемое сообщение m = 26.

Пусть B хочет передать C сообщение m = 28. B выбирает р = 31,

С_Bd_B mod (р - 1) = 1.

С_B = 13, d_B = 7.

Аналогично. C выбирает параметры

С_cd_c mod (p - 1) = 1

C_c = 7 и d_c = 9. Переходим к протоколу Шамира.

Шаг 1. x₁ = 28¹³mod 31 =21.

Шаг 2. х₂ = 21⁷ mod 31 = 11.

ШагЗ. x₃= 11⁷ mod 31 =13.

Шаг 4. х₄ = 13⁹ mod 31 =28.

Таким образом, C получил передаваемое сообщение m = 28.

Пусть R хочет передать A сообщение m = 30. C выбирает р = 37,

С_Rd_R mod (р - 1) = 1.

С_R = 7 , d_R = 31.

Аналогично. В выбирает параметры

С_Ad_A mod (p - 1) = 1

C_A = 17 и d_A = 17. Переходим к протоколу Шамира.

Шаг 1. x₁ = 30⁷mod 37 =3.

Шаг 2. х₂ = 3¹⁷ mod 37 = 25.

ШагЗ. x₃= 25³¹ mod 37 = 13.

Шаг 4. х₄ = 13⁷ mod 37 =30.

Таким образом, A получил передаваемое сообщение m = 30.

Задача 3. Шифрование по алгоритму Эль - Гамаля

По таблице 3, выбрать сообщение m и секретный ключ x и провести шифрование по методу Эль-Гамаля для пяти абонентов. Вариант задания определяется последними цифрами номера студенческого билета. По номеру i (предпоследняя цифра) студент выбирает сообщение для зашифровывания, по j (последняя цифра) – требуемые для реализации этого алгоритма секретный ключ x. Исходные данные для других четырех секретных ключей x выбираются циклически по процедуре (i+1) и (j+1).

I	0	1	2	3	4
Сообщение	5	7	9	11	13
G	0	1	2	3	4
X	29	11	13	7	19

I	5	6	7	8	9
Сообщение	3	15	11	15	13
G	5	6	7	8	9
X	31	37	43	47	51

Пусть имеются абоненты А, В, С, D, E которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. Шифр Эль – Гамаля решает эту задачу, используя, в отличие от шифра Шамира, только одну пересылку сообщения. Фактически здесь используется схема Диффи – Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново.

Для всей группы абонентов выбираются некоторое большое простое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети).

Нам необходимо выбрать числа p и g так, чтобы они отвечали следующим требованиям:

g^q mod p

где p=2q+1.

Возьмем p=61 и g=11.

2q+1=71 q=35

Проверим соотношение:

7³⁵mod 61= 60

1 – выполняется.

Затем каждый абонент группы выбирает свое секретное число c_i:

1 < C_i < р – 1

(см. таблицу 5.1), и вычисляет соответствующее ему открытое число d_i:

d_i=g^Сimod p (3.1)