Rsa-шифрування. Опис і реалізація алгоритму rsa
Відео: Алгоритм шифрування RSA: крок другий
RSA-шифрування є однією з перших практичних криптосистем з відкритим ключем, яка широко використовується для безпечної передачі даних. Її основна відмінність від подібних сервісів в тому, що ключ шифрування є відкритим і відрізняється від ключа дешифрування, який тримається в секреті. В технології RSA ця асиметрія заснована на практичній складності факторингового відтворення двох великих простих чисел (проблема факторингу).
Історія створення
Назва RSA складається з початкових літер прізвищ Ривест, Шамір і Адлеман, - вчених, які вперше публічно описали подібні алгоритми шифрування в 1977 році. Кліффорд Кокс, англійський математик, який працював на спецслужби Великобританії, вперше розробив еквівалентну систему в 1973 році, але вона не була розсекречена до 1997 р
Користувач RSA створює і потім публікує відкритий ключ, заснований на двох великих простих числах разом з допоміжним значенням. Прості числа повинні зберігатися в таємниці. Будь-яка людина може використовувати відкритий ключ для шифрування повідомлення, але якщо він досить великий, то тільки хто-небудь зі знанням простих чисел може декодувати повідомлення. Розкриття RSA шифрування відомо як основна проблема: сьогодні залишається відкритою дискусія про те, наскільки це надійний механізм.
RSA є відносно повільним алгоритмом, у зв`язку з чим він не так широко використовується для безпосереднього шифрування даних користувача. Найчастіше цей метод використовують для передачі в зашифрованому вигляді загальних ключів для симетричного ключа шифрування, який, в свою чергу, може виконувати операції масового шифрування і дешифрування на набагато більш високій швидкості.
Коли з`явилася криптосистема в сучасному вигляді?
Ідея асиметричного ключа криптосистеми приписується Діффі і Хеллману, які опублікували концепцію в 1976 році, представивши цифрові підписи і спробувавши застосувати теорію чисел. Їх формулювання використовує загальний секретний ключ, створений з експоненціаціі деякого числа по модулю простого числа. Проте, вони залишили відкритою проблему реалізації цієї функції, оскільки принципи факторингу були добре вивчені в той час.
Відео: Hackerdom-02-03 Алгоритм RSA
Ривест, Аді Шамір і Адлеман в Массачусетському технологічному інституті зробили кілька спроб протягом року, щоб створити односпрямовану функцію, яку важко розкодувати. Ривест і Шамір (як комп`ютерні вчені) запропонували безліч потенційних функцій, в той час як Адлеманом (як математиком) здійснювався пошук «слабких місць» алгоритму. Вони використовували багато підходів і в кінцевому підсумку в квітні 1977 року розробили остаточно систему, сьогодні відому як RSA.
ЕЦП і відкритий ключ
Електронний цифровий підпис, або ЕЦП, є складовою частиною документів електронного типу. Вона утворюється при певному криптографическом зміні даних. За допомогою цього атрибута можливо провести перевірку цілісності документа, його конфіденційності, а також встановити, хто є його власником. По суті, це альтернатива звичайної стандартної підпису.
Дана криптосистема (RSA-шифрування) пропонує відкритий ключ, чим відрізняється від симетричних. Принцип її функціонування в тому, що застосовують два різних ключі - закритий (зашифрований), а також відкритий. Перший застосовують для того, щоб згенерувати ЕЦП і згодом отримати можливість розшифровки тексту. Другий - для власне шифрування і перевірки ЕЦП.
Використання підпису дозволяє краще зрозуміти шифрування RSA, приклад якого можна привести як звичайний засекречений «закритий від сторонніх очей» документ.
У чому суть алгоритму?
Алгоритм RSA складається з чотирьох етапів: генерації ключів, їх розподілу, шифрування і дешифрування. Як вже було зазначено, RSA-шифрування включає в себе відкритий ключ і закритий ключ. Відкритий може бути відомий всім і використовується для шифрування повідомлень. Суть його полягає в тому, що повідомлення, зашифровані за допомогою відкритого ключа, можуть бути розшифровані тільки в певний проміжок часу з використанням секретного ключа.
З метою безпеки цілі числа повинні бути обрані випадковим чином і бути однаковими за величиною, але при цьому відрізнятися по довжині на декілька цифр, щоб зробити факторинг складніше. Однакові ж числа можуть бути ефективно знайдені за допомогою тесту на їх простоту, тому шифрування інформації повинно обов`язково ускладнюватися.
Відео: Шифрування RSA
Відкритий ключ складається з модуля і публічної експоненти. Закритий складається з модуля і приватного показника, який повинен зберігатися в таємниці.
Шифрування файлів RSA і слабкі місця
Однак існує цілий ряд механізмів по злому простого RSA. При шифруванні з низькими показниками і малими значеннями чисел шифр може бути легко розкритий, якщо підібрати корінь шифротекста над цілими числами.
Оскільки RSA-шифрування є детермінованим алгоритмом (тобто не має випадкової складової), зловмисник може успішно запустити обраний відкритий текст атаки проти криптосистеми шляхом шифрування ймовірних відкритих текстів під відкритим ключем і перевірками на предмет того, чи рівні вони шіфротекста. Криптосистема називається семантично безпечної в тому випадку, якщо зловмисник не зможе відрізнити дві шифровки один від одного, навіть якщо він знає відповідні тексти в розкритому вигляді. Як було описано вище, RSA без доповнення іншими сервісами не є семантично безпечною.
Додаткові алгоритми шифрування і захисту
Щоб уникнути вищезгаданих проблем, при практичній реалізації RSA зазвичай вбудовують деяку форму структурованого, рандомізованого заповнення перед шифруванням. Це гарантує, що зміст не потрапляє в діапазон небезпечних відкритих текстів і що це повідомлення не зможе бути розкрито шляхом випадкового підбору.
Безпека криптосистеми RSA і шифрування інформації засновані на двох математичних задачах: проблеми розкладання на множники великих чисел і власне проблеми RSA. Повне розкриття шифротекста і ЕЦП в RSA вважається неприпустимим на тому припущенні, що обидві ці проблеми неможливо вирішити в сукупності.
Однак завдяки можливості відновлення простих множників, зловмисник може обчислити секретний показник з відкритого ключа, а потім розшифрувати текст за допомогою стандартної процедури. Незважаючи на те що сьогодні жоден існуючий метод для факторизації великих чисел на класичному комп`ютері не знайдено, не було доведено, що він не існує.
Автоматизація
Інструмент, званий Yafu, може бути використаний для оптимізації цього процесу. Автоматизація в YAFU є сучасною функцію, яка поєднуватиме алгоритми факторизації в інтелектуальній і адаптивної методології, яка зводить до мінімуму час, щоб знайти чинники довільних вхідних чисел. Більшість реалізацій алгоритму багатопотокові, що дозволяє Yafu в повній мірі використовувати мульти- або багато багатоядерні процесори (В тому числі SNFS, SIQS і ECM). Перш за все, це керований інструмент командного рядка. Час, витрачений на пошук фактора шифрування з використанням Yafu на звичайному комп`ютері, може бути зменшено до 103.1746 секунд. Інструмент виробляє обробку бінарних файлів ємністю 320 біт або більше. Це дуже складне програмне забезпечення, яке вимагає певної кількості технічних навичок для установки і настройки. Таким чином, RSA-шифрування C може виявитися уразливим.
Спроби злому в новітній час
У 2009 році Бенджамін Муді за допомогою бітового ключа RSA-512 працював над розшифровкою кріптотексте протягом 73 днів, використовуючи тільки загальновідоме програмне забезпечення (GGNFS) і середньостатистичний настільний комп`ютер (двоядерний Athlon64 при 1900 МГц). Як показав цей досвід, треба було трохи менше 5 гігабайт диска і близько 2,5 гігабайт оперативної пам`яті для процесу «просіювання».
Станом на 2010 рік, найбільший факторізовано номер RSA був 768 біт довжиною (232 десяткові цифри, або RSA-768). Його розкриття тривало два роки на кількох сотнях комп`ютерів одночасно.
На практиці ж ключі RSA мають велику довжину - як правило, від 1024 до 4096 біт. Деякі експерти вважають, що 1024-бітові ключі можуть стати ненадійними в найближчому майбутньому або навіть вже можуть бути зламані досить добре фінансованим атакуючим. Однак, мало хто стане стверджувати, що 4096-бітові ключі можуть бути також розкриті в доступному для огляду майбутньому.
перспективи
Тому, як правило, передбачається, що RSA є безпечним, якщо числа досить великі. Якщо ж основне число 300 біт або коротше, шифротекст і ЕЦП може бути розкладений протягом декількох годин на персональному комп`ютері з використанням програмного забезпечення, наявного вже у вільному доступі. Ключі довжиною 512 біт, як було доведено, могли бути розкриті вже в 1999 році з використанням декількох сотень комп`ютерів. У наші дні це можливо протягом декількох тижнів з використанням загальнодоступного апаратного забезпечення. Таким чином, цілком можливо, що в будущембудет легко розкриватися RSA-шифрування на пальцях, і система стане безнадійно застарілою.
Офіційно в 2003 році була поставлена під сумнів безпеку 1024-бітних ключів. В даний час рекомендується мати довжину не менше 2048 біт.
