RSA

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

RSA — криптографічна система з відкритим ключем.

Shifrovannyi-tonnel-dlya-obsheniya-cherez-VK-(RSA--GreaseMonkey)-2-ukr.jpg

RSA став першим алгоритмом такого типу, придатним і для шифрування і для цифрового підпису. Алгоритм використовується у великій кількості криптографічних застосунків.

Історія[ред.ред. код]

Опис RSA було опубліковано у 1977 році Рональдом Райвестом, Аді Шаміром і Леонардом Адлеманом з Масачусетського Технологічного Інституту (MIT).

Британський математик Кліфорд Кокс[en] (англ. Clifford Cocks), що працював в центрі урядового зв'язку (GCHQ) Великобританії, описав аналогічну систему в 1973 році у внутрішніх документах центру, але ця робота не була розкрита до 1997 року, тож Райвест, Шамір і Адлеман розробили RSA незалежно від роботи Кокса.

В 1983 році був виданий патент 4405829 США, термін дії якого минув 21 вересня 2000 року.

Опис алгоритму[ред.ред. код]

Безпека алгоритму RSA побудована на принципі складності факторизації цілих чисел. Алгоритм використовує два ключі — відкритий (public) і секретний (private), разом відкритий і відповідний йому секретний ключі утворюють пари ключів (keypair). Відкритий ключ не потрібно зберігати в таємниці, він використовується для шифрування даних. Якщо повідомлення було зашифровано відкритим ключем, то розшифрувати його можна тільки відповідним секретним ключем.

Генерування ключів[ред.ред. код]

Для того, щоб згенерувати пари ключів виконуються такі дії:

  1. вибираються два великі прості числа і приблизно 512 біт завдовжки кожне
  2. обчислюється їх добуток
  3. обчислюється функція Ейлера
  4. вибирається ціле таке, що та взаємно просте з
  5. за допомогою розширеного алгоритму Евкліда знаходиться число таке, що

Число називається модулем, а числа і  — відкритою й секретною експонентами (англ. encryption and decryption exponents), відповідно. Пари чисел є відкритою частиною ключа, а  — секретною. Числа і після генерації пари ключів можуть бути знищені, але в жодному разі не повинні бути розкриті.

Шифрування й розшифрування[ред.ред. код]

Для того, щоб зашифрувати повідомлення обчислюється

.

Число використовується в якості шифротексту. Для розшифрування потрібно обчислити

.

Неважко переконатися, що при розшифруванні ми відновимо вихідне повідомлення:

З умови

випливає, що

для деякого цілого , отже

Згідно з теоремою Ейлера:

,

тому

RSA припущення — RSA є односторонньою перестановкою, тобто для будь-якого дієвого алгоритму A ймовірність

дуже мала, що означає неможливість обернення RSA без секретної інформації — .

Наведений вище варіант шифрування називається підручник RSA (англ. textbook RSA) і є цілком уразливим[1]. В жодному разі його не можна використовувати в криптосистемах.

Цифровий підпис[ред.ред. код]

RSA може використовуватися не тільки для шифрування, але й для цифрового підпису. Підпис повідомлення обчислюється з використанням секретного ключа за формулою:

Для перевірки правильності підпису потрібно переконатися, що виконується рівність

Способи зламу системи RSA[ред.ред. код]

