 |
|
Теоретическая часть
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
| к расчётно-графической работе | ||
| по | Информационная безопасность | |
| (наименование дисциплине) |
| Группа | Фамилия И.О. | Подпись | Дата | Оценка | ||
| ПИ-302з | ||||||
| Студент | Тихонов Е.В. | __.__.____ | ||||
| Консультант | Абдулнагимов А.И. | __.__.____ | ||||
| Принял | __.__.____ |
Задание №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.