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

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

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

Алгоритм

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

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

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

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

Шифрование

Второй участник, Боб, шифрует сообщение. $M$ Алисе под ее открытым ключом $(G,q,g,h)$ следующее:

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

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

Расшифровка

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

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

Эй Джей Менезес; ПК ван Ооршот; С.А. Ванстон. «Глава 8.4 Шифрование с открытым ключом Эль-Гамаля» (PDF) . Справочник по прикладной криптографии . ЦРК Пресс.
Дэн Бонех (1998). «Решение проблемы Диффи-Хеллмана». Алгоритмическая теория чисел . Конспекты лекций по информатике. Том. 1423. стр. 48–63. CiteSeerX 10.1.1.461.9971 . дои : 10.1007/BFb0054851 . ISBN 978-3-540-64657-0 .

Ссылки

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

[1] Тахер Эль-Гамаль (1985). «Криптосистема с открытым ключом и схема подписи, основанная на дискретных логарифмах» (PDF) . Транзакции IEEE по теории информации . 31 (4): 469–472. CiteSeerX 10.1.1.476.4791 . дои : 10.1109/TIT.1985.1057074 . S2CID 2973271 . (версия конференции появилась в CRYPTO '84, стр. 10–18)

[cryptutor-2] Jump up to: ^а ^б Майк Росулек (13 декабря 2008 г.). «Эльгамальская схема шифрования» . Университет Иллинойса в Урбана-Шампейн . Архивировано из оригинала 22 июля 2016 г.

[3] Цюнис, Яннис; Юнг, Моти (24 мая 2006 г.). «О безопасности шифрования на основе Эль-Гамаля». Криптография с открытым ключом . Конспекты лекций по информатике. Том. 1431. стр. 117–134. дои : 10.1007/BFb0054019 . ISBN 978-3-540-69105-1 .

[DHIES-4] Абдалла, Мишель; Белларе, Михир; Рогауэй, Филипп (1 января 2001 г.). «Предположения Oracle Диффи-Хеллмана и анализ DHIES» . Темы криптологии — CT-RSA 2001 . Конспекты лекций по информатике. Том. 2020. стр. 143–158. дои : 10.1007/3-540-45353-9_12 . ISBN 978-3-540-41898-6 .

[1]

[2]

[3]

[4]