Шифрование Эль-Гамаля

Криптосистема с открытым ключом

В криптографии система шифрования ElGamal представляет собой асимметричный алгоритм шифрования для криптографии с открытым ключом , основанный на обмене ключами Диффи–Хеллмана . Он был описан Тахером Эльгамалем в 1985 году. ^[1] Шифрование ElGamal используется в свободном программном обеспечении GNU Privacy Guard , последних версиях PGP и других криптосистемах . Алгоритм цифровой подписи (DSA) является вариантом схемы подписи ElGamal , которую не следует путать с шифрованием ElGamal.

Шифрование Эль-Гамаля может быть определено над любой циклической группой , например мультипликативной группой целых чисел по модулю  n, тогда и только тогда, когда n равно 1, 2, 4, p ^k или 2 p ^k , где p — нечетное простое число, а k > 0. Его безопасность зависит от сложности определенной задачи, связанной с вычислением дискретных логарифмов . ${\displaystyle G}$ ${\displaystyle G}$

Алгоритм

Алгоритм можно описать как сначала выполняющий обмен ключами Диффи-Хеллмана для установления общего секрета , а затем использующий его как одноразовый блокнот для шифрования сообщения. Шифрование Эль-Гамаля выполняется в три этапа: генерация ключа, шифрование и расшифровка. Первый этап — это чисто обмен ключами, тогда как последние два смешивают вычисления обмена ключами с вычислениями сообщения. ${\displaystyle s}$

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

Первая сторона, Алиса, генерирует пару ключей следующим образом:

• Сгенерируйте эффективное описание циклической группы порядка с генератором . Пусть представляет собой единичный элемент . ${\displaystyle G\,}$ ${\displaystyle q\,}$ ${\displaystyle g}$ ${\displaystyle e}$ ${\displaystyle G}$

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

• Выберите случайное целое число из . ${\displaystyle x}$ ${\displaystyle \{1,\ldots ,q-1\}}$
• Вычислить . ${\displaystyle h:=g^{x}}$
• Открытый ключ состоит из значений . Алиса публикует этот открытый ключ и сохраняет его как свой закрытый ключ , который должен храниться в секрете. ${\displaystyle (G,q,g,h)}$ ${\displaystyle x}$

Шифрование

Вторая сторона, Боб, шифрует сообщение для Алисы с помощью ее открытого ключа следующим образом: ${\displaystyle M}$ ${\displaystyle (G,q,g,h)}$

• Сопоставьте сообщение с элементом , используя функцию обратимого сопоставления. ${\displaystyle M}$ ${\displaystyle m}$ ${\displaystyle G}$
• Выберите случайное целое число из . ${\displaystyle y}$ ${\displaystyle \{1,\ldots ,q-1\}}$
• Вычислить . Это называется общим секретом . ${\displaystyle s:=h^{y}}$
• Вычислить . ${\displaystyle c_{1}:=g^{y}}$
• Вычислить . ${\displaystyle c_{2}:=m\cdot s}$
• Боб отправляет зашифрованный текст Алисе. ${\displaystyle (c_{1},c_{2})}$

Обратите внимание, что если вы знаете и зашифрованный текст , и открытый текст , вы можете легко найти общий секрет , так как . Поэтому для каждого сообщения генерируется новый и, следовательно, новый для повышения безопасности. По этой причине также называется эфемерным ключом . ${\displaystyle (c_{1},c_{2})}$ ${\displaystyle m}$ ${\displaystyle s}$ ${\displaystyle c_{2}\cdot m^{-1}=s}$ ${\displaystyle y}$ ${\displaystyle s}$ ${\displaystyle y}$

Расшифровка

Алиса расшифровывает зашифрованный текст с помощью своего закрытого ключа следующим образом: ${\displaystyle (c_{1},c_{2})}$ ${\displaystyle x}$

• Вычислить . Так как , , и, таким образом, это тот же самый общий секрет, который использовался Бобом при шифровании. ${\displaystyle s:=c_{1}^{x}}$ ${\displaystyle c_{1}=g^{y}}$ ${\displaystyle c_{1}^{x}=g^{xy}=h^{y}}$
• Вычислить , обратную величину в группе . Это можно вычислить одним из нескольких способов. Если — подгруппа мультипликативной группы целых чисел по модулю  , где — простое число, то модульную мультипликативную обратную величину можно вычислить с помощью расширенного алгоритма Евклида . Альтернативой является вычисление как . Это обратная величина из-за теоремы Лагранжа , поскольку . ${\displaystyle s^{-1}}$ ${\displaystyle s}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle s^{-1}}$ ${\displaystyle c_{1}^{q-x}}$ ${\displaystyle s}$ ${\displaystyle s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e}$
• Вычислить . Это вычисление дает исходное сообщение , потому что ; следовательно . ${\displaystyle m:=c_{2}\cdot s^{-1}}$ ${\displaystyle m}$ ${\displaystyle c_{2}=m\cdot s}$ ${\displaystyle c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m}$
• Вернитесь к открытому текстовому сообщению . ${\displaystyle m}$ ${\displaystyle M}$

