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

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

Алгоритм RSA (Rivest-Shamir-Adleman) – это ассиметричный алгоритм шифрования, в основе которого как раз лежит математическая задача факторизации больших чисел. Сегодня он очень активно используется для защиты программного обеспечения, при обмене данными, а также в областях, где необходимо верифицировать отправителя. Кроме того, на RSA базируется защищенный протокол HTTPS, использование которого в России достигло 98% по данным Яндекс.Радара.

Безопасность таких алгоритмов, как RSA и ECC - Elliptic Curve Cryptography (криптография на эллиптических кривых) зависит от вычислительной сложности решения задач, которые легли в их основу при создании. С появлением квантовых компьютеров они станут уязвимыми. На Рис.1 представлено влияние квантовых вычислений на современные алгоритмы шифрования. Это значительно увеличило интерес государств к созданию квантового компьютера, многие крупные корпорации сегодня вкладывают огромные суммы в технологии, основанные на принципах квантовой механики. Все это ставит перед учеными задачу разработать защиту от новых сверхмощных технологий, которые могут быть использованы с целью кражи конфиденциальных данных.

Пара слов о квантовой механике в криптографии

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

Впервые концепция использования квантовых элементов для обеспечения безопасности передачи данных была выдвинута Стивеном Визнером в 1970 году. Через десять лет, под влиянием идей Визнера, Чарльз Беннет из IBM и Жиль Брассар из Университета Монреаля предложили схему передачи секретных ключей с использованием квантовых объектов (Рис.2). В 1984 году была выдвинута идея о создании принципиально надежного квантового коммуникационного канала. В результате возникла схема BB84, согласно которой два пользователя, Алиса и Боб, обмениваются фотонами с разной поляризацией через квантовый канал для передачи сообщений.

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

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

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

В BB84 носителям информации являются фотоны. Их поляризуют под углом в 0, 90, 45 или 135 градусов. Измерить возможно только сам базис:

- вертикальная поляризация (0 и 90 градусов)

- диагональной поляризация (45 и 135 градусов)

В условных обозначениях вертикальной поляризации присваивается «+», в диагональной – «x».

Кодируются состояния следующим образом:

Кодирование происходит в несколько этапов:

1.  На первом этапе отправитель (Алиса) случайным образом выбирает последовательность фотонов с разной поляризацией, формирует набор фотонов и передает его легитимному получателю (Бобу):

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

3.  Далее Боб передает Алисе по открытому каналу связи информацию о том, какие базисы он выбрал, обозначая их, согласно Таблице 1, как 0 и 1:

4.  Сравниваются исходная последовательность Алисы и полученная последовательность Боба. Совпадения фиксируются.

Видим, что примерно в 50% случаев результаты будут совпадать.

5. После этого Алиса и Боб снова связываются по открытому каналу и выясняют, какие базисы у них совпали. Информация о несовпавших базисах отбрасывается. Последовательность совпавших базисов становится открытым ключом:

Открытый ключ получается одинаковым и у Алисы, и у Боба.

Данный алгоритм гарантирует, что злоумышленник не сможет при перехвате восстановить ключ, по крайней мере, незаметно для Алисы и Боба. Если попытаться перехватить фотоны, то, поскольку выбранный Алисой Базис злоумышленнику неизвестен, то он может только выбирать его случайно, как делает Боб, но измерение поляризации приводит к изменению состояния вектора состояния. Злоумышленник не сможет после измерения отправить тот же самый фотон Бобу, так как не знает, в каком состоянии он был изначально. Также он не сможет просто скопировать передаваемый фотон, согласно теореме о запрете квантового клонирования. Таким образом, если нарушитель что-то попытается сделать с фотонами, то Алиса и Боб получат разные ключи, т.е. будет обнаружено постороннее вмешательство.

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