Дискретная математика
Криптографические алгоритмы: RSA и эллиптические кривые
RSA-2048 защищает 85% HTTPS-трафика в интернете. Его взлом требует факторизации 617-значного числа - лучший алгоритм (GNFS) занял бы тысячи лет на всех существующих компьютерах. Вся эта стойкость следует из одной теоремы Эйлера и арифметики простых чисел.
- TLS 1.3 (HTTPS): каждое соединение использует ECDH на кривой P-256 для обмена ключами - 256-битный ключ ECC обеспечивает ту же стойкость, что и 3072-битный RSA, при в 12 раз меньшем размере.
- SSH-ключи на GitHub: Ed25519 (алгоритм на базе кривой Curve25519) стал стандартом в 2019 году - генерация ключа занимает миллисекунды, проверка подписи ещё быстрее.
- Signal Protocol (WhatsApp, Telegram Secret Chat): двойной храповик на базе ECDH обновляет сессионные ключи при каждом сообщении - компрометация одного ключа не раскрывает историю.
Цели урока
- Объяснять математическую основу RSA через теорему Эйлера и задачу факторизации
- Конструировать группу точек эллиптической кривой и описывать операцию сложения
- Анализировать ECDH-протокол и обосновывать его стойкость через ECDLP
Предварительные знания
- Модульная арифметика и теорема Эйлера
- Группы и поля (dm-16)
- Расширенный алгоритм Евклида для вычисления обратных элементов
RSA: от теоремы Эйлера к шифрованию
Корректность RSA следует из теоремы Эйлера: для $\gcd(m, n) = 1$ выполнено $m^{\phi(n)} \equiv 1 \pmod{n}$. Тогда $c^d \equiv m^{ed} \equiv m^{1 + k\phi(n)} \equiv m \cdot (m^{\phi(n)})^k \equiv m \pmod{n}$. Безопасность: зная $e$ и $n$, но не $p, q$, вычислить $d$ эквивалентно факторизации $n$ - задача, требующей субэкспоненциального времени $\exp(O(n^{1/3} (\log n)^{2/3}))$ при лучшем алгоритме (GNFS).
Публичная экспонента $e = 65537 = 2^{16} + 1$ выбрана не случайно: это простое число с только двумя единицами в двоичной записи. Алгоритм «возведения в квадрат и умножения» требует $O(\log e)$ умножений, из которых множителей ровно столько, сколько единиц в $e$. Для $e = 65537$ это 17 шагов квадратования и всего 1 умножение.
Эллиптические кривые: геометрия вместо факторизации
Точки эллиптической кривой $E: y^2 = x^3 + ax + b$ над $\mathbb{F}_p$ образуют абелеву группу. Сложение $P + Q$ геометрически: прямая через $P$ и $Q$ пересекает кривую в третьей точке $R'$, затем отражение $R = -R'$ по оси $x$. Задача дискретного логарифма на кривой (ECDLP): по точкам $G$ и $Q = kG$ найти $k$. Лучший алгоритм (rho Полларда) требует $O(\sqrt{|E(\mathbb{F}_p)|})$ операций - без субэкспоненциальных алгоритмов, известных для RSA.
Не все эллиптические кривые одинаково безопасны. Суперсингулярные кривые уязвимы к MOV-атаке (сводится к DLP в расширении поля). Кривые с малым порядком группы легко атакуются перебором. NIST, Brainpool и Bernstein (Curve25519) публикуют кривые с доказанными параметрами безопасности.
RSA опубликован в 1977 году Ривестом, Шамиром и Адлеманом - через год после откр
RSA опубликован в 1977 году Ривестом, Шамиром и Адлеманом - через год после открытой криптографии с открытым ключом Диффи и Хеллмана. Эллиптические кривые в криптографии предложили независимо Коблиц и Миллер в 1985 году. В 2022 году NIST стандартизировал постквантовые алгоритмы (CRYSTALS-Kyber, CRYSTALS-Dilithium) - ни RSA, ни ECC не устоят против квантового компьютера с алгоритмом Шора.
Математика RSA
В 1977 году Ривест, Шамир и Адлеман опубликовали RSA. Сегодня ключи RSA-2048 защищают HTTPS-трафик 85% сайтов из топ-1М Alexa. Безопасность RSA опирается на вычислительную сложность разложения на множители: лучший известный алгоритм (GNFS) требует exp(O(n^{1/3})) операций для n-битного числа.
Почему в RSA публичный показатель e часто выбирают равным 65537?
Криптография на эллиптических кривых
Кобліц и Миллер предложили ECC в 1985 году. Кривая P-256 (secp256r1), используемая в TLS 1.3 и Bitcoin ECDSA, обеспечивает 128-битную безопасность при ключе всего 256 бит против 3072-битного RSA. ECDH-обмен в TLS выполняется за 0.2 мс на iPhone 14 против 2 мс для RSA-2048.
Почему ECC обеспечивает ту же безопасность, что RSA, при существенно меньшем ключе?
Сравнение уровней стойкости
Для 128-битной стойкости (AES-128): RSA требует 3072-битный модуль, ECC достаточно 256-битного ключа (кривая P-256). Для 256-битной стойкости: RSA - 15360 бит, ECC - 512 бит. Причина: субэкспоненциальные атаки на факторизацию (GNFS) сильнее, чем $O(\sqrt{p})$ атаки на ECDLP. Меньший ключ - быстрее генерация, подпись, проверка, меньше трафика.
Итоги
- RSA строится на теореме Эйлера: стойкость = сложность факторизации.
- ECC строится на ECDLP: стойкость при в 12 раз меньшем ключе.
- ECDH обеспечивает обмен ключами: стороны публикуют $aG$ и $bG$, секрет $abG$ недоступен без решения ECDLP.
Связь с другими темами
Группы (dm-16) поставляют математическую основу: $\mathbb{Z}_p^*$ для RSA/DH, $E(\mathbb{F}_p)$ для ECC. Теория чисел (dm-09, dm-10) обеспечивает тесты простоты и алгоритм Евклида. В постквантовой криптографии те же групповые идеи переносятся на решётки и коды исправления ошибок.
- Dm 16 — связан
- Dm 09 — связан
- Dm 10 — связан
Вопросы для размышления
- Алгоритм Шора на квантовом компьютере факторизует $n$ за $O((\log n)^3)$ - это уничтожит RSA. Но он же решает ECDLP. Почему тогда ECC и RSA одинаково уязвимы к квантовым атакам, хотя в классическом мире ECC значительно эффективнее?