Как квантовые компьютеры уничтожат и (возможно) спасут криптографию

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

Большинство секретов были защищены с помощью той или иной формы асимметричного шифрования с тех пор, как Уитфилд Диффи, Марк Хеллман и Ральф Меркл публично раскрыли эту концепцию в 1976 году в своей основополагающей статье под названием « Новые направления в криптографии» . Подумайте о RSA, SSL, TLS и HTTPS. Мы говорим о большинстве веб-сайтов, загрузках с цифровой подписью, финансовых онлайн-транзакциях, VPN, смарт-картах и ​​большинстве беспроводных сетей — все это может быть взломано в мгновение ока.

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

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

Возвращаясь к моему выступлению много лет назад: когда я отвечал на вопросы в конце презентации, меня спросили, сколько времени, по моему мнению, пройдет, прежде чем квантовые компьютеры станут достаточно хороши, чтобы раскрыть все эти секреты. Я сказал: «10 лет. Большинство экспертов по квантовой физике считают, что до этого осталось всего 10 лет». Когда я ушел со сцены, светило индустрии Брюс Шнайер последовал за мной. Он небрежно сказал мне, проходя мимо, не замедляя шага: «Как давно ты говоришь 10 лет?»

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

Как работают квантовые компьютеры

Ну, это уже не 10 лет. По словам доктора Марка Джексона, физика-теоретика и научного руководителя по развитию бизнеса в Cambridge Quantum Computing (CQC), до квантовых вычислений остается может быть четыре-пять лет, а в некоторых областях ограниченное коммерческое применение — например, квантовая химия — может даже быть возможно к середине 2021 года. Что изменилось? Что ж, теперь у нас есть множество квантовых компьютеров, устройств и программного обеспечения, достаточно сложных, чтобы быть полезными без так называемой «коррекции ошибок».

Квантовые компьютеры могут победить традиционные цифровые компьютеры благодаря принципу работы, который в них используется. Очевидно, что квантовые компьютеры опираются на квантовую механику (тема слишком обширная и сложная, чтобы ее можно было охватить здесь), но в двух словах их преимущество заключается в следующем. Цифровой компьютер является двоичным. Каждый транзистор или логический вентиль в своем центральном процессоре (ЦП) способен удерживать только одно «состояние» одновременно. Он может быть «открытым» или «закрытым», под напряжением или нет, иметь значение «1» или «0». Отсюда и слово двоичный.

Квантовые компьютеры основаны на так называемых квантовых битах (кубитах, qubits или qbits). Каждый кубит может находиться в обоих состояниях одновременно. Таким образом, один кубит эквивалентен двум двоичным логическим элементам. Кубиты становятся экспоненциальными по мере их добавления. Два кубита могут одновременно содержать четыре состояния, три кубита — восемь одновременных состояний и так далее.

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

Как и когда квантовые компьютеры смогут взломать криптографию с открытым ключом

Мы долго ждали, когда квантовые вычисления станут реальностью. Сколько? По крайней мере, с 1959 года, когда  доктор Ричард Фейнман прочитал об этом лекцию. Многие эксперты по квантовым вычислениям считают алгоритм доктора Питера Шора, выпущенный в 1994 году, настоящим началом квантовых вычислений.

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

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

Итак, на каком этапе жизненного цикла квантовых вычислений мы находимся? По словам доктора Джексона, для того, чтобы превзойти традиционные двоичные компьютеры, потребуется квантовый компьютер, имеющий «всего» 49 идеальных кубитов. Это известно как «квантовое превосходство» — переломный момент, когда квантовые компьютеры наконец станут более мощными, чем бинарные компьютеры. Это похоже на то, как суперкомпьютер IBM Deep Blue победил чемпиона мира по шахматам Гарри Каспарова в 1997 году.

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

В марте 2018 года Google анонсировала несовершенный 72-кубитный компьютер. Текущая (известная) реализация Google допускает ошибку примерно раз в 200 вычислений. Когда вы выполняете миллиарды вычислений в секунду, такой уровень ошибок становится катастрофой. Десятки, если не сотни миллиардов долларов по всему миру тратятся на создание более стабильных квантовых компьютеров. Некоторые говорят, что переход к 4000 кубитам уже не так сложен, как раньше.

Доктор Джексон, который непосредственно работает с квантовыми компьютерами, говорит: «Мы выросли с девяти до 72 кубитов всего за один год, так что совсем не безумие, что мы можем получить 4000 еще за пять [лет]. Учитывая, что правительство США, наконец, присоединилось к делу несколько месяцев назад, я думаю, что сейчас это консервативная оценка».

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

Доктор Ааронсон также был настроен скептически. Он написал: «Я буду удивлен, если это произойдет через пять лет. Я не могу сказать, что это невозможно, но ожидаю, что это займет немного больше времени. Я буду рад, если через три-пять лет Google, IBM и другие преуспеют в своих нынешних усилиях по созданию шумных 70-кубитных квантовых компьютеров и если они начнут превосходить классические компьютеры в некоторых (в основном искусственных) задачах. Даже если это так, это все еще далеко от угрозы для криптографии с открытым ключом из-за необходимости исправления ошибок и больших накладных расходов существующих схем отказоустойчивости, которые могут легко привести к требованию миллионов высококачественных физических кубитов».

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

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

Развивающаяся индустрия квантовых вычислений

Все большее число компаний и организаций — по крайней мере, 44 известных организации — пытаются создать квантовый компьютер. Четыре всемирно известные американские компании — это Google, IBM, Intel и Microsoft. Все большее число стартапов, похоже, также добиваются прогресса. Одна из них, фирма доктора Джексона, CQC, в настоящее время сотрудничает, в частности, с Google и IBM.

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

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

Общие методы квантовых вычислений включают сверхпроводимость, захват ионов и майорановские фермионы. Сверхпроводимость и захват ионов приводят к образованию наибольшего количества кубитов прямо сейчас. Для сверхпроводимости требуются очень низкие температуры, близкие к абсолютному нулю (около -460F или -273C), и полученные кубиты могут быть хрупкими и нестабильными.

Менее зрелый фермионный метод Майораны, используемый Microsoft, в настоящее время дает меньше кубитов, чем другие методы, но кажется гораздо менее хрупким. Доктор Джексон описал фермионный метод Майораны как заплетение косичек из волос. На них может воздействовать внешняя среда, но их квантовое состояние остается прежним. Доктор Джексон говорит: «Если бы мы могли заставить их работать в больших масштабах, они были бы явными победителями. Но мы знаем о них меньше».

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

Кембриджские квантовые вычисления (CQC)

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

CQC имеет собственный квантовый язык программирования и компилятор, который они называют «t|ket». Доктор Джексон говорит, что этот язык чем-то похож на C. Компилятор не зависит от платформы и работает со всеми типами квантовых компьютеров на базе множества различных платформ. Он работает для разделения вычислительных усилий между традиционным цифровым процессором и новым квантовым процессором (QPU).

Доктор Джексон говорит, что точно так же, как традиционный графический процессор (GPU) справляется с интенсивными графическими нагрузками или традиционный цифровой процессор (NPU) справляется с тяжелыми математическими нагрузками для обычного цифрового компьютера, QPU будет обрабатывать квантовые задачи.

Компилятор CQC передает вычислительные нагрузки, с которыми хорошо справляются традиционные цифровые компьютеры, на обычный процессор (CPU), а специализированные квантовые вычисления — на квантовый процессов (QPU). Затем результаты повторно синтезируются в общий выходной поток. «В ближайшее время вам не придется выбрасывать свои цифровые компьютеры. Они нам все еще нужны», — говорит доктор Джексон. Это отличная новость, потому что мне было интересно, как мы собираемся носить с собой компьютеры, которым нужны сверхнизкие температуры.

Проверенные генераторы случайных чисел

CQC также производит аппаратное обеспечение, в том числе «проверенный» квантовый генератор случайных чисел. Традиционные цифровые компьютеры никогда не были способны генерировать по-настоящему случайные числа. Это просто невозможно. Традиционные компьютеры управляются очень стабильными и предсказуемыми кварцевыми часами, которые определяют, насколько быстро и когда ЦП может перемещать информацию в регистры ЦП и из них. Каждый такт составляет то же количество времени, что и раньше. Это означает, что окончательный «источник истины», лежащий в основе любого традиционного генератора случайных чисел, предсказуем (т. е. не является по-настоящему случайным).

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

Национальный институт стандартов и технологий (NIST) обсудил необходимость создания генераторов действительно случайных чисел в апрельском номере журнала Nature за 2018 год. Оказывается, квантовые вычисления также очень хороши в генерации проверенных случайных чисел. Самые ранние поддающиеся проверке квантовые генераторы случайных чисел были очень большими (размером со здание длиной 200 метров) и довольно медленными.

Как случайные числа могут спасти криптографию в постквантовом мире

Компания CQC представила аппаратный прототип устройства «коробка для пиццы» под названием IronBridge, размером примерно с видеомагнитофон, который, как ожидается, будет генерировать около 4 миллионов случайных бит в секунду – этого достаточно, чтобы быть коммерчески жизнеспособным для поддержки протоколов шифрования, обеспечивающих квантовую безопасность сегодня. Ух ты! Действительно случайность всех этих чисел подтверждается математической и физической теоремой «Неравенство Белла» .

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

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

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

Источник: https://www.csoonline.com/article/565953/how-quantum-computers-will-destroy-and-maybe-save-cryptography.html