Угроза появления квантового компьютера для современной криптографии и шифрования

Введение

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

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

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

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

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

Что же такое квантовый компьютер? Это вычислительное устройство, которое использует явления квантовой механики (квантовая суперпозиция, квантовая запутанность) для передачи и обработки данных [2]. В качестве носителей информации он использует квантовые объекты, которые в свою очередь объединены в квантовую систему для произведения вычислений.

Квантовые объекты обладают следующими свойствами:

• Имеет определенное состояние с двумя граничными уровнями: это означает, что объект может иметь два состояния, как бит. Примером из реальной жизни может являться обычная монетка.

• Находится в суперпозиции своего состояния до момента измерения: некоторых источники объясняют это тем, что объект находится в двух состояниях одновременно до осуществления вычисления, но правильнее сказать, что объект имеет некоторую вероятность встать в состояние A или в состояние B, и в сумме эти вероятности равны 1 (например, при подбросе монетки мы не можем узнать на какую именно сторону она упадет);

• Запутывается с другими объектами для создания квантовых систем: квантовые объекты в квантовой системе имеют взаимосвязь и влияют друг на друга (несколько подброшенных монет могут сталкиваться между собой и влиять на результаты друг друга);

• Выполняет теорему о запрете клонирования (нельзя скопировать состояние объекта): до начала вычисления нельзя отследить состояния квантовых объектов в системе, ровно, как и скопировать систему целиком.

Любой объект, для которого выполняются свойства квантового объекта и который мы можем создать и управлять, может использоваться как носитель информации в квантовом компьютере [1]. По-другому физические носители информации в квантовых компьютерах называют кубитами. Наиболее известные из них:

• сверхпроводниковые кубиты;

• зарядовые кубиты;

• ионные ловушки;

• квантовые точки.

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

• Алгоритм Шора (факторизация);

• Алгоритм Гровера (быстрый поиск в неупорядоченной базе данных);

• Алгоритм Дойча-Йожи (ответ на вопрос, постоянная или сбалансированная функция);

• Алгоритм Саймона (решение задачи о черном ящике экспоненциально быстрее, чем любой другой классический алгоритм);

• Алгоритм Залки-Визнера (позволяет моделировать унитарную эволюцию квантовой системы n частиц за почти линейное время с использованием O(n) кубитов) [1][2].

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

Хотя скорость вычислений у квантового компьютера значительно выше, существуют несколько «но», которые ограничивают нас от перехода в «квантовый мир».

Во-первых, максимальная продолжительность работы квантовой системы в настоящее время составляет 150–200 мкс (54-кубитный процессор Google Sycamore). За такой краткий период квантовый компьютер должен инициализировать систему кубитов, провести вычисление и считать результат. Непродолжительность работы связана с таким явлением, как квантовая декогеренция. Простым языком — это разрушение связи между кубитами, при любом внешнем воздействии. Чем больше запутанных кубитов в системе, тем проще ее разрушить, делая квантовую систему крайне хрупкой и требующей строгих условий для поддержания.

Во-вторых, создание и реализация супермощного квантового компьютера требует еще более высоких технологий, которых человечество ещё не достигло. Для поддержания квантовой системы, в которой кубиты будут находиться в суперпозиции, необходимы “саркофаги”, которые не позволят никаким внешним фактором повлиять на систему. Например, существующие квантовые компьютеры поддерживают температуру немного выше абсолютного нуля и максимально защищены от внешних воздействий [2].

В-третьих, квантовый компьютер имеет некоторый процент ошибок из-за вероятностной природы результата (например, монета встанет на ребро). Ошибки в данном случае могут быть вызваны декогеренцией системы, вычислениями кубитов или считыванием окончательного результата.

Термин «квантовое превосходство» обсуждается в интернете уже несколько лет. Он означает, что квантовые компьютеры в определенный момент смогут решать задачи, для выполнения которых ни один классический компьютер не сможет уложиться в разумное время. Совершенно неожиданно к концу 2019 года исследователи Google объявили, что достигли квантового превосходства. Они разработали 54-кубитный процессор Sycamore, который выполнял целевое вычисление (вычисление случайной выборки) за 200 секунд. IBM оспорила это утверждение, заявив, что идеальная симуляция одной и той же задачи может быть выполнена на классическом компьютере за 2,5 дня с гораздо большей точностью. Эксперимент Google не следует рассматривать как доказательство того, что квантовые устройства «превосходят» классические компьютеры. Тем не менее он прекрасно демонстрирует прогресс в квантовых вычислениях на основе сверхпроводников, демонстрируя ультрасовременную точность воспроизведения на 53-кубитной системе [6].

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

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

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

Современные методы шифрования и криптографии

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

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

Однако далеко не каждый современный пользователь осведомлен о значениях и реальной важности вышеупомянутых терминов. Шифрование представляет собой технологию кодирования и декодирования данных. Зашифрованные данные – это результат применения математического алгоритма для кодирования данных с целью сделать их недоступными для чтения. Исходные данные могут быть восстановлены в свою первоначальную форму только при использовании специального ключа [7].

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

В симметричных криптосистемах в парах взаимосвязанных криптографических преобразований применяется один и тот же криптографический ключ. Также они предполагают, что отправитель и получатель должны заранее согласовать секретный ключ. Причем должно существовать взаимное доверие между сторонами, участвующими в обмене информацией. Безопасность симметричных систем основана на ключе: компрометация ключа фактически равноценна взлому криптосистемы. Наиболее широко распространены такие симметричные криптосистемы, как AES (Advanced Encryption Standard), 3DES (Triple Data Encryption Standard) и IDEA (International Data Encryption Algorithm), которые используются по сей день [8].

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

Самым старым и используемым многими компаниями методом ассиметричного шифрования является RSA (Rivest Shamir Adleman). Его практически невозможно взломать с помощью современных компьютеров. RSA использует два уникальных больших простых числа в сложной алгебре для генерации своих пар открытый-закрытый ключи [9]. Одним из наиболее современных методов ассиметричного шифрования является PQC (Post-Quantum Cryptography).

Наряду с вышеупомянутыми методами, современная криптография использует алгоритмы хеширования, которые преобразуют данные произвольного размера в массив фиксированного размера - хеш-сумму. Примеры современных хеш-функций включают SHA-256 (Secure Hash Algorithm 256-bit), SHA-3, BLAKE2 и другие. Они широко используются для обеспечения целостности данных, создания цифровых подписей, а также в качестве ключей в различных криптографических протоколах [11].

Потенциальные угрозы со стороны квантовых компьютеров

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

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

Пример факторизации квантовым компьютером:

Учёные из Китая смогли факторизовать целые числа длиной до 48 бит, используя 10 кубитов. На основании чего сделали предположение, чтобы взломать RSA-2048 используя их алгоритм, состоящий из классической редукции решётки (алгоритм Шнорра) и квантового алгоритма приближенной оптимизации (QAOA), понадобится 372 кубита. В заключении этого исследования сами учёные говорят о том, что масштабируемость их алгоритма остаётся на уровне гипотезы [14].

Что будет с криптовалютой?

Один из самых главных вопросов с учётом нарастающих волнений на фоне новостей о возможностях квантовых компьютеров. За пример будет взята одна из самых популярных криптовалют – биткоин. В этой системе используются хэш-функции SHA-256 и SHA-512. Их уязвимостью является коллизии, когда 2 разных ссылки выдадут один и тот же хэш. И парадокс заключается в том, что известный алгоритм поиска коллизий Ван Оршота-Вине, намного доступней чем любой из известных на данный момент квантовый алгоритм [15]. А значит никакого преимущества у квантовых компьютеров в этой области нет, скорее наоборот, современные компьютеры справятся с этой задачей лучше, чем квантовые.

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

Так же есть новость от доктора наук и основателя исследовательской компании Planalto Research, Эда Герка, о том, что его команда успешно взломала ключ RSA-2048. Новость не была подтверждена[16]. 

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

Криптография и методы защиты тоже не отстают в развитии. Например, Национальный институт стандартов и технологий (NIST) является крупным игроком в создании средств защиты.

С 2016 года они выполняют задачу в рамках своего проекта по стандартизации кибербезопасности после создания квантовых компьютеров, занимаясь поиском лучших новых криптографических приемов, способных противостоять квантовому натиску [17].

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

Криптография на основе решетки:

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

Криптография на основе изогении:

Изогональная криптография представляет собой подход, схожий с эллиптической криптографией (ECC), где для шифрования данных используются эллиптические кривые. Вместо решения логарифмических задач, характерных для ECC, изогональная криптография опирается на изогении, то есть отображение между эллиптическими кривыми. Эти вычисления могут быть достаточно сложными, чтобы оставаться устойчивыми к воздействию квантовых вычислений [18].

Криптография на основе кода:

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

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

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

Квантовая физика

Квантовая физика занимается проблемой распределения ключей, и решает её на квантовом уровне. Она использует материю и её природу для создания и распределения ключей, привлекая в процесс физические системы основанные, на квантовой физике. Рассмотрим процесс создания и передачи ключа с помощью фотона. Главное его преимущество для криптографии – смена свойства при взаимодействии с ним, будь то копирование или изменение.

Этапы формирования ключей [21]:

• Алиса случайным образом выбирает один из базисов. Затем внутри базиса случайно выбирает одно из состояний, соответствующее 0 или 1, и посылает фотоны. Они могут посылаться все вместе или один за другим, но главное, чтобы Алиса и Боб смогли установить взаимно однозначное соответствие между посланным и принятым фотоном.

• Боб случайно и независимо от Алисы выбирает для каждого поступающего фотона: прямолинейный или диагональный базис, и измеряет в нём значение фотона.

• Для каждого переданного состояния Боб открыто сообщает, в каком базисе проводилось измерение кубита, но результаты измерений остаются в секрете.

• Алиса сообщает Бобу по открытому общедоступному каналу связи, какие измерения были выбраны в соответствии с исходным базисом Алисы.

• Пользователи оставляют только те случаи, в которых выбранные базисы совпали. Эти случаи переводят в биты (0 и 1), и составляют ключ.·    

В таком случае примерно 50 % данных выбрасывается. Оставшийся более короткий ключ называется «просеянным». К использованию фотонов прибегают протоколы BB84 [22] и его облегченная версия – протокол B92 [23].

Подтверждение или опровержение гипотезы.

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

Гипотеза подтверждается.

Выводы

На основе изложенной выще информации можно сделать следующие заключения о возможной опасности развития квантовых компьютеров:

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

• В силу своей стоимости изучения квантовые технологии будут изучаться далеко не во всех странах, можно сделать предположение, что это будет 5-6 стран.

• Основываясь, на том, что изучение квантовых компьютеров идут с 1998 года, а на момент 2023 года, есть информация о компьютере IBM Quantum Condor с 433 кубитами, можно сделать вывод, что никаких резких скачков и появления квантового компьютера с миллионом кубитов ближайшие годы ждать не стоит. Эксперты в этой области дают 15–20  лет изучения, прежде чем мы достигнем такой вычислительной мощности.

• Так же в связи с постепенным развитием квантовых компьютеров. Возможности тоже будут расти постепенно. Сперва будут короткие ключи и так по нарастающей.

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

Заключение

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

Список источников

1. Как работают квантовые компьютеры. Собираем паззл // Хабр – URL: https://habr.com/ru/articles/480480/ (дата обращения 8.12.2023)

2. Квантовый компьютер // Википедия – URL: https://ru.wikipedia.org/wiki/Квантовый_компьютер (дата обращения 8.12.2023)

3. У кого кубитов больше. Когда ждать новую квантовую гонку вооружений? // Новостной блог N+1 – URL: https://nplus1.ru/material/2019/11/07/quantum-advantage (дата обращения 8.12.2023)