Практическое использование

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

Безопасность

Безопасность схемы Эль-Гамаля зависит от свойств базовой группы , а также от любой схемы заполнения, используемой в сообщениях. Если вычислительное предположение Диффи-Хеллмана (CDH) выполняется в базовой циклической группе , то функция шифрования является односторонней . ^[2] ${\displaystyle G}$ ${\displaystyle G}$

Если предположение о решении Диффи–Хеллмана (DDH) выполняется в , то Эль-Гамаль достигает семантической безопасности . ^{[2] [3]} Семантическая безопасность не подразумевается только вычислительным предположением Диффи–Хеллмана. См. Предположение о решении Диффи–Хеллмана для обсуждения групп, где предположение считается выполненным. ${\displaystyle G}$

Шифрование Эль-Гамаля безусловно податливо , и поэтому не является безопасным при атаке с использованием выбранного шифротекста . Например, имея шифрование некоторого (возможно неизвестного) сообщения , можно легко построить действительное шифрование сообщения . ${\displaystyle (c_{1},c_{2})}$ ${\displaystyle m}$ ${\displaystyle (c_{1},2c_{2})}$ ${\displaystyle 2m}$

Для достижения безопасности выбранного шифртекста схема должна быть дополнительно модифицирована или должна быть использована соответствующая схема заполнения. В зависимости от модификации предположение DDH может быть необходимым или необязательным.

Также были предложены другие схемы, связанные с ElGamal, которые обеспечивают безопасность против атак с использованием выбранного шифртекста. Криптосистема Крамера–Шоупа безопасна при атаке с использованием выбранного шифртекста, предполагая, что DDH выполняется для . Ее доказательство не использует модель случайного оракула . Другая предложенная схема — DHIES , ^[4] доказательство которой требует предположения, которое сильнее предположения DDH. ${\displaystyle G}$

Эффективность

Шифрование Эль-Гамаля является вероятностным , то есть один открытый текст может быть зашифрован множеством возможных шифртекстов, в результате чего общее шифрование Эль-Гамаля обеспечивает расширение размера открытого текста до размера шифртекста в соотношении 1:2.

Шифрование по Эль-Гамалю требует двух возведений в степень ; однако эти возведения в степень не зависят от сообщения и могут быть вычислены заранее, если это необходимо. Расшифровка требует одного возведения в степень и одного вычисления групповой инверсии, которые, однако, можно легко объединить в одно возведение в степень.

Смотрите также

• Тахер Элгамал , разработчик этой и других криптосистем
• Схема подписи Эль-Гамаля
• Гомоморфное шифрование

Дальнейшее чтение

• AJ Menezes; PC van Oorschot; SA Vanstone. "Глава 8.4 Шифрование с открытым ключом Эль-Гамаля" (PDF) . Справочник по прикладной криптографии . CRC Press.
• Дэн Боне (1998). "Решение проблемы Диффи-Хеллмана". Алгоритмическая теория чисел. Конспект лекций по информатике. Том 1423. С. 48–63. CiteSeerX  10.1.1.461.9971 . doi :10.1007/BFb0054851. ISBN 978-3-540-64657-0.

Ссылки

1. Тахер Эль-Гамаль (1985). «Криптосистема с открытым ключом и схема подписи на основе дискретных логарифмов» (PDF) . Труды IEEE по теории информации . 31 (4): 469–472. CiteSeerX 10.1.1.476.4791 . doi :10.1109/TIT.1985.1057074. S2CID  2973271. (версия конференции появилась в CRYPTO '84, стр. 10–18)
2. Mike Rosulek (2008-12-13). "Схема шифрования Elgamal". Университет Иллинойса в Урбане-Шампейне . Архивировано из оригинала 2016-07-22.
3. Tsiounis, Yiannis; Yung, Moti (2006-05-24). "О безопасности шифрования на основе ElGamal". Криптография с открытым ключом . Конспект лекций по информатике. Том 1431. С. 117–134. doi :10.1007/BFb0054019. ISBN 978-3-540-69105-1.
4. Абдалла, Мишель; Белларе, Михир; Рогауэй, Филлип (2001-01-01). «Предположения Oracle Диффи-Хеллмана и анализ DHIES». Темы по криптологии — CT-RSA 2001. Конспект лекций по информатике. Том 2020. С. 143–158. doi :10.1007/3-540-45353-9_12. ISBN 978-3-540-41898-6.