Криптография с открытым ключом

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

История

Предпосылки и первые идеи

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

Публичная разработка (1976–1977)

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

Развитие и стандартизация

В 1980-е и 1990-е годы были созданы другие важные криптосистемы: криптография на эллиптических кривых (ECC), предложенная Нилом Коблицем и Виктором Миллером в 1985 году, и схема Эль-Гамаля (1985). В 1990-е годы началась массовая коммерциализация технологий (SSL/TLS, PGP). В 2000-е годы асимметричная криптография стала неотъемлемой частью интернет-безопасности, электронной подписи и блокчейн-технологий.

Основные принципы

Математическая основа

В основе криптографии с открытым ключом лежат так называемые односторонние функции с лазейкой (trapdoor one-way functions). Такая функция легко вычисляется в одном направлении, но обратное вычисление (нахождение исходных данных) является вычислительно сложным без знания дополнительной секретной информации — «лазейки» (закрытого ключа). Классическими примерами являются:

• Факторизация больших чисел (используется в RSA): перемножить два больших простых числа легко, но разложить их произведение на множители — трудно.
• Дискретное логарифмирование (используется в Diffie-Hellman, Эль-Гамале, DSA): возведение в степень по модулю простого числа легко, а нахождение показателя степени — трудно.
• Задача дискретного логарифмирования на эллиптической кривой (используется в ECDSA, EdDSA): сложение точек на кривой легко, а нахождение множителя — трудно.

Генерация ключей

Процесс начинается с генерации пары ключей. Сначала с помощью генератора случайных чисел создаётся закрытый ключ, который представляет собой большое число. Затем на основе закрытого ключа и математического алгоритма вычисляется открытый ключ. Открытый ключ может быть опубликован, например, в открытом реестре или передан напрямую.

Шифрование и расшифрование

1. Шифрование: Отправитель берёт открытый ключ получателя и сообщение, применяет алгоритм шифрования. Полученный шифротекст может быть расшифрован только с помощью соответствующего закрытого ключа.
2. Расшифрование: Получатель использует свой закрытый ключ для восстановления исходного сообщения из шифротекста. Даже если злоумышленник перехватит шифротекст и будет знать открытый ключ, он не сможет его расшифровать без закрытого ключа.

Виды и алгоритмы

Алгоритмы шифрования

• RSA: Основан на сложности факторизации больших чисел. Используется для шифрования и цифровых подписей. Длина ключа обычно составляет 2048 или 4096 бит.
• Эль-Гамаль: Основан на задаче дискретного логарифмирования. Используется в стандартах шифрования и в криптосистемах на эллиптических кривых.
• Криптосистемы на эллиптических кривых (ECC): Обеспечивают сопоставимую стойкость при значительно меньшей длине ключа (например, 256-битный ключ ECC эквивалентен по стойкости 3072-битному ключу RSA). Широко применяются в современных протоколах (TLS 1.3, Bitcoin, Ethereum).

Алгоритмы цифровой подписи

• DSA (Digital Signature Algorithm): Стандарт, разработанный NIST в 1991 году. Основан на дискретном логарифмировании.
• ECDSA (Elliptic Curve Digital Signature Algorithm): Версия DSA на эллиптических кривых. Используется в криптовалютах (Bitcoin, Ethereum) и в протоколах аутентификации.
• EdDSA (Edwards-curve Digital Signature Algorithm): Современный алгоритм подписи на эллиптических кривых (Ed25519, Ed448). Отличается высокой скоростью и устойчивостью к некоторым атакам.

Протоколы обмена ключами

• Diffie-Hellman (DH): Позволяет двум сторонам получить общий секретный ключ по незащищённому каналу связи, не передавая его напрямую.
• ECDH (Elliptic Curve Diffie-Hellman): Версия DH на эллиптических кривых. Используется в современных протоколах TLS и Signal.

Применение

Обеспечение конфиденциальности

• Шифрование электронной почты: Стандарты PGP (Pretty Good Privacy) и S/MIME используют асимметричное шифрование для защиты содержимого писем.
• Защита веб-трафика: Протоколы HTTPS (TLS/SSL) используют асимметричное шифрование на этапе установления соединения (рукопожатие) для безопасного обмена симметричным сеансовым ключом.
• VPN и SSH: Протоколы IPsec и SSH применяют асимметричную криптографию для аутентификации сторон и обмена ключами.

Аутентификация и целостность

• Цифровые подписи: Используются для подтверждения авторства и целостности электронных документов, программного обеспечения, финансовых транзакций. В России цифровые подписи регулируются Федеральным законом № 63-ФЗ «Об электронной подписи».
• Сертификаты открытых ключей: Инфраструктура открытых ключей (PKI) удостоверяет принадлежность открытого ключа конкретному лицу или организации через сертификаты, выдаваемые удостоверяющими центрами.

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

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

Критика и уязвимости

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

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

Атаки на реализацию

• Атаки по времени (Timing attacks): Злоумышленник может анализировать время выполнения криптографических операций для восстановления закрытого ключа.
• Атаки по побочным каналам (Side-channel attacks): Использование информации об энергопотреблении, электромагнитном излучении или акустических шумах устройства во время вычислений.
• Атаки с использованием некачественных генераторов случайных чисел: Если генератор случайных чисел при создании ключей предсказуем, это может привести к компрометации закрытого ключа.

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

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

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

• Первая публичная реализация асимметричного шифрования (RSA) была запатентована в 1983 году, и патент действовал до 2000 года, что ограничивало его свободное использование.
• В 1997 году правительство Великобритании рассекретило документы, показавшие, что Джеймс Эллис, Клиффорд Кокс и Малкольм Уильямсон из GCHQ разработали концепцию криптографии с открытым ключом на несколько лет раньше Диффи и Хеллмана.
• Размер открытого ключа в системе RSA обычно составляет 2048 бит, а в системе на эллиптических кривых (например, Curve25519) — всего 256 бит при сопоставимой криптографической стойкости.

Источники

• 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.
• Федеральный закон от 6 апреля 2011 г. № 63-ФЗ «Об электронной подписи» (с изменениями и дополнениями).
• NIST Special Publication 800-186: Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters.