Может ли квантовый компьютер расшифровать
За последний год сразу несколько групп, включая такие большие компании как IBM и Google, объявили о создании квантовых компьютеров, содержащих более 50 кубит и потенциально способных выполнять универсальные вычисления. В то же время, вы, возможно, слышали, что одна из вещей, которые квантовые компьютеры делают лучше, чем классические, — это взлом ключей, шифрующих информацию в современных системах связи. Означает ли это, что пора беспокоиться о сохранности денег на наших счетах?
Что сейчас?
Уже этот пример демонстрирует, что, как минимум, не всякий шифр окажется по зубам квантовым вычислениям. Однако наиболее распространёнными всё же являются не AES или подобные стандарты, а шифрование с открытым ключом .
Уверенность, что даже зная открытый код никто не сможет расшифровать послание, основана на математической уловке, называемой односторонние преобразования. Оказывается, существуют математические операции, которые легко и быстро выполняются в одну сторону, но очень сложны с вычислительной точки зрения для выполнения в обратную.
Например, есть быстрый алгоритм поиска очень больших простых чисел. Однако если два таких числа перемножить, то чтобы найти что это были за числа, когда известно только их произведение, требуется перебрать все простые числа подряд. И это занимает совершенно нереальное для современных компьютеров время. На этом основан самый популярный метод шифрования с открытым ключом RSA .
Задача разложения больших чисел на простые множители, однако, относится к классу задач, называемых задачами со скрытой подгруппой. Группа — это термин, который обозначает определённую математическую структуру, а скрытая подгруппа — это другая структура, которая входит в состав группы, но не может быть извлечена простым способом. В примере с разложением числа на множители группу образует операция умножения, а простые множители образуют скрытую подгруппу.
Квантовые компьютеры называют угрозой для классического шифрования, поскольку доказано, что они могут решать задачу поиска скрытой подгруппы экспоненциально быстрее, чем классические компьютеры. Например, чтобы разложить на множители число из 2¹⁵³⁶⁰ цифр классическому компьютеру требуется перебрать порядка 2²⁵⁶ простых чисел. Квантовый же компьютер справится с этой же задачей за время, эквивалентное перебору всего лишь 20 000 ключей! И это, очевидно, огромная разница.
Как решить проблему?
Так, означает ли это, что классической криптографии пора на свалку? Не совсем. Хотя некоторые, действительно, призывают переходить на квантовое шифрование, которое в принципе не может быть взломано так, чтобы об этом не стало известно участникам общения, классические шифры тоже можно сделать квантово-устойчивыми.
Дело в том, что не все односторонние преобразования приводят к задачам со скрытой подгруппой. Примером может служить криптография на решётках . Она основана на задаче поиска кратчайшего расстояния между двумя узлами скошенной решётки, построенной в n измерениях.
Сверху — решётка Алисы со скошенными углами, снизу — решётка Боба с прямыми углами. Положения узлов для обеих решёток совпадают.
Сверху — решётка Алисы со скошенными углами, снизу — решётка Боба с прямыми углами. Положения узлов для обеих решёток совпадают.
Идеальная защита?
Хотя в теории квантовые системы связи не позволяют скрытно перехватывать информацию, практические реализации нельзя назвать неуязвимыми. Во-первых, проблема помех и большого расстояния не позволяет передавать единичные фотоны. Конечно, их число сводят к минимуму, но, раз фотонов больше одного, появляется теоретическая возможность перехватить один фотон и считать его состояние, не трогая остальные. Во-вторых, примерно стокилометровый лимит расстояния для работы квантовых систем резко сужает спектр использования технологии. Даже если пользователи готовы раскошелиться на прямой оптоволоконный канал между ними, географически разнесенные точки общаться без «репитера», промежуточной точки, не смогут, а это очевидно уязвимое место для прослушивания и атаки «человек посередине».
Квантовые криптосистемы являются неуязвимыми только в недостижимых идеальных условиях. Поэтому традиционные средства защиты рано списывать со счетов.
В-третьих, хакеры от науки обнаружили, что, «ослепляя» фотодетекторы мощным лазером, можно манипулировать их показаниями, что позволяет фальсифицировать данные в системах квантового распределения ключей. Правда, эти уязвимости относятся к недостаткам реализации, а не концепции, они вполне устранимы в будущем. Но уже произошедшие взломы лишь демонстрируют, что квантовые системы тоже не являются панацеей и защита передачи данных, если и перейдет из рук математиков в руки физиков, останется острой проблемой на многие годы вперед. Ну и наконец, маленькая, но серьезная проблема — в отличие от имеющихся технологий, квантовые системы еще долго останутся нишевыми и не будут десятками установлены в каждой квартире, как это сегодня обстоит с Wi-Fi, GSM и прочими. А значит, математиков рано списывать со счетов — классические криптосистемы, работающие с любым каналом связи, останутся востребованными еще многие десятилетия. Просто для них придется подобрать математические алгоритмы, непосильные квантовым компьютерам.
Разбираемся, как разные сервисы защищают ваши данные с помощью шифрования и что могут изменить квантовые компьютеры.
Недавно мы вам рассказывали об особенных квантовых компьютерах, которые могут очень быстро решать очень сложные задачи — такие, над которыми даже суперкомпьютер надолго задумается. Правда, задачи эти пока далеки от жизни, а сами квантовые системы во многом ограничены. Но прогресс не стоит на месте, и может оказаться, что в будущем эта технология захватит мир. Рассказываем, как это повлияет на нашу с вами безопасность.
Что дальше?
Почему же до сих пор используются методы шифрования из семейства RSA? В первую очередь из-за их простоты. Ну и надо понимать, что квантовые компьютеры всё же пока далеки от того, чтобы эффективно их взламывать. Лучшее, что они на данный момент смогли, — это разложить 15 на 5 и 3. Для этого потребовалось пять кубит. На большем количестве кубит задачу разложения числа на множители пока делать не пытались.
Тем не менее, Национальный институт стандартизации и технологий США NIST в 2016 году запустил программу проверки квантово стойких шифров. Программа должна продлиться от 4 до 6 лет.
Это вполне разумный срок. С одной стороны, специалистам требуется время, чтобы проверить возможные пути взлома предложенных алгоритмов. Например, в 2014 году британские шифровальщики предложили основанный на решётке метод шифрования, который казался квантово устойчивым, однако через несколько лет удалось показать, что его расшифровка сводится к классу задач со скрытой подгруппой, и поэтому уязвима для квантовых компьютеров.
С другой стороны, вряд ли можно ожидать, что в ближайшие 5—10 лет появятся квантовые компьютеры, способные взламывать современные шифры на основе RSA. Так что опасности для ваших кредитных карт достижения в квантовых вычислениях пока что не представляют.
Теоретически квантовые компьютеры будут способны быстро решать задачи, на которые у суперкомпьютеров уходили бы тысячи лет. Эта технология может изменить привычный нам мир. Популярно о квантовых компьютерах рассказывает Евгений Глушко в очередном выпуске на канале наших друзей Sci-One TV. Текстовую версию — как и всегда — читайте под катом.
Обычному пользователю квантовый компьютер ещё долго будет не нужен, может быть даже никогда. Но с его помощью уже сегодня можно поставить на колени всё и всех, кто зависит от интернета: например, мировые банки и любые современные финансовые системы. Ну или просто можно узнать всё, что от вас пытаются скрыть другие люди.
В 90-х годах прошлого века американский математик Питер Шор придумал квантовый алгоритм, который способен очень быстро разложить большущее число на два простых сомножителя. Казалось бы, кому это вообще надо? К сожалению, обычные компьютеры (как и суперкомпьютеры) справляются с этой задачей из рук вон плохо. Т.е. разложить число 15 в произведение 3*5 они могут, а вот если в числе 100 или 1000 знаков, то уже не очень. Чисто технически они могут это сделать — просто переберут все комбинации, но на это уйдёт не один миллион лет. И эту слабость классических компьютеров используют современные криптографические алгоритмы. На сегодняшний день практически вся ценная информация, которая передаётся через интернет, зашифрована с таким расчётом. Это и банковские транзакции, и секретные переговоры, и даже ваша переписка в социальных сетях. Расшифровать всё это с помощью классических компьютеров практически нереально. Теперь представьте, что кто-то вдруг создал квантовый компьютер и запустил на нём алгоритм Шора. И тогда любая зашифрованная в мире информация станет для него доступна.
Но этому можно помешать. Например, с помощью квантовой криптографии, когда информация зашифровывается в квантовое состояние отдельных фотонов. Так что вам будет не обойтись без квантового компьютера. А квантовый компьютер невозможен без кубитов. Кубиты — квантовые биты — такие же элементарные блоки квантового процессора, как транзисторы в процессорах обычных компьютеров. Нужно различать теоретическое понятие кубита, как единицы квантовой информации, и физическое воплощение кубитов, для которого могут быть использованы различные физические системы — фотоны, ионы, спины ядер и электронов. Сегодня больше всего надежд возлагается на сверхпроводящие кубиты.
Но как работает кубит? Всем нам знакомы биты — нули и единички, которые обрабатываются обычными компьютерами. Квантовые биты очень на них похожи (хотя и не без квантовых странностей). У них тоже есть два основных состояния — 0 и 1, но, благодаря особому квантовому свойству — суперпозиции — они могут находиться в любом из состояний между нулем и единичкой.
Суперпозиция наглядно показана в знаменитом мысленном эксперименте с котом Шрёдингера: кот в закрытом ящике одновременно и жив, и мёртв, пока мы не откроем крышку и не посмотрим на него. Так же и с кубитами — они могут находиться в произвольном состоянии между нулём и единицей. Но когда мы измерим их, то всегда с определённой вероятностью получим либо 0, либо 1.
Кстати, кубиты были одной из любимых тем Фейнмана! В 1980-х годах он предложил использовать существующие в природе квантовые системы с двумя состояниями (двухуровневые системы), чтобы симулировать сложные для классических компьютеров задачи. Правда, сам он не знал слово «кубит» — оно было придумано чуть позже Стивеном Визнером. А кубит Визнер придумал для обозначения квантовых денег.
Как создать кубиты? Уже предложено множество разных решений: квантовые точки, захваченные ионы, дефектные алмазы, фотоны и, конечно же, сверхпроводящие схемы, которыми занимаемся мы с коллегами. И нам удалось создать первый в России сверхпроводящий кубит. Достоинства такого типа кубитов очевидны — это большие квантовые объекты, которые можно спокойно поместить на чип и не беспокоиться, что они куда-то улетят, подобно атомам или ионам. Их можно размещать как угодно и в каком угодно количестве, а также точно контролировать их параметры. Подобная искусственная квантовая система — наиболее вероятный кандидат для построения квантового компьютера. А ещё сверхпроводящие кубиты очень похожи на существующие процессоры, поэтому не составит большого труда наладить их полномасштабное производство.
Сверхпроводящий кубит — это просто кольцо из сверхпроводника (металла, по которому электрический ток может течь без потерь). Но можно заметить и несколько особенностей. Они называются джозефсоновскими переходами и представляют собой два кусочка сверхпроводника, разделенных тонкой прослойкой изолятора. Пары электронов могут без проблем проникать через эту прослойку благодаря квантовому туннелированию. Благодаря джозефсоновским переходам мы можем управлять энергетическими уровнями в наших кубитах, подстраивая их необходимым образом. К примеру, когда ток в кольце течёт по часовой стрелке, кубит находится в состоянии 0, а когда против часовой — в состоянии 1. Но и это всё в теории. Как же практически создать такие структуры? Здесь на помощь приходит электронная литография — рисование пучком электронов по чувствительной поверхности. Таким способом можно создавать невероятно маленькие структуры размером вплоть до 10 нанометров!
Когда нужная структура нарисована, на поверхность чипа напыляется металл (например, алюминий). И сверхпроводящий кубит готов! Потом его нужно измерить. Для этого мы помещаем чип в большой криостат. Это тот же холодильник, только очень дорогой и работающий на смеси жидкого гелия. Он позволяет получать крайне низкие температуры — вплоть до одной сотой градуса выше абсолютного нуля! Это в сто раз холоднее, чем в самом холодном месте во Вселенной! Зачем нужны такие низкие температуры? Во-первых, чтобы сверхпроводники, из которых сделан наш чип, начали сверхпроводить — чтобы электроны объединились в пары и стали двигаться согласованно и без потерь энергии. Во-вторых, чтобы максимально изолировать нашу хрупкую квантовую систему от внешнего мира. В первую очередь — от теплового шума — злейшего врага любой «квантовости».
Собственно, это одна из проблем, из-за которой до сих пор не удалось создать настоящий полноценный квантовый компьютер. Вы, наверное, слышали, что компания IBM объявила о наступившей эре квантовых компьютеров и даже дала всем желающим доступ к одному такому через интернет. Но это пока больше реклама, хотя и основанная на серьёзной научной работе. Правда в том, что инженеры IBM собрали процессор всего из 5 кубитов, на котором ничего серьёзного запустить нельзя (для этого их нужно несколько сотен). Хрупкость кубитов мешает нам вступить в новую эру. А когда их соединяют вместе, время жизни кубитов стремительно уменьшается.
Происходит это потому, что кубиты — хрупкие квантовые системы, которые желательно максимально изолировать от окружающего мира (тогда они смогут сохранять своё квантовое состояние). А когда рядом с ними мы сажаем ещё кубиты, они неизбежно начинают взаимодействовать друг с другом, и квантовое состояние каждого из них разрушается. И чем больше их будет рядом — тем быстрее оно будет разрушаться.
Любители компьютерных игр наверняка спросят: и столько сил ради компьютера, на котором даже Доту или Майнкрафт не запустить? Про шифрование я уже говорил. Но важно и другое. Создав квантовый компьютер, мы сможем выиграть в скорости решения пусть всего нескольких, но крайне важных для современной цивилизации видов задач:
- быстрый поиск по гигантским базам данных (а их становится всё больше);
- оптимизация грузоперевозок (задача коммивояжёра);
- ускорение и удешевление поиска новых лекарств и материалов, например, высокотемпературных сверхпроводников.
Полезные ссылки:
Парадоксы и загадки квантовой физики будоражат умы ученых уже давно. Сегодня на основе необычных свойств квантовых частиц строятся новые приборы и устройства, которые могут по своим характеристикам многократно превосходить классические аналоги.
С рассказом о событиях в “Квантовой отрасли” перед сотрудниками Acronis выступил научный руководитель группы «Квантовые информационные технологии» РКЦ Алексей Федоров. В этом посте мы приводим расшифровку его лекции о квантовых технологиях с дополнениями, чтобы поделиться полезными и интересными данными с подписчиками Acronis на Habrahabr.
Крупномасштабные проекты реализуются в США, Европе, Китае и России. Наибольший интерес представляет собой квантовый компьютер — в гонку за его построением вовлечены не только университеты, но также и крупные корпорации среди которых Google, IBM, Microsoft и Intel. Прогнозируется, что квантовые компьютеры могут совершить революцию в целом ряде направлений, например, в защите информации, искусственном интеллекте и моделировании новых материалов.
В современном контексте квантовые технологии — это методы управления индивидуальными квантовыми объектами, такими как атомы, фотоны, электроны, ионы и так далее. В отличие от классических систем, находящихся всегда в одном из возможных состояний, квантовые системы могут быть в состоянии квантовой суперпозиции: находиться одновременно во всех допустимых состояниях. Примером различия между классическим миром и квантовым может быть монетка. У монетки можно определить два состояния — орел или решка — и закодировать их как 0 и 1. Тогда классическая монетка может находиться либо в состоянии 0, либо в состоянии 1. Две монетки — в одном из 4 возможных состояний в один момент времени. Четыре монетки — в одном из 16 состояний. Десять монеток — в одном из 1024 состояний.
Принцип суперпозиции позволяет одной “квантовой монетке” быть не только строго орлом или решкой, но и находиться в одном из бесконечного числа «промежуточных» состояний между орлом и решкой. Точнее будет сказать, что квантовая монетка может находиться в состоянии орла и решки одновременно. При этом две несовместимые с классической точки зрения альтернативы (выпавшая орлом монетка и выпавшая решкой монетка) как бы накладываются друг на друга внутри единого квантовом состояния. Это то, что ученые называют квантовой суперпозицией, и то, что наш мозг, выросший в классическом мире, даже не способен представить — к этому можно только привыкнуть. При этом, чтобы полностью описать такое квантовое наложение требуются два комплексных числа, соответствующих каждой из классически различимых альтернатив. Две “квантовые монетки” могут находиться в суперпозиции из 4 состояний. А 10 “квантовых монеток” — в суперпозиции из 1024 состояниях. Такие “квантовые монетки” называют кубитами — квантовыми аналогами битов информации. Для описания системы из n кубит требуется 2^n комплексных числа.
Основная фишка квантовых вычислений состоят именно в этом: с ростом числа кубитов количество параметров, которым мы оперируем при вычислениях, растет экспоненциально. При наличии даже 50 кубитов количество комплексных чисел, необходимых для описания их состояния — 2^50 — будет настолько большим, что точно промоделировать такую систему будет невозможно даже на самом мощном суперкомпьютере. Такой порог является одним из возможных объяснений для явления, называемого квантовым превосходством (quantum supremacy или quantum advantage): возможности при помощи квантового компьютера решать те задачи, на которые не способны существующие классические компьютеры.
Квантовый квест и квантовая гонка
Однако построить такой компьютер непросто. Для этого нужно решить целый “квест” по управлению квантовой материей. В данный момент множество лабораторий в мире разрабатывают новые методы управления квантовыми объектами. Квантовая гонка идет одновременно и среди корпораций, и в научном сообществе. Ведущие разработчики представляют все новые и новые решения. Но квантовая гонка имеет важное фундаментальное значение — за порогом квантового превосходства нас ждут новые открытия в совершенно различных областях физики: от физики низких температур до физики высоких энергий. К тому же у квантовых компьютеров также большой потенциал для решения практических задач, поэтому в его разработку включились корпорации.
В чем же заключается квест по управлению квантовой материей? С одной стороны необходимо иметь достаточно большое число кубит, чтобы обеспечить большое пространство состояний, но, с другой стороны, необходимо контролировать каждый кубит в отдельности. Ясно, что чем больше система, тем сложнее она поддается управлению на уровне отдельных индивидуальных компонентов. Эта особенно важно для квантовой физики, но, если задуматься, то касается и других сфер деятельности человека. Например, если вы хотите создать огромную и крутую компанию, вам придется нанять много талантливых людей. Но чем больше будет этих людей, тем сложнее окажутся их взаимодействия, и тем сложнее будет их контролировать :-)
В квантовом мире поиск баланса между масштабом и предсказуемостью — самый большой челлендж на сегодня. Но, преодолев его, мы сможем разрабатывать мощные квантовые компьютеры, способные решать интересные задачи. Например, в IBM используют термин квантовый объем — это количество кубит на количество ошибок при совершении операции. Это очень наглядная мера, она показывает, что недостаточно просто сказать сколько в системе кубитов, важна еще и степень контроля над ними, которая позволяет избежать ошибок. Для роста квантового объема необходим рост и количества, и “качества” кубитов.
Следует всегда учитывать, что вероятность ошибок — неотъемлемое свойство квантового“ железа”. Поэтому говоря о кубитах нужно разделять физические кубиты и логические кубиты. Физические кубиты — это реальные атомы или сверхпроводящие цепочки, так сказать “наштампованные” элементы. Логические кубиты — те объекты, над которыми есть реальный контроль, и к ним можно обращаться с фиксированными параметрами без ошибок. Вычислительные возможности квантового компьютера определяются, в конечном счете, именно количеством логических кубитов, которые работают безупречно. В терминах квантового объема можно понимать это так: если уровень ошибок нулевой, то дальше вычислительные возможности (квантовые объем) растет за счет увеличения числа логических кубитов.
Если говорить о достижениях в области работающих квантовых компьютеров, нельзя не упомянуть компьютер IBM на 50 кубитах. Он стал одним из первых квантовых компьютеров такого масштаба. “Рабочая лошадка” квантовых компьютеров компании IBM — сверхпроводящие кубиты, которые для своей работы должны быть охлаждены до очень низких температур. В квантовом процессоре IBM не реализован индивидуальный контроль над каждым кубитом и достаточно высок уровень ошибок, но сам чип уже существует. Также у IBM есть открытый 5-кубитный и 16-кубитные квантовые компьютеры, которым может воспользоваться каждый человек через Интернет. Кроме того, через несколько лет корпорация планирует сделать систему на 100 кубитов. Недавно IBM анонсировала интегрированный квантовый компьютер IBM System One, который является законченным устройством, не требующим, по словам разработчиков, каких либо специальных условий для работы — это существенно приближает такую систему к пользователям, однако о решении практически важных и востребованных задач с помощью подобного компьютера пока говорить сложно.
Компания Intel находится на пороге того же рубежа в 50 кубит, но использует другую технологию для создания кубитов. И это хорошо, ведь если одна из корпораций столкнется с проблемами при реализации своего подхода, вторая продолжит движение к прогрессу.
Лидером квантовой гонки сегодня можно считать компанию Google, которой был продемонстрирован квантовый компьютер из 72 кубитов. Базовая технология у Google такая же как у IBM — сверхпроводящие кубиты. Группой ученых и разработчиков Google также был опубликован ряд научных статей, описывающих подходы к достижению квантового превосходства. Так что в ближайшее время от компании можно ожидать демонстрации квантового превосходства с помощью разработанного ими квантового процессора.
В академическом сообществе тоже была создана система из 51 кубита — это удалось группе Михаила Лукина (выпускника Физтеха и главы Международного консультативного совета Российского квантового центра) на основе ультрахолодных нейтральных атомов, а также система из 53 кубитов от группы Кристофера Монро из Университета Мэрилэнда, который также является основателем компании IonQ, разрабатывающей коммерческий квантовый компьютер на ионах. Кстати, IonQ — не единственный пример стартапа в сфере квантовых вычислений — их сейчас больше десятка.
Очевидно, что большой потенциал в квантовой сфере есть у Китая. “Поднебесная” вынашивает грандиозные планы, планируя сконструировать самый большой квантовый компьютер, и на это у разработчиков уже есть 12 миллиардов долларов для создания Национальной квантовой лаборатории.
Несколько особняком стоит компания D-Wave. В процессоре D-Wave тысячи кубитов, но работают они в другом режиме — режиме квантового отжига. Это позволяет решить при помощи такого компьютера, фактически, лишь одну задачу. Несмотря на то, что с D-Wave уже работают компании, например, Google и Volkswagen, насчет преимуществ подобного квантового компьютера компании ведутся горячие споры.
Что такое квантовый компьютер?
Напомню, что квантовые компьютеры так же, как и классические, представляют информацию в виде последовательности битов. Каждый бит может принимать значение 0 или 1. Главная особенность квантовых компьютеров заключается в использовании явления квантовой суперпозиции, которое позволяет каждому биту — в этом случае их называют квантовыми битами или кубитами — находится в произвольной суперпозиции состояний 0 и 1. В некотором смысле кубиты как бы находятся одновременно и в состоянии 0, и в состоянии 1, позволяя проводить операции сразу с обеими значениями.
Разница между классическим битом и квантовым битом аналогична разнице между сферой и её двумя полюсами. © University of Strathclyde
Разница между классическим битом и квантовым битом аналогична разнице между сферой и её двумя полюсами. © University of Strathclyde
Такой квантовый параллелизм для некоторых задач, которые решаются только перебором, позволяет значительно ускорить время поиска ответа. Например, для стандарта шифрования AES взлом на классическом компьютере требует перебора 2²⁵⁶ вариантов ключей — это число с 78 знаками! Для квантового компьютера существует алгоритм поиска, который эквивалентен перебору всего лишь 2¹²⁸ ключей — это число с 39 знаками. Разница колоссальна, однако видно, что вариантов всего равно много, и вряд ли в обозримом будущем удастся создать систему, которая выполнит такой перебор за разумное время.
Квантовая криптография
Коммерческая система Cerberis для квантового распределения ключей
В отличие от квантовых компьютеров, квантовые криптосистемы уже давно не являются лабораторной инновацией. Хотя первые научные работы на эту тему появились тоже на рубеже 70–80-х годов ХХ века, до практического воплощения дело дошло быстрее. Первые лабораторные тесты прошли в 1989 году, а уже в конце 90-х функционировали коммерческие системы квантовой передачи ключей на расстояние от 20 до 50 км. Такие компании, как id Quantique и MagiQ Technologies, продают готовые системы передачи криптоключей по обычному оптоволоконному кабелю. Эти системы достаточно просты для установки обычным специалистом по прокладке компьютерных сетей. Соответственно, кроме разного рода военных и правительственных организаций их взяли на вооружение крупные коммерческие организации, банки и даже FIFA.
Защита от квантового взлома
Если вас бросает в дрожь от идеи, что когда-нибудь ваши данные расшифруют и украдут богатые преступники с квантовым компьютером, не переживайте: специалисты по безопасности уже думают о защите. На сегодняшний день есть несколько основных механизмов, которые должны спасти пользовательскую информацию от посягательств злоумышленников.
- Традиционные алгоритмы шифрования, устойчивые к квантовым атакам. В это трудно поверить, но мы уже используем методы шифрования, которым не так уж страшны квантовые компьютеры. К примеру, взлом распространенного алгоритма AES, применяемого в мессенджерах вроде WhatsApp и Signal, квантовые компьютеры хоть и ускоряют, но незначительно. Не являются они смертельной угрозой и для многих других симметричных (то есть с одним ключом) шифров. Правда, тут мы возвращаемся к проблеме передачи ключа всем участникам беседы.
- Алгоритмы, разработанные специально для защиты от квантовых атак. Хотя прямо сейчас никто еще не взламывает асимметричные шифры, математики уже придумывают новые, которым даже могучие квантовые технологии не страшны. Так что к моменту, когда киберпреступники возьмут квантовые компьютеры на вооружение, защитники данных, скорее всего, смогут дать отпор.
- Шифрование несколькими способами сразу. Неплохое и доступное уже сейчас решение — шифровать данные несколько раз с помощью разных алгоритмов. Даже если злоумышленники взломают один — не факт, что они справятся с остальными.
- Использование квантовых технологий против них самих. Для безопасного использования симметричных шифров, которые, как мы помним, менее уязвимы для взлома с помощью квантовых компьютеров, применяют системы квантовой передачи ключей. Они не гарантируют защиты от взломщиков, но позволяют наверняка узнать, что информацию перехватили. Так что если ключ шифрования украдут в пути, можно от него отказаться и передать другой. Правда, для этого нужна специальная техника, но она вполне себе продается и работает в государственных организациях и частных компаниях.
В ожидании чуда
Работа над квантовыми компьютерами продолжается, и сегодня одинаково важны вопросы создания нового железа и разработки новых алгоритмов. Сделать это не так просто, потому что программистам приходится иметь дело с совершенно новыми сущностями, а архитекторам — разрабатывать принципиально новые устройства для управления квантовыми системами. Научное сообщество и корпорации-лидеры смотрят в сторону квантовых компьютеров с большим оптимизмом — для него есть поводы.
Квантовые системы не только существуют, но и продаются за деньги, создавая и решая новые проблемы безопасности – в основном, в сфере криптографии.
Квантовые вычисления и квантовая связь — сами эти понятия были изобретены буквально 30 лет назад, и первые работы ученых даже не брали в научные журналы: говорили, что фантастика, а не наука. Сегодня же квантовые системы не только существуют, но и продаются за деньги, создавая и решая новые проблемы безопасности, в основном в сфере криптографии.
Мы живем в мире радиоволн и электромагнитных сигналов. Wi-Fi, GSM, спутниковое ТВ и GPS, точное время и FM-тюнер — лишь немногие из повседневных технологий, в которых используются электромагнитные волны. Конечно, в список нужно включить и все виды компьютеров, от гигантских дата-центров до смартфонов и ноутбуков. Одна из особенностей электромагнитных сигналов состоит в том, что их довольно легко измерить, то есть перехватить. Именно поэтому практически все вышеперечисленное сегодня снабжено технологией шифрования, защищающей информацию от чтения и изменения посторонними. При этом запасного канала связи обычно нет, и разработчики криптосистем блестяще решили сложную проблему — как договориться о секретном ключе шифрования, когда весь процесс переговоров могут слушать посторонние? Именно решение этой проблемы лежит в основе всех современных систем защиты, и именно ему предположительно положат конец квантовые компьютеры. Спасет ли положение возникшая заодно квантовая криптография?
Квантовый взлом шифров
Итак, зашифрованное публичным ключом можно расшифровать только его приватным «напарником» — и никак иначе. А значит, злоумышленники стараются приватный ключ узнать. Перехватить его, как мы говорили, нельзя, потому что он никуда не передается. Но теоретически его можно получить из публичного.
Однако криптографические алгоритмы специально делаются такими, чтобы задачу получения приватного ключа из публичного было невозможно решить за разумное количество времени.
Вот тут-то и выходят на сцену квантовые компьютеры. Дело в том, что благодаря своей природе они решают подобные задачи гораздо быстрее, чем традиционные компьютеры.
Таким образом, неразумное время, которое требуется на взлом шифра, при использовании квантового компьютера может превратиться во вполне разумное. И это в теории может свести на нет весь смысл использования шифра, который уязвим к взлому с помощью квантового компьютера.
Дело не только в железе
Для следующего прорыва, однако, нужно не только железо, но и новые быстрые квантовые алгоритмы. Тут есть заметный прогресс. Например, для изучения соединения Fe2S2 с помощью алгоритмов квантовой химии раньше требовалось тридцать лет при анализе на квантовом компьютере. За счет поиска более оптимального алгоритма, это время сократилось до 2 минут с учетом использования того же железа.
Однако квантовых алгоритмов пока все еще недостаточно. Пока их все еще лишь несколько десятков, а для полноценного развития сферы квантовых вычислений, алгоритмов должно стать намного больше.
Прикладная сторона вопроса
Несмотря на все усилия, на сегодняшний день квантовые компьютеры позволяют решать не так много практических задач вопросов, но потенциал выглядит впечатляюще. Сейчас развитие квантовых вычислений идет по двум направлениям:
- Специализированные квантовые компьютеры, которые направлены на решение одной конкретной специфической задачи, например, задачи оптимизации. Примером продукта являются квантовые компьютеры D-Wave.
- Универсальные квантовые компьютеры — которые способны реализовать произвольные квантовые алгоритмы. На сегодняшний день существуют только небольшие прототипы универсальных квантовых компьютеров — в этом направлении работают Google, IBM и Intel. Они закладывают основу, но пока не позволяют делать что-то масштабное и не умеют справляться с ошибками.
Благодаря тому, что IBM предлагает всем желающим воспользоваться квантовым компьютером, современные квантовые программисты уже тренируются в сборке задач и запуске их на небольших квантовых компьютерах. Например, для поиска по неупорядоченной базе данных квантовый алгоритм имеет квадратичное преимущество. В такой задаче неупорядоченная база данных может быть представлена как некоторый “черный ящик”, на вход которого подаются запросы (адреса элементов в этой базе данных), а черный ящик на них отвечает “да” или “нет” (подходит ли элемент, расположенный по данному адресу, требованиям запроса). Представим, что в некоторой базе данных адрес каждого из элементов состоит из n бит, и в этой базе данных есть лишь один элемент, удовлетворяющий некоторым условиям. Чтобы найти этот элемент нам в среднем потребуется порядка 2^n запросов (более точно 2^(n-1)), т.к. из-за неупорядоченности базы данных все, что нам остается это последовательно перебирать все возможные адреса (которых 2^n штук) до тех пор пока нам наконец не повезет и мы не попадем на нужный элемент. В случае же, если у нас есть квантовый аналог подобного черного ящика (его еще называют «квантовым оракулом») для того, чтобы получить ответ нам потребуется порядка 2^(n/2) запросов. Преимущество «алгоритма квантового перебора», названного в честь Л. Гровера, обусловлено возможностью задавать множество вопросов квантовому ящику одновременно — формировать суперпозицию запросов.
Важно отметить, что задача поиска в неупорядоченной базе данных носит универсальный характер — к ней можно свести практически любую другую задачу (в том числе и NP-полную). Однако для её решения потребуется количество запросов, растущее экспоненциально с ростом сложности задачи (в рассмотренном примере, ей соответствовал параметр n). Таким образом, не стоит относиться к квантовому компьютеру как к всемогущему инструменту, способному решать произвольные вычислительные задачи с экспоненциальным ускорением. В ряде случаев его возможности будут значительно скромнее.
Тем не менее, большой потенциал уже сегодня очевиден для задач из сферы квантовой химии. Например, в промышленности востребован расчет параметров химических соединений и моделировании химических реакций. При использовании классических компьютеров, нам не хватает возможностей и приходится, зачастую, идти на компромисс с точностью. Квантовые компьютеры могут помочь детально определить цепочки реакций, динамику процессов, найти катализаторы для нужных реакций — все это очень полезно! Одна из наиболее обсуждаемых сегодня задач — производство аммиака. Это соединение активно используется в удобрениях для растений, и на его производство тратится 1-2% всей энергии на земле (данные Quantum Computing Report и BP). Если бы при помощи квантового компьютера можно было бы оптимизировать процесс производства аммиака за счет точного знаниях всех параметров, то он уже окупил бы все вложения, которые совершены в разработки технологий (помните, 1-2% мировой энергии).
Недавно на стыке квантовой физики и машинного обучения возникло новое направление — квантовое машинное обучение или, как часто говорят, Quantum AI. При этом важно, что превосходство квантового компьютера над классическими в задачах машинного обучения не требует полноценного и многокубитного квантового компьютера. При помощи квантового компьютера, например, можно будет ускорить отдельные элементы алгоритмов машинного обучения, а также ускорить процесс их обучения. В Google последние годы квантовое машинное обучение считается одним из топовых направлений всей сферы квантовых технологий.
Шаги к цели
D-Wave Two — квантовый компьютер-отжигатель
В чем соль
Название квантовых систем точно передает смысл — их работа основана на квантовых эффектах, таких как суперпозиция и спутывание (сцепление) микрочастиц.
Квантовый компьютер непригоден для большинства повседневных дел, зато способен быстро решить математические задачи, на которых основана современная криптография.
Принципиальным отличием квантового компьютера от обычного является то, что его операционная единица — кубит (квантовый бит) может находиться в состоянии неопределенности, или, если угодно, в нескольких состояниях одновременно. Звучит запутанно, еще сложнее на практике, но, как показали годы исследований, это работает. Квантовый компьютер сильно отличается от классического и вряд ли пригоден для игры в «Тетрис», зато он неизмеримо быстрее обычного решает вероятностные и оптимизационные задачи. Среди вещей, которые можно радикально ускорить квантовыми вычислениями, — оптимизация маршрутов транспорта, секвенирование ДНК, предсказание биржевых котировок и подбор криптографических ключей. Правда, ответ тоже всегда будет вероятностным, даже считать его с компьютера является сложной проблемой, но, сделав несколько довольно быстрых прогонов одной и той же задачи, можно прийти к одному-единственному, правильному ответу: в интересующем нас случае — ключу шифрования.
Все кванты — в беленьком квадратике справа
Шифрование данных — залог безопасности в Интернете
В основе защиты данных в компьютерах и прочих интернетах лежит шифрование. Зашифровать информацию означает с помощью некоего секретного правила и набора символов — ключа — преобразовать ее в бессмысленную кашу. Чтобы понять, что отправитель хотел сказать, нужно расшифровать «кашу» — тоже с помощью ключа.
Один из самых простых примеров шифрования — когда каждую букву заменяют на определенное число (скажем, А — 1, Б — 2 и так далее). В этом примере слово «баобаб» будет выглядеть как «2 1 15 2 1 2», а ключом будет алфавит, в котором каждой букве соответствует число. На самом деле, конечно, используют более сложные правила, но суть процесса остается примерно той же.
Второй, публичный ключ устроен так, чтобы любой мог зашифровать им информацию, но расшифровать ее можно было бы только с помощью соответствующего ему приватного ключа. В результате его не страшно передавать в незашифрованным виде — это ничем не грозит. Такой подход к шифрованию называют асимметричным.
Чтобы понять, как это работает, представим себе такую ситуацию. Допустим, Борис хочет переслать Алле секретный документ. Он сообщает ей об этом, и Алла в ответ присылает ему замок, который запирается без ключа, а ключ оставляет себе.
Борис кладет документ в железный ящик, вешает на него замок и отправляет Алле. Даже если по дороге посылку перехватят шпионы, открыть замок у них не получится, ведь ключ один — и он есть только у Аллы.
В современных системах шифрования и «замок», и «ключ» (то есть публичный и приватный ключи) — это, как правило, очень большие числа, а сами алгоритмы построены на сложных математических операциях, в которых эти числа участвуют. Причем операции обязательно выбираются такие, что «провернуть их назад» чрезвычайно сложно. Поэтому знание публичного ключа не поможет желающему взломать шифр.
Весь Интернет не взломают
Итак, квантовые компьютеры хотя и смогут, судя по всему, взламывать шифры, недоступные традиционным, они все же не всемогущи. К тому же защитные технологии разрабатываются на опережение и не дадут злоумышленникам перехватить преимущество в гонке вооружений.
Так что все мировое шифрование разом вряд ли обрушится, просто одним алгоритмам со временем придут на смену другие, и не факт, что это плохо. Это и сейчас происходит, ведь технологии не стоят на месте.
Так что иногда проверять, какой алгоритм шифрования использует тот или иной сервис и не считается ли этот алгоритм устаревшим (то есть уязвимым к взлому), стоит в любом случае. А особо ценные данные, предназначенные для длительного хранения, будет разумно уже сейчас начинать шифровать так, как будто эра квантовых компьютеров уже наступила.
Страхи и технологии ИБ
Квантовой компьютер имеет две стороны: темную и светлую. До сих пор мы говорили о светлой стороне — решении им практически востребованных задач, которые не могут быть решены при помощи классических компьютеров. Но и есть и темная сторона: квантовый компьютер намного лучше классического решает задачу факторизации. Сложность этой задачи, как известно, является одной из основ обеспечения стойкости распространенных алгоритмов криптографии с открытым ключом. Задача факторизации чрезвычайно сложна для классического компьютера, а на квантовом может быть эффективно решена при помощи алгоритма Шора. Например, взлом RSA-ключа, состоящего из 1024 бит, займет миллионы лет непрерывных вычислений на классических компьютерах, тогда как на квантовом компьютере эта задача будет решена за 10 часов (если предположить, что каждая квантовая операция выполняется 10 нс и что в распоряжении имеется компьютер из достаточного количества логических кубитов). Пока квантовые компьютеры не позволяют ничего взломать — ведь для криптоанализа RSA нужно несколько тысяч управляемых кубитов. И хотя потенциально опасного компьютера еще не существует, сообщество уже сегодня задумывается о защите от возможных проблем в будущем.
Один вариант решения — использование технологии квантовой распределение ключей, которая позволяет двум сторонам обмениваться криптографическими ключами для симметричного шифрования. Как известно, одиночный фотон нельзя разделить, а квантовое состояние нельзя скопировать — это фундаментальное ограничение квантовой механики. На таком принципе — защите передаваемых данных фундаментальными физическими законами — строятся новые приборы. В этой сфере на мировой арене лидирует Китай. В России технология квантового распределения ключей развиваются несколькими группами, например, в РКЦ, МГУ им. М.В. Ломоносова и ИТМО. Прибор, разработанный в РКЦ уже проходил испытания в Сбербанке и Газпромбанке.
Центральная идея заключается в том, чтобы использовать квантово-распределенные ключи в шифре Вернама — одноразовом блокноте. Насколько известно, в самых критически важных системах Китая реализуется именно такая система.
Второй принцип защиты — это постквантовая криптография. Она включает в себя новый класс алгоритмов с открытым ключом, которые основаны на задачах, являющихся вычислительно сложными как для классического компьютера, так и для квантового.
Многих интересует вопрос о том, навредит ли квантовый компьютер блокчейну. Да, это возможно. За счет атак на цифровые подписи, а также за счет использования квантового алгоритма Шора и воздействия на алгоритмы консенсуса со стороны квантового алгоритма Гровера. Однако и защитить блокчейны можно также квантовым распределением ключей или постквантовой криптографией.
В чем трудность
Квантовый компьютер, быть может, давно стоял бы на столе каждого малолетнего хакера, желающего читать переписку одноклассников в «ВКонтакте», но создание компьютера сопряжено с рядом чисто инженерных сложностей, которые настолько велики, что некоторые специалисты считают создание «полноценного» квантового компьютера невыполнимой задачей. Главная проблема состоит в том, чтобы поддерживать кубиты в состоянии запутанности, поскольку любая квантовая система то и дело норовит «свалиться» в классическую, лишенную неопределенности. Тут нельзя не упомянуть многострадального кота Шредингера, который все же не может быть жив и мертв одновременно, а в квантовом компьютере это удивительное состояние должно поддерживаться достаточное время для прогона задачи и измерения результатов. Обычно речь идет о наносекундах, в лучших системах — единицах секунд. Сложность задачи растет с ростом числа кубитов. Для решения задач по взлому шифров нужен квантовый компьютер с 500–2000 кубитов (в зависимости от разрядности ключа в криптоалгоритме), в то время как большинство существующих систем оперируют с единицами кубитов (рекорд – 14 кубитов). Таким образом, взлом вашего SSL-сертификата на квантовом компьютере сегодня еще невозможен, но, возможно, будет реален уже через пять лет.
Главные популяризаторы науки и многострадального кота Шредингера — Пенни и Шелдон из «Теории Большого взрыва»
Читайте также: