Интерактивная демонстрация RSA
Управляйте генерацией ключей и шифруйте сообщения с помощью алгоритма RSA
Математическая схема алгоритма RSA
Генерация ключей
Шифрование и расшифрование
Результат
Сгенерируйте ключи и нажмите "Зашифровать"
История
Ривест, Шамир, Адлеман
1977
Создатели RSA, MIT
RSA — один из первых практических алгоритмов асимметричного шифрования, названный по первым буквам фамилий его создателей: Рона Ривеста, Ади Шамира и Леонарда Адлемана.
Алгоритм был впервые опубликован в 1977 году в статье "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems". Интересно, что идея криптографии с открытым ключом была впервые предложена Уитфилдом Диффи и Мартином Хеллманом в 1976 году, а RSA стал её первой практической реализацией.
Интересный факт: В 1977 году создатели RSA предложили взломать 129-разрядное число за $100. Задача была решена лишь через 17 лет, в 1994 году, с помощью распределенных вычислений.
Принципы работы
RSA основан на сложности факторизации больших чисел. Произведение двух больших простых чисел легко вычислить, но очень сложно разложить обратно.
Генерация ключей
Выбираются два больших простых числа p и q. Вычисляется их произведение n = p × q.
Вычисление функции Эйлера
φ(n) = (p-1) × (q-1)
Выбор открытой экспоненты
Выбирается число e (обычно 65537), взаимно простое с φ(n).
Вычисление закрытой экспоненты
Вычисляется d = e⁻¹ mod φ(n) с помощью расширенного алгоритма Евклида.
Математические формулы
Открытый ключ: (e, n)
Закрытый ключ: (d, n)
Шифрование: C = Mᵉ mod n
Расшифрование: M = Cᵈ mod n
где M — исходное сообщение, C — зашифрованное сообщение
Безопасность
Важно: Современные реализации RSA используют ключи длиной 2048-4096 бит. Демонстрация использует малые числа только для образовательных целей.
Основные угрозы
Факторизация n
Если злоумышленник сможет разложить n на множители p и q, он сможет вычислить закрытый ключ d.
Атаки по времени
Анализируя время, необходимое для выполнения операций шифрования/расшифрования, можно получить информацию о ключе.
Слабые простые числа
Использование предсказуемых или слишком маленьких простых чисел делает систему уязвимой.
Оценка безопасности
Применение
Основные области применения
- SSL/TLS протоколы для защищенного веб-сёрфинга (HTTPS)
- PGP и S/MIME для шифрования электронной почты
- Защита банковских транзакций и онлайн-платежей
- Аутентификация в мобильных приложениях
Цифровые подписи
- Подписание документов и программного обеспечения
- SSL-сертификаты для веб-сайтов
- Электронные контракты и юридические документы
Современные альтернативы
С развитием квантовых вычислений разрабатываются пост-квантовые алгоритмы:
- Решёточная криптография (LWE, NTRU)
- Кодовая криптография
- Многомерные квадратичные системы
Интересный факт
RSA использовался в первых версиях Netscape Navigator (1994 год) для реализации SSL. Это позволило создать первую коммерческую систему безопасных онлайн-транзакций и заложило основы современного электронного бизнеса.