Шифрование Эль-Гамаля
Криптосистема с открытым ключом

В криптографии система шифрования 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 с}

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

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

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

Шифрование

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

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

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

Расшифровка

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

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

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

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

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

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

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

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

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

Также были предложены другие схемы, связанные с ElGamal, которые обеспечивают безопасность против атак с использованием выбранного шифртекста. Криптосистема Крамера–Шоупа безопасна при атаке с использованием выбранного шифртекста, предполагая, что DDH выполняется для . Ее доказательство не использует модель случайного оракула . Другая предложенная схема — DHIES , [4] доказательство которой требует предположения, которое сильнее предположения DDH. G {\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. ^ ab 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=ElGamal_encryption&oldid=1261182250"