Арифметика
Криптография на пальцах
От Цезаря до Тьюринга: 2000 лет тайных посланий
**Юлий Цезарь** шифровал приказы простой заменой: каждую букву сдвигал на 3 позиции (A→D, B→E). Враги не могли прочесть - им не хватало идеи. Через 2000 лет немецкая **Энигма** использовала ту же идею замены, но с роторами, менявшими шифр после каждой буквы. Казалось - непобедима.
Тот, кто владеет информацией - владеет миром. - Уинстон Черчилль
Вся криптография до 1970-х была **симметричной**: один ключ для шифрования и дешифрования. Проблема: как передать ключ? Курьером? А если его перехватят? Это называлось «проблемой распределения ключей» - и казалось неразрешимой.
Секретное открытие, изменившее мир
В **1973 году** британский криптограф **Джеймс Эллис** из секретного агентства GCHQ придумал невозможное: шифрование без передачи ключа. Через два года 22-летний математик **Клиффорд Кокс** нашёл реализацию - ту самую, которую мир узнает как RSA. Но открытие было **засекречено на 24 года**.
Криптография - это единственная область, где можно быть параноиком и при этом правым. - Уитфилд Диффи
Когда в **1991 году** Фил Циммерман создал **PGP** (Pretty Good Privacy) и выложил в интернет, правительство США возбудило против него уголовное дело - криптография была **оружием**. Три года расследований. Но джинна уже не загнать в бутылку: RSA стал основой интернет-безопасности, а затем - **Bitcoin** и всей криптоэкономики.
Каждый раз, когда в браузере появляется замочек, работает RSA. Номер карты шифруется публичным ключом магазина. Расшифровать его может только магазин - приватным ключом. Хакер перехватил данные? Бесполезно. За шифрованием стоит простая идея: умножить 100-значные простые числа займёт миллисекунду, разложить их произведение - миллиарды лет.
- **HTTPS:** защита веб-трафика
- **Банки:** шифрование транзакций
- **Электронная подпись:** юридически значимые документы
Идея публичного ключа
**Криптография с публичным ключом** - революционная идея 1970-х: два ключа вместо одного. Публичный ключ шифрует, приватный - расшифровывает. Знание публичного не помогает узнать приватный.
**Симметричная криптография (старая):** Один ключ для шифрования и дешифрования. Проблема: как передать ключ по незащищённому каналу? **Асимметричная (публичный ключ):** • Публичный ключ: можно раздавать всем • Приватный ключ: держим в секрете Шифруем публичным → расшифровываем приватным
Криптография с публичным ключом решила проблему распределения ключей. Теперь можно безопасно общаться с незнакомцами через интернет.
Что можно сделать, зная только публичный ключ?
Концепция RSA
**RSA** - первый и самый известный алгоритм с публичным ключом. Основан на сложности факторизации: умножить два простых числа просто, разложить их произведение - практически невозможно для больших чисел.
**Ключевая идея RSA:** Легко: p × q = n (умножить простые) Трудно: n → (p, q) (факторизовать) **Параметры:** • p, q - большие простые числа (секрет) • n = p × q - модуль (публичный) • e - экспонента шифрования (публичный) • d - экспонента дешифрования (секрет)
RSA превращает трудность факторизации в криптографическую безопасность. Пока не существует быстрого алгоритма факторизации, RSA остаётся надёжным.
На какой математической трудности основана безопасность RSA?
Модулярное возведение в степень
**Модулярное возведение в степень** - вычисление a^b mod n. Наивный подход (вычислить a^b, потом взять mod) невозможен для больших чисел. Метод быстрого возведения решает эту проблему.
**Свойство модульной арифметики:** (a × b) mod n = ((a mod n) × (b mod n)) mod n **Следствие:** Можно брать остаток на каждом шаге, не накапливая огромные числа. **Метод "возведение в квадрат и умножение":** a^b вычисляется за O(log b) умножений
Быстрое возведение в степень позволяет работать с показателями в тысячи бит. Без этого алгоритма RSA был бы непрактичным.
Сколько умножений нужно для вычисления a^1024 mod n методом быстрого возведения?
Почему RSA работает
Математическое обоснование RSA основано на **малой теореме Ферма** и её обобщении - **теореме Эйлера**. Они гарантируют, что дешифрование восстанавливает исходное сообщение.
**Малая теорема Ферма:** Если p простое и gcd(a, p) = 1, то: a^(p-1) ≡ 1 (mod p) **Теорема Эйлера:** Если gcd(a, n) = 1, то: a^φ(n) ≡ 1 (mod n) где φ(n) - функция Эйлера
Красота RSA - в использовании глубоких теорем теории чисел для практической задачи. Эйлер в XVIII веке не подозревал, что его теорема защитит банковские транзакции в XXI веке.
RSA абсолютно надёжен и никогда не будет взломан
RSA надёжен пока факторизация трудна; квантовые компьютеры изменят ситуацию
Алгоритм Шора на квантовом компьютере может факторизовать числа за полиномиальное время. Когда квантовые компьютеры станут достаточно мощными, RSA придётся заменить на постквантовую криптографию. Но пока (2020-е) RSA с ключами 2048+ бит считается безопасным.
Какая теорема гарантирует, что дешифрование RSA восстанавливает исходное сообщение?
Ключевые идеи
- Публичный ключ шифрует, приватный - расшифровывает
- RSA основан на трудности факторизации n = p × q
- Быстрое возведение в степень: O(log n) операций
- Теорема Эйлера гарантирует M^(ed) ≡ M (mod n)
Связанные темы
RSA использует фундаментальные концепции:
- Модульная арифметика — Основа вычислений
- Простые числа — p и q в ключах
- НОД и алгоритм Евклида — Нахождение d
Вопросы для размышления
- Почему RSA использует именно простые числа, а не любые?
- Как квантовые компьютеры угрожают RSA?
- Почему публичный ключ можно раздавать всем без риска?