Пора паниковать? Как человечество готовится к квантовому апокалипсису, который может наступить уже совсем скоро

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

Нас определенно ждет Q-day — день, которого в кругах кибербезопасности опасаются больше всего. Это момент, когда практически все современные методы защиты станут абсолютно бесполезными.

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

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

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

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

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

Именно поэтому инженеры уже активно работают над созданием и внедрением постквантовой криптографии. Журнал Nature подробно рассказал о том, как сейчас продвигается работа в этом направлении.

В 1976 году трое американских ученых-компьютерщиков — Уитфилд Диффи, Мартин Хеллман и Ральф Меркл создали концепцию шифрования с открытым ключом, которая впервые позволила людям обмениваться информацией без опаски быть «подслушанными» в интернете.

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

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

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

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

В 2015 году Агентство национальной безопасности США заявило об уязвимости существующих криптографических систем. Через год NIST (Национальный институт стандартов и технологий в США) предложил всем желающим инженерам представить потенциальные постквантовые алгоритмы. 82 команды с разных стран мира представили свои алгоритмы, из которых отобрали 65. После начала «конкурса», инженеры начали взламывать алгоритмы друг друга, а со временем список сократился до 15. Уже скоро NIST объявит о результатах исследования и сообщество получит первые алгоритмы, прошедшие проверку.

Большинство алгоритмов, попавших в «полуфинал», прямо или косвенно опираются на криптографию на основе математики решеток. Она использует наборы точек, которые располагаются на пересечениях прямых линий (решетки), которые проходят через пространство. Чем больше измерений в решетке — тем больше времени занимает ее декодинг.

Самым популярным подходом этого направления является обучение с ошибками (LWE — learning with errors). В своей простейшей форме он опирается на арифметику.

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

Одед Регев, исследователь компьютерных наук из Нью-Йоркского университета и создатель алгоритма, называет это «школьным уровнем математики». Благодаря этому подобный способ защиты легче, чем алгоритмы на основе математики решеток, поскольку он не имеет отношения к векторам, но при этом остается настолько же защищенным.

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

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

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

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

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

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

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

Автор: Кирилл Чеботарев для НВ