Теоретическая часть. к расчётно-графической работе по Информационная безопасность (наименование дисциплине)

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

Задание №17

На расчётно-графическую работу по дисциплине

«Информационная безопасность»

Студент Тихонов Е.В. Группа ПИ-302з

Консультант Абдулнагимов А.И.

1. Тема курсовой работы: Изучение алгоритма шифрования RSA

Изучить алгоритм шифрования RSA.

Зашифровать и расшифровать собственные фамилию, имя, отчество по алгоритму RSA, используя случайные простые числа p=17 и q=11.

Цифровой эквивалент ФИО получить с помощью вычисления их порядковых номеров в алфавите (Буква А=1, Б=2, В=3 и т.д.)

2. Пояснительная записка должна содержать

- теоретическую часть

- основные формулы

- результаты расчетов

3. Структура оформления пояснительной записки:

- титульный лист

- задание

- содержание

- основной текст

- список литературы

4. Форматирование: лист А4, отступ слева – 3 см, остальные – 2см

5. Сроки предоставления: весенняя сессия

Консультация по email: studentconsult@rambler.ru

Оглавление

Задание №17. 2

Теоретическая часть. 4

Результаты расчетов. 6

Выводы.. 9

Список литературы.. 9

Теоретическая часть

Очевидно, первую реальную криптосистему шифрования/дешифрования с открытым ключом предложил в 1973 году Клиффорд Кок (Clifford Cock) из британской Группы защиты электронных коммуникаций (CESG). Метод Кока практически идентичен RSA.

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

Здесь как нельзя лучше подойдет следствие теоремы Эйлера: для таких любых двух простых чисел p и q и таких любых двух целых чисел n и m, что n = pq и 0 < m < n, и произвольного целого числа k выполняются следующие соотношения:

mkφ (n)+1 = mk(p− 1)(q− 1)+1 ≡ m mod n,

где φ (n) является функцией Эйлера, значение которой равно числу положительных целых чисел, меньших n и взаимно простых с n. В случае простых p и q имеем φ (pq) = (p− 1)(q− 1).

Поэтому требуемое отношение получается при условии

ed = kφ (n) + 1.

Это эквивалентно следующим соотношениям:

ed ≡ 1 mod φ (n),

d ≡ e− 1 mod φ (n),

т.е. e и d являются взаимно обратными по модулю φ (n). Обратите внимание, что в соответствии с правилами арифметики в классах вычетов это может иметь место только тогда,

когда d (а следовательно, и e) является взаимно простым с φ (n). В эквивалентной записи

gcd(φ (n), d) = 1.

Теперь у нас есть все, чтобы представить схему RSA. Компонентами схемы являются:

p и q – два простых числа (секретные, выбираются),

n = pq (открытое, вычисляется),

такое e, что gcd(φ (n), e) = 1, 1 < e, φ (n), (открытое, выбирается),

d ≡ e− 1 mod φ (n) (секретное, вычисляется).

Личный ключ складывается из {d, n}, а открытый – из {e, n}. Предположим, что пользователь A опубликовал свой открытый ключ и теперь пользователь B собирается переслать

ему сообщение M. Тогда пользователь B вычисляет C = Me(mod n) и пересылает C. Получив этот шифрованный текст, пользователь A дешифрует его, вычисляя M = Cd(mod n).

Имеет смысл привести здесь обоснование этого алгоритма. Мы выбрали e и d такие, что d ≡ e− 1 mod φ (n).

Таким образом, ed ≡ 1 mod φ (n).

Значит, ed имеет вид kφ (n) + 1. Но по следствию теоремы Эйлера, для таких любых двух простых чисел p и q и целых чисел n = pq и M, что 0 < M < n, выполняются соотношения Mkφ (n)+1 = Mk(p− 1)(q− 1)+1 ≡ M mod n.

Поэтому Med ≡ M mod n. Теперь мы имеем

C =Me mod n,

M =C

d mod n = (Me)

d mod n = Med mod n ≡ M mod n.

Пример генерации ключей и шифрования по алгоритму RSA:

1. Выбирается два простых числа, p = 7 и q = 17.

2. Вычисляется n = pq = 7 × 17 = 119.

3. Вычисляется φ (n) = (p − 1)(q − 1) = 96.

4. Выбирается e, взаимно простое с φ (n) = 96 и меньшее, чем φ (n); в данном случае

e = 5.

5. Определяется такое d, что de = 1 mod 96 и d < 96. Соответствующим значением будет

d = 77, так как 77 × 5 = 385 = 4 × 96 + 1.

В результате получаются открытый ключ KU = {5, 119} и личный ключ KR = {77, 119}.

В данном примере показано использование этих ключей с вводимым открытым текстом

M = 19. При шифровании 19 возводится в пятую степень, что в результате дает 2476099.

В результате деления на 119 определяется остаток, равный 66. Следовательно, 195 =

66 mod 119, и поэтому шифрованным текстом будет 66. Для дешифрования выясняется, что

6677 ≡ 19 mod 119.