льні кошти, за малий інтервал часу.
В основу криптографічного системи з відкритим ключем RSA ставиться завдання множення і розкладання складених чисел на прості співмножники, яка є обчислювально односпрямованої завданням.
У криптографічного системі з відкритим ключем у кожного абонента є відкритий ключем (public key) і секретний ключем (secret key). Кожен ключ частину інформації. У криптографічного системі RSA кожен ключ складається з пари цілих чисел. Кожен абонент набирає свій відкритий і секретний ключ самостійно. Секретні ключі секретними, відкриті ключі можна повідомляти. Відкритий і секретний ключі кожного абонента обміну повідомленнями взаємно зворотні.
Алгоритм створення відкритого і секретного ключів
Вибираються два випадкових простих числа p і q заданого розміру (наприклад, 512 бітів кожне).
Обчислюється їх добуток n = pq
Обчислюється значення функції Ейлера від числа n:
В
Вибирається ціле число e, взаємно просте зі значенням функції. e - прості числа, що містять невелику кількість одиничних бітів в двійковій запису. Наприклад, прості числа Ферма 17, 257, 65537. p> Обчислюється число d , мультиплікативно зворотне до числа e по модулю, т. е число, що задовольняє порівнянні:
;
тобто, де k будь натуральне число (0, 1, 2 ...).
Пара G = (e, n) публікується в якості відкритого ключа RSA (RSA public key).
Пара N = (d, n) грає роль секретного ключа RSA (RSA secret key) і тримається в секреті.
Число n називається модулем, а числа e і d - відкритою і секретної експонентами, відповідно.
Припустимо абонент У хоче послати повідомлення абоненту В по комутаційного каналу.
Повідомленням є цілі числа лежать від 0 до n-1,.
Алгоритм шифрування:
Береться відкритий ключ (e, n) сторони A, вставляється відкритий текст L, передається шифрування повідомлення:
В
Алгоритм дешифрування:
Приймається зашифроване повідомлення С, для розшифровки сполучення застосовується секретний ключ (d, n):
В
Цифровий підпис
Система RSA може використовуватися не тільки для шифрування, але і для цифрового підпису.
Припустимо, що абоненту A потрібно відправити абоненту B відповідь L 1 , підтверджений цифровим підписом.
Алгоритм підпису
Взяти відкритий текст L 1 , потім створюємо цифровий підпис wc допомогою секретного ключа (d, n).
В
Далі передаємо (L 1 , w), яка складається з повідомлення і підпису.
Алгоритм перевірки справжності підпису
Прийняти (L 1 , w), беремо відкритий ключ (e, n) абонента А, перевіряємо справжність підпису
підпис вірна
Оскільки цифрова підпис забезпечує як аутентифікацію автора повідомлення, так і підтвердження цілісності вмісту підписаного повідомлення, вона служить аналогом підпису, зробленим від руки наприкінці рукописного документа.
Важлива властивість цифрового підпису полягає в тому, що її може перевірити кожен, хто має доступ до відкритого ключа її автора. Один з учасників обміну повідомленнями після перевірки автентичності цифрового підпису може передати підписане повідомлення ще комусь, хто теж в змозі перевірити цю підпис.
Зауважимо, що підписане повідомлення L 1 не шифрується. Воно пересилається в початковому вигляді і його вміст не захищене. Шляхом спільного застосування представлених вище схем шифрування і цифрового підпису в системі RSA можна створювати повідомлення, які будуть і зашифровані, і містити цифровий підпис. Для цього автор спочатку повинен додати до повідомлення свою цифровий підпис, а потім - зашифрувати вийшла в результаті пару (що складається з самого повідомлення і підписи до нього) за допомогою відкритого ключа належить одержувачу. Одержувач розшифровує отримане повідомлення за допомогою свого секретного ключа. Якщо проводити аналогію з пересилкою звичайних паперових документів, то цей процес схожий на те, як якби автор документа поставив під ним свій друк, а потім поклав його в паперовий конверт і запечатав, з тим щоб конверт був роздрукований лише тією людиною, кому адресоване повідомлення.
RSA
Приклад
Спочатку потрібно згенерувати ключ
Вибираємо два простих ключа p = 13, q = 41
Обчислюємо модуль n = p * q = 13 * 41 = 533
Обчислюємо функцію Ейлера П† (n) = (P-1) * (q-1) = (13-1) * (41-1) = 480
Вибираємо відкритий показник е = 13
Обчислюємо секретний показник d = 37
Відкритий ключ (e, n) = (13, 533)
Секретний ключ (d, n) = (37, 533)
Шифрування
Вибираємо відкритий текст L = 4545
Обчислюємо шифротекст G (L) = L e mod n = 99
Розшифрування
Обчислюємо вихідне повідомлення
N (C) = С d
