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

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

Шифрование Эль-Гамаля может быть определено на любом циклическая группа ${ displaystyle G}$ , подобно мультипликативная группа целых чисел по модулюп. Его безопасность зависит от сложности определенной проблемы в ${ displaystyle G}$ связанные с вычислениями дискретные логарифмы.

Алгоритм

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

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

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

Создайте эффективное описание циклической группы ${ Displaystyle G ,}$ порядка ${ displaystyle q ,}$ с генератор ${ displaystyle g}$ . Позволять ${ displaystyle e}$ представляют собой единичный элемент ${ displaystyle G}$ .
Выберите целое число ${ 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 s ^ {- 1}}$ в качестве ${ displaystyle c_ {1} ^ {q-x}}$ . Это обратное ${ displaystyle s}$ потому что Теорема Лагранжа, поскольку ${ displaystyle s cdot c_ {1} ^ {qx} = g ^ {xy} cdot g ^ {(qx) y} = (g ^ {q}) ^ {y} = e ^ {y} = e }$ .
Вычислить ${ Displaystyle m: = c_ {2} cdot s ^ {- 1}}$ . Этот расчет дает исходное сообщение ${ displaystyle m}$ , потому что ${ Displaystyle c_ {2} = м cdot s}$ ; следовательно ${ displaystyle c_ {2} cdot s ^ {- 1} = (m cdot s) cdot s ^ {- 1} = m cdot e = m}$ .
карта ${ displaystyle m}$ назад к текстовому сообщению ${ displaystyle M}$ .

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

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

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

Безопасность схемы Эль-Гамаля зависит от свойств основной группы. ${ displaystyle G}$ а также любую схему заполнения, используемую в сообщениях.

Если вычислительное предположение Диффи – Хеллмана (CDH) выполняется в основной циклической группе ${ displaystyle G}$ , то функция шифрования в одну сторону.^[2]

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

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

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

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

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

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

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

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

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

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

А. Дж. Менезес; П. К. ван Оршот; С. А. Ванстон. «Глава 8.4 Шифрование с открытым ключом Эль-Гамаля» (PDF). Справочник по прикладной криптографии. CRC Press.

Дэн Бонех (1998). Решающая проблема Диффи – Хеллмана. Конспект лекций по информатике. 1423. С. 48–63. CiteSeerX 10.1.1.461.9971. Дои:10.1007 / BFb0054851. ISBN 978-3-540-64657-0.