Криптосистема с открытым ключом

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

История

Предпосылки и ранние идеи

До середины 1970-х годов вся криптография была симметричной: для шифрования и расшифрования использовался один и тот же ключ, который необходимо было передавать отправителю и получателю по защищённому каналу. Это создавало серьёзную проблему распределения ключей, особенно в системах с большим числом участников. В 1970 году британский криптограф Джеймс Эллис из Центра правительственной связи (GCHQ) предложил идею асимметричного шифрования, но не смог найти практической реализации. В 1973 году его коллега Клиффорд Кокс разработал математическую схему, основанную на сложности факторизации больших чисел, которая фактически предвосхитила алгоритм RSA. Однако эти работы были засекречены и стали известны лишь в 1997 году.

Публикация и признание

В 1976 году Уитфилд Диффи и Мартин Хеллман опубликовали статью «New Directions in Cryptography», в которой впервые открыто изложили концепцию криптосистемы с открытым ключом и предложили протокол обмена ключами (протокол Диффи — Хеллмана). В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман представили алгоритм RSA, ставший первой полной асимметричной криптосистемой, пригодной для шифрования и цифровой подписи. За эти разработки Диффи, Хеллман и Ривест в 2015 году получили премию Тьюринга.

Принцип работы

Основные понятия

Криптосистема с открытым ключом основана на использовании пары ключей:

• Открытый ключ (public key) — известен всем участникам системы, используется для шифрования сообщений и проверки подписей.
• Закрытый ключ (private key) — известен только владельцу, используется для расшифрования и создания подписей.

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

Процесс шифрования

1. Отправитель получает открытый ключ получателя (например, из открытого репозитория или по незащищённому каналу).
2. Отправитель шифрует сообщение с помощью открытого ключа, используя алгоритм шифрования (например, RSA).
3. Зашифрованный текст передаётся получателю по любому каналу.
4. Получатель расшифровывает текст с помощью своего закрытого ключа.

Цифровая подпись

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

1. Владелец подписывает документ своим закрытым ключом.
2. Любой проверяющий может использовать открытый ключ владельца для проверки подлинности подписи и целостности документа.

Классификация асимметричных криптосистем

По сложности математической задачи

• Факторизационные — безопасность основана на сложности разложения большого целого числа на простые множители. Пример: RSA.
• Дискретно-логарифмические — безопасность основана на сложности вычисления дискретного логарифма в конечной группе. Примеры: протокол Диффи — Хеллмана, алгоритм Эль-Гамаля, криптосистемы на эллиптических кривых (ECC).
• На основе решёток — безопасность основана на сложности задач теории решёток (например, LWE). Примеры: NTRU, Kyber, Dilithium.
• На основе кодов — безопасность основана на сложности декодирования линейных кодов. Пример: криптосистема Мак-Элиса.
• На основе хэш-функций — используются для построения схем подписи (например, подписи Меркла).

По назначению

• Шифрование — RSA, Эль-Гамаля, NTRU.
• Цифровая подпись — RSA, DSA, ECDSA, EdDSA, Dilithium.
• Обмен ключами — протокол Диффи — Хеллмана, ECDH.

Основные алгоритмы

RSA

RSA (Rivest–Shamir–Adleman) — один из первых и наиболее распространённых асимметричных алгоритмов. Его стойкость основана на сложности факторизации произведения двух больших простых чисел. Используется для шифрования и цифровой подписи. Длина ключа обычно составляет 2048 или 4096 бит.

Криптосистема Эль-Гамаля

Разработана Тахером Эль-Гамалем в 1985 году. Основана на задаче дискретного логарифмирования. Используется для шифрования и подписи. В отличие от RSA, является вероятностной: один и тот же открытый текст может быть зашифрован по-разному в зависимости от случайного числа.

Криптосистемы на эллиптических кривых (ECC)

ECC — класс алгоритмов, использующих группы точек на эллиптических кривых. Позволяют достичь той же стойкости, что и RSA, при значительно меньшей длине ключа (например, 256-битный ключ ECC эквивалентен 3072-битному ключу RSA). Широко применяются в современных протоколах (TLS, Bitcoin, Ethereum). Примеры: ECDSA (цифровая подпись), ECDH (обмен ключами).

Постквантовые криптосистемы

С развитием квантовых компьютеров классические асимметричные алгоритмы (RSA, ECC) становятся уязвимыми для атаки с использованием алгоритма Шора. В связи с этим активно разрабатываются постквантовые криптосистемы, устойчивые к квантовым атакам. К ним относятся:

• Криптосистемы на основе решёток — например, CRYSTALS-Kyber (шифрование) и CRYSTALS-Dilithium (подпись), выбранные NIST в 2022 году.
• Криптосистемы на основе хэш-функций — например, SPHINCS+.
• Криптосистемы на основе кодов — например, Classic McEliece.

Применение

Защита каналов связи

Асимметричные криптосистемы лежат в основе протоколов защищённой передачи данных, таких как TLS/SSL (используется в HTTPS), SSH, IPsec. В этих протоколах асимметричное шифрование применяется для аутентификации сторон и безопасного обмена сессионными ключами, после чего для шифрования данных используются симметричные алгоритмы (например, AES).

Электронная подпись

Цифровые подписи на основе асимметричных алгоритмов применяются для подтверждения авторства и целостности электронных документов, в том числе в государственных информационных системах (например, в России — ГОСТ Р 34.10-2012, основанный на эллиптических кривых), в банковской сфере, в системах электронного документооборота.

Криптовалюты и блокчейн

В криптовалютах, таких как Bitcoin и Ethereum, используются асимметричные криптосистемы для создания адресов (открытые ключи) и подписи транзакций (закрытые ключи). В Bitcoin применяется алгоритм ECDSA на эллиптической кривой secp256k1.

Аутентификация и управление доступом

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

Критика и ограничения

Производительность

Асимметричные алгоритмы значительно медленнее симметричных при шифровании больших объёмов данных. Например, RSA-2048 на современных процессорах может шифровать данные со скоростью порядка нескольких мегабайт в секунду, тогда как AES-256 — сотни мегабайт в секунду. Поэтому на практике асимметричное шифрование используется только для ключей и небольших сообщений, а основные данные шифруются симметрично.

Уязвимость к квантовым атакам

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

Управление ключами

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

Интересные факты

• Алгоритм RSA был назван по первым буквам фамилий его создателей — Ривест, Шамир, Адлеман.
• В 1997 году британское правительство рассекретило документы, показавшие, что асимметричная криптография была изобретена в GCHQ на несколько лет раньше, чем опубликована Диффи и Хеллманом.
• Протокол Диффи — Хеллмана не является полной криптосистемой, так как не обеспечивает шифрования сообщений, а только позволяет двум сторонам согласовать общий секретный ключ.
• В 2022 году Национальный институт стандартов и технологий США (NIST) выбрал первые постквантовые алгоритмы для стандартизации: CRYSTALS-Kyber (шифрование) и CRYSTALS-Dilithium (подпись).

Источники

• Diffie, W., Hellman, M. E. (1976). «New Directions in Cryptography». IEEE Transactions on Information Theory.
• Rivest, R. L., Shamir, A., Adleman, L. (1978). «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems». Communications of the ACM.
• Menezes, A. J., van Oorschot, P. C., Vanstone, S. A. (1996). «Handbook of Applied Cryptography». CRC Press.
• NIST (2022). «Post-Quantum Cryptography: Selected Algorithms».
• ГОСТ Р 34.10-2012. «Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи».