1. Чому криптографія тримається на теорії чисел
Коли ви відкриваєте банківський застосунок або надсилаєте повідомлення в захищеному месенджері, дані на шляху до сервера шифруються. Значна частина сучасної криптографії з відкритим ключем — зокрема алгоритм RSA — спирається не на складні шифри-заміни, а на просту математичну ідею: перемножити два великих прості числа легко, а розкласти отриманий добуток назад на множники — надзвичайно важко, якщо числа достатньо великі (сотні десяткових цифр).
Ця асиметрія «легко в один бік, важко в інший» називається односторонньою функцією і є фундаментом безпеки багатьох криптосистем із відкритим ключем. Якби факторизація великих чисел була легкою задачею, вся сучасна інфраструктура захищеного зв'язку в інтернеті потребувала б перегляду.
Важливо: у реальних системах RSA числа p і q мають по 150–300 і більше десяткових цифр. У цій статті ми навмисно беремо крихітні числа — виключно щоб показати механіку обчислень вручну. Такий «іграшковий» приклад не є криптографічно стійким і в реальному шифруванні ніколи не використовується.
2. Модулярна арифметика — коротко
Модулярна арифметика («арифметика годинника») працює з остачами від ділення. Вираз a mod n означає остачу від ділення a на n: наприклад, 17 mod 5 = 2, бо 17 = 3×5 + 2. У криптографії всі обчислення виконуються за модулем деякого числа n, тому результати завжди залишаються в межах від 0 до n−1, незалежно від того, наскільки великими були проміжні числа.
Дві ключові операції RSA — піднесення до степеня за модулем (модулярне експоненціювання) та знаходження оберненого елемента за модулем — обидві є стандартними інструментами теорії чисел, детальніше про які можна прочитати в довіднику з теорії чисел.
3. Алгоритм RSA крок за кроком (навчальний приклад)
Використаємо класичний навчальний приклад із підручників з криптографії — числа p = 61 і q = 53.
Крок 1. Обираємо два прості числа
Крок 2. Обчислюємо модуль n
Число n стає частиною і публічного, і приватного ключа. У реальній системі саме n потрібно розкласти на p і q, щоб зламати шифр, — і саме це неможливо зробити за розумний час для великих n.
Крок 3. Обчислюємо функцію Ойлера φ(n)
Функція Ойлера φ(n) показує, скільки чисел від 1 до n є взаємно простими з n. Для n = p×q, де p і q — прості, вона обчислюється саме так — простим множенням (p−1)(q−1).
Крок 4. Обираємо відкритий показник e
Число e має задовольняти умову 1 < e < φ(n) та бути взаємно простим із φ(n) (тобто НСД(e, φ(n)) = 1). Традиційно обирають e = 17.
Крок 5. Обчислюємо приватний показник d
d — це число, обернене до e за модулем φ(n): d повинно задовольняти рівняння e × d ≡ 1 (mod φ(n)). Це знаходять за допомогою розширеного алгоритму Евкліда. Для наших чисел класичний результат:
Отже, e × d mod φ(n) = 1 — умова виконана, пара ключів коректна.
| Величина | Значення | Роль |
|---|---|---|
| p, q | 61, 53 | секретні прості множники |
| n = p×q | 3233 | модуль (публічний) |
| φ(n) | 3120 | допоміжне число (секретне) |
| e | 17 | публічний показник шифрування |
| d | 2753 | приватний показник розшифрування |
Крок 6. Шифрування та розшифрування
Публічний ключ — пара (n, e) = (3233, 17), її можна оприлюднити. Приватний ключ — число d = 2753, його ніхто, крім власника, не повинен знати.
Щоб зашифрувати повідомлення m (у навчальному прикладі часто беруть m = 65), відправник обчислює шифротекст c за формулою:
Вручну підносити 65 до 17-го степеня незручно — на практиці для цього використовують метод швидкого модулярного експоненціювання (послідовне піднесення до квадрата з узяттям остачі на кожному кроці), який виконує комп'ютер за долі секунди навіть для чисел у сотні цифр. У цьому класичному підручниковому прикладі результатом є c = 2790.
Отримавши шифротекст c, власник приватного ключа розшифровує його тим самим способом, але з показником d:
Результат — вихідне повідомлення m = 65 — повністю відновлюється. Це і є суть асиметричного шифрування: операція з e «замикає» повідомлення, а обернена операція з d, відома лише власнику ключа, «відмикає» його. Математично це працює завдяки теоремі Ейлера й тому, що e та d — взаємно обернені за модулем φ(n).
4. Чому факторизацію n так важко обернути
Щоб зламати RSA «в лоб», зловмиснику потрібно, маючи лише публічне n, знайти множники p і q. Для n = 3233 це тривіально (3233 = 61 × 53), і саме тому такий розмір ключа непридатний для реального захисту. Але коли n складається з двох простих чисел по 150–300 цифр кожне (реальні ключі RSA мають довжину 2048 або 4096 біт), найкращі відомі класичні алгоритми факторизації (наприклад, «решето числового поля») вимагають часу, що зростає суперполіноміально відносно кількості цифр — практично роки обчислень навіть на потужних кластерах.
Саме ця обчислювальна вартість, а не секретність самого алгоритму, і забезпечує безпеку RSA: алгоритм відкритий і добре вивчений, але без знання p і q обернути операцію шифрування неможливо за прийнятний час.
Про цю статтю
Ця стаття є частиною бази знань calculator.party — освітнього ресурсу, що поєднує теорію з практичними інструментами. Матеріал орієнтований на студентів, учнів і фахівців, що прагнуть глибокого розуміння теми. Тут зібрані ключові концепції, формули та реальні приклади застосування.
Теорія чисел вивчає властивості цілих чисел — подільність, прості числа, модулярну арифметику. Від криптографії до кодів корекції помилок — теорія чисел лежить в основі багатьох технологій XXI ст.
Навіщо читати цю статтю
Після прочитання ви зможете впевнено пояснити, як алгоритм RSA перетворює прості числа на криптографічний захист, самостійно повторити навчальний приклад обчислень та розуміти, чому довжина ключа має значення для безпеки.