Існує кілька способів злому RSA.

  • Найбільш ефективна атака: знайти секретний (private) ключ, відповідний необхідному відкритому (public) ключу. Це дозволить нападнику читати всі повідомлення, зашифровані відкритим (public) ключем і підробляти підписи. Таку атаку можна провести, знайшовши головні співмножники (фактори) загального модуля n – p і q. На підставі p, q і e (загальний показник), нападник може легко обчислити приватний показник d. Основна складність — пошук головних співмножників (факторинг) n; безпека RSA залежить від розкладання на множники (факторингу), що є складнорозв'язним завданням, не має ефективних способів вирішення. Фактично, завдання відновлення секретного (private) ключа еквівалентна задачі розкладання на множники (факторингу) модуля: можна використовувати d для пошуку співмножників n, і навпаки можна використовувати n для пошуку d. Треба зазначити, що удосконалення обчислювального обладнання само по собі не зменшить стійкість криптосистеми RSA, якщо ключі будуть мати достатню довжину. Фактично ж вдосконалення устаткування збільшує стійкість криптосистеми.
  • Інший спосіб зламати RSA полягає в тому, щоб знайти метод обчислення кореня ступеня з e mod n. Оскільки З = M**e*(mod n), то коренем ступеня e (mod n) є повідомлення M. Обчисливши корінь, можна розкрити зашифровані повідомлення і підробляти підписи, навіть не знаючи приватний (private) ключ. Така атака не еквівалентна факторингу, але в даний час невідомі методи, які дозволяють зламати RSA таким чином. Проте, в особливих випадках, коли на основі одного і того ж показника відносно невеликої величини шифрується досить багато пов'язаних повідомлень, є можливість розкрити повідомлення. Згадані атаки — єдині способи розшифрувати всі повідомлення, зашифровані цим ключем RSA.

Існують і інші типи атак, що дозволяють, однак, розкрити тільки одне повідомлення і не дозволяють нападнику розкрити інші повідомлення, зашифровані тим же ключем.

  • Найпростіший напад на єдине повідомлення — атака по передбачуваному відкритому тексту. Нападник, маючи зашифрований текст, передбачає, що повідомлення містить якийсь певний текст, наприклад, «Напад на світанку», потім шифрує передбачуваний текст відкритими (public) ключем одержувача і порівнює отриманий текст з наявним зашифрованим текстом. Таку атаку можна запобігти, додавши в кінці повідомлення кілька випадкових бітів. Інша атака єдиного сполучення застосовується в тому разі, якщо хтось посилає одне і те ж повідомлення M трьом кореспондентам, кожен з яких використовує загальний показник e = 3. Знаючи це, форвард може перехопити ці повідомлення і розшифрувати повідомлення M.Таку атаку можна запобігти вводячи в повідомлення перед кожним шифруванням кілька випадкових біт. Також існують декілька атак за зашифрованим текстом (або атаки окремих повідомлень з метою підробки підпису), при яких нападник створює деякий зашифрований текст і отримує відповідний відкритий текст, наприклад, змушуючи обманним шляхом зареєстрованого користувача розшифрувати підроблене повідомлення. Зрозуміло, існують і атаки націлені не на криптосистему безпосередньо, а на вразливі місця всієї системи комунікацій в цілому; такі атаки не можуть розглядатися як злом RSA, так як говорять не про слабкість алгоритму RSA, а швидше про уразливості його конкретної реалізації.

Наприклад, нападник може заволодіти секретним (private) ключем, якщо той зберігається без належних обережностей. Необхідно підкреслити, що для повного захисту недостатньо захистити виконання алгоритму RSA і вжити заходів обчислювальної безпеки, тобто використовувати ключ достатньої довжини. На практиці ж найбільший успіх мають атаки на незахищені етапи управління ключами системи RSA.

Швидкість роботи алгоритму RSA[ред.ред. код]

Як при шифруванні і розшифруванні, так і при створенні і перевірці підпису, алгоритм RSA у своїй сутності складається з піднесення в степінь, яке виконується як ряд множень.

У практичних додатках для відкритого ключа зазвичай обирається відносно невеликий показник, а часто групи користувачів використовують один і той же відкритий показник, але кожен з різним модулем. Якщо відкритий показник незмінний, вводяться деякі обмеження на головні співмножники (фактори) модуля. При цьому шифрування даних йде швидше, ніж розшифровка, а перевірка підпису — швидше ніж підписання.

