обчислює DB(EB(P))= Р. Більше ніхто не може прочитати це зашифроване повідомлення ЕВ(Р), оскільки передбачається, що система шифрування достатньо надійна, а одержати ключ Dв на підставі відомого ключа Ев дуже важко. Посилаючи відповідь, Боб передає ЕA(R). Таким чином, Аліса і Боб одержують надійний секретний канал зв'язку.
Зверніть увагу на використовувану тут термінологію. Шифрування з відкритим ключем припускає у кожного користувача наявність двох ключів —відкритого ключа, і закритого ключа, потрібного користувачу для дешифрації повідомлень, що приходять до нього. Ми будемо і далі називати ці ключі відкритим і закритим, щоб відрізняти їх від секретних ключів, використовуваних для шифрування і дешифрації в звичайній криптографії з симетричним ключем.
Питання 7
Алгоритм RSA
Єдина заковика полягає в тому, щоб знайти алгоритми, що задовольняють всім трьом вимогам. Оскільки переваги шифрування з відкритим ключем очевидні, багато дослідників невпинно працювали над створенням подібних алгоритмів, і деякі з них вже опубліковані. Один хороший метод був розроблений групою дослідників Массачусетського технологічного інституту (Rivest і ін., 1978). Він названий по початкових буквах прізвищ трьох розробників: RSA (Rivest, Shamir, Adleman). Цей метод ось вже чверть століття витримує спроби злому і вважається дуже міцним. На його основі побудовані багато практичних систем безпеки. Головний недолік RSA полягає в тому, що для забезпечення достатнього рівня захищеності потрібен ключ завдовжки, принаймні, 1024 біта (проти 128 біт в алгоритмах з симетричними ключами). Через це алгоритм працює досить поволі.
У основі методу RSA лежать деякі принципи теорії чисел. Опишемо у загальних рисах, як користуватися цим методом. Подробиці див. у відповідних джерелах.
Виберемо два великі прості числа р і q (звичайно завдовжки 1024 біта).
Злічимо n=pq і z = (р - 1)(q - 1).
Виберемо число d, що є взаємно простим з числом z.
Знайдемо таке число е, що залишок від ділення твору ed на число z рівний 1.
Обчисливши наперед ці параметри, можна починати шифрування. Спочатку розіб'ємо весь відкритий текст (що розглядається як бітовий рядок) на блоки так, щоб кожне повідомлення Р потрапляло в інтервал 0 < Р < n. Це нескладно зробити, якщо розбити відкритий текст на блоки по до біт, де до — максимальне ціле число, для якого 2k < n.
Щоб зашифрувати повідомлення Р, обчислимо З = Pe (mod n). Щоб розшифрувати З, злічимо Р= Сd (mod n). Можна довести, що для всіх значень Р у вказаному діапазоні функції шифрування і дешифрації є взаємно зворотними. Щоб виконати шифрування, потрібні е і n. Для дешифрації потрібно d і n. Таким чином, відкритий ключ складається з пари (е, n), а закритий ключ — з пари (d, n).
Надійність методу забезпечується складністю знаходження множників великих чисел. Якби криптоаналітик міг розкласти на множники (відкрите) число n, він міг би тоді знайти значення р і q, а отже, і число z. Після цього числа e і d можна знайти за допомогою алгоритму Евкліда. На щастя, математики намагалися вирішити проблему розкладання на множники великих чисел щонайменше 300 років, і накопичений досвід дозволяє припустити, що ця проблема надзвичайно важка.
Рівест (Rivest) з колегами стверджує, що для розкладання на множники числа з 500 цифр необхідне 1025лет, якщо застосовувати грубу силу. Передбачається, що задіяні кращий відомий алгоритм і комп'ютер, що виконує одну інструкцію за 1 мкс. Навіть при збереженні експоненціального зростання швидкостей комп'ютерів буде потрібно століття, щоб знайти множники числа з 500 цифр, а до цього часу наші нащадки можуть просто вибрати ще більші р і q.
Тривіальний учбовий приклад роботи алгоритму RSA приведений на мал. 8.14. Для цього прикладу ми вибрали р = 3, а q = 11, що дає значення n = 33, а z = 20. Число d можна вибрати рівним 7, оскільки числа 20 і 7 не мають загальних дільників. При такому виборі значення е можна знайти, вирішивши рівняння 7е = 1 (mod 20), звідки витікає, що е = 3. Зашифрований текст З виходить з відкритого повідомлення Р по формулі З = Р3 (mod 33). Одержувач розшифровує повідомлення по формулі Р= С7 (mod 33). Як приклад на малюнку показано шифрування слова «SUZANNE».
Оскільки вибрані для даного прикладу прості числа такі малі, Р повинне бути менше 33, тому кожен блок відкритого тексту може містити лише одну букву. В результаті виходить моно алфавітний підстановлювальний шифр, що не дуже вражає. Якби ми натомість вибрали числа р і q близько 2512, тоді число n було б близько 21024. В цьому випадку кожен блок міг би містити до 1024 біт, або 128 восьми розрядних символів, проти 8 символів шифру DES або 16 AES.
Слід зазначити, що використання алгоритму RSA в описаному раніше вигляді аналогічно використанню симетричного алгоритму в режимі ЕСВ (Electronic Code Book — електронний шифроблокнот), в якому однакові блоки на вході перетворяться в однакові блоки на виході. Таким чином, для шифрування даних потрібне зчеплення блоків в якому-небудь вигляді. Проте на практиці алгоритм RSA з відкритим ключем використовується тільки для передачі одноразового секретного ключа, після чого застосовується який-небудь алгоритм з симетричним ключем типу AES або потрійного DES. Система RSA дуже повільна, щоб шифрувати великі об'єми даних, проте вона широко застосовується для розповсюдження ключів.