Квантовые компьютеры УЖЕ ломают интернет [Veritasium]
[музыка] В эту самую секунду различные государства и некоторые люди перехватывают и сохраняют зашифрованные послания, пароли, данные банковской карты и номера соцстрахования. Прочитать эти файлы они не могут. Так в чем же смысл? В том, что лет через 10-20 может появится квантовый компьютер, способный расшифровать данные за считанные минуты. Такой подход называют "собирать сейчас, расшифруешь потом" или коротко, в этом есть своя логика.
Некоторые данные не потеряют ценности через десяток лет. Например, исследования в промышленности, фармацевтики или засекреченные разведданные об угрозе. Хорошо известно, что Агентство национальной безопасности считает, что если появится достаточно мощный квантовый компьютер, то опасность взлома всех алгоритмов с открытым ключом станет реальностью через 5-10 лет. В современном виде ждать таких квантовых компьютеров существуют уже сейчас.
По этой причине шифрование, которым мы пользуемся сейчас, отлично справлялось со своей задачей уже больше 40 лет. До 1970-х, чтобы обмениваться конфиденциальной информацией, сначала нужно было встретиться и лично передать ключ. Один и тот же ключ использовался для того, чтобы зашифровать, а потом расшифровать послание. Такая схема называется алгоритмом симметричного шифрования.
Никто не узнает, что в вашем сообщении, если не разгадает ключ. Но что если придется отправить весточку человеку, которого вы никогда не видели, и встретиться с ним сложно? Ключ нельзя продиктовать по телефону или отправить письмо. Это опасно, в таком виде его могут перехватить. В 1977 эту проблему решили Ривест, Шамир и Адлеман. Они разработали криптографический алгоритм, названный по первым буквам их фамилий, который работает примерно так: у каждого человека есть большие простые числа, которые они никому не раскрывают.
Эти числа перемножаются, что дает еще большее число, которое открыто всем желающим. Отправляя личное сообщение другому человеку, я шифрую его с помощью большого числа адресата так, чтобы расшифровать его можно было только зная два простых множителя, из которых это число получилось. Это алгоритм с асимметричным ключом. Защищенное сообщение шифруется с помощью одного ключа, расшифровывается с помощью другого.
Для адресата расшифровка не составит труда. Но вот постороннему человеку придется подбирать числа, из которых получился открытый ключ. Если бы кто-нибудь раздобыл суперкомпьютер, то мог бы это сделать с помощью общего метода решения числового поля. Современная криптография использует простые числа длиной около 314 знаков. Чтобы подобрать эти числа, зная лишь их произведение, даже у суперкомпьютера уйдет около [музыка].
Он ударит двух и трех. И если мы проведем такое же вычисление, как на обычном компьютере, то сразу возведем семерку во все доступные степени и получим суперпозицию всех результатов, а это 1749 и 343. Добавив всего лишь еще один кубик, мы удвоим количество возможных состояний. То есть три кубита вместе дадут 8 состояний, что позволит проводить 8 вычислений одновременно. Увеличим число кубитов всего до 20 и сможем одновременно представить больше миллиона состояний.
А значит, получить одновременно больше миллиона результатов. 300 кубитов дадут нам больше состояний, чем частиц во всей обозримой Вселенной. Звучит очень мощно и не без оснований. Но только есть один нюанс: все ответы упакованы в суперпозиции состояний, и просто так суперпозицию не прочитаешь. Совершая измерения, мы получаем только одно случайное значение из возможных, вся остальная информация теряется.
Чтобы обуздать квантовый компьютер, нужен способ перевести суперпозицию состояний в ответ, в котором будет только нужная нам информация. Это очень сложно и потому для большинства привычных нам дел квантовые компьютеры бесполезны. Круг задач, где уже научились извлекать нужный ответ, довольно узок. Но именно эти задачи лежат в основании всей современной криптографии.
Вот так нам повезло. В 1994 Питер Шор и Дон Копперсмит адаптировали преобразование Фурье для квантовых вычислений. Работает все так же, как и в обычном преобразовании. Применяем его к некоторому периодическому сигналу и получаем частоты, которые он содержит. Может звучит не очень увлекательно, но не торопитесь скучать.
При суперпозиции состояний, обладающих некоторой периодичностью, то есть содержащих какой-то параметр, меняющейся с постоянным шагом, преобразование Фурье позволит узнать, так сказать, "чистоту" сигнала, которую мы можем измерить. Квантовое преобразование Фурье позволяет узнать частоту периодически суперпозиции. Почему же квантовый компьютер подбирает простые множители для больших чисел быстрее обычного?
Для начала объясню базовые принципы на примере безо всяких квантовых компьютеров, а потом покажу, как за очень короткое время квантовый компьютер справляется даже с очень большими числами. Возьмем некое число N, которое является произведением двух простых чисел P и Q. Для наглядности присвоим N значение 77. Готов поспорить, что вы уже догадались, чему равны P и Q, но пока притворимся, что они нам неизвестны.
Будь это большие простые числа, мы бы их не знали. Сейчас надо вспомнить один математический фокус. Возьмите G — какое-нибудь число без общих множителей с N. Если много-много раз множить G на самом себя, то рано или поздно получится число, равное произведению некоего M на N + 1. Иными словами, есть такое число G, что если возвести G в степень R, получится M/N + 1.
Посмотрим, что это значит. Берем любое число меньше 77, например 8. Общих множителей у них нет. И если N — произведение двух больших простых чисел, G можно брать любое, почти наверняка общих множителей с N у него не будет. Умножьте 8 на само себя один раз, два, три, четыре раза и так далее, увеличивая степень все больше и больше, а затем делите каждый результат на 77. Не так важно, какая будет в ответе целая часть, нас интересует остаток.
Потому что рано или поздно получится так, что он окажется равен единице. Посмотрим. 8 делить на 77 — 0 и 8 в остатке. 64 на 77 — это 0 в остатке, 64 делим на 512, получаем 6 в остатке 50. Идем дальше и получаем в остатках 15, 43, 36, 57, 71, 29 и наконец 1. Вот мы до этого и дошли: 8 в десятой степени на единицу больше, чем M на 77.
Мы нашли степень R, которая удовлетворяет условиям уравнения. Но как это поможет разложить на множители? Нам просто надо привести уравнение, один переносим в левую часть, потом разбиваем ее на два сомножителя, и тогда, если R четное, получается целое число на целое число, равное произведению M и N. На вид очень напоминает, P на Q равно N.
Раз уж мы знаем, что P и Q находятся в правой части уравнения, то они же должны быть и в левой, просто там они еще на что-то умножены. Разберемся в том, что мы наделали. Мы взяли какое-то случайное значение G и, найдя степень R, получили два числа, у которых с большей вероятностью найдутся общие множители.
Цен R равен 10. Со множителями в нашем случае будут 8 в 5 плюс 1, это 32,769 и 8 в 5 степени минус 1, или 32,767. У этих двух чисел вполне вероятно должны найтись общие множители. Как их найти? Тут нам поможет алгоритм Евклида. Чтобы найти наибольший общий делитель для двух чисел, таких как, скажем, 32,769 и 77, нужно сначала поделить большее число на меньшее, записать остаток. Так и сделаем. В остатке при делении этих чисел у нас получится 44.
Затем нужно сдвинуть все на одну позицию влево и еще раз поделить. Делим 77 на 44 и в остатке получаем 33. Повторяем те же действия еще раз: 44 делим на 33, в остатке дадут 11, и, наконец, 33 делится на 11 без остатка. Когда в остатке оказывается 0, под чертой последней операции мы видим наибольший общий делитель двух исходных чисел. В нашем случае 11, и на это число действительно без остатка делится 77 и 32,769.
То же самое можно проделать со вторым сомножителем уравнения. Или что проще: поделить 77 на 11, получим 7. Если нам придется искать простые множители PQ, для начала можно взять случайное значение G. Затем выяснить, сколько раз нужно умножить, чтобы получить шаг 3. С помощью полученной степени найти два числа, у которых могут быть общие множители, и, наконец, с помощью алгоритма Евклида вычистить общие множители этих чисел и N.
Таким образом, мы вероятно найдем P и Q. Чтобы произвести все эти действия, квантовый компьютер не нужен. Но на обычном компьютере этот способ будет работать не быстрее, чем любые другие. Однако квантовые компьютеры ускоряют второй этап этого процесса: поиск степени, в которой нужно возвести G, чтобы получить произведение N + 1.
Чтобы разобраться, каким образом, вернемся назад. Мы только что выяснили, что восемь в десятой степени дает M на N + 1. Вот что будет, если мы пойдем дальше по этой таблице: 8 в 11, в 12 и так далее, мы получаем следующие остатки: 8, 64, 50, 15, 43, 36, 57, 71, 29 и снова 1. У остатков есть цикл, они будут так повторяться и дальше.
Обратите внимание: остаток 1 получается, когда 8 стоит в двадцатой степени. На 10 больше, чем когда единица встретилась впервые. Так будет каждый раз: 8 в 30, 840 и 8 в любой степени кратной 10 при делении на 77 в остатке даст единицу. Отметим еще, что выбрав любой остаток, например 15, мы также будем встречать его через каждые 10 степеней. Получается степень, которая даст нам плюс 1, равна промежутку между любыми одинаковыми остатками. Не только единицами это важно.
Вот остатки деления, расположенные на логарифмической шкале. Здесь хорошо видно циклы в 10 шагов. Если бы я изначально выбрал другой G — не 8, а, скажем, 15, — период был бы другой, остатки были бы другие. Но где-то всё так же была бы единица. Но почему мы знаем, что все значения остатков цикличны? Если заглянуть на самое начало, там должно быть G в степени 0, а это всегда единица. То есть один — это самый первый остаток, которым будет открываться каждый новый цикл.
Что ж, теперь мы готовы взять квантовый компьютер и найти множители произведения двух простых чисел. Сначала разделим кубиты на два набора. Первым будет суперпозиция и значение 0, 1, 2, 3, 4, 5, 6, 7, 8 и так до 10 в степени 1234. Да, просто умопомрачительной суперпозиции. Но если бы у нас были идеальные кубиты, их нам понадобилось бы всего 4,100. Второй набор меньше по объему и состоянию.
Все кубиты одинаковые, но теперь берем G. Чтобы не выбрали, скорее всего, общих множителей с N не будет. Возводим G во все степени, записанные в состоянии первого набора кубитов. Но нельзя просто так взять и измерить эту суперпозицию. Так мы получим разве что случайное число, которое ни о чем не скажет.
Но можно применить один приемчик: если измерить не всю суперпозицию, а только набор с остатками, мы узнаем значение одного из них. Но этот остаток будет встречаться снова и снова по одному разу. Каждому цикле. Вот что будет, если взять числа из нашего примера: N78, G8. Допустим, мы получили остаток 15. Суперпозиция будет встречаться регулярно, ведь получить его можно возводя G в разную степень.
Например, степень 4, 14, 24, 34 и так далее. Это период шагом в 10 степеней, и 10 это как раз нужное значение R в нашем уравнении. В общем, так или иначе, мы получим суперпозицию состояния с одинаковым остатком, а связанные с ними степени будут находиться друг от друга на расстоянии R. Это и есть число, которое мы ищем. Раз остаток одинаковый, про него можно забыть: мы получили периодическую суперпозицию, которой все элементы разделены расстоянием R. Применяем квантовое преобразование Фурье, и сейчас я немного упрощаю.
У нас останутся состояния, которые будут содержать единицу, деленную на R. Теперь нам остается только найти R путем инвертирования. Вот и вся квантовая часть. Если R четное число, мы можем спокойно взять в качестве G любое число и получить значение, у которых N могут найтись общие множители. Если сомножители сами не равны, M на N, мы можем использовать алгоритм Евклида, чтобы найти множители N и взломать шифр. Для этого нужны всего несколько тысяч идеальных кубитов, но пока таких у нас нет.
Нужны дополнительные кубиты, они работают как вспомогательная информация. По оценкам 2012 года, чтобы взломать шифр с открытым ключом, понадобится миллиард физических кубитов. Спустя 5 лет это число упало до 230 миллионов, а в 2019 после ряда заметных достижений в квантовых технологиях говорили уже от 20 миллионов физических. Но сколько кубитов мы можем себе позволить сегодня? Если говорить, например, об успехах, мы даже близко не подошли к 20 миллионам.
Но похоже, прогресс идет экспоненциально. Вопрос только в том, когда этот момент ознаменует крах современного шифрования. Об этой опасности уже хорошо известно, поэтому ученые уже давно взялись за поиск способов защитить данные от обычных и от квантовых компьютеров. В 2016-м Национальный Институт стандартов и технологий запустил конкурс, суть которого была в том, чтобы разработать алгоритмы, устойчивые ко взлому с квантового компьютера. 82 варианта, которые предложили специалисты со всего мира, подверглись испытанию.
Некоторые из них не прошли. 5 июля 2022 Институт стандартов и технологий назвал четыре варианта, способных противостоять квантовой угрозе. Как работают эти алгоритмы? Три из них построены на основе решётки. Давайте посмотрим на простой образец такой решетки в двухмерном пространстве. Есть два вектора. Складывая разные произведения этих векторов на целые числа, например 3 на R1 или 1 на R2, вы оказываетесь в разных точках. Все точки, которые можно получить таким образом, и будут называться решеткой.
Давайте поставим сюда точку C. Как думаете, какая комбинация векторов R1 и R2 приведет нас в точку на решетке, максимально близкую к точке C? Вполне очевидно, что быстрее всего будет взять два вектора R2 и 2 вектора минус R1. Ничего сложного. Но такую решетку нам могут дать не только векторы R1 и R2. Вот B1 и B2, например, они дадут точно такую же решетку.
Если я задам тот же вопрос, можете подсказать комбинации этих векторов, которые приведут нас к ближайшей точке? Задачка усложнилась. Но почему? С каждым шагом приближаемся к цели, либо по оси X, либо Y, используя векторы B. Каждый раз, подходя ближе по одной оси, мы оказываемся дальше по другой. Поэтому, с векторами B решить задачу сложнее. Чтобы попасть в нужную точку на решетке, нам понадобится 8B1 и 6 минус B2.
Довольно неудобно, но все-таки долго головой ломать не пришлось. Если же переместиться в трехмерное пространство, сразу становится гораздо труднее. Особенно учитывая, что полной решетки со всеми точками у нас не будет, только построившие ее векторы. Поэтому, найдя точку на решетке рядом с нужной, нужно будет еще проверить все точки вокруг, чтобы убедиться, что ваше ближайшее.
Возьмем окружность радиусом R. В двухмерном пространстве число точек на решетке будет пропорционально квадрату радиуса, в трехмерном пространстве их число будет пропорционально радиусу в кубе. Только посмотрите, как растет количество точек, если увеличивать число измерений. Проложить путь в ближайшую точку в трех измерениях — эта задача, с которой компьютер справляется даже при 100 измерениях, она вполне решаема.
Но в будущем предлагается использовать алгоритмы, в которых придется решать задачу примерно в 1000 измерениях. Делая один шаг в нужном направлении, и возможно, совершая 999 шагов не в ту сторону, чуть-чуть выигрываем, но проиграть можем неизмеримо больше. С таким количеством измерений, даже для очень мощного компьютера, становится сложно найти ближайшую точку. Разве что у вас есть удобный набор векторов.
И как это использовать? Шифрование данных. Вернемся к нашему двухмерному примеру. У каждого из двух пользователей есть свой набор удобных векторов, которые описывают решетку, но они никому их не показывают. Другим доступны только варианты похуже. Если я захочу отправить кому-нибудь сообщение, я отмечу точку на решетке адресата и присвою этой точке значение семь. Если я захочу отправить кому-нибудь семёрку, я укажу на эту точку, но добавлю немного шума.
Тогда сообщение будет попадать не строго в эту точку, а где-то рядом. Чтобы расшифровать сообщение, получателю нужно будет найти точку, ближайшую к той, что я послал. Тысячи измерений сделать это невероятно трудно всем, кроме того, кому это сообщение предназначалось. Ведь у него есть удобные векторы. То есть расшифровать послание будет довольно просто для адресата и только для него. Насколько известно, сейчас как для обычных, так и для квантовых компьютеров, эта задача будет крайне тяжелой.
Целое воинство исследователей, математиков и программистов давно заняты вопросом, как сохранить в тайне ваши данные. Это невоспитанные герои, которые оберегают наше спокойствие, защищают нас от вмешательства.