Квантовые компьютеры смогут взломать почти всё. Как инженеры готовятся к Q-Day и защищают системы шифрования

Доступа к сверхбыстрым вычислениям ждут не только учёные, но и хакеры. Поэтому интернет должен успеть войти в эру постквантовой криптографии.

В обозримом будущем наступит Q-day — день, когда большинство современных методов защиты информации станут бесполезны. Квантовые компьютеры смогут чуть ли не моментально подбирать ключи шифрования для популярных криптографических протоколов, а значит любые данные станут доступны. Уже сейчас высчитывают, какая мощь нужна для взлома алгоритма шифрования биткоина — и хоть таких не будет ещё долго, некоторые системы шифрования уязвимы уже сейчас.

Чтобы защитить их, надо внедрять новые алгоритмы, не дожидаясь Q-day. Уже сейчас инженеры занимаются постквантовой криптографией — она должна защитить от кибератак с помощью квантовых компьютеров. Как сейчас идёт работа в этом направлении, рассказал журнал Nature.

Криптография встречается повсеместно: шифрование используется при обмене сообщениями в мессенджерах, покупках в интернете, управлении автомобилем. Её задача — предотвратить утечку информации, обеспечивая безопасность связи с помощью правил, которые позволяют получать данные и обрабатывать их только тем, кто имеет соответствующий доступ.

При этом сам метод преобразования не является тайной, но никто, кроме отправителя и получателя, не знает главного секретного параметра шифрования — криптографического ключа. Но квантовые компьютеры смогут легко и быстро узнать его.

Используемая десятилетиями система шифрования RSA строится на умножении простых целых чисел. И хотя умножить два больших числа несложно, найти неизвестные простые множители очень большого числа чрезвычайно трудно. Но всё же возможно даже с использованием обычного компьютера, пусть на это и уходит много времени перебора.

В 2018 году Инженерная рабочая группа Интернета (IETF), виртуальная организация, которая руководит принятием стандартов безопасности в глобальном масштабе, одобрила другую систему с открытым ключом для замены существующей. Эта система называется криптографией на основе эллиптических кривых, она основана на вычислении n-ой степени целого числа, которое связано с точкой на кривой.

В этом случае только одна сторона знает число n, которое является секретным ключом. Вычислить экспоненту числа легко, но сложно определить, чему равно n. Этот метод безопаснее, чем RSA, и, к тому же, быстрее.

Ещё в 1994 году математик из Массачусетского технологического института (MIT) Питер Шор показал, что квантовый компьютер должен иметь возможность раскладывать большие числа на простые намного быстрее, чем классический компьютер. Один из шагов квантового алгоритма Шора также может эффективно взломать ключ на эллиптической кривой. То есть все существующие распространённые системы криптографии бессильны перед квантовым компьютером — и об этом давно известно.

Более того, машины, которых ещё не существует, угрожают не только будущим коммуникациям, но и нашим нынешним и прошлым. Злоумышленники уже сейчас могут накапливать зашифрованные данные, которые затем смогут разблокировать, как только квантовые компьютеры станут доступны. То есть почти всё, что происходило в интернете до сегодняшнего дня, возможно узнать.

После прорыва Шора мир крипто-исследований начал обращать внимание на возможность Q-day. Разные страны разрабатывают системы, устойчивые к будущему вероятному взлому. Какой из новых алгоритмов станет стандартным, может в значительной степени зависеть от решения, которое вскоре будет объявлено Национальным институтом стандартов и технологий США (NIST).

Ещё в 2016 году NIST пригласил исследователей в области компьютерных наук со всего мира представить потенциальные постквантовые алгоритмы. Есть два принципиальных новых подхода: квантовая и постквантовая криптографии.

Первая строится на квантовом распределении ключей, когда биты информации кодируются в одиночные частицы (фотоны). В этом случае также легко определить вмешательство злоумышленников по числу ошибок при передаче данных. Если оно не превышает определенный порог, можно сократить ключи таким образом, чтобы информация перехватчика о сокращённых ключах была недостаточной — это называется «усилением секретности». В таком случае даже при наличии квантового компьютера злоумышленник не сможет получить доступ к информации.

Впрочем, у этого метода есть существенные недостатки: чем на большее расстояние передаются фотоны, тем больше частиц теряются из-за шумов и декогеренции, таким образом снижая пропускную способность, используемую для формирования секретного ключа. Кроме того, всё же остается опасность наличия уязвимостей.

Постквантовая криптография построена на идее создания новых алгоритмов, в которых применяются более сложные математические задачи, чем разложение простых чисел, при решении которых квантовый компьютер не будет иметь существенных преимуществ. Постквантовая криптография хороша тем, что ее можно легко и быстро интегрировать.

