EC-ElGamal

EC-ElGamal (эллиптическая криптосистема Эль-Гамаля) — это асимметричный криптографический алгоритм с открытым ключом, основанный на сложности задачи дискретного логарифмирования в группе точек эллиптической кривой. Является адаптацией классической схемы Эль-Гамаля, предложенной Тахером Эль-Гамалем в 1985 году, для работы с эллиптическими кривыми. Обеспечивает шифрование и цифровую подпись, при этом обладает меньшим размером ключей по сравнению с аналогами, использующими конечные поля, при эквивалентном уровне стойкости.

История

Схема Эль-Гамаля была предложена в 1985 году египетским криптографом Тахером Эль-Гамалем как расширение протокола Диффи — Хеллмана для шифрования. В 1987 году Нил Коблиц и Виктор Миллер независимо друг от друга предложили использовать эллиптические кривые в криптографии, что привело к созданию алгоритмов на их основе, включая EC-ElGamal. Первые практические реализации появились в середине 1990-х годов, когда были разработаны стандарты на эллиптическую криптографию (например, ANSI X9.62, IEEE P1363). В 2000-х годах EC-ElGamal стал одним из основных алгоритмов для шифрования в системах с открытым ключом, особенно в средах с ограниченными вычислительными ресурсами, таких как смарт-карты и устройства Интернета вещей.

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

EC-ElGamal базируется на алгебраической структуре эллиптической кривой — множестве точек, удовлетворяющих уравнению: \[ y^2 = x^3 + ax + b \mod p \] где \(p\) — простое число, а \(a\) и \(b\) — коэффициенты, обеспечивающие отсутствие сингулярностей (дискриминант не равен нулю). Точки кривой образуют абелеву группу с операцией сложения точек. Для криптографических целей выбирается циклическая подгруппа простого порядка \(n\) с генератором \(G\).

Задача дискретного логарифмирования на эллиптической кривой (ECDLP)

Стойкость EC-ElGamal основана на вычислительной сложности задачи дискретного логарифмирования на эллиптической кривой: для заданных точек \(P\) и \(Q = kP\) найти целое число \(k\) (секретный ключ). Наилучшие известные алгоритмы решения ECDLP (например, метод Полларда — ро) имеют экспоненциальную сложность, что делает EC-ElGamal устойчивым к атакам при правильном выборе параметров.

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

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

1. Выбирается эллиптическая кривая \(E\) над полем \(\mathbb{F}_p\) с параметрами \(a, b, p\).
2. Выбирается базовая точка \(G\) простого порядка \(n\).
3. Случайным образом выбирается секретный ключ \(d\) — целое число из интервала \([1, n-1]\).
4. Вычисляется открытый ключ \(Q = dG\).
5. Открытый ключ: \((E, G, n, Q)\), закрытый ключ: \(d\).

Шифрование

Для шифрования сообщения \(m\) (представленного в виде точки на кривой \(M\)):

1. Выбирается случайное целое число \(k\) из интервала \([1, n-1]\).
2. Вычисляется точка \(C_1 = kG\).
3. Вычисляется точка \(C_2 = M + kQ\).
4. Шифротекст: \((C_1, C_2)\).

Дешифрование

Получатель, имея закрытый ключ \(d\):

1. Вычисляет точку \(dC_1 = d(kG) = k(dG) = kQ\).
2. Восстанавливает сообщение: \(M = C_2 - dC_1\).

Отображение сообщений в точки кривой

Поскольку EC-ElGamal шифрует точки на кривой, а не произвольные битовые строки, требуется процедура кодирования сообщения в точку. Один из методов — метод Коблица, при котором сообщение \(m\) представляется как координата \(x\) точки, а \(y\) вычисляется из уравнения кривой. Для этого выбирается параметр \(\ell\) (обычно \(\ell = 20\)), и сообщение умножается на \(\ell\): \(x = m\ell + j\), где \(j\) — целое число от 0 до \(\ell-1\), такое, что \(x\) является координатой точки на кривой. Вероятность успеха высока, так как для каждого \(x\) существует примерно 50% точек на кривой.

