Шифрування RSA: ключі, математика і онлайн-калькулятор

Шифрування RSA — це асиметричний метод, у якому є два ключі: відкритий і закритий. Відкритий ключ можна публікувати будь-де: ним шифрують повідомлення. Розшифрувати їх може лише власник закритого ключа. Алгоритм запропонували Рівест, Шамір і Адлеман 1977 року. Відтоді RSA захищає HTTPS-сертифікати, SSH, цифрові підписи документів і оновлення прошивок.

Калькулятор генерує справжню пару ключів RSA-2048 у вашому браузері, шифрує й розшифровує текст. Нижче є навчальний режим на малих числах, де видно кожну формулу.

Ідея асиметричного шифрування

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

Математика RSA крок за кроком

Безпека RSA тримається на тому, що перемножити два великі прості числа легко, а розкласти добуток на множники — надзвичайно важко.

1. Обираємо два прості числа p і q.
2. Обчислюємо модуль n = p · q.
3. Обчислюємо функцію Ейлера φ(n) = (p − 1)(q − 1).
4. Обираємо відкриту експоненту e, взаємно просту з φ(n). На практиці e = 65537.
5. Знаходимо закриту експоненту d: d · e ≡ 1 (mod φ(n)). Це обернений елемент за модулем, його рахують розширеним алгоритмом Евкліда.

Відкритий ключ — пара (e, n), закритий — (d, n). Далі шифрування та розшифрування числа m:

c = m^e mod n     // шифрування відкритим ключем
m = c^d mod n     // розшифрування закритим ключем

Класичний приклад із калькулятора: p = 61, q = 53, тоді n = 3233, φ(n) = 3120. При e = 17 маємо d = 2753. Число 65 шифрується в 65¹⁷ mod 3233 = 2790. Розшифрування 2790²⁷⁵³ mod 3233 знову дає 65.

Швидке піднесення до степеня

Число 2790²⁷⁵³ має тисячі цифр, але обчислювати його повністю не потрібно. Алгоритм «піднесення квадратом» бере остачу на кожному кроці й виконує лише близько log₂(d) множень:

function modPow(b, e, m) {      // b, e, m — BigInt
  let r = 1n;
  b %= m;
  while (e > 0n) {
    if (e & 1n) r = r * b % m;
    b = b * b % m;
    e >>= 1n;
  }
  return r;
}
modPow(65n, 17n, 3233n);  // 2790n

Чому справжній RSA складніший за підручниковий

Доповнення OAEP

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

Обмеження довжини

RSA-2048 з OAEP-SHA256 шифрує не більше 190 байт. Тому RSA не шифрує файли напряму. Застосовують гібридну схему: генерують випадковий ключ AES, шифрують ним дані, а сам ключ шифрують RSA. Так працюють PGP, S/MIME і старіші версії TLS.

Довжина ключа

Квантові комп’ютери з алгоритмом Шора теоретично ламають RSA будь-якої довжини. Тому NIST уже стандартизував постквантові алгоритми ML-KEM і ML-DSA, і перехід на них поступово триває.

Цифровий підпис

RSA працює і «навпаки»: власник підписує хеш документа закритим ключем, а будь-хто перевіряє підпис відкритим. Так перевіряють сертифікати сайтів, оновлення Windows і Android, а також підписані прошивки мікроконтролерів (secure boot на ESP32 чи STM32).

Підсумок

• RSA — асиметричне шифрування: відкритий ключ шифрує, закритий розшифровує.
• Стійкість базується на складності факторизації n = p · q.
• Для даних RSA поєднують з AES, а ключі беруть від 2048 біт.

Решту методів, від шифру Цезаря до XOR, зібрано в огляді методи шифрування.

Детальніше про метод див. статтю «RSA» у Вікіпедії.