Якщо k — кількість бітів у модулі, то зазвичай в алгоритмах, що використовуються для RSA, кількість кроків, необхідна для виконання операції з відкритим ключем, пропорційна другій степені k, кількість кроків для операцій секретного ключа — третій степені k, кількість кроків для операції створення ключів — четвертій степені k.

Методи «швидкого множення» — наприклад, методи основані на швидкому перетворенні Фур'є — виконуються меншою кількістю кроків. Проте вони не набули широкого поширення через складність програмного забезпечення, а також тому, що з типовими розмірами ключів вони фактично працюють повільніше. Однак продуктивність та ефективність програм і обладнання, які реалізовують алгоритм RSA, швидко збільшується.

Алгоритм RSA набагато повільніший, ніж DES та інші алгоритми блокового шифрування. Програмна реалізація DES працює швидше принаймні в 100 разів і від 1,000 до 10,000 — в апаратній реалізації (в залежності від конкретного пристрою). Завдяки проведенню розробок, швидкість алгоритму RSA, ймовірно, прискориться, але одночасно прискориться і робота алгоритмів блокового шифрування.

Деякі особливості алгоритму[ред.ред. код]

Генерація простих чисел[ред.ред. код]

Для знаходження двох великих простих чисел і , при генерації ключа, звичайно використовуються ймовірносні тести чисел на простоту, які дозволяють швидко виявити й відкинути складені числа.

Для генерації і необхідно використовувати криптографічно надійний генератор випадкових чисел. У порушника не має бути можливості одержати будь-яку інформацію про значення цих чисел.

і не повинні бути занадто близькими одне до одного, інакше можна буде знайти їх використовуючи метод факторизації Ферма. Крім того, необхідно вибирати «сильні» прості числа, щоб не можна було скористатися p-1 алгоритмом Поларда.

Доповнення повідомлень[ред.ред. код]

При практичному використанні необхідно деяким чином доповнювати повідомлення. Відсутність доповнень може призвести до деяких проблем:

  • значення і дадуть при зашифруванні шифртексти 0 і 1 при будь-яких значеннях і .
  • при малому значенні відкритого показника (, наприклад) можлива ситуація, коли виявиться, що . Тоді , і зловмисник легко зможе відновити вихідне повідомлення обчисливши корінь ступеня з .
  • оскільки RSA є детермінованим алгоритмом, тобто не використовує випадкових значень у процесі роботи, то зловмисник може використати атаку з обраним відкритим текстом.

Для розв'язання цих проблем повідомлення доповнюються перед кожним зашифруванням деяким випадковим значенням. Доповнення виконується таким чином, щоб гарантувати, що , і . Крім того, оскільки повідомлення доповнюється випадковими даними, то зашифровуючи той самий відкритий текст ми щораз будемо одержувати інше значення шифртексту, що робить атаку з обраним відкритим текстом неможливою.

Вибір значення відкритого показника[ред.ред. код]

RSA працює значно повільніше симетричних алгоритмів. Для підвищення швидкості шифрування відкритий показник вибирається невеликим, звичайно 3, 17 або 65537 (2 обрати не можна, бо повинно бути взаємно простим із ). Ці числа у двійковому вигляді містять тільки по дві одиниці, що зменшує число необхідних операцій множення при піднесенні до степеня. Наприклад, для піднесення числа до степеня 17 потрібно виконати тільки 5 операцій множення:

Вибір малого значення відкритого показника може призвести до розкриття повідомлення, якщо воно відправляється відразу декільком одержувачам, але ця проблема вирішується за рахунок доповнення повідомлень.

Вибір значення секретного показника[ред.ред. код]

Значення секретного показника повинне бути досить великим. У 1990 році Міхаель Вінер (Michael J. Wiener) показав, що якщо і , то є ефективний спосіб обчислити по і . Однак, якщо значення вибирається невеликим, то виявляється досить великим і проблеми не виникає.

Довжина ключа[ред.ред. код]

Число n повинне мати розмір не менше 512 біт. На 2007 рік система шифрування на основі RSA вважалась надійною, починаючи з величини N в 1024 біта.

