На даний момент асиметричне шифрування на основі відкритого ключа RSA (розшифровується, як Rivest, Shamir and Aldeman - творці алгоритму) використовує більшість продуктів на ринку інформаційної безпеки.
Його криптостойкость грунтується на складності розкладання на множники великих чисел, а саме - на виняткової складності завдання визначити секретний ключ на підставі відкритого, так як для цього буде потрібно вирішити задачу про існування дільників цілого числа. Найбільш криптостійкі системи використовують 1024-бітові і великі числа.
Розглянемо алгоритм RSA з практичної точки зору.
Для початку необхідно згенерувати відкритий і секретні ключі:- Візьмемо два великих простих числа p and q.
- Визначимо n, як результат множення p on q (n = p * q).
- Виберемо випадкове число, яке назвемо d. Це число повинне бути взаємно простим (не мати жодного спільного дільника, крім 1) з результатом множення (p-1) * (q-1).
- Визначимо таке число е, для якого є істинним наступне співвідношення (e * d) mod ((p-1) * (q-1)) = 1.
- Hазовем відкритим ключем числа e і n, а секретним - d і n.
- розбити шіфруемий текст на блоки, кожен з яких може бути представлений у вигляді числа M (i) = 0,1,2. n-1 (тобто тільки до n-1).
- зашифрувати текст, що розглядається як послідовність чисел M (i) за формулою C (i) = (M (I) ^ e) mod n.
Щоб розшифрувати ці дані, використовуючи секретний ключ, необхідно виконати наступні обчислення: M (i) = (C (i) ^ d) mod n. В результаті буде отримано безліч чисел M (i), які представляють собою вихідний текст.
Наступний приклад наочно демонструє алгоритм шифрування RSA:
Зашифруємо і розшифруємо повідомлення "САВ" за алгоритмом RSA. Для простоти візьмемо невеликі числа - це скоротить наші розрахунки.- Виберемо p = 3 and q = 11.
- Визначимо n = 3 * 11 = 33.
- Hайди (p-1) * (q-1) = 20. Отже, d дорівнюватиме, наприклад, 3: (d = 3).
- Виберемо число е за такою формулою: (e * 3) mod 20 = 1. Значить е дорівнюватиме, наприклад, 7: (e = 7).
- Уявімо шіфруемого повідомлення як послідовність чисел у диапозоне від 0 до 32 (не забувайте, що закінчується на n-1). Буква А = 1, В = 2, С = 3.
Тепер зашіфруем повідомлення, використовуючи відкритий ключ
C1 = (3 ^ 7) mod 33 = 2187 mod 33 = 9;
C2 = (1 ^ 7) mod 33 = 1 mod 33 = 1;
C3 = (2 ^ 7) mod 33 = 128 mod 33 = 29;
Тепер розшифруємо дані, використовуючи закритий ключ.
M1 = (9 ^ 3) mod 33 = 729 mod 33 = 3 (С);
M2 = (1 ^ 3) mod 33 = 1 mod 33 = 1 (А);
M3 = (29 ^ 3) mod 33 = 24389 mod 33 = 2 (В);