Свойства

Гомоморфизм

EC-ElGamal обладает свойством гомоморфизма по сложению: произведение (в смысле сложения точек) шифротекстов соответствует шифрованию суммы исходных сообщений. Если \(E(m_1) = (C_{1,1}, C_{2,1})\) и \(E(m_2) = (C_{1,2}, C_{2,2})\), то: \[ E(m_1 + m_2) = (C_{1,1} + C_{1,2}, C_{2,1} + C_{2,2}) \] Это свойство используется в гомоморфном шифровании и протоколах с нулевым разглашением.

Размер шифротекста

Шифротекст состоит из двух точек на кривой, что приводит к расширению данных в 2 раза по сравнению с открытым текстом (при кодировании сообщения в точку). Для сообщения длиной \(n\) бит размер шифротекста составляет \(2n\) бит.

Стойкость

EC-ElGamal устойчив к атакам на основе выбранного открытого текста (IND-CPA) при условии, что задача ECDLP является трудноразрешимой. Однако он не является устойчивым к атакам на основе выбранного шифротекста (IND-CCA2) без дополнительных модификаций, таких как использование схемы Фуджисаки — Окамото или преобразования Cramer-Shoup.

Применение

EC-ElGamal используется в различных криптографических протоколах и системах:

• Системы электронной подписи — на основе EC-ElGamal построен стандарт цифровой подписи ECDSA (Elliptic Curve Digital Signature Algorithm), широко применяемый в блокчейн-технологиях (например, в биткойне).
• Гомоморфное шифрование — используется в системах конфиденциальных вычислений, где требуется обработка зашифрованных данных без их расшифровки.
• Протоколы с нулевым разглашением — применяется для доказательства знания секретного ключа без его раскрытия.
• Криптовалюты и блокчейн — EC-ElGamal используется в некоторых криптовалютах для анонимных транзакций (например, в Monero, где применяется схема RingCT на основе EC-ElGamal).
• Интернет вещей (IoT) — благодаря малому размеру ключей и высокой скорости вычислений EC-ElGamal подходит для устройств с ограниченными ресурсами.

Сравнение с другими алгоритмами

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

• Расширение данных — шифротекст в 2 раза больше открытого текста, что может быть неэффективно для больших сообщений.
• Необходимость кодирования — требуется преобразование сообщения в точку на кривой, что усложняет реализацию.
• Уязвимость к атакам на основе выбранного шифротекста — без дополнительных мер EC-ElGamal не обеспечивает IND-CCA2.
• Зависимость от параметров кривой — неправильный выбор кривой (например, с малым порядком или сингулярностью) может привести к потере стойкости.
• Уязвимость к квантовым компьютерам — как и все алгоритмы на основе факторизации и дискретного логарифмирования, EC-ElGamal будет взломан при появлении достаточно мощного квантового компьютера (алгоритм Шора).

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

• EC-ElGamal является основой для схемы шифрования ElGamal на эллиптических кривых, используемой в стандарте IEEE P1363.
• В 2013 году Национальный институт стандартов и технологий США (NIST) рекомендовал использовать эллиптические кривые с длиной ключа не менее 256 бит для обеспечения стойкости до 2030 года.
• EC-ElGamal поддерживает мультипликативное гомоморфное шифрование только в том случае, если сообщения представлены в виде точек на кривой, что ограничивает его применение в некоторых протоколах.

Источники

• ElGamal, T. (1985). A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory.
• Koblitz, N. (1987). Elliptic Curve Cryptosystems. Mathematics of Computation.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press.
• Hankerson, D., Menezes, A., Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer.
• NIST Special Publication 800-186 (2023). Recommendations for Discrete Logarithm-based Cryptography: Elliptic Curve Domain Parameters.