Міністерство освіти і науки України Національний університет «Львівська політехніка» Звіт до лабораторної роботи №3 з дисципліни: «Математичні методи представлення знань» Тема: Шифрування і дешифрування текстової інформації за допомогою алгоритму RSA Мета: Навчитись шифрування і дешифрування текстової інформації за допомогою алгоритму RSA, вивчити властивості алгоритму RSA Короткі теоретичні відомості Перший алгоритм кодування з відкритим ключем (Public Key Encryption, далі PKE) було запропоновано Вітфілдом Діффі та Мартіном Хелманом у Стендфордському університеті. Вони, а також незалежно від них Ральф Меркл, розробили основні його поняття у 1976 році. Перевага PKE полягає у відсутності потреби секретної передачі ключа. PKE базується на нерозв'язності проблеми розкладу натурального числа на прості множники. RSA схему шифрування було запропоновано у 1978 році та названо іменами трьох його винахідників: Роном Рівестом (Ron Rivest), Аді Шаміром (Adi Shamir) та Леонардом Адлеманом (Leonard Adleman). RSA належить до класу алгоритмів кодування з відкритим ключем. У 80-х роках криптосистема переважно використовувалася для забезпечення секретності та достовірності цифрових даних. У сучасному світі RSA використовується в web - серверах та браузерах для зберігання таємності даних що передаються по мережі. Схема RSA базується на обчисленні виразів зі степенями. Відкритий текст шифрується блоками, довжина кожного із яких менша за деяке число n. Алгоритм генерації ключа A повинен згенерувати відкритий та секретний ключі: 1. Вибрати два великих простих числа p та q; 2. Обчислити n = p * q; 3. Обчислити функцію Ейлера
= (p - 1) * (q - 1); 4. Вибрати натуральне e, таке що 1<e<
, взаємно просте з
; 5. Використовуючи розширений алгоритм Евкліда, розв'язати рівняння d*e =1 (mod
). Тобто знайти d. Відкритий ключ: (n, e). Секретний ключ: d. Числа p і q після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті. Схема шифрування RSA B шифрує повідомлення m та надсилає A. 1. Шифрування. В робить наступні дії: а) отримати відкритий ключ (n, e) від А; б) представити повідомлення у вигляді натурального числа m з проміжку [1..n]; в) обчислити c = me mod n; г) надіслати шифротекст c до А. 2. Дешифрування. Для отримання повідомлення m із шифротексту c А робить наступні дії: а) використовуючи секретний ключ d, обчислити m = cd mod n. Як відправник, так і одержувач повинні знати значення п. Відправник знає значення е, і тільки одержувачеві відоме значення d. Отже, дана схема є алгоритмом шифрування з відкритим ключем KU = {е, п} і особистим ключем KR = {d, n}. Щоб цей алгоритм міг використатися для шифрування з відкритим ключем, повинні бути виконані наступні вимоги. 1. Повинні існувати такі значення е, d і п, що
( m (mod п) для всіх m < п. 2. Повинні відносно легко обчислюватися
і
для всіх значень m < п. 3. Повиннo бути практично неможливо визначити d за наявними е і п. Виконання: Ширування: C=(P+K) mod 33 Повідомлення К О Н Т А К Т  Ключ Р О М А Н Р О  Криптотекст А Ґ Б У О В Ж   Шифруємо слово “Контакт”. Ключове слово “Роман”. Алгоритм RSA Шифрування Вибрати два простих числа q = 11, p = 3 Обчислити їх добуток: n = q = 33 Обчислити функцію Ейлера: (n) = (p - 1)(q - 1) = 20 Вибрати 1 < e <
(n) та взаємно просте з
(n): e = 7 Вибрати таке d, що e∙d ≡ 1 (mod
(n)), та d ≠ e: d = 3 Шифрувати повідомлення “А Ґ БУОВЖ”, для цього перевести його на цифрову форму за своїм алфавітом. Алфавіт: А = 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, Я = 33 Повідомлення: 1 | 5 | 2 | 24 | 19 | 3 | 9 Далі шифрується кожне цифрове значення символу за формулою с = me (mod n) (c – зашифрований символ, (e, n) – відкритий ключ, m – цифрове значення символу): 17 (mod 33) = 1 (mod 33) = 1 57 (mod 33) = 78125 (mod 33) = 14 27 (mod 33) = 128 (mod 33) = 29 247 (mod 33) = 4586471424 (mod 33) = 18 197 (mod 33) = 893871739 (mod 33) = 13 37 (mod 33) = 2187 (mod 33) = 9 97 (mod 33) = 4782969 (mod 33) = 15 1 | 14 | 29 | 18 | 13 | 9 | 15 Відкритий ключ (e, n) = (7, 33) Закритий ключ (d, n) = (3, 33) Дешифрування Для дешифрування використовується закритий ключ, в даному випадку: (d, n) = (3, 33) Далі дешифрується кожен зашифрований символ за формулою m = cd (mod n) (c – зашифрований символ, (d, n) – закритий ключ, m – цифрове значення символу): 13 (mod 33) = 1 (mod 33) = 1 143 (mod 33) = 2744 (mod 33) = 5 293 (mod 33) = 24389 (mod 33) = 2 183 (mod 33) = 5832 (mod 33) = 24 133 (mod 33) = 2197 (mod 33) = 19 93 (mod 33) = 729 (mod 33) = 3 153 (mod 33) = 3375 (mod 33) = 9 Отже дешифроване повідомлення: 1 | 5 | 2 | 24 | 19 | 3 | 9 За алфавітом переводимо цифрові значення символів в символи і отримуємо повідомлення: «А Ґ БУОВЖ» Дешифрування: p=(C-K+33) mod 33 Повідомлення А Ґ Б У О В Ж  Ключ Р О М А Н Р О  Криптотекст К О Н Т А К Т