Асимметричное шифрование

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

История

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

Первой практической реализацией асимметричного шифрования стала криптосистема RSA, разработанная в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлеманом. Она основана на вычислительной сложности факторизации больших целых чисел. В 1978 году алгоритм был опубликован, и до сих пор остаётся одним из самых широко используемых асимметричных алгоритмов.

В 1985 году Тахер Эль-Гамаль предложил криптосистему, основанную на сложности задачи дискретного логарифмирования (ElGamal). Позднее, в 1986 году, Нил Коблиц и Виктор Миллер независимо предложили криптографию на эллиптических кривых (ECC), которая обеспечивает сопоставимую стойкость при меньшей длине ключа.

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

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

Процесс шифрования и расшифрования выглядит следующим образом:

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

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

RSA

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

ElGamal

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

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

ECC (Elliptic Curve Cryptography) — подход, использующий алгебраическую структуру эллиптических кривых над конечными полями. Стойкость ECC основана на сложности задачи дискретного логарифмирования на эллиптической кривой. Главное преимущество — высокая криптостойкость при значительно меньшей длине ключа (например, 256-битный ключ ECC эквивалентен по стойкости 3072-битному ключу RSA). ECC широко применяется в мобильных устройствах и веб-протоколах.

Другие алгоритмы

• DSA (Digital Signature Algorithm) — алгоритм цифровой подписи, основанный на задаче дискретного логарифмирования.
• ECDSA (Elliptic Curve Digital Signature Algorithm) — вариант DSA на эллиптических кривых.
• NTRU — криптосистема, основанная на решётках (lattice-based cryptography), устойчивая к квантовым атакам.

Применение

Асимметричное шифрование является фундаментом современной информационной безопасности и используется в следующих областях:

Безопасная передача данных (SSL/TLS)

Протоколы SSL/TLS, обеспечивающие безопасность HTTPS-соединений, используют асимметричное шифрование для установления защищённого канала. При установлении соединения клиент и сервер обмениваются открытыми ключами и используют асимметричный алгоритм (например, RSA или ECDHE) для согласования общего сеансового ключа. После этого данные шифруются симметричным алгоритмом (например, AES), который работает быстрее.

Электронная почта (PGP, S/MIME)

Системы шифрования электронной почты, такие как PGP (Pretty Good Privacy) и S/MIME, используют асимметричное шифрование для обеспечения конфиденциальности и аутентификации. Отправитель шифрует сообщение открытым ключом получателя, а получатель расшифровывает его своим закрытым ключом. Также применяется цифровая подпись для подтверждения авторства.

Цифровые подписи

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

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

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

Аутентификация (SSH, VPN)

Протоколы SSH (Secure Shell) и многие VPN-решения используют асимметричное шифрование для аутентификации пользователей и серверов. Пользователь генерирует пару ключей, публичный ключ размещается на сервере, а приватный хранится у пользователя. При подключении сервер проверяет, что пользователь владеет соответствующим закрытым ключом.

Преимущества и недостатки

Преимущества

• Решение проблемы распределения ключей: Открытый ключ можно свободно распространять, не опасаясь компрометации.
• Масштабируемость: Для связи с N участниками требуется всего N пар ключей (по одной на каждого), в то время как в симметричных системах необходимо N(N-1)/2 ключей.
• Цифровые подписи: Обеспечивают неотказуемость и аутентификацию без предварительного обмена секретами.

Недостатки

• Низкая скорость: Асимметричное шифрование значительно медленнее симметричного (в сотни и тысячи раз) из-за сложных математических операций.
• Большая длина ключа: Для обеспечения высокой стойкости требуются ключи длиной от 2048 бит (RSA) и выше.
• Уязвимость к квантовым атакам: Многие современные асимметричные алгоритмы (RSA, ECC) могут быть взломаны с помощью квантового компьютера, способного выполнять алгоритм Шора. В связи с этим активно разрабатывается постквантовая криптография.

Сравнение с симметричным шифрованием

Постквантовая криптография

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

• Криптография на решётках (lattice-based): NTRU, Kyber, Dilithium.
• Криптография на основе кодов (code-based): McEliece.
• Криптография на основе хэш-функций (hash-based): SPHINCS+.
• Многомерная криптография (multivariate): Rainbow.

Национальный институт стандартов и технологий США (NIST) в 2024 году завершил отбор первых постквантовых стандартов, выбрав алгоритм Kyber для шифрования и Dilithium для цифровых подписей.

Источники

• Диффи, У., Хеллман, М. «New Directions in Cryptography» (1976).
• Ривест, Р., Шамир, А., Адлеман, Л. «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems» (1978).
• Коблиц, Н. «Elliptic Curve Cryptosystems» (1987).
• Миллер, В. «Use of Elliptic Curves in Cryptography» (1986).
• NIST. «Post-Quantum Cryptography: Final Report» (2024).
• Шнайер, Б. «Прикладная криптография» (1996).