Постквантовая криптография

Идет гонка на создание новых способов защиты данных и коммуникаций от угрозы, создаваемой сверхмощными квантовыми компьютерами.

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

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

Как работает цифровое шифрование?

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

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

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

Хакеры могут попытаться взломать код, попробовав все возможные варианты ключа, пока он не заработает. Но защитники действительно усложняют им жизнь, используя очень длинные пары ключей — например, 2048-битная реализация RSA, которая отображает ключ длиной 617 десятичных цифр. Выполнение всех возможных перестановок для получения закрытых ключей может занять многие тысячи, если не миллионы, лет на обычных компьютерах.

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

Потому что они могли бы помочь хакерам быстрее вернуться через алгоритмические ловушки. В отличие от классических компьютеров, которые используют биты, которые могут быть равны 1 или 0, квантовые машины используют кубиты, которые могут одновременно представлять многочисленные возможные состояния 1 и 0 — явление, известное как суперпозиция. Они также могут влиять друг на друга на расстоянии, благодаря явлению, известному как запутывание.

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

Хакеры также могут использовать квантовые алгоритмы, которые оптимизируют определенные задачи. Один из таких алгоритмов, опубликованный Ловом Гровером из Bell Labs компании AT&T в 1996 году, помогает квантовым компьютерам гораздо быстрее находить возможные перестановки. Другой, опубликованный в 1994 году Питером Шором, который тогда работал в Bell Labs и в настоящее время является профессором Массачусетского технологического института, помогает квантовым машинам невероятно быстро находить основные факторы целых чисел.

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

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

Это очень маловероятно. В исследовании, проведенном Национальными академиями, говорится, что для создания реальной угрозы квантовым машинам потребуется гораздо больше вычислительной мощности, чем достигали лучшие современные квантовые машины.

Тем не менее, то, что некоторые исследователи в области безопасности называют «Y2Q» — год, когда квантовый взлом кода становится основной головной болью — может неожиданно быстро подкрасться. В 2015 году исследователи пришли к выводу, что квантовому компьютеру понадобится миллиард кубитов, чтобы достаточно легко взломать 2048-битную систему RSA; Более поздняя работа предполагает, что компьютер с 20 миллионами кубитов может выполнить работу всего за восемь часов.

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

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

Что такое постквантовая криптография?

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

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

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

Цель состоит в том, чтобы сосредоточиться на одном или нескольких методах, которые могут быть широко приняты. Национальный институт стандартов и технологий США в 2016 году запустил процесс разработки стандартов для постквантового шифрования для государственного использования. Он уже сузил первоначальный набор из 69 предложений до 26, но говорит, что, вероятно, будет около 2022 года, прежде чем начнут появляться проекты стандартов.

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