RSA (шифрування RSA) — один із перших і найпоширеніших алгоритмів з відкритим ключем, названий на честь Рона Рівеста, Аді Шаміра та Леонарда Адлемана; застосовується для шифрування й цифрового підпису.
Як працює RSA
RSA опублікували в MIT у 1977 році. Його стійкість ґрунтується на складності розкладання дуже великого числа на два прості множники:
- Власник ключа обирає два великі випадкові прості числа й перемножує їх; добуток (модуль) стає частиною відкритого ключа.
- Під час шифрування повідомлення підноситься до степеня відкритої експоненти за цим модулем; обернути операцію може лише той, хто знає прості множники й може обчислити закриту експоненту.
- Підписування працює навпаки: закритий ключ створює цифровий підпис, який будь-хто може перевірити відкритим ключем.
На практиці RSA шифрує лише невеликі значення, наприклад сеансові ключі, і завжди використовується зі схемами доповнення: OAEP для шифрування та PSS для підписів.
Чому RSA важливий
Як ключовий алгоритм криптографії з відкритим ключем, RSA підписує більшість TLS-сертифікатів, сертифікати підписування коду й оновлення ПЗ, а також захищає SSH-ключі та шифрування пошти. Його слабкості добре вивчені:
- Короткі ключі — 829-бітне число RSA-250 розклали у 2020 році; 1024-бітні ключі вважаються застарілими, рекомендовано щонайменше 2048 біт.
- Оракули доповнення — атака Бляйхенбахера 1998 року на доповнення PKCS #1 v1.5 повернулася у 2017 році як вразливість ROBOT у багатьох TLS-серверах.
- Слабка генерація ключів — вразливість ROCA (2017) у бібліотеці Infineon дозволяла факторизувати ключі смарт-карток, зокрема естонських ID-карток.
У TLS 1.3 передавання ключів через RSA повністю прибрали на користь ефемерного протоколу Діффі — Геллмана, що забезпечує пряму секретність.
RSA і квантові обчислення
Алгоритм Шора на досить потужному квантовому комп’ютері зможе ефективно факторизувати модулі RSA. Тому NIST запропонував визнати RSA та інші класичні алгоритми з відкритим ключем застарілими до 2030 року й заборонити їх після 2035 року, перейшовши на постквантову криптографію. Організаціям варто вже зараз з’ясувати, де використовується RSA, і спланувати міграцію.
