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