Тахер Эль-Гамаль

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

Биография

Тахер Эль-Гамаль родился в 1955 году в Египте. Получил степень бакалавра наук в области электротехники в Каирском университете в 1977 году. Затем продолжил обучение в Стэнфордском университете (США), где в 1981 году получил степень магистра, а в 1985 году — докторскую степень (Ph.D.) по электротехнике. Его научным руководителем был Мартин Хеллман, один из пионеров криптографии с открытым ключом.

После защиты диссертации Эль-Гамаль работал в исследовательском центре корпорации Hewlett-Packard (HP Labs) в Пало-Альто, Калифорния. В 1990-х годах он стал одним из основателей компании VeriSign, которая занималась цифровыми сертификатами и безопасностью интернет-транзакций. В 2000-х годах Эль-Гамаль перешёл в компанию RSA Security (ныне подразделение Dell Technologies), где занимал должность главного научного сотрудника. В 2010-х годах он работал в компании Cisco Systems, а затем в стартапе в области блокчейн-технологий.

Научный вклад

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

В 1985 году Тахер Эль-Гамаль опубликовал работу «A public key cryptosystem and a signature scheme based on discrete logarithms», в которой предложил асимметричную криптосистему, основанную на сложности задачи дискретного логарифмирования. Эта система, получившая название криптосистема Эль-Гамаля, стала одной из ключевых в современной криптографии.

Алгоритм работает следующим образом:

• Генерация ключей: выбирается большое простое число \( p \) и генератор мультипликативной группы \( g \). Случайное число \( x \) (секретный ключ) используется для вычисления открытого ключа \( y = g^x \mod p \).
• Шифрование: отправитель выбирает случайное число \( k \), вычисляет \( c_1 = g^k \mod p \) и \( c_2 = m \cdot y^k \mod p \), где \( m \) — открытый текст. Шифротекст — пара \( (c_1, c_2) \).
• Расшифрование: получатель использует секретный ключ \( x \) для вычисления \( m = c_2 \cdot (c_1^x)^{-1} \mod p \).

Криптосистема Эль-Гамаля обладает свойством гомоморфизма: произведение шифротекстов соответствует шифротексту произведения открытых текстов. Это свойство используется в некоторых протоколах электронного голосования и облачных вычислениях.

Цифровая подпись Эль-Гамаля

В той же работе 1985 года Эль-Гамаль предложил схему цифровой подписи на основе дискретного логарифмирования. Эта схема стала основой для ряда стандартов, включая американский стандарт цифровой подписи (DSA — Digital Signature Algorithm), разработанный NIST в 1991 году. В отличие от подписи RSA, подпись Эль-Гамаля является вероятностной (использует случайное число \( k \)), что делает её более устойчивой к некоторым атакам.

Эллиптические кривые

Тахер Эль-Гамаль внёс значительный вклад в развитие криптографии на эллиптических кривых (ECC). В 1985 году, независимо от Виктора Миллера, он предложил использовать эллиптические кривые для построения криптосистем с открытым ключом. Эллиптическая криптография позволяет достичь того же уровня безопасности, что и RSA, но при значительно меньшей длине ключа (например, 256-битный ключ ECC эквивалентен 3072-битному ключу RSA). Это делает ECC особенно эффективной для мобильных устройств, смарт-карт и интернета вещей.

Применение

Криптосистема Эль-Гамаля и её модификации широко используются в современных информационных системах:

• Стандарты шифрования: алгоритм включён в стандарт IEEE P1363, а также в протоколы OpenPGP и GNU Privacy Guard (GnuPG).
• Электронная подпись: схема Эль-Гамаля лежит в основе стандарта DSA, а также его варианта на эллиптических кривых (ECDSA), используемого в криптовалютах (например, Bitcoin, Ethereum).
• Гомоморфное шифрование: свойство гомоморфизма используется в системах защищённого облачного хранения и обработки данных.
• Протоколы аутентификации: алгоритмы на основе Эль-Гамаля применяются в протоколах Диффи-Хеллмана и STS (Station-to-Station).

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

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

Схема цифровой подписи Эль-Гамаля также имеет ограничения: если случайное число \( k \) используется повторно, секретный ключ может быть восстановлен. Это привело к известным инцидентам, например, в 2010 году в протоколе Sony PlayStation 3, где была использована фиксированная константа вместо случайного числа.

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

• Тахер Эль-Гамаль является соавтором нескольких патентов в области криптографии, включая патент на метод генерации цифровых подписей (US 4,995,082).
• В 2012 году он был удостоен премии IEEE Richard W. Hamming Medal за вклад в теорию и практику криптографии.
• Эль-Гамаль активно выступает за использование криптографии с открытым ключом в защите персональных данных и конфиденциальности в интернете.

Источники

• ElGamal, T. (1985). «A public key cryptosystem and a signature scheme based on discrete logarithms». IEEE Transactions on Information Theory, 31(4), 469–472.
• Menezes, A., van Oorschot, P., Vanstone, S. (1996). «Handbook of Applied Cryptography». CRC Press.
• Schneier, B. (1996). «Applied Cryptography: Protocols, Algorithms, and Source Code in C». John Wiley & Sons.
• NIST (1991). «Digital Signature Standard (DSS)». Federal Information Processing Standards Publication 186.
• IEEE (2000). «Standard Specifications for Public-Key Cryptography». IEEE P1363.