Шифрування RSA є основою безпечного зв’язку в Інтернеті. Це вид криптографії з відкритим ключем, який захищає електронні листи, цифрові транзакції та конфіденційні дані, що передаються мережами. Алгоритм названо на честь своїх творців: Рональда Л. Рівеста, Аді Шаміра та Леонарда Адлемана. Вони розробили цю систему, працюючи викладачами у Массачусетському технологічному інституті.
Безпека RSA спирається на просту математичну перешкоду, яку легко створити, але майже неможливо звернути назад. Користувач починає з вибору двох великих простих чисел, p та q. Ці числа настільки великі, що множення їх отримання n тривіально, але факторизація n назад на p і q обчислювально неможлива.
Уявіть це так: множення двох величезних чисел займає частку секунди. Спроба з’ясувати, які два числа було перемножено, щоби отримати цей результат? З використанням сучасних технологій це може зайняти мільярди років.
Станом на 2015 рік стандарти безпеки уряду США вимагають, щоб модуль n становив не менше 2048 біт. У десятковій системі це означає, що p і q мають близько 308 цифр кожне, що створює 617-значне число для n*. Найбільші числа, які вдалося успішно розкласти на множники, мають лише половину цього розміру. Складність факторизації приблизно подвоюється з кожними трьома додатковими цифрами в модулі. Це експонентне зростання складності гарантує, що 617-значні ключі залишаються захищеними від атак методом грубої сили протягом десятиліть.
Механіка генерації ключів
Після вибору p та q система генерує відкритий та закритий ключі. Користувач вибирає ціле число e менше n. Це число має бути взаємно простим із твором (p – 1) та (q – 1). Простими словами, e немає спільних множників з цим твором, крім 1.
Цей конкретний вибір забезпечує існування іншого числа d. Коли ви множите e на d і поділяєте найменше загальне кратне (p – 1) і (q – 1), залишок дорівнює 1.
Знайти d легко, якщо ви знаєте p та q. Алгоритм Евкліда обчислює його за мить. Але якщо ви не знаєте p і q, знаходження d з e так само складно, як і факторизація n. Ця складність є основою криптографічної безпеки RSA.
Безпека RSA – це не магія; це математика. Зокрема, це асиметрія між легким множенням та неможливою факторизацією.
Відкриті ключі проти закритих ключів
Мітки d і e описують функції, а чи не суворі ролі. Ключі взаємозамінні. Ця гнучкість дозволяє RSA виконувати дві різні завдання: забезпечення секретності та автентифікацію.
Для створення каналу секретності користувач А публікує e та n у відкритому каталозі. Користувач А зберігає d у секреті. Коли хтось хоче надіслати приватне повідомлення А, він перетворює повідомлення на числа, менші за n, і шифрує його, використовуючи e і n. Тільки А може розшифрувати його, тому що тільки А має * d . Припущення і сильні докази свідчать, що ніхто інший не може розшифрувати повідомлення без факторизації n*.
Аутентифікація працює інакше. Користувач А публікує d та n та зберігає e у секреті. Користувач B хоче переконатися, що він спілкується з А. B відправляє перевірочне повідомлення А. Якщо А повертає зашифровану версію, використовуючи e, B може її розшифрувати за допомогою відкритого d. Якщо розшифроване повідомлення збігається з перевірочним, B знає, що відправник має e. Оскільки А має e, особистість підтверджена.
Цифрові підписи та хешування
Цифровий підпис додає шар складності. Вона потребує криптографічно стійкої хеш-функції. Це публічна функція, яка стискає будь-яке повідомлення у меншу контрольну суму (дайджест). Кожен біт дайджесту залежить від кожного біта вихідного повідомлення. Змініть один біт у вихідному повідомленні, і приблизно половина бітів у дайджесті зміниться.
Криптографічно стійкий хеш робить обчислювально неможливим знаходження повідомлення, що дає конкретну заздалегідь призначену контрольну суму. Він також ускладнює знаходження іншого повідомлення з тією самою контрольною сумою, що й відомого.
Щоб підписати повідомлення, шифрує дайджест своїм секретним e і додає його до повідомлення. Саме повідомлення не обов’язково має бути таємним. Будь-який може використовувати відкритий ключ d А для розшифрування підпису та відновлення дайджесту. Потім вони незалежно вираховують дайджет отриманого повідомлення. Якщо два дайджести збігаються, підпис дійсний. Тільки А міг зашифрувати дайджест, бо тільки А знає e.
Гібридна реальність
За цю безпеку доводиться платити. Асиметричне шифрування вимагає значно більше обчислень, ніж симетричне (з одним ключем) шифрування. Це високе споживання процесорних ресурсів різко знижує пропускну здатність. Протягом приблизно 20 років алгоритми з одним ключем досягали пропускної спроможності в 1000-10 000 разів вище, ніж алгоритми з двома ключами, при порівнянні безпеки.
Оскільки RSA працює повільно, він рідко використовується для прямого шифрування великих обсягів даних. Натомість він живить гібридні системи. RSA бере на себе основну роботу з аутентифікації та цифрових підписів. Він також безпечно обмінюється випадково згенерованим сеансовим ключем. Після того, як цей ключ передано, система перемикається на алгоритм з одним ключем для високошвидкісної передачі фактичних даних. Коли сеанс закінчується, ключ відкидається.
Це поєднання дає нам найкраще з обох світів. Ми отримуємо безпечний обмін ключами за допомогою криптографії з відкритим ключем та швидкість симетричного шифрування для основної частини наших даних.
Математика витримує перевірку. Ключі залишаються у безпеці. Але зі зростанням обчислювальної потужності визначення «великого» числа змінюється. Те, що сьогодні неможливо зламати, завтра може виявитися завданням. Ми продовжуємо створювати більші прості числа. Ми продовжуємо сподіватися, що розрив між легким множенням та складною факторизацією залишається досить широким, щоб захистити наше цифрове життя.
