Алгоритм RSA (за першими літерами прізвищ його творців Rivest-Shamir-Adleman) заснований на властивостях простих чисел (причому дуже великих). Простими називаються такі числа, які не мають дільників, крім самих себе і одиниці.
А взаємно простими називаються числа, що не мають спільних дільників, крім 1.
Для початку виберемо два дуже великих простих числа (великі вихідні числа потрібні для побудови великих криптостійкі ключів. Наприклад, Unix-програма ssh-keygen за замовчуванням генерує ключі довжиною 1024 біта). Визначимо параметр n як результат перемноження р і q. Виберемо велике випадкове число і назвемо його d, причому воно повинно бути взаємно простим з результатом множення (р -1) * (q -1). Відшукаємо таке число e, для якого правильне співвідношення
(E * d) mod ((р -1) * (q -1)) = 1
(Mod - залишок від ділення, тобто якщо e, помножене на d, поділити на ((р -1) * (q -1)), то у залишку отримаємо 1).
Відкритим ключем є пара чисел e і n, а закритим - d і n. При шифруванні вихідний текст розглядається як числовий ряд, і над кожним його числом ми здійснюємо операцію
C (i) = (M (i) e) mod n.
У результаті виходить послідовність C (i), яка і складе криптотекст. Декодування інформації відбувається за формулою
M (i) = (C (i) d) mod n.
Як бачите, розшифровка передбачає знання секретного ключа.
Давайте спробуємо на маленьких числах. Встановимо р = 3, q = 7. Тоді n = р * q = 21. Вибираємо d як 5. З формули (e * 5) mod 12 = 1 обчислюємо e = 17. Відкритий ключ 17, 21, секретний - 5, 21.
Зашифруємо послідовність «2345»:
C (2) = лютого 1917 mod 21 = 11
C (3) = 17 Березня mod 21 = 12
C (4) = 17 Квітня mod 21 = 16
C (5) = 17 травня mod 21 = 17
Криптотекст - 12 листопада 1916 17.
Перевіримо розшифровкою:
M (2) = 11 травня mod 21 = 2
M (3) = 12 травня mod 21 = 3
M (4) = 16 травня mod 21 = 4
M (5) = 17 травня mod 21 = 5
Як бачимо, результат збігся.
Для початку виберемо два дуже великих простих числа (великі вихідні числа потрібні для побудови великих криптостійкі ключів. Наприклад, Unix-програма ssh-keygen за замовчуванням генерує ключі довжиною 1024 біта). Визначимо параметр n як результат перемноження р і q. Виберемо велике випадкове число і назвемо його d, причому воно повинно бути взаємно простим з результатом множення (р -1) * (q -1). Відшукаємо таке число e, для якого правильне співвідношення
(E * d) mod ((р -1) * (q -1)) = 1
(Mod - залишок від ділення, тобто якщо e, помножене на d, поділити на ((р -1) * (q -1)), то у залишку отримаємо 1).
Відкритим ключем є пара чисел e і n, а закритим - d і n. При шифруванні вихідний текст розглядається як числовий ряд, і над кожним його числом ми здійснюємо операцію
C (i) = (M (i) e) mod n.
У результаті виходить послідовність C (i), яка і складе криптотекст. Декодування інформації відбувається за формулою
M (i) = (C (i) d) mod n.
Як бачите, розшифровка передбачає знання секретного ключа.
Давайте спробуємо на маленьких числах. Встановимо р = 3, q = 7. Тоді n = р * q = 21. Вибираємо d як 5. З формули (e * 5) mod 12 = 1 обчислюємо e = 17. Відкритий ключ 17, 21, секретний - 5, 21.
Зашифруємо послідовність «2345»:
C (2) = лютого 1917 mod 21 = 11
C (3) = 17 Березня mod 21 = 12
C (4) = 17 Квітня mod 21 = 16
C (5) = 17 травня mod 21 = 17
Криптотекст - 12 листопада 1916 17.
Перевіримо розшифровкою:
M (2) = 11 травня mod 21 = 2
M (3) = 12 травня mod 21 = 3
M (4) = 16 травня mod 21 = 4
M (5) = 17 травня mod 21 = 5
Як бачимо, результат збігся.
Криптосистема RSA широко застосовується в Інтернеті. Коли ви під'єднуйтеся до захищеного сервера по протоколу SSL, встановлюєте на свій ПК сертифікат WebMoney або підключаєтеся до віддаленого сервера з допомогою Oрen SSH або SecureShell, то всі ці програми застосовують шифрування відкритим ключем з використанням ідей алгоритму RSA. Чи справді ця система така надійна?
З моменту свого створення RSA постійно піддавалася атакам типу Brute-force attack (атака методом грубої сили, тобто перебором). У 1978 р. автори алгоритму опублікували статтю, де призвели рядок, зашифровану щойно винайденим ними методом. Першому, хто розшифрує повідомлення, було призначено винагороду в розмірі 100 дол, але для цього було потрібно розкласти на два співмножники 129-значне число. Це був перший конкурс на злом RSA. Завдання вирішили лише через 17 років після публікації статті.
Крипостійкість RSA грунтується на тому припущенні, що так важко, якщо взагалі реально, визначити закритий ключ з відкритого неба. Для цього було потрібно вирішити задачу про існування дільників величезного цілого числа. До цих пір її аналітичними методами ніхто не вирішив, і алгоритм RSA можна зламати лише шляхом повного перебору. Строго кажучи, твердження, що завдання розкладання на множники складна і що злом системи RSA важкий, також не доведено.
Компанія RSA регулярно проводить конкурси на злом власних (і не тільки власних) шифрів. Попередні конкурси виграла організація Distributed, що є Інтернет-спільнотою добровольців.
Учасники Distributed.net завантажують до себе на ПК невелику програму-клієнт, яка приєднується до центрального сервера і отримує шматочок даних для обчислень. Потім усі дані завантажуються на центральний сервер, і клієнт отримує наступний блок вихідної інформації. І так відбувається до тих пір, поки всі комбінації не будуть перебрані. Користувачі, учасники системи, об'єднуються в команди, а на сайті ведеться рейтинг як команд, так і країн. Наприклад, що бере участь в конкурсі по злому RC5-64 (блочний шифр компанії RSA, що використовує ключ довжиною 64 біта) організації Distributed.net вдалося здійснити злом через п'ять років (1757 днів) роботи. За цей час у проекті брали участь 327 856 користувачів і було перебрати 15 268 315 356 922 380 288 варіантів ключа. З'ясувалося, що була (не без гумору) зашифрована фраза «some things are better left unread» («деякі речі краще залишати непрочитані»). Загальні рекомендації по шифру RC5-64 такі: алгоритм досить стійкий для повсякденних потреб, але шифрувати їм дані, що залишаються секретними протягом більш ніж п'яти років, не рекомендується ».
З моменту свого створення RSA постійно піддавалася атакам типу Brute-force attack (атака методом грубої сили, тобто перебором). У 1978 р. автори алгоритму опублікували статтю, де призвели рядок, зашифровану щойно винайденим ними методом. Першому, хто розшифрує повідомлення, було призначено винагороду в розмірі 100 дол, але для цього було потрібно розкласти на два співмножники 129-значне число. Це був перший конкурс на злом RSA. Завдання вирішили лише через 17 років після публікації статті.
Крипостійкість RSA грунтується на тому припущенні, що так важко, якщо взагалі реально, визначити закритий ключ з відкритого неба. Для цього було потрібно вирішити задачу про існування дільників величезного цілого числа. До цих пір її аналітичними методами ніхто не вирішив, і алгоритм RSA можна зламати лише шляхом повного перебору. Строго кажучи, твердження, що завдання розкладання на множники складна і що злом системи RSA важкий, також не доведено.
Компанія RSA регулярно проводить конкурси на злом власних (і не тільки власних) шифрів. Попередні конкурси виграла організація Distributed, що є Інтернет-спільнотою добровольців.
Учасники Distributed.net завантажують до себе на ПК невелику програму-клієнт, яка приєднується до центрального сервера і отримує шматочок даних для обчислень. Потім усі дані завантажуються на центральний сервер, і клієнт отримує наступний блок вихідної інформації. І так відбувається до тих пір, поки всі комбінації не будуть перебрані. Користувачі, учасники системи, об'єднуються в команди, а на сайті ведеться рейтинг як команд, так і країн. Наприклад, що бере участь в конкурсі по злому RC5-64 (блочний шифр компанії RSA, що використовує ключ довжиною 64 біта) організації Distributed.net вдалося здійснити злом через п'ять років (1757 днів) роботи. За цей час у проекті брали участь 327 856 користувачів і було перебрати 15 268 315 356 922 380 288 варіантів ключа. З'ясувалося, що була (не без гумору) зашифрована фраза «some things are better left unread» («деякі речі краще залишати непрочитані»). Загальні рекомендації по шифру RC5-64 такі: алгоритм досить стійкий для повсякденних потреб, але шифрувати їм дані, що залишаються секретними протягом більш ніж п'яти років, не рекомендується ».
Немає коментарів:
Дописати коментар