Алгоритм шифрування даних
з відкритим ключем RSA
Алгоритм шифрування даних з відкритим ключем є найбільш переспективний зараз (RSA - Rivest, Shamir and Aldeman - його винахідники).
Просте число - ділиться тільки на 1 і на саме себе;
Взаємно простим- не мають жодного спільного дільника, крім 1;
Результат операції i mod j - залишок від цілочисельного ділення i на j.
Щоб використовувати алгоритм RSA, треба спочатку згенерувати відкритий і секретні ключі виконавши наступні кроки:
1) Виберемо два дуже великих простих числа p and q.
2) Визначимо n, як результат множення p on q (n = p * q).
3) Виберемо велике випадкове число, яке назвемо d. Це число повинне бути взаємно простим з результатом множення (p-1) * (q-1).
4) Визначимо таке число е, для якого є істинним наступне співвідношення (e * d) mod ((p-1) * (q-1)) = 1.
5) 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), які представляють собою вихідний текст.
Hу, щоб більш наочно уявити алгоритм RSA, наведу такий приклад:
Зашифруємо і розшифруємо повідомлення "САВ" за алгоритмом RSA. Для простоти буду використовувати маленькі числа (на практиці - потрібно брати набагато більші).
1) Виберемо p = 3 and q = 11.
2) Визначимо n = 3 * 11 = 33.
3) Hайди (p-1) * (q-1) = 20. Отже, d дорівнюватиме, наприклад, 3: (d = 3).
4) Виберемо число е за такою формулою: (e * 3) mod 20 = 1. Значить е дорівнюватиме, наприклад, 7: (e = 7).
5) Уявімо шіфруемого повідомлення як послідовність чисел у диапозоне від 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 (В);
Все, дані розшифровані.
Крипостійкість алгоритму RSA грунтується на припущенні, що так важко визначити секретний ключ за відомим, оскільки для цього необхідно вирішити задачу про існування дільників цілого числа. Дане завдання є NP-повною, і, як наслідок цього факту, не допускає cейчас ефективного (поліномінальної) рішення. Більш того, саме питання існування ефективних алгоритмів розв'язання NP-повних задач є до теперішнього часу відкритим. Якщо Ви використовуєте числа, що складаються з 200 цифр (такі і треба використовувати для шифрування даних), для несанкціонованої розшифровки доведеться генерувати величезну кількість операцій (близько 10 ^ 23).
P.S / Дані, наведені вище, не повинні бути використані в незаконних цілях!
[An error occurred while processing this directive]