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

редактировать

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

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

Содержание

  • 1 Алгоритм
    • 1.1 Генерация ключа
    • 1.2 Шифрование
    • 1.3 Расшифровка
    • 1.4 Практическое использование
  • 2 Безопасность
  • 3 Эффективность
  • 4 См. Также
  • 5 Дополнительная литература
  • 6 Ссылки

Алгоритм

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

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

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

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

Шифрование

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

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

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

Decryption

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. Также

Дополнительная литература

Ссылки

  1. ^Тахер Эль-Гамал (1985). «Криптосистема с открытым ключом и схема подписи на основе дискретных логарифмов» (PDF). IEEE Transactions по теории информации. 31 (4): 469–472. CiteSeerX 10.1.1.476.4791. doi : 10.1109 / TIT.1985.1057074.(версия для конференции появилась в CRYPTO '84, стр. 10–18)
  2. ^ Майк Розулек (2008-12- 13). «Схема шифрования Эльгамаля». Университет Иллинойса в Урбане-Шампейне. Архивировано из оригинала 22.07.2016.
  3. ^Циунис, Яннис; Юнг, Моти (24 мая 2006 г.). «О безопасности шифрования на основе Эль-Гамаля». Криптография с открытым ключом 1998. Конспект лекций по информатике. 1431 : 117–134. doi : 10.1007 / BFb0054019. ISBN 978-3-540-69105-1.
  4. ^ Абдалла, Мишель; Белларе, Михир; Рогавей, Филипп (1999-03-17). «DHAES: схема шифрования, основанная на проблеме Диффи-Хеллмана». Библиотека теории криптографии.
Последняя правка сделана 2021-05-18 10:02:19
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте