Проект Quantum-Secure Net (часть 1/3): Квантовая угроза современной криптографии

25/01/21

Эта статья разделена на три части и предназначена для прослеживания основных элементов криптографии и изменений, внесенных «квантовым» миром вплоть до проекта Quantum Key Distribution и европейского проекта Quantum-Secure Net, осуществленного Italtel, Cefriel, Политехнический институт Милана, CNR, Политехнический университет Мадрида и Telefonica.

Первая часть, начиная с текущего состояния криптографии, сводится к определению контуров так называемой «квантовой угрозы». Вторая часть описывает контуры квантовой и постквантовой криптографии, ведущие к введению квантового распределения ключей (QKD). В третьей части рассказывается о проекте Quantum-Secure Net.

1. Современное состояние криптографии

Криптография с открытым ключом жизненно важна для онлайн-безопасности и используется во множестве повседневных систем, от банковских до мобильных приложений, которые мы используем каждый день. Когда две или более сторон хотят общаться, при текущем уровне развития технологий криптография с открытым ключом гарантирует, что информация является конфиденциальной и точной, а также что правильные стороны общаются. В большинстве случаев шифрование работает за кулисами, и вы не подозреваете, что оно используется, не говоря уже о типе шифрования, который используется в настоящее время. Когда вы посещаете веб-сайт HTTPS (на следующем изображении - деталь сертификата сайта HTTPS), используя Safari или Google Chrome, щелкая значок сертификата, а затем «Подробности» и прокручивая вниз до «Информация об открытом ключе», чтобы увидеть, какие алгоритмы используются защищая соединение с этим сайтом, вы, вероятно, увидите алгоритмы RSA или ECC.

В основе каждой схемы открытого ключа лежит «сложная» математическая задача, которая имеет сложное (но не невозможное) разрешение или с высокой «числовой сложностью». Если человек или компьютер могут эффективно решить эту проблему, они могут обойти криптографическую систему. Не все сложные математические задачи подходят для использования в криптографии; Ключевой особенностью является то, что проблема должна быть трудной для решения в одном направлении, но легкой в ​​противоположном. Например, легко умножить два больших простых числа, но очень сложно разложить большое число на простые числа, составляющие его (особенно, когда размер и количество простых чисел, которые множат выбранное число, увеличиваются).

Используемая в настоящее время криптография с открытым ключом основана на проблемах, связанных с факторизацией простых чисел (RSA), дискретными логарифмами (Диффи-Хеллмана) и эллиптическими кривыми (ECC). Хотя это кажутся разными проблемами, на самом деле все они являются случаями общей проблемы, называемой проблемой абелевых скрытых подгрупп. Эту проблему сложно решить, особенно с классическими алгоритмами, которые имеют так называемую (суб) экспоненциальную сложность. Потребуются годы, чтобы взломать текущую криптографию с открытым ключом даже на самых мощных компьютерах, если система будет реализована правильно.

2. Как атакуются системы шифрования

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

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

Решение математической проблемы, наоборот, является проблемой устойчивости алгоритма шифрования. Математическую проблему можно определить как трудно решаемую в безусловном или практическом смысле. Например, математическая задача, которую сложно решить сегодня, может не быть решена завтра, поскольку вычислительная мощность атакующего увеличивается. В криптографии термин "безусловная вычислительная безопасность" относится к тем проблемам, которые не могут быть решены независимо от вычислительной мощности злоумышленника. В то время как «практические» (практическая вычислительная безопасность) указываются те, которые не поддаются обработке с вычислительными ресурсами, доступными в настоящее время, но которые могут стать управляемыми в будущем.

3. Квантовая угроза

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

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

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

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

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

  1. Трудно оценить, когда квантовые вычисления достигнут такой применимости, чтобы повредить существующие криптографические системы. Это новая форма науки и технологий, в которой компании, правительства и университеты пробуют разные подходы, а оценки варьируются от десяти до тридцати лет. Однако новую квантовую криптографию необходимо изучить, внедрить и протестировать, прежде чем кто-либо разработает квантовый компьютер.
  2. Переход на криптографические системы может занять много лет. Это часто упускается из виду, но переход любой технологии, особенно в крупной организации, - сложный процесс, масштаб которого может занять десять лет. Даже простое обновление алгоритма или ключа может занять много времени. Может потребоваться новая инфраструктура, обучение разработчиков, переработка старых приложений и новые криптографические стандарты, развертывание нового решения в сети. Это относится ко всей структуре, на которой сегодня основана большая часть Интернета.
  3. В дополнение к зашифрованным данным при передаче, хранилище данных должно быть защищено. Компании уже хранят зашифрованные данные в соответствии с законодательными нормами (например, GDPR). Хотя сегодня квантовый мир представляет собой относительно отдаленный риск, и некоторые данные могут оказаться не столь актуальными через десять или тридцать лет, большинство данных по-прежнему будут конфиденциальными. Такие данные, как личная информация или информация о здоровье (личная информация, позволяющая установить личность / личная медицинская информация PII / PHI) или правительственная информация, нуждаются в долгосрочном шифровании.
  4. Алгоритмы квантовой защиты более безопасны как для квантовых, так и для классических атак, а в некоторых случаях также более эффективны и гибки.

Итак, какими безопасными квантовыми алгоритмами можно заменить существующие и как удовлетворить растущую потребность в безопасности? Ответы делятся на две возможные категории: квантовая криптография и постквантовая криптография.

Энрико Фрументо (1), Надя Фабрицио (1), Паоло Мария Коми (2)

(1) Миланский политехнический институт CEFRIEL, Viale Sarca 226 - 20126 Милан

(2) Italtel, Via Reiss Romoli - loc. Кастеллетто - 20019 Сеттимо Миланезе (Ми)

Процитированные работы

[1]

Р. Йожа, «Квантовое разложение, дискретные логарифмы и проблема скрытых подгрупп», Вычислительные системы в науке и технике, т. 3, вып. 2, стр. 34-43, 17 12 2001.

[2]

«Трудности понимания квантового алгоритма для проблемы абелевых скрытых подгрупп», [Online]. Имеется в наличии: https://qastack.it/cstheory/19129/difficulty-in-understanding-the-quantu....

[3]

Википедия, «Алгоритм Шора», [Интернет]. Имеется в наличии: https://en.wikipedia.org/wiki/Shor%27s_algorithm.

Изображения: GCN / Интернет

Проект Quantum-Secure Net (часть 2/3): европейский продукт Quantum Key Distribution

Проект Quantum-Secure Net (часть 3/3): европейский продукт QUANTUM KEY DISTRIBUTION

оборона рейнметалла