Насколько стойкими являются современные криптографические алгоритмы? Ответ таков: Достаточно устойчивыми до того момента, пока в дело не вмешаются квантовые вычислительные системы.
В настоящее время между квантовыми вычислениями и классической криптографией ведется опасное соревнование. Классическая криптография защищает Интернет, регистры блокчейнов, средства коммуникации и многие другие системы.
Постквантовая криптография, также известная как квантово-устойчивая криптография, нацелена на создание методов шифрования, которые не могут быть взломаны алгоритмами, работающими на будущих квантовых компьютерах.
Квантовый мир и кубиты
Квантовые вычисления представляют собой новый подход к обработке информации, который отличается от классических вычислений. В основе квантовых вычислений лежит понятие кубита (квантового бита). В отличие от классического бита, который может принимать значения 0 или 1, кубит может находиться в состоянии суперпозиции, представляя собой комбинацию состояний 0 и 1 одновременно.
Эта особенность кубита напоминает знаменитый эксперимент с котом Шредингера. В этом эксперименте кот находится в закрытом ящике и может быть одновременно и живым, и мертвым, пока мы не откроем ящик и не проверим его состояние. Точно так же кубит может находиться в состоянии суперпозиции до момента измерения.
В квантовых вычислениях используется двумерный вектор-столбец для описания состояния кубита. Этот вектор, называемый вектором квантового состояния, содержит всю информацию о кубите. Например, векторы квантовых состояний [1| 0] и [0|1] представляют базовые состояния кубита, соответствующие классическим состояниям 0 и 1.
Алгоритм Шора и угроза криптографии
Квантовые компьютеры обладают неограниченным потенциалом и особыми талантами, такими как алгоритмы Шора и Гровера, которые могут взломать криптографию.
Алгоритм Шора, разработанный Питером Шором в 1994 году, способен разложить число на простые множители. Он позволяет эффективно взламывать криптосистемы, основанные на задачах факторизации и дискретного логарифмирования, такие как DSA, ECDSA и RSA.
RSA — это широко используемая система шифрования с открытым ключом, на которой основаны такие вещи, как интернет-браузеры и программное обеспечение для цифровой подписи. В RSA приватный ключ состоит из двух больших простых чисел, сгенерированных алгоритмом. Произведение этих двух чисел затем используется для создания публичного ключа.
Шифрование зависит от того, насколько трудоемко разложить большое число из публичного ключа, чтобы определить два простых числа, составляющих приватный ключ.
Наилучшие из известных классических алгоритмов факторизации требуют значительного времени, но алгоритм Шора, работая на квантовом компьютере, может выполнить эту задачу за очень короткий срок.
Хеш-функции и подпись Меркла
Постквантовая криптография в основном сосредоточена на пяти различных подходах, которые могут обеспечить защиту от квантовых атак. Один из таких подходов — криптография, основанная на хеш-функциях. Примером может служить подпись Меркла с открытым ключом на основе хеш-дерева. Этот алгоритм цифровой подписи был предложен Ральфом Чарльзом Мерклом в 1979 году как альтернатива цифровым подписям RSA и DSA.
Однако стоит отметить, что для любого открытого ключа на основе хеш-функции существует ограничение на количество подписей, которые могут быть получены из соответствующего набора закрытых ключей.
Вклад Беннета и Брассарда
Чарльз Беннет и Жиль Брассард внесли значительный вклад в развитие квантовой криптографии. Их идеи использовались для шифровки связи между главами государств и другими важными персонами. Они разработали методы, которые позволяют обеспечить безопасное квантовое шифрование, устойчивое к атакам даже с использованием квантовых компьютеров.
Квантовая криптография использует законы квантовой физики для передачи частной информации таким образом, что невозможно незаметное перехватывание.
Квантовое распределение ключей (QKD) использует серию фотонов для передачи секретной случайной последовательности, известной как ключ. Сравнивая измерения, выполненные на обоих концах передачи, пользователи узнают, был ли ключ скомпрометирован.
Выводы
Основная проблема с популярными на сегодняшний день алгоритмами заключается в том, что их безопасность основана на одной из трех сложных математических задач: задаче факторизации целых чисел, задаче дискретного логарифмирования или задаче дискретного логарифмирования на эллиптических кривых. Все эти задачи могут быть легко решены на достаточно мощном квантовом компьютере, использующем алгоритм Шора.
В настоящее время многие криптографы работают над разработкой новых алгоритмов в преддверии эры квантовых компьютеров. Эта работа привлекает все больше внимания как в академической среде, так и в промышленности. Например, конференция PQCrypto, которая проводится с 2006 года, а также ряд семинаров по квантово-безопасной криптографии.