В криптографии , то система шифрования ElGamal является асимметричным ключом алгоритм шифрования для криптографии с открытым ключом , который основан на обмене ключа Диффи-Хеллмана . Он был описан Тахером Эльгамалом в 1985 году. [1] Шифрование Эль-Гамаля используется в бесплатном программном обеспечении GNU Privacy Guard , последних версиях PGP и других криптосистемах . Алгоритм цифровой подписи (DSA) представляет собой вариант схемы подписи Эль - Гамаля , который не следует путать с шифрованием ElGamal.
Шифрование Эль-Гамаля может быть определено для любой циклической группы , например мультипликативной группы целых чисел по модулю n . Его безопасность зависит от сложности определенной проблемы, связанной с вычислением дискретных логарифмов .
Алгоритм [ править ]
Шифрование Эль-Гамаля состоит из трех компонентов: генератора ключей, алгоритма шифрования и алгоритма дешифрования.
Генерация ключей [ править ]
Первая сторона, Алиса, генерирует пару ключей следующим образом:
- Сгенерируйте эффективное описание циклической группы порядка с генератором . Позвольте представить единичный элемент .
- Случайным образом выбрать целое число из .
- Вычислить .
- Открытый ключ состоит из значений . Алиса публикует этот открытый ключ и сохраняет в качестве своего закрытого ключа , который должен храниться в секрете.
Шифрование [ править ]
Вторая сторона, Боб, шифрует сообщение Алисе своим открытым ключом следующим образом:
- Сопоставьте сообщение к элементу с помощью обратимой функции отображения.
- Случайным образом выбрать целое число из .
- Вычислить . Это называется общим секретом .
- Вычислить .
- Вычислить .
- Боб отправляет зашифрованный текст Алисе.
Обратите внимание: если известен как зашифрованный, так и открытый текст, можно легко найти общий секрет , поскольку . Следовательно, для повышения безопасности для каждого сообщения создается новое, а значит, и новое . По этой причине его еще называют эфемерным ключом .
Расшифровка [ править ]
Алиса расшифровывает зашифрованный текст своим закрытым ключом следующим образом:
- Вычислить . Поскольку , а значит, это тот же общий секрет, который использовал Боб при шифровании.
- Вычислить , обратное в группе . Это можно вычислить одним из нескольких способов. Если является подгруппой мультипликативной группы целых чисел по модулю n , модульное мультипликативное обратное может быть вычислено с использованием расширенного алгоритма Евклида . Альтернативой является вычисление как . Это обратное из- за теоремы Лагранжа , поскольку .
- Вычислить . Этот расчет дает исходное сообщение , потому что ; следовательно .
- Карта назад в сообщении открытого текста .
Практическое использование [ править ]
Как и большинство систем с открытым ключом, криптосистема Эль-Гамаля обычно используется как часть гибридной криптосистемы, где само сообщение шифруется с использованием симметричной криптосистемы, а затем Эль-Гамаль используется для шифрования только симметричного ключа. Это связано с тем, что асимметричные криптосистемы, такие как Эль-Гамаль, обычно медленнее, чем симметричные, для того же уровня безопасности , поэтому быстрее зашифровать сообщение, которое может быть сколь угодно большим, с помощью симметричного шифра, а затем использовать Эль-Гамал только для шифрования симметричного ключа. , который обычно довольно мал по сравнению с размером сообщения.
Безопасность [ править ]
Безопасность схемы Эль-Гамаля зависит от свойств базовой группы, а также от любой схемы заполнения, используемой в сообщениях.
Если вычислительное предположение Диффи – Хеллмана (CDH) выполняется в основной циклической группе , то функция шифрования является односторонней . [2]
Если решающее допущение Диффи – Хеллмана (DDH) остается в силе, то Эль-Гамал достигает семантической безопасности ; [3] [2] Семантическая безопасность не подразумевается только вычислительным предположением Диффи – Хеллмана. [4] См. Решающее предположение Диффи – Хеллмана для обсуждения групп, в которых предположение считается верным.
Шифрование Эль-Гамаля безусловно податливо и, следовательно, небезопасно при атаке с выбранным зашифрованным текстом . Например, имея шифрование некоторого (возможно, неизвестного) сообщения , можно легко построить действительное шифрование сообщения .
Чтобы обеспечить безопасность выбранного шифротекста, необходимо дополнительно изменить схему или использовать соответствующую схему заполнения. В зависимости от модификации допущение DDH может быть или не быть необходимым.
Также были предложены другие схемы, относящиеся к Эль-Гамалу, которые обеспечивают защиту от атак с выбранным зашифрованным текстом. Криптосистема Крамер-Шоап безопасна при выбранном шифротексте предполагающего ДДГ справедливо для . Его доказательство не использует случайную модель оракула . Другая предложенная схема DHAES , [4] , доказательство которой требует предположения , что слабее , чем DDH предположения.
Эффективность [ править ]
Шифрование Эль-Гамаля является вероятностным , что означает, что один открытый текст может быть зашифрован до множества возможных зашифрованных текстов, в результате чего общее шифрование Эль-Гамаля дает увеличение размера 1: 2 от открытого текста к зашифрованному тексту.
Для шифрования Эль-Гамаля требуется два возведения в степень ; однако эти возведения в степень не зависят от сообщения и при необходимости могут быть вычислены заранее. Для расшифровки требуется одно возведение в степень и одно вычисление группового обратного, которые, однако, можно легко объединить в одно возведение в степень.
См. Также [ править ]
- Тахер Эльгамал , разработчик этой и других криптосистем
- Схема подписи Эль-Гамаля
- Гомоморфное шифрование
Дальнейшее чтение [ править ]
- AJ Menezes; PC van Oorschot; С.А. Ванстон. «Глава 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.
Ссылки [ править ]
- ^ Taher ElGamal (1985). «Криптосистема с открытым ключом и схема подписи на основе дискретных логарифмов» (PDF) . IEEE Transactions по теории информации . 31 (4): 469–472. CiteSeerX 10.1.1.476.4791 . DOI : 10.1109 / TIT.1985.1057074 . (версия для конференции опубликована в CRYPTO '84, стр. 10–18)
- ^ a b Майк Розулек (13 декабря 2008 г.). «Схема шифрования Эльгамаля» . Университет Иллинойса в Урбана-Шампейн . Архивировано из оригинала на 2016-07-22.
- ^ Циунис, Яннис; Юнг, Моти (24 мая 2006 г.). «О безопасности шифрования на основе Эль-Гамаля». Криптография с открытым ключом 1998 . Конспект лекций по информатике. 1431 : 117–134. DOI : 10.1007 / BFb0054019 . ISBN 978-3-540-69105-1.
- ^ а б Абдалла, Мишель; Белларе, Михир; Рогавей, Филипп (1999-03-17). «DHAES: схема шифрования, основанная на проблеме Диффи-Хеллмана» . Библиотека теории криптографии .