Если верить Эдварду Сноудену, шифрование является “единственной верной защитой от слежки”. Однако развитие квантовых технологий может поставить под угрозу эту защиту. В этой статье мы выясним, почему квантовые вычисления представляют опасность для сохранности данных и что с этим делать. Вместо сугубо теоретического анализа, будем опираться на примеры кода на языках Python, C и Linux.
Основы квантования
Когда в 2019 году исследователи Google сообщили о первом случае квантового превосходства, это вызвало невероятный ажиотаж. Одной из областей, где квантовые вычисления могут оказать существенное влияние, является шифрование. Чтобы разобраться в этом вопросе, рассмотрим основы квантования.
В отличие от классических компьютеров, алгоритмы квантовых компьютеров опираются не на биты, а на кубиты. Бит может принимать состояние 0 или 1. При многократном измерении бита неизменно получается один и тот же результат. С кубитами все обстоит иначе. Как бы странно это ни звучало, но кубиты могут одновременно принимать значения 0 и 1. При многократном измерении существует лишь определенная вероятность получить результат 0 или 1. В начальном состоянии кубита вероятность измерения 0 обычно составляет 100%. Однако с помощью суперпозиции можно получить различные распределения вероятностей. Причины этого лежат в квантовой механике, подчиняющейся иным законам, чем “обычная” жизнь.
Основное преимущество квантовых компьютеров — их вероятностная природа. Классические компьютеры отлично решают задачи, где достоверно нужен один результат. Квантовые же машины превосходно справляются с вероятностями и комбинаторикой. Операция, выполняемая с кубитом в состоянии суперпозиции, одновременно применяется и к значению 0, и к значению 1. С увеличением числа кубитов растет и преимущество перед классическим компьютером. Квантовая машина с тремя кубитами может одновременно обрабатывать до восьми значений (2³): двоичные числа 000, 001, 010, 011, 100, 101, 110 и 111.
В научной литературе высказывается мнение о том, что квантовые компьютеры помогут решить проблемы, ранее казавшиеся неразрешимыми. Однако оптимальных квантовых компьютеров пока не существует. Современное поколение квантовых компьютеров основано на квантовой технологии промежуточного масштабирования (NISQ). Такие машины имеют ограниченную вычислительную мощность и чувствительны к ошибкам. Современные устройства содержат до нескольких сотен кубитов. Примером может служить 433-кубитный чип Osprey, представленный IBM в 2022 году. Теперь компания планирует разработать машину со 100 000 кубитов к 2033 году.
Далее мы расскажем, почему такая эволюция представляет угрозу для безопасности данных. Покажем на примерах кода, почему квантовые компьютеры могут взломать некоторые виды шифрования, и обсудим обходные пути.
Исходный код доступен на GitHub. Он был разработан в среде Kali Linux 2023.2 с использованием Anaconda с Python 3.10.
Шифрование и простые множители
Относительно простым способом шифрования сообщения является применение симметричного алгоритма. В этом случае один и тот же ключ используется как для шифрования открытого текста, так и для расшифровки шифротекста. Основной проблемой при таком подходе является безопасный обмен ключами между отправителем и получателем. Как только закрытый ключ становится известен третьей стороне, у нее появляется возможность перехватить и расшифровать сообщение.
Асимметричная криптография казалась решением этой проблемы. Такие методы, как RSA (алгоритм Ривеста-Шамира-Адлемана), используют разные ключи для шифрования и дешифрования. Шифрование здесь осуществляется с помощью одного или нескольких открытых ключей, которые получатель делает доступными для всех. Для расшифровки получатель использует закрытый ключ, который известен только ему. Таким образом, отправитель может получить открытый ключ без риска, поскольку он все равно не является секретным. Защищенным должен быть только закрытый ключ получателя. Но как можно защитить такую процедуру, если потенциальные злоумышленники знают открытый ключ? Для этого асимметричные алгоритмы опираются на такие математические задачи, как разложение (факторизация) целого числа на простые множители.
Разложение целого на простые множители лучше всего понять на примере. В языке Python для определения простых множителей заданного целого числа можно использовать функцию factorint библиотеки SymPy.
>>> import sympy
>>> sympy.factorint(10)
{2: 1, 5: 1}
>>> 2**1 * 5**1
10
>>> sympy.factorint(1000)
{2: 3, 5: 3}
>>> 2**3 * 5**3
1000
>>> sympy.factorint(55557)
{3: 2, 6173: 1}
>>> 3**2 * 6173**1
55557
>>>
Приведенный выше консольный вывод показывает, что каждое целое число натурального ряда может быть выражено в виде произведения простых чисел. Эти числа называются простыми множителями. Из школьного курса математики нам известно, что простое число делится только на 1 и на само себя. Например, число 10 можно выразить уравнением 10=2¹ * 5¹ . Таким образом, простыми множителями числа 10 являются 2 и 5. Аналогично, число 55557 можно выразить уравнением 55557=3² * 6173¹. Таким образом, простыми множителями числа 55557 являются 3 и 6173. Процесс нахождения простых множителей для заданного целого числа называется разложением на простые множители.
В классических компьютерах разложение на простые множители легко осуществляется для малых чисел, но становится все более сложным для больших целых чисел. Каждое новое число резко увеличивает сумму возможных комбинаций. В какой-то момент определение простых множителей становится практически невозможным для классического компьютера. В качестве примера можно привести следующее число (RSA-260) из конкурса задач на разложение больших целых чисел, проводившегося компанией RSA Security и завершившегося в 2007 году. На момент написания статьи оно еще не было разложено.
#!/usr/bin/env python
import sympy
rsa_260 = 22112825529529666435281085255026230927612089502470015394413748319128822941402001986512729726569746599085900330031400051170742204560859276357953757185954298838958709229238491006703034124620545784566413664540684214361293017694020846391065875914794251435144458199
print("Start factoring...")
factors = sympy.factorint(rsa_260)
# Результат, возможно, не будет достигнут
print(factors)
Асимметричные алгоритмы, такие как RSA, используют вычислительную трудность разложения на простые множители и аналогичные проблемы для обеспечения безопасности шифрования. К сожалению, квантовый мир подчиняется своим законам.
Квантовые алгоритмы
В области криптографии особым вниманием пользуются два квантовых алгоритма. Алгоритм Шора обеспечивает эффективный способ разложения на простые множители. Если его выполнить на большом квантовом устройстве, то теоретически можно взломать асимметричные методы, такие как RSA. С практической точки зрения такой сценарий относится к будущему. В статье, опубликованной в Nature в 2023 году, сообщается, что для этого потребуется не менее 1 000 000 кубитов. Кроме того, трудно найти реализацию алгоритма, которая бы надежно масштабировалась на больших квантовых машинах. Предпринятая попытка компании IBM реализовать функцию во фреймворке Qiskit оказалась вытесненной версией 0.22.0. Однако экспериментальные реализации алгоритма Шора можно найти в интернете.
Алгоритм Гровера представляет угрозу для симметричного шифрования. Известный также как квантовый алгоритм поиска, он позволяет ускорить неструктурированный поиск входных данных для заданной функции. Квантовые компьютеры могут использовать его для ускорения криптоанализа методом перебора всех возможных вариантов для защиты симметрично зашифрованной информации. Однако, в отличие от алгоритма Шора, предлагаемое ускорение не является экспоненциальным. Проще говоря, увеличение длины ключа, используемого для шифрования, приводит к чрезмерному удорожанию поиска. Например, мощная атака на 128-битный ключ требует максимум 2¹²⁸ итераций. Если предположить, что поиск Гровера сокращает это число до 2⁶⁴, то удвоение длины ключа до 256 бит снова увеличивает его до 2¹²⁸ итераций. Это открывает путь к возможным обходным решениям.
Обходное решение: симметричное шифрование
При определенных условиях симметричное шифрование является готовым и простым способом противодействия квантовым алгоритмам. Причина в том, что поиск Гровера не масштабируется экспоненциально, а алгоритм Шора угрожает только асимметричным подходам. Насколько известно, симметричные алгоритмы с высокой степенью сложности можно считать квантовоустойчивыми.
В настоящее время как американский NIST (Национальный институт стандартов и технологий), так и немецкий BSI (Федеральное управление по информационной безопасности) относят AES-256 к этой категории. Аббревиатура AES расшифровывается как Advanced Encryption Standard (передовой стандарт шифрования), а число 256 означает битовую длину ключа. В Linux AES-256 реализуется программой GNU Privacy Guard (GnuPG).
Следующий shell-скрипт показывает, как можно зашифровать и затем расшифровать файл с помощью AES-256.
# Зашифровка
gpg --output encrypted.gpg --symmetric --cipher-algo AES256 plain.txt
# Расшифровка
gpg --output decrypted.txt --decrypt encrypted.gpg
Приведенный выше скрипт шифрует содержимое файла “plain.txt”, записывает шифротекст в документ “encrypted.gpg”, снова расшифровывает его и сохраняет результат в файле “decrypted.txt”. Перед шифрованием GnuPG запрашивает парольную фразу для генерации закрытого ключа. В целях безопасности очень важно выбрать надежную ключевую фразу и держать ее в секрете. GnuPG может запомнить эту фразу и не запрашивать ее при расшифровке. Чтобы очистить кэш, выполните следующую shell-команду:
gpg-connect-agent reloadagent /bye
Интеграция GnuPG в Python осуществляется достаточно просто с помощью модуля subprocess. Прототипная реализация шифрования с помощью AES-256 приведена в следующем фрагменте кода.
#!/usr/bin/env python
import subprocess
import getpass
# Чтение парольной фразы
passphrase = getpass.getpass("Passphrase:")
passphrase2 = getpass.getpass("Passphrase:")
if passphrase != passphrase2:
raise ValueError("Passphrases not identical!")
# Зашифровка
print("Encrypting...")
args = [
"gpg",
"--batch",
"--passphrase-fd", "0",
"--output", "encrypted.gpg",
"--symmetric",
"--yes",
"--cipher-algo", "AES256",
"plain.txt",
]
result = subprocess.run(
args, input=passphrase.encode(),
capture_output=True)
if result.returncode != 0:
raise ValueError(result.stderr)
Для получения парольной фразы приведенный выше скрипт использует модуль getpass. После подтверждения парольная фраза передается в GnuPG через стандартный ввод. На это указывает аргумент passphrase-fd 0. Кроме того, парольная фраза может быть передана в GnuPG в виде строки или файла с аргументами командной строки. Однако, поскольку эти аргументы видны другим пользователям, оба варианта были отвергнуты в прототипе.
Другим, более безопасным способом является использование GPG-Agent. Выбор варианта зависит от желаемого уровня безопасности. Здесь приводится примерный вариант, включающий шифрование и дешифрование. В качестве альтернативы GnuPG существуют и другие реализации AES-256. Здесь важно выбрать надежный источник.
Обходное решение: асимметричное шифрование
В поисках асимметричного решения хорошей отправной точкой является программа Post-Quantum Cryptography Standardization (стандартизация постквантовой криптографии), разработанная NIST. С 2016 года в рамках этой программы оценивается множество кандидатов на создание квантовоустойчивых алгоритмов. Одним из победителей стала система Kyber. В ней реализован так называемый механизм безопасной инкапсуляции ключей. Как и другие алгоритмы, Kyber решает трудноразрешимую задачу защиты обмена ключами между двумя сторонами. В его основе лежит не разложение на простые множители, а принцип, называемый “обучение с ошибками”. Уровень защиты Kyber зависит от длины ключа. Например, Kyber-1024 обеспечивает уровень безопасности, определяемый исследователями как “примерно эквивалентный AES-256”.
Эталонная реализация Kyber, написанная на языке C, доступна на GitHub. В Linux можно клонировать и собрать фреймворк, выполнив приведенные ниже shell-команды. Для установки необходимы предварительные условия, указанные в README проекта.
git clone https://github.com/pq-crystals/kyber.git
cd kyber/ref && make
Существует несколько способов интегрировать эталонную реализацию в Python. Один из них — написать программу на языке C и вызвать ее. Приведенная ниже функция на языке C использует Kyber для выполнения обмена ключами между двумя вымышленными персонажами, Алисой и Бобом. Полный исходный код — здесь.
#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include "kem.h"
#include "randombytes.h"
void round_trip(void) {
uint8_t pk[CRYPTO_PUBLICKEYBYTES];
uint8_t sk[CRYPTO_SECRETKEYBYTES];
uint8_t ct[CRYPTO_CIPHERTEXTBYTES];
uint8_t key_a[CRYPTO_BYTES];
uint8_t key_b[CRYPTO_BYTES];
//Алиса генерирует открытый ключ
crypto_kem_keypair(pk, sk);
print_key("Alice' public key", pk);
//Боб получает секретный ключ и создает ответ
crypto_kem_enc(ct, key_b, pk);
print_key("Bob's shared key", key_b);
print_key("Bob's response key", ct);
//Алиса использует ответ Боба для получения общего ключа
crypto_kem_dec(key_a, ct, sk);
print_key("Alice' shared key", key_a);
}
Не вдаваясь в детали, можно заметить, что в Kyber используется несколько открытых и закрытых ключей. В приведенном примере Алиса генерирует открытый ключ (pk) и закрытый ключ (sk). Далее Боб использует открытый ключ (pk) для получения общего ключа (key_b) и ключа ответа (ct). Последний возвращается Алисе. Наконец, Алиса использует ключ ответа (ct) и свой закрытый ключ (sk) для генерации экземпляра общего ключа (key_a). До тех пор пока обе стороны хранят в секрете свои закрытые и общие ключи, алгоритм обеспечивает защиту. При выполнении программы получаем результат, аналогичный приведенному ниже тексту.
Alice' public key: F0476B9B5867DD226588..
Bob's shared key: ADC41F30B665B1487A51..
Bob's response key: 9329C7951AF80028F42E..
Alice' shared key: ADC41F30B665B1487A51..
Для вызова функции языка C в Python используется модуль subprocess. В качестве альтернативы можно создать совместно используемую библиотеку и вызывать ее с помощью модуля ctypes. Второй вариант реализован в приведенном ниже Python-скрипте. После загрузки совместно используемой библиотеки, сгенерированной из C-кода Kyber, процедура round_trip вызывается как любая другая функция Python.
#!/usr/bin/env python
import os
import ctypes
# Загрузка общей библиотеки
libname = f"{os.getcwd()}/execute_round_trip1024.so"
clib = ctypes.CDLL(libname, mode=1)
print("Shared lib loaded successfully:")
print(clib)
# Вызов функции round trip
print("Executing round trip:")
clib.round_trip()
Помимо эталонной реализации Kyber, алгоритм реализован и другими поставщиками. В качестве примера можно привести проекты с открытым исходным кодом Botan и Open Quantum Safe.
Заключение
Как показывает проведенный нами анализ, квантовые технологии все еще находятся на ранних стадиях своего развития. Однако не стоит недооценивать угрозу, которую они представляют для шифрования и других криптографических методов, таких как сигнатуры. Прорывные инновации дадут толчок развитию в любой момент. Злоумышленники могут сохранять сообщения сейчас, а расшифровывать их позже. Поэтому меры безопасности должны быть приняты незамедлительно. Тем более что существуют обходные пути.
При правильном использовании симметричные алгоритмы, такие как AES-256, считаются квантовоустойчивыми. Кроме того, развиваются асимметричные решения, такие как Kyber. Какие именно альтернативы использовать, зависит от конкретного приложения. Согласно концепции Zero Trust (полное отсутствие зон доверия), наилучшую защиту обеспечивает комбинация подходов. Имейте в виду: квантовая угроза, подобно проблеме Y2K (проблеме 2000 года — предполагаемому компьютерному сбою тысячелетия) может оказаться самосбывающимся пророчеством.
Читайте также:
- AEGIS — система аутентификации платформы Ankorstore
- 7 расширенных возможностей Python
- Как автоматизировать удаление ненужных файлов с помощью Python
Читайте нас в Telegram, VK и Дзен
Перевод статьи Christian Koch: Post-Quantum Cryptography with Python and Linux