Из минусов — секретность постквантовой криптографии всё ещё основывается на некоторых предположениях о сложности решения определенных классов математических задач. А значит есть вероятность того, что появится «постквантовый» компьютер, который легко разгадает и постквантовые алгоритмы.

Большинство алгоритмов, попавших в список NIST, относятся как раз ко второму типу: прямо или косвенно опираются на криптографию на основе математики решёток. Она использует наборы точек, расположенных на пересечениях прямых линий, проходящих через пространство. Если решётка имеет много измерений, то вычисление наименьших векторов занимает очень много времени.

Популярный подход к криптографии на основе решётки называется обучением с ошибками (LWE), который лежит в основе нескольких финалистов NIST. Он был представлен в 2005 году исследователем в области компьютерных наук Одедом Регевом из Нью-Йоркского университета, и в своей простейшей форме опирается на арифметику.

Чтобы создать открытый ключ, человек, который хочет получить сообщение, выбирает большое секретное число — закрытый ключ. Затем они вычисляют несколько кратных этому числу и добавляют к каждому случайные «ошибки»: полученный список чисел является открытым ключом. Отправитель складывает эти целые числа и другое число, представляющее сообщение, и высылает результат.

Чтобы получить сообщение обратно, всё, что получателю нужно сделать, это разделить его на секретный ключ и вычислить остаток. «Это действительно школьный уровень математики», — говорит Регев.

В то время как открытый ключ текущего интернет-приложения имеет размер твита, для шифрования на основе решётки обычно требуются ключи размером не менее одного мегабайта. Системы со «структурированной решёткой» используют по сути алгебраические хитрости, чтобы резко уменьшить размер открытого ключа, но это делает их более уязвимыми для атак.

Среди алгоритмов-кандидатов NIST есть системы, использующие алгебру методов исправления ошибок. Известные как «алгоритмы на основе кода», они хранят данные с избыточностью, что позволяет восстановить исходный файл после того, как он был слегка повреждён. В криптографии алгоритмом хранения данных является открытый ключ, а секретный ключ необходим для восстановления исходного сообщения.

В ближайшие несколько месяцев NIST выберет два алгоритма-финалиста, затем начнет разрабатывать стандарты для одного, а другой сохранит в качестве резерва на случай, если первый вариант окажется взломанным в результате неожиданной атаки, квантовой или иной.

Cloudflare и Google уже начали проводить реальные тесты некоторых постквантовых алгоритмов, включив их в некоторые бета-версии браузера Chrome и в серверное ПО. Тестирование имеет решающее значение, поскольку для бесперебойной работы интернет-коммуникаций недостаточно иметь идеально совместимые серверы и браузеры. Для их подключения данные также должны проходить через сетевые устройства, которые могут блокировать трафик, помечаемый ими как необычный из-за незнакомых протоколов шифрования. Антивирусное программное обеспечение может вызывать аналогичные проблемы.

Проблемы также существуют в некоторых странах, которые отслеживают действия пользователей, что уже усложнило переход от RSA и может также нарушить развертывание квантово-защищенных алгоритмов.

Ранний тест в 2016 году реализовал New Hope — структурированную версию LWE, названную в честь оригинального фильма «Звездные войны», — в бета-версии Chrome, и она работала без сбоев. Но более масштабный эксперимент, проведённый Google в 2021 году с другим алгоритмом, столкнулся с некоторыми проблемами. Некоторые интернет-устройства, по-видимому, «сломались», поскольку вступительное сообщение браузера было длиннее, чем ожидалось, так как содержало большой открытый ключ.

Проблема с браузерами не представляется столь серьёзной, в отличие от работы с множеством современных подключенных устройств, таких как автомобили, камеры видеонаблюдения и «умные дома». Многие из них имеют функции безопасности, встроенные в заводские чипы, а значит изменить их невозможно.

В любом случае первоначальные реализации будут гибридными, с использованием постквантовой технологии для дополнительной безопасности поверх существующих систем. Если всё пойдет по плану, к тому времени, когда вычислительная техника войдет в свою квантовую эру, интернет уже будет в постквантовой эре. Тогда для взлома криптосистем квантовым компьютерам потребуется примерно в тысячу раз больше вычислительных компонентов (кубитов), чем сейчас.

По оценкам исследователей, полный переход всех технологий на квантово-устойчивые займет как минимум пять лет. Но и в этом случае, когда наступает день Q-day, множество устройств и технологий останутся уязвимыми.

#технологии #криптография