В эпоху стремительного развития квантовых технологий вопросы информационной безопасности приобретают критическое значение. Видео канала Veritasium, которое ведет Дерек Мюллер, посвящено одной из самых серьезных угроз цифровому миру — квантовым вычислениям и их способности взломать современное шифрование.
🔐 Угроза «сохрани сейчас, расшифруй потом» 0:00
На сегодняшний день спецслужбы и другие субъекты активно перехватывают и накапливают огромные объемы зашифрованных данных: пароли, банковские реквизиты, записи о социальном обеспечении. Процедура получила название SNDL (Store Now, Decrypt Later — «сохрани сейчас, расшифруй потом»).
Суть угрозы заключается в следующем:
- Злоумышленники полагаются на то, что в течение следующих 10–20 лет они получат доступ к квантовому компьютеру, способному взломать текущие алгоритмы шифрования за считанные минуты.
- Национальное агентство безопасности США (NSA) предупреждает, что мощный квантовый компьютер способен подорвать все широко распространенные алгоритмы с открытым ключом в ближайшие 5–10 лет.
- Осознавая опасность, Конгресс США уже принял законодательство, предписывающее государственным агентствам начать переход на новые методы криптографии, устойчивые к квантовым атакам.
💻 От RSA к квантовой реальности 1:19
Современная криптография, включая стандарт RSA, базируется на сложности факторизации — процессе разложения больших чисел на простые множители.
- В 1977 году ученые Ривест, Шамир и Адлеман разработали систему RSA, основанную на использовании двух огромных простых чисел.
- Публичное число, являющееся произведением этих простых множителей, используется для шифрования, а чтобы расшифровать данные, необходимо знать исходные простые числа.
- Классическим суперкомпьютерам потребовались бы миллионы лет, чтобы найти множители для современных 313-значных чисел.
Принципиальное отличие квантового компьютера заключается в использовании кубитов. В то время как классический бит может быть либо «0», либо «1», кубит благодаря суперпозиции может находиться в обоих состояниях одновременно.
- Два кубита могут представлять 4 состояния сразу, три кубита — 8, а 300 кубитов — больше состояний, чем частиц в наблюдаемой Вселенной.
- Однако прочитать результат напрямую нельзя: измерение коллапсирует суперпозицию, выдавая лишь случайное значение.
🧠 Квантовый алгоритм: магия факторизации 6:45
В 1994 году Питер Шор и Дон Копперсмит нашли способ использовать квантовые вычисления для решения проблемы факторизации. Весь процесс можно представить как поиск периодичности:
- Выбирается случайное число $G$, не имеющее общих множителей с числом $N$.
- Алгоритм ищет период $R$ — степень, при которой $G^R \equiv 1 \pmod{N}$.
- Используя найденный период $R$ и алгоритм Евклида, можно вычислить простые множители $P$ и $Q$.
Классические компьютеры справляются с этим медленно, но квантовые системы находят $R$ экспоненциально быстрее благодаря квантовому преобразованию Фурье. Хотя в 2012 году требовался миллиард физических кубитов для взлома RSA, к 2019 году это число упало до 20 миллионов благодаря технологическому прогрессу.
🛡️ Постквантовая криптография: защита на основе решеток 17:37
В 2016 году NIST запустил конкурс на поиск алгоритмов, устойчивых к квантовым атакам. Победители были объявлены 5 июля 2022 года.
Большинство выбранных методов основаны на математике решеток:
- Задача заключается в нахождении ближайшей точки в многомерном пространстве (задача о ближайшем векторе).
- В 2D это просто, но при увеличении размерности до 1000 и более нахождение ближайшей точки становится невыполнимым даже для квантовых компьютеров.
- Шифрование строится на том, что обладатель «секретных векторов» легко находит путь к нужной точке, в то время как злоумышленник, имеющий только «сложные векторы», вынужден блуждать в многомерном лабиринте без шансов на успех.
