Криптография на эллиптических кривых
- Автор метода
- Neal Koblitz
- Год
- 1985
- Тип
- asymmetric encryption and key agreement
- Семейство
- Public-key cryptography
Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском
Что он делает?
Криптография на эллиптических кривых (ECC) — это система криптографии с открытым ключом, основанная на алгебраической структуре эллиптических кривых над конечными полями.
Предложенная независимо Нилом Коблицем и Виктором Миллером в 1985 году, ECC обеспечивает эквивалентную RSA безопасность при значительно меньших размерах ключей. Современная криптография всё чаще отдаёт предпочтение ECC из-за её эффективности: 256-битный ключ ECC обеспечивает безопасность, сравнимую с 2048-битным ключом RSA, что делает её идеальной для ограниченных сред и высокопроизводительных систем.
Интуиция метода
ECC основана на проблеме дискретного логарифмирования на эллиптических кривых: при заданном уравнении кривой и двух точках легко вычислить их сумму, используя геометрические свойства кривой, но чрезвычайно трудно обратить эту операцию и найти, сколько раз одну точку нужно прибавить саму к себе, чтобы получить другую точку. Эта асимметрия позволяет безопасно генерировать и обмениваться ключами. В отличие от RSA, полагающегося на проблему факторизации, сложность ECC обусловлена структурой группы эллиптической кривой.
История
ECC была независимо изобретена Нилом Коблицем и Виктором Миллером в 1985–1987 годах. Первоначально внедрение было медленным из-за патентных проблем и устоявшегося доминирования RSA. Однако с 2000-х годов ECC приобрела известность как превосходящая альтернатива, особенно после того, как Агентство национальной безопасности (АНБ) рекомендовало эллиптические кривые для секретной информации. Современные протоколы, такие как TLS 1.3, Signal и блокчейн-системы, в значительной степени стандартизировали кривые ECC, такие как Curve25519 и P-256.
Когда применять
ECC идеально подходит для приложений, требующих надёжной безопасности при ограниченных ресурсах, таких как мобильные устройства, системы Интернета вещей (IoT) и встраиваемые системы. Она является стандартом в современных интернет-протоколах (TLS 1.3 использует ECDHE), блокчейн-системах (Bitcoin и Ethereum используют ECDSA) и приложениях для обмена сообщениями (Signal использует Curve25519). ECC следует предпочитать RSA для новых систем из-за превосходной производительности и эквивалентной безопасности.
Ограничения и замечания
- Более сложные математические основы, чем у RSA, что затрудняет реализацию и анализ.
- Требует тщательного выбора параметров эллиптической кривой; слабые кривые (например, с низкой степенью вложения) уязвимы для атак.
- Безопасность сильно зависит от используемой конкретной кривой; стандартизированные кривые предпочтительны, но их выбор вызывает некоторые споры.
Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.
Сильные стороны
- Значительно меньшие размеры ключей по сравнению с RSA при эквивалентных уровнях безопасности, что снижает накладные расходы на хранение и передачу.
- Более быстрое создание ключей, шифрование и дешифрование по сравнению с RSA при той же силе безопасности.
- Хорошо подходит для устройств с ограниченными ресурсами, таких как мобильные телефоны, устройства IoT и смарт-карты.
- Все более стандартизируется и поддерживается в современных криптографических библиотеках и протоколах.
Применение
- Шифрование TLS/SSL для HTTPS и современной веб-безопасности с использованием обмена ключами ECDHE
- Блокчейн и криптовалютные системы (Bitcoin использует ECDSA на secp256k1, Ethereum на secp256k1)
- Обмен сообщениями и безопасная связь (Signal Protocol использует Curve25519 и X25519)
- Аутентификация и цифровые подписи в смарт-картах, аппаратных модулях безопасности и государственных удостоверениях
- Безопасность IoT и встраиваемых систем с ограниченными вычислительными ресурсами
- Исследования в области постквантовой криптографии, изучение гиперболических кривых для квантово-устойчивых алгоритмов
Как это работает
Как это работает
Выберите уравнение эллиптической кривой (обычно y^2 = x^3 + ax + b над конечным полем), образующую точку G на кривой и порядок n (количество точек на кривой). Закрытый ключ d — это случайное целое число, а открытый ключ Q = d × G вычисляется путём умножения точек.
Точки на эллиптической кривой образуют группу относительно геометрической операции сложения. Чтобы сложить две различные точки, проводят через них прямую, находят точку её пересечения с кривой и отражают результат относительно оси x. Для удвоения точки используется касательная.
Чтобы зашифровать сообщение для открытого ключа Q, генерируют случайное k и вычисляют два значения: точку (x, y) = k × G и зашифрованное сообщение, которое объединяет сообщение с хешем k × Q.
Получатель использует свой закрытый ключ d для вычисления d × (k × G) = k × (d × G) = k × Q, восстанавливая общий секрет и расшифровывая сообщение.
Частые ошибки
- Реализация умножения точек без защиты от атак по побочным каналам может привести к утечке закрытого ключа через анализ времени или энергопотребления.
- Использование слабых или нестандартных эллиптических кривых, которые могут иметь математические слабости, снижающие безопасность до нулевого уровня.
- Неиспользование криптографически стойкого генератора случайных чисел для эфемерного ключа k в подписях ECDSA, что делает подписи подделываемыми.
Часто задаваемые вопросы
Почему 256-битный ключ ECC так же безопасен, как 2048-битный ключ RSA?
Проблема дискретного логарифмирования на эллиптических кривых сложнее, чем проблема факторизации целых чисел. Решение ECDLP требует экспоненциального времени даже на квантовых компьютерах с использованием алгоритма Шора, тогда как факторизация целых чисел становится полиномиальной по времени на квантовых компьютерах.
Какие эллиптические кривые используются наиболее часто?
Стандартизированные NIST кривые P-256, P-384 и P-521. Кривая Curve25519 Бернштейна предпочтительна в современных системах из-за её устойчивости к атакам на реализацию. Bitcoin использует secp256k1, а Ethereum также использует secp256k1 для подписей аккаунтов и транзакций.
Уязвима ли ECC для квантовых компьютеров?
Да, алгоритм Шора может решать проблему дискретного логарифмирования на эллиптических кривых на квантовых компьютерах, делая уязвимыми как ECC, так и RSA. Исследования в области постквантовой криптографии разрабатывают решётчатые, кодовые и многомерные альтернативы.
В чём разница между ECDH и ECDSA?
ECDH (Elliptic Curve Diffie-Hellman) — это протокол согласования ключей для установления общих секретов по незащищенным каналам. ECDSA (Elliptic Curve Digital Signature Algorithm) используется для создания и проверки цифровых подписей.
Можно ли использовать один и тот же ключ для ECDH и ECDSA?
Технически это возможно, но не рекомендуется. Использование отдельных ключей для операций шифрования и подписи следует принципу разделения ключей и снижает риск тонких уязвимостей.
Похожие методы
Источники
Miller, V. S. (1985). Use of Elliptic Curves in Cryptography. In Proceedings of the Advances in Cryptology - CRYPTO 1985, LNCS 218, pp. 417-426.
Открыть ссылку DOIСкопировано.Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177), 203-209.
Открыть ссылку DOIСкопировано.