Замок из простых чисел.
каждый раз, когда браузер показывает 🔒 — работают простые числа. RSA держится на одном факте: перемножить легко, разложить обратно — нет.
Каждый день вы используете простые числа. Когда заходите в банк онлайн. Когда пишете в мессенджер. Когда браузер показывает замочек рядом с адресом сайта. За каждым из этих действий стоит RSA — алгоритм шифрования, изобретённый в 1977 году. Ривест, Шамир, Адлеман — три буквы, три фамилии. В основе — асимметрия простых чисел1.
Возьмите два больших простых числа, скажем p и q. Перемножьте: n = p · q. Это легко — компьютер делает за микросекунды, даже если каждое из чисел занимает несколько сотен знаков. Теперь обратная задача: дано n, найти p и q. Это факторизация, и она катастрофически медленна.
Для маленьких чисел всё просто. 15 = 3 · 5, в уме. Для чисел в 1024 бита — это около 309 десятичных знаков — лучшие современные алгоритмы факторизации работают годами на специализированных кластерах. Для 2048 бит, стандарта современного RSA, — нынешние компьютеры потратят больше времени, чем существует вселенная. И это не «сложно», а «практически невозможно» в инженерном смысле.
Именно на этой асимметрии и построен RSA. Перемножение — за O(n²) или быстрее. Факторизация — за субэкспоненциальное время в лучшем случае, что для практических размеров ключей означает «вечно».
RSA — это малая теорема Ферма на службе у банков.
Как это работает в деталях? Берём n = p · q. Выбираем открытую экспоненту e (обычно 65537 — простое число с удобным двоичным представлением). Вычисляем секретную экспоненту d из условия e · d ≡ 1 (mod (p − 1)(q − 1)). Шифрование сообщения m: c = me mod n. Расшифровка: m = cd mod n. Открытым ключом (n, e) шифрует кто угодно — он публичен. Расшифровывает только владелец секретного d.
Математика гарантирует, что зная только n и e, восстановить d без знания p и q вычислительно невозможно. Именно вычислительно — не теоретически. Теоретически можно: достаточно факторизовать n. Просто это займёт 1020 лет на современном железе. Вселенная закончится раньше.
Элегантность RSA в том, что открытый и закрытый ключи связаны математически — но вычислить один из другого без знания простых множителей невозможно. Можно кричать свой открытый ключ на весь мир — секрет не раскроется. Это и есть фундаментальное изобретение асимметричной криптографии: разделение «зашифровать» и «расшифровать» на две принципиально разные операции.
Что будет, если появится быстрый алгоритм факторизации? RSA сломается мгновенно и полностью. Все зашифрованные данные, которые накопил мир за последние 50 лет, станут открытыми. Именно поэтому P vs NP — не абстрактный вопрос. Если P = NP, факторизация решаема за полиномиальное время, и интернет в нынешнем виде перестаёт существовать в одну ночь.
Квантовые компьютеры — реальная угроза, не теоретическая. Алгоритм Шора, опубликованный Питером Шором в 1994 году, решает задачу факторизации на квантовом компьютере за O((log n)³) — то есть быстро2. Квантового компьютера достаточной мощности (нужно несколько тысяч идеально-стабильных кубитов) пока нет. Но он будет. NIST уже стандартизирует постквантовую криптографию — алгоритмы, устойчивые к квантовым атакам, основанные на других задачах: решёточных, кодовых, изогенных. Финальные стандарты опубликованы в 2024 году3.
Простые числа изучали тысячелетиями из чистого любопытства. Никто не думал, что они станут фундаментом глобальной инфраструктуры. Евклид доказал их бесконечность около 300 года до нашей эры. Ривест применил их свойства в 1977 году. 2277 лет между чистым открытием и инфраструктурным применением. Малая теорема Ферма, доказанная в 1640 году в письме другу, без всякой практической задачи в виду — оказалась ровно тем фактом, на котором держится RSA. Без неё не было бы способа доказать, что (me)d mod n снова даёт m.
Математика всегда опережает применение. Иногда на десятилетия, иногда на тысячелетия. И в обоих случаях невозможно заранее предсказать, какой именно факт о простых числах в каком веке окажется фундаментом следующего технологического слоя. Возможно, гипотеза Римана через сто лет окажется встроена в какую-нибудь криптографическую систему, которой мы сейчас не можем себе представить. Возможно — нет. Это и есть та часть математики, в которой никакое планирование не работает.