Покроковий алгоритм RSA: оберіть два прості числа, обчисліть n та φ(n), знайдіть відкриту e та закриту d експоненти, зашифруйте та розшифруйте повідомлення.
Безпека RSA спирається на складність факторизації великих чисел. Маючи n = p·q, обчислити φ(n) = (p−1)(q−1) легко при відомих p і q, але практично неможливо при відомому лише n.
Оберіть два прості числа p та q. Система обчислює n, φ(n), відкритий ключ e та закритий d. Введіть повідомлення для шифрування відкритим та розшифрування закритим ключем.
RSA опублікований у 1977 році Рівестом, Шаміром та Адлеманом. Той самий алгоритм незалежно відкрив Кліффорд Кокс у GCHQ у 1973, але він залишався засекреченим до 1997. Сучасний RSA використовує 2048+ бітні ключі.
Ця симуляція крок за кроком демонструє криптосистему з відкритим ключем RSA. Ви обираєте два різних простих числа p та q, і вона обчислює модуль n = p×q і функцію Ейлера φ(n) = (p−1)(q−1). Потім вона перелічує допустимі відкриті експоненти e, взаємно прості з φ(n), виводить закриту експоненту d як модульний обернений елемент e−¹ mod φ(n) за допомогою розширеного алгоритму Евкліда та дозволяє вам зашифрувати й розшифрувати число.
Випадні списки p та q обирають прості числа (від 2 до 97), кнопка «Обчислити ключі» перераховує все наново, а пігулки e дають змогу вибрати допустиму відкриту експоненту. Шифрування використовує C = Me mod n, а розшифрування M = Cd mod n, обидва через швидке модульне піднесення до степеня. RSA лежить в основі HTTPS, цифрових підписів і захищеної електронної пошти, причому реальні ключі використовують прості числа завдовжки сотні цифр.
Що показує ця симуляція?
Вона демонструє повний робочий процес RSA на малих, зрозумілих числах: генерацію ключів із двох простих чисел, вибір відкритої експоненти, виведення закритої експоненти, а потім шифрування й розшифрування повідомлення. Кожна формула та проміжне значення показані, тож математика залишається прозорою.
Як насправді генеруються ключі?
Із обраних вами простих чисел p та q обчислюється n = p×q і φ(n) = (p−1)(q−1). Ви обираєте відкриту експоненту e, взаємно просту з φ(n), і симулятор знаходить закриту експоненту d, що задовольняє d×e ≡ 1 (mod φ(n)), за допомогою розширеного алгоритму Евкліда.
Що роблять елементи керування?
Випадні списки p та q задають два прості числа зі списку від 2 до 97, а «Обчислити ключі» перераховує модуль, функцію Ейлера та експоненти. Пігулки e дають змогу перемикатися між допустимими відкритими експонентами, а поле повідомлення дозволяє ввести ціле число M для шифрування та розшифрування.
Шифрування обчислює шифротекст як C = M^e mod n, де M — повідомлення, e — відкрита експонента, а n — модуль. Розшифрування виконує зворотну операцію M = C^d mod n із закритою експонентою d. Обидва використовують модульне піднесення до степеня, реалізоване тут через BigInt, щоб уникнути переповнення.
Відкрита експонента e має задовольняти gcd(e, φ(n)) = 1, щоб існував модульний обернений елемент d. Без взаємної простоти немає єдиного d, і розшифрування зазнало б невдачі. Симуляція пропонує лише ті значення e, які відповідають цій умові.
RSA працює в арифметиці за модулем n, тож будь-яке повідомлення має бути цілим числом у діапазоні 0 ≤ M < n, щоб його можна було однозначно відновити. Якби M дорівнювало n або було більшим за нього, операція за модулем відобразила б різні повідомлення на одне значення, і розшифрування не повернуло б оригіналу.
Алгоритм є справжнім RSA: ті самі рівняння генерації ключів, шифрування та розшифрування, що використовуються на практиці. Єдине спрощення — масштаб. Реальний RSA використовує прості числа із сотень цифр (ключі 2048 біт або більші), тоді як тут крихітні прості числа роблять кожен крок зрозумілим.
Його безпека ґрунтується на складності розкладання n назад на p та q. Обчислити φ(n), а отже й d, легко, якщо ви знаєте прості числа, але вважається практично неможливим, якщо ви знаєте лише n. За достатньо великих ключів жоден відомий класичний алгоритм не може розкласти n за прийнятний час.
Оскільки d є модульним оберненим елементом e, піднесення шифротексту до степеня d скасовує піднесення повідомлення до степеня e. За теоремою Ейлера M^(e×d) ≡ M (mod n), тож (M^e)^d mod n відновлює M точно. Симуляція перевіряє цю відповідність за вас.
RSA захищає з'єднання HTTPS, підписує програмне забезпечення та сертифікати, захищає електронну пошту за стандартами на кшталт PGP і лежить в основі багатьох протоколів обміну ключами та автентифікації. Його часто використовують для обміну симетричним сеансовим ключем, який потім ефективніше шифрує основний обсяг даних.
У принципі так. Алгоритм Шора може ефективно розкладати великі цілі числа на достатньо потужному квантовому комп'ютері, що зламало б RSA. Саме тому дослідники розробляють постквантову криптографію, хоча сьогодні жодна квантова машина не є достатньо великою, щоб загрожувати реальним ключам.