4. Квантовый компьютер: что это, как работает и на что способен // Skillbox Media – URL: https://skillbox.ru/media/code/chto-takoe-kvantovyy-kompyuter-i-kak-on-rabotaet/ (дата обращения 8.12.2023)

5. What is Quantum Computing? // IBM – URL: https://www.ibm.com/top­ics/quantum-computing (дата обращения 15.12.2023)

6. What is a quantum computer? // New Scientist – URL: https://www.newscientist.com/question/what-is-a-quantum-computer/ (дата обращения 15.12.2023)

7. Квантовая физика: декогеренция // Хабр – URL: https://habr.com/ru/articles/449888/ (дата обращения 15.12.2023)

8. Что такое квантовое превосходство? // New-Science.ru – URL: https://new-science.ru/chto-takoe-kvantovoe-prevoshodstvo/ (дата обращения: 15.12.2023)

9. Что такое шифрование? | Шифрование данных | Определение шифрования // Kaspersky.ru – URL: https://www.kaspersky.ru/resource-center/definitions/encryption (дата обращения: 22.12.2023)

10. Шпаргалка по криптографии: что делать, если попал в проект с криптографами // Хабр – URL: https://habr.com/ru/companies/infotecs_official/articles/761008/ (дата обращения: 22.12.2023).

11. Asymmetric Encryption: What It Is & Why Your Security Depends on It - Hashed Out by The SSL Store // thesslstore – URL: https://www.thess­lstore.com/blog/asymmetric-encryption-what-it-is-why-your-security-depends-on-it/ (дата обращения: 22.12.2023).

12. Encryption: Symmetric and Asymmetric - Practical Cryptography for Developers // CryptoBook Nakov – URL: https://crypto­book.nakov.com/encryption-symmetric-and-asymmetric (дата обращения: 10.01.2024).

13. Хеш-функция, что это такое? // Хабр – URL: https://habr.com/ru/articles/534596/ (дата обращения: 10.01.2024).

14. Bao Yan, Factoring integers with sublinear resources on a superconducting quantum processor/ Bao Yan, Ziqi Tan, Shijie Wei [и др.] // arxiv – URL: https://arxiv.org/pdf/2212.12372.pdf (дата обращения: 13.01.2024)

15. Are hash functions strong against quantum cryptanalysis and/or independent enough of mathematics? // Crypto.StackExchange – URL: https://crypto.stackexchange.com/questions/59375/are-hash-functions-strong-against-quantum-cryptanalysis-and-or-independent-enoug (дата обращения 13.01.2024)

16. Ed Gerck, Quantum computing (QC) has become a reality //  LimledIn – URL : https://www.linkedin.com/feed/up­date/urn:li:activity:7125215279688601600/ (дата обращения: 13.01.2024 )

17. Quantum Computing Threats to Cryptography and Solutions // Cryptomus – URL: https://cryptomus.com/blog/quantum-computing-threats-to-cryptography-and-solutions (дата обращения: 15.01.2024 )

18. Explore the impact of quantum computing on cryptography // Tech Target Data Center – URL : https://www.tech­target.com/searchdatacenter/feature/Explore-the-impact-of-quantum-computing-on-cryptography (дата обращения: 15.01.2024)

19. Basics of Post-Quantum Cryptography // Archon – URL : https://www.archonsecure.com/post-quantum-cryptography-guide#chapter-2 (дата обращения 15.01.2024)

20. Post-Quantum Cryptography Standardization // NIST – URL: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptog­raphy-standardization (дата обращения: 15.01.2024)

21.  Квантовое распределение ключей  // Википедия – URL: https://ru.wikipedia.org/wiki/Квантовое_распределение_ключей#Обмен_квантовыми_ключами (дата обращения: 16.01.2024)

22. Протокол BB84 // Википедия – URL: https://ru.wikipedia.org/wiki/BB84 (дата обращения 18.01.2024)

23. Протокол B92 // Википедия – URL: https://ru.wikipedia.org/wiki/B92 (дата обращения 18.01.2024)