Квантовые компьютеры и конец безопасности

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

Мы живем в мире радиоволн и электромагнитных сигналов. Wi-Fi, GSM, спутниковое ТВ и GPS, точное время и FM-тюнер — лишь немногие из повседневных технологий, в которых используются электромагнитные волны. Конечно, в список нужно включить и все виды компьютеров, от гигантских дата-центров до смартфонов и ноутбуков. Одна из особенностей электромагнитных сигналов состоит в том, что их довольно легко измерить, то есть перехватить. Именно поэтому практически все вышеперечисленное сегодня снабжено технологией шифрования, защищающей информацию от чтения и изменения посторонними. При этом запасного канала связи обычно нет, и разработчики криптосистем блестяще решили сложную проблему — как договориться о секретном ключе шифрования, когда весь процесс переговоров могут слушать посторонние? Именно решение этой проблемы лежит в основе всех современных систем защиты, и именно ему предположительно положат конец квантовые компьютеры.  Спасет ли положение возникшая заодно квантовая криптография?

В чем соль

Название квантовых систем точно передает смысл — их работа основана на квантовых эффектах, таких как суперпозиция и спутывание (сцепление) микрочастиц.

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

Все кванты — в беленьком квадратике справа

Хозяйке на заметку. Современные системы, например лежащие в основе SSL, HTTPS, VPN и т.п., обычно шифруют все данные с помощью секретного ключа и симметричного алгоритма. Ключ одинаков у отправителя и получателя (отсюда название симметричный), устанавливается в начале сессии при помощи второй, асимметричной криптосистемы. Асимметричный алгоритм используется только для передачи секретного ключа в силу своей вычислительной сложности. Безопасность асимметричной криптосистемы основана на математической сложности решения той или иной задачи, например разложения на множители очень больших целых чисел (алгоритм RSA). Даже просто перемножить два больших числа относительно трудоемко, что уж говорить о переборе!  То есть речь идет о том, что шпион может перехватить сообщения, но на расшифровку уйдет неразумно много времени (от десятков до миллионов лет в зависимости от длины ключа). Как выясняется, квантовые компьютеры при помощи алгоритма Шора приходят к необходимому состоянию, соответствующему найденному решению математической задачи, существенно быстрее — почти так же быстро, как обычный компьютер проводит шифрование. Таким образом, несмотря на необходимость нескольких запусков и поддержку со стороны классических компьютеров,  квантовый компьютер может за очень короткое время подобрать числа для асимметричного алгоритма, что поможет атакующему извлечь секретный ключ и дальше спокойно расшифровывать основной обмен сообщениями. Качественные симметричные алгоритмы, например AES, кстати, не имеют особенностей, которые хотя бы теоретически приводили к таким опасным последствиям. В частности, квантовый компьютер, по имеющимся оценкам, может ускорить перебор ключей AES, но не радикально. Поиск 256-битного ключа AES  на квантовом компьютере эквивалентен поиску 128-битного ключа на обычном — вполне терпимо, запас прочности остается большим.

В чем трудность

Квантовый компьютер, быть может, давно стоял бы на столе каждого малолетнего хакера, желающего читать переписку одноклассников в «ВКонтакте», но создание компьютера сопряжено с рядом чисто инженерных сложностей, которые настолько велики, что некоторые специалисты считают создание «полноценного» квантового компьютера невыполнимой задачей. Главная проблема состоит в том, чтобы поддерживать кубиты в состоянии запутанности, поскольку любая квантовая система то и дело норовит «свалиться» в классическую, лишенную неопределенности. Тут нельзя не упомянуть многострадального кота Шредингера, который все же не может быть жив и мертв одновременно, а в квантовом компьютере это удивительное состояние должно поддерживаться достаточное время для прогона задачи и измерения результатов. Обычно речь идет о наносекундах, в лучших системах — единицах секунд. Сложность задачи растет с ростом числа кубитов. Для решения задач по взлому шифров нужен квантовый компьютер с 500–2000 кубитов (в зависимости от разрядности ключа в криптоалгоритме), в то время как большинство существующих систем оперируют с единицами кубитов (рекорд – 14 кубитов). Таким образом, взлом вашего SSL-сертификата на квантовом компьютере сегодня еще невозможен, но, возможно, будет реален уже через пять лет.

Главные популяризаторы науки и многострадального кота Шредингера — Пенни и Шелдон из «Теории Большого взрыва»

Шаги к цели

На фоне вышеописанных сложностей, с которыми сталкиваются почти все разработчики, очень вызывающе выглядят заявления физиков компании D-Wave, которая продает квантовые компьютеры из 512 кубит. Многие специалисты отрицают, что у D-Wave получился «настоящий» квантовый компьютер, поскольку он основан на эффекте квантового отжига,  но трудно спорить с деньгами — первыми клиентами, заплатившими до $10 млн за свой компьютер, стали гигант оборонной промышленности США Lockheed Martin и Google. Несмотря на все «но», компьютер решает определенный класс задач оптимизации явно квантовыми методами, то есть честно выполняет свою работу. Он не приспособлен для решения многих других «квантовых» задач, что признают и создатели, но практическую пользу уже приносит. Google планирует решать на компьютере задачи машинного обучения, а Lockheed Martin на ряде экспериментов убедились, что компьютер способен находить ошибки в программном коде сложнейших приложений, управляющих истребителями F-35.  Правда (и это хорошие новости для нас с вами), компьютер D-Wave плохо приспособлен для вышеописанных задач по факторизации, поэтому не представляет особой угрозы для современных криптоалгоритмов.  Угроза лежит в иной плоскости — работающий квантовый компьютер стимулирует большие компании и государства более активно вкладываться в разработки, ускоряя появление других видов квантовых компьютеров, которые способны подбирать криптоключи.

D-Wave Two — квантовый компьютер-отжигатель

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

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

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

Коммерческая система Cerberis для квантового распределения ключей

В отличие от квантовых компьютеров, квантовые криптосистемы уже давно не являются лабораторной инновацией. Хотя первые научные работы на эту тему появились тоже на рубеже 70–80-х годов ХХ века, до практического воплощения дело дошло быстрее. Первые лабораторные тесты прошли в 1989 году, а уже в конце 90-х функционировали коммерческие системы квантовой передачи ключей на расстояние от 20 до 50 км. Такие компании, как id Quantique и MagiQ Technologies, продают готовые системы передачи криптоключей по обычному оптоволоконному кабелю. Эти системы достаточно просты для установки обычным специалистом по прокладке компьютерных сетей. Соответственно, кроме разного рода военных и правительственных организаций их взяли на вооружение крупные коммерческие организации, банки и даже FIFA.

Идеальная защита?

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

В-третьих, хакеры от науки обнаружили, что, «ослепляя» фотодетекторы мощным лазером, можно манипулировать их показаниями, что позволяет фальсифицировать данные в системах квантового распределения ключей. Правда, эти уязвимости относятся к недостаткам реализации, а не концепции, они вполне устранимы в будущем. Но уже произошедшие взломы лишь демонстрируют, что квантовые системы тоже не являются панацеей и защита передачи данных, если и перейдет из рук математиков в руки физиков, останется острой проблемой на многие годы вперед. Ну и наконец, маленькая, но серьезная проблема — в отличие от имеющихся технологий, квантовые системы еще долго останутся нишевыми и не будут десятками установлены в каждой квартире, как это сегодня обстоит с Wi-Fi, GSM и прочими. А значит, математиков рано списывать со счетов — классические криптосистемы, работающие с любым каналом связи, останутся востребованными еще многие десятилетия. Просто для них придется подобрать математические алгоритмы, непосильные квантовым компьютерам.