🔐 Криптографія · Теорія чисел
📅 Березень 2026⏱ 12 хв читання🔴 Просунутий · Останнє оновлення: 23 червня 2026 р.

RSA: математика великих простих чисел

Щоразу, коли ваш браузер показує замочок, найімовірніше задіяно RSA. Опублікований 1977 року Рівестом, Шаміром і Адлеманом, RSA став першою практичною криптосистемою з відкритим ключем. Його безпека зводиться до простого питання: маючи n = p × q для двох величезних простих чисел, наскільки важко знайти p і q?

Автор: Команда MySimulator · Редакційна перевірка: Редакція MySimulator

1. Ідея відкритого ключа

До RSA безпечний зв'язок потребував заздалегідь узгодженого секретного ключа — фізичної зустрічі для обміну кодовою книгою. Криптографія з відкритим ключем усуває це: кожен може опублікувати відкритий ключ E. Будь-хто використовує E, щоб «замкнути» повідомлення. Лише власник відповідного приватного ключа D може його «відімкнути». Замок односторонній: легко застосувати, обчислювально неможливо обернути.

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

2. Модульна арифметика

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

a mod n = остача від a ÷ n
Приклади: 17 mod 5 = 2,   100 mod 7 = 2

Властивості: (a × b) mod n = ((a mod n) × (b mod n)) mod n
Це означає: модульне піднесення до степеня можна виконати ефективно через повторне піднесення до квадрата

Модульний обернений елемент: для цілого e його обернений d задовольняє e × d ≡ 1 (mod φ(n)). Знаходження d виконується за допомогою розширеного алгоритму Евкліда за O(log²n) — швидко.

3. Теорема Ейлера

Серце RSA — теорема Ейлера: для будь-якого цілого m, взаємно простого з n:

m^φ(n) ≡ 1 (mod n)

Де φ(n) — функція Ейлера, кількість цілих чисел від 1 до n, взаємно простих з n. Для n = p × q (двох різних простих чисел):

φ(p × q) = (p − 1)(q − 1)

Це ключове розуміння: щоб обчислити φ(n), потрібно знати прості множники n. Якщо зловмисник не може розкласти n на множники, він не може обчислити φ(n), а отже, не може знайти приватний ключ d з відкритого ключа e.

4. Генерація ключів RSA

Оберіть два великі різні прості числа p і q (2048-бітний RSA: кожне просте число має ~617 десяткових цифр). Використовуйте ймовірнісні тести простоти (Міллера-Рабіна).
Обчисліть n = p × q та φ(n) = (p−1)(q−1). Модуль n є відкритим; φ(n) тримають у секреті.
Оберіть e — відкритий показник, взаємно простий з φ(n). Зазвичай e = 65537 (= 2¹⁶ + 1). Це значення дає ефективне піднесення до степеня та є відомо безпечним.
Обчисліть d = e⁻¹ mod φ(n) за допомогою розширеного алгоритму Евкліда. Це приватний ключ.
Відкритий ключ: (n, e). Поширюйте вільно. Приватний ключ: (n, d). Тримайте в секреті. Знищте p, q, φ(n).

5. Шифрування та дешифрування

Щоб зашифрувати відкритий текст m (де m < n) відкритим ключем (n, e):

c = m^e mod n   (шифротекст)

Щоб дешифрувати шифротекст c приватним ключем (n, d):

m = c^d mod n = (m^e)^d mod n = m^(ed) mod n

Оскільки ed ≡ 1 (mod φ(n)), маємо ed = kφ(n) + 1 для деякого цілого k.
За теоремою Ейлера: m^(ed) ≡ m^1 ≡ m (mod n) ✓
Навчальний приклад: p=61, q=53, n=3233, φ(n)=3120, e=17, d=2753.
Шифруємо m=65: c = 65¹⁷ mod 3233 = 2790.
Дешифруємо: 2790²⁷⁵³ mod 3233 = 65.   ✓

6. Чому це безпечно

Безпека RSA залежить від задачі розкладання цілого числа на множники та задачі RSA (відновлення m з c без d). Наразі для жодної з них не відомо класичного алгоритму з поліноміальним часом.

Найкраща відома атака: загальне решето числового поля (GNFS). Для 2048-бітного ключа RSA (617-цифровий модуль) оцінений час на найшвидшому у світі комп'ютері становить ~10¹⁸ років — набагато довше за вік Всесвіту.

Квантові комп'ютери: алгоритм Шора виконується за поліноміальний час на квантовому комп'ютері і зламав би RSA. Квантовий комп'ютер з ~4000+ логічними кубітами (мільйони фізичних кубітів) міг би зламати RSA-2048. Сучасні квантові комп'ютери мають ~1000 зашумлених фізичних кубітів. Постквантові криптографічні стандарти (NIST 2024: ML-KEM, ML-DSA на основі задач ґраток) уже впроваджуються як підготовка.

Практичний RSA потребує схем доповнення (OAEP), щоб запобігти відомим атакам. Підручниковий RSA (як показано тут) детермінований і вразливий до атак з обраним відкритим текстом — ніколи не використовуйте його в продакшні.

7. Сучасний RSA та альтернативи

RSA-2048 — поточний стандарт для обміну ключами (наприклад, ключі сертифікатів TLS). RSA-4096 забезпечує запас безпеки на 30+ років. Розміри ключів менше за 2048 вважаються застарілими.

Криптографія на еліптичних кривих (ECC) забезпечує еквівалентну безпеку з набагато коротшими ключами: ECC-256 ≈ RSA-3072 за безпекою, з швидшими обчисленнями. TLS 1.3 надає перевагу ECDH (Діффі-Геллман на еліптичних кривих) для обміну ключами.