Схема Эль-Гамаля

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).

Схема была предложена Тахером Эль-Гамалем в 1984 году.[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Генерация ключей[править | править вики-текст]

  1. Генерируется случайное простое число ~p длины ~n битов.
  2. Выбирается случайный примитивный элемент ~g поля \mathbb Z_p.
  3. Выбирается случайное целое число ~x такое, что ~1 < x < p-1.
  4. Вычисляется ~y = g^x\,\bmod\,p.
  5. Открытым ключом является тройка \left( p,g,y \right), закрытым ключом — число ~x.

Работа в режиме шифрования[править | править вики-текст]

Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.

Шифрование[править | править вики-текст]

Сообщение ~M шифруется следующим образом:

  1. Выбирается сессионный ключ — случайное целое число ~k такое, что ~1 < k < p - 1
  2. Вычисляются числа a = g^k\,\bmod\,p и b = y^k M\,\bmod\,p.
  3. Пара чисел \left( a, b \right) является шифротекстом.

Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения M вдвое.

Расшифрование[править | править вики-текст]

Зная закрытый ключ ~x, исходное сообщение можно вычислить из шифротекста \left( a, b \right) по формуле:

M = b(a^x)^{-1}\,\bmod\,p.

При этом нетрудно проверить, что

~(a^x)^{-1}\equiv g^{-kx}\pmod{p}

и поэтому

~b(a^x)^{-1}\equiv (y^kM)g^{-xk}\equiv (g^{xk}M) g^{-xk}\equiv M \pmod{p}.

Для практических вычислений больше подходит следующая формула:

M = b(a^x)^{-1}\,\bmod\,p = b \cdot a^{(p-1-x)}\,\bmod\,p

Схема шифрования[править | править вики-текст]

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

Пример[править | править вики-текст]

  • Шифрование
    1. Допустим что нужно зашифровать сообщение ~M=5.
    2. Произведем генерацию ключей :
      1. пусть ~p=11, g=2. Выберем ~x=8 - случайное целое число ~x такое,что ~1 < x < p.
      2. Вычислим ~y= g^x\bmod{p}=2^8\bmod{11}=3.
      3. Итак , открытым является тройка ~(p,g,y)=(11,2,3),а закрытым ключом является число ~x=8.
    3. Выбираем случайное целое число ~k такое, что 1 < k < (p − 1). Пусть ~k=9.
    4. Вычисляем число ~a=g^k\bmod{p}=2^9 \bmod{11}=512 \bmod{11}=6.
    5. Вычисляем число ~b=y^k M\bmod{p}=3^9 5 \bmod{11}=19683 \cdot 5 \bmod{11}=9.
    6. Полученная пара ~(a,b)=(6,9) является шифротекстом.
  • Расшифрование
    1. Необходимо получить сообщение ~M=5 по известному шифротексту ~(a,b)=(6,9) и закрытому ключу ~x=8.
    2. Вычисляем M по формуле : ~M=b(a^x)^{-1}\bmod{p}=9(6^8)^{-1}\mod{11}=5
    3. Получили исходное сообщение ~M=5.

Так как в схему Эль-Гамаля вводится случайная величина k,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа ~k такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение M и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины k для шифровки различных сообщений M и M'. Если использовать одинаковые k, то для соответствующих шифротекстов (a,b) и (a',b') выполняется соотношение b(b')^{-1}=M(M')^{-1}. Из этого выражения можно легко вычислить M', если известно M.

Работа в режиме подписи[править | править вики-текст]

Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции ~h(\cdot), значения которой лежат в интервале \left( 1, p - 1 \right).

Цифровая подпись по схеме Эль-Гамаля

Подпись сообщений[править | править вики-текст]

Для подписи сообщения ~M выполняются следующие операции:

  1. Вычисляется дайджест сообщения ~M: ~m = h(M).
  2. Выбирается случайное число ~1< k < p-1 взаимно простое с ~p - 1 и вычисляется ~r = g^k\,\bmod\,p.
  3. Вычисляется число  s \, \equiv \, (m-x r)k^{-1} \pmod{p-1}.
  4. Подписью сообщения ~M является пара \left( r,s \right).

Проверка подписи[править | править вики-текст]

Зная открытый ключ \left( p,g,y \right), подпись \left( r,s \right) сообщения ~M проверяется следующим образом:

  1. Проверяется выполнимость условий: ~0<r<p и ~0<s<p-1. Если хотя бы одно из них не выполняется,то подпись считается неверной.
  2. Вычисляется дайджест ~m = h(M).
  3. Подпись считается верной, если выполняется сравнение:
    ~y^r r^s \equiv g^m \pmod{p}.

Пример[править | править вики-текст]

  • Подпись сообщения.
    1. Допустим,что нужно подписать сообщение ~M=baaqab.
    2. Произведем генерацию ключей:
      1. Пусть ~p=23 ~g=5 переменные, которые известны некоторому сообществу. Секретный ключ ~x=7 — случайное целое число ~x такое, что ~1 < x < p.
      2. Вычисляем открытый ключ ~y: ~y=g^x\bmod p=5^7 \bmod 23=17.
      3. Итак,открытым ключом является тройка ~(p,g,y)=(23,5,17).
    3. Теперь вычисляем хэш-функцию: ~h(M)=h(baaqab)=m=3.
    4. Выберем случайное число ~k такое, что выполняется условие 1 < k < p-1. Пусть ~k=5.
    5. Вычисляем ~r=g^k modp=5^5 \bmod 23=20.
    6. Находим число  s \, \equiv \, (m-x r)k^{-1} \pmod{p-1}. Такое ~s существует, так как НОД(k,p-1)=1. Получим что ~s=21.
    7. Итак, мы подписали сообщение: ~<baaqab,20,21>.
  • Проверка подлинности полученного сообщения.
    1. Вычисляем хэш-функцию: ~h(M)=h(baaqab)=m=3.
    2. Проверяем сравнение ~y^r \cdot r^s\equiv g^m \pmod{p}.
    3. Вычислим левую часть по модулю 23: ~17^{20} \cdot 20^{21} \bmod 23=16 \cdot 15 \bmod 23=10.
    4. Вычислим правую часть по модулю 23: ~5^3\bmod 23=10.
    5. Так как правая и левая части равны, то это означает что подпись верна.

Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле \mathbb{Z}_p. Следует сделать несколько комментариев:
  • Случайное число ~k должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число ~k и саму подпись, то он легко может найти секретный ключ по формуле: ~x=(m-ks)r^{-1} \bmod (p-1) и полностью подделать подпись.

Число ~k должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.

  • Использование свертки ~m=h(M) объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа ~i,j,удовлетворяющие условиям ~0<i<{p-1} , 0<j<{p-1}, НОД(j,p-1)=1 и предположить что
    ~r=g^i \cdot y^{-j} \bmod p
    ~s=r \cdot j^{-1} \bmod (p-1)
    ~m=r \cdot i \cdot j^{-1} \bmod (p-1)

то легко удостовериться в том,что пара ~(r,s) является верной цифровой подписью для сообщения ~x=M.

  • Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: ~y^A \cdot r^B=g^C(modp), в котором тройка ~(A,B,C) принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при ~A=r,~B=s, ~C=m.На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения ~A=r, ~B=-s,~C=m, а в Российском стандарте: ~A=-x, ~B=-m, ~C=s.
  • Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел ~(s,m) на пару чисел ~(s \bmod q,m \bmod q),где ~q является каким-то простым делителем числа ~(p-1). При этом сравнение для проверки подписи по модулю ~p нужно заменить на новое сравнение по модулю ~q: (~y^A \cdot r^B) \bmod p = g^C \pmod{q}. Так сделано в американском стандарте DSS (Digital Signature Standard).

Криптостойкость и особенности[править | править вики-текст]

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

~y \equiv g^x\pmod{p}.

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.

Сравнение некоторых алгоритмов:

Алгоритм Ключ Назначение Криптостойкость, MIPS Примечания
RSA До 4096 бит Шифрование и подпись 2,7•1028 для ключа 1300 бит Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты
ElGamal До 4096 бит Шифрование и подпись При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•1028 для ключа 1300 бит Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS
DSA До 1024 бит Только подписание Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ.
ECDSA До 4096 бит Шифрование и подпись Криптостойкость и скорость работы выше, чем у RSA Современное направление. Разрабатывается многими ведущими математиками

Примечания[править | править вики-текст]

  1. Taher ElGamal (1985). «A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms». IEEE Transactions on Information Theory 31 (4): 469-472. DOI:10.1109/TIT.1985.1057074.

Ссылки[править | править вики-текст]