Застосування RSA[ред.ред. код]

Система RSA використовується для захисту програмного забезпечення й у схемах цифрового підпису. Також вона використовується у відкритій системі шифрування PGP.

Через низьку швидкість шифрування (близько 30 кбіт/сек при 512 бітному ключі на процесорі 2 ГГц), повідомлення звичайно шифрують за допомогою продуктивніших симетричних алгоритмів з випадковим ключем (сеансовий ключ), а за допомогою RSA шифрують лише цей ключ.

На практиці криптосистема RSA часто використовується разом з криптографічного системою секретного ключа типу DES для шифрування повідомлення ключем RSA за допомогою цифрового конверта.

Припустимо, що Аліса посилає зашифроване повідомлення Бобу. Спочатку вона шифрує повідомлення за алгоритмом DES, використовуючи випадково вибраний ключ DES і потім шифрує ключ DES відкритими (public) ключем RSA Боба. Повідомлення зашифроване ключем DES і ключ DES зашифрований у свою чергу ключем RSA разом формують цифровий конверт RSA і надсилаються Бобу. Отримавши цифровий конверт, Боб розшифровує ключ DES за допомогою свого секретного (private) ключа, а потім використовує ключ DES, щоб розшифрувати саме повідомлення.

На практиці така схема реалізована в обладнанні Zaxus (Racal), що здійснює обмін шифрованою інформацією відкритими каналами. При початку нової сесії два пристрої Zaxus (Racal) DataCryptor 2000 спочатку обмінюються ключами DES для цієї сесії, шифруючи їх за алгоритмом RSA, а потім шифрують передану інформацію ключами DES. Такий метод дозволяє об'єднати переваги високої швидкості алгоритму DES із надійністю системи RSA.

Використання криптосистеми RSA зараз

Криптосистема RSA використовується у різних продуктах, на різних платформах і у багатьох галузях. В даний час криптосистема RSA вбудовується в комерційні продукти, число яких постійно збільшується. Також її використовують операційні системи Microsoft, Apple, Sun і Novell. В апаратному виконанні RSA алгоритм застосовується в захищених телефонах, на мережних платах Ethernet, на смарт-картах, широко використовується в криптографічному обладнанні Zaxus (Racal). Крім того, алгоритм входить в склад всіх основних протоколів для захищених комунікацій Internet, в тому числі S/MIME, SSL, S/WAN, а також використовується в багатьох установах, наприклад, в урядових службах, у більшості корпорацій, в державних лабораторіях і університетах. На осінь 2000 року технології з застосуванням алгоритму RSA були ліцензовані більш ніж 700 компаніями.

Технологію шифрування RSA BSAFE використовують близько 500 мільйонів користувачів з усього світу. Так як в більшості випадків при цьому використовується алгоритм RSA, то його можна вважати найбільш поширеною криптосистемой загальних (public) ключа в світі і ця кількість має явну тенденцію до збільшення по мірі зростання Internet.

Примітки[ред.ред. код]

Література[ред.ред. код]

  • Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. — CRC Press, 1996. — 794 p. (pdf)
  • Брассар Ж. Современная криптология = Modern Cryptology: A Tutorial. — М. : Полимед, 1999. — 176 с.
  • Земор Ж. Курс криптографии = Cours de cryptographie. — Ижевск : РХД, 2006. — 256 с.
  • Коутинхо С. Введение в теорию чисел. Алгоритм RSA = The Mathematics of Ciphers: Number Theory and RSA Cryptography. — М. : Постмаркет, 2001. — 328 с.
  • ван Тилборг Х. К. А. Основы криптологии = Fundamentals of Cryptology. — М. : Мир, 2006. — 472 с.
  • Ян С. Криптоанализ RSA = Cryptanalytic Attacks on RSA. — Ижевск : РХД, 2011. — 312 с.
  • Ященко В. В. Введение в криптографию. — М. : МЦНМО, 2012. — 348 с. (pdf)