Схема Эль-Гамаля
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1985 году.[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA, алгоритм Эль-Гамаля не был запатентован и поэтому стал более дешёвой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.
Генерация ключей
- Генерируется случайное простое число [math]\displaystyle{ p }[/math].
- Выбирается целое число [math]\displaystyle{ g }[/math] — первообразный корень [math]\displaystyle{ p }[/math].
- Выбирается случайное целое число [math]\displaystyle{ x }[/math] такое, что [math]\displaystyle{ (1 \lt x \lt p - 1) }[/math].
- Вычисляется [math]\displaystyle{ y = g^x \bmod p }[/math].
- Открытым ключом является [math]\displaystyle{ (y,g,p) }[/math], закрытым ключом — число [math]\displaystyle{ x }[/math].
Работа в режиме шифрования
Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана.[источник не указан 1000 дней] Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.
Шифрование
Сообщение [math]\displaystyle{ M }[/math] должно быть меньше числа [math]\displaystyle{ p }[/math]. Сообщение шифруется следующим образом:
- Выбирается сессионный ключ — случайное целое число, взаимно простое с [math]\displaystyle{ (p - 1) }[/math], [math]\displaystyle{ k }[/math] такое, что [math]\displaystyle{ 1 \lt k \lt p - 1 }[/math].
- Вычисляются числа [math]\displaystyle{ a = g^k \bmod p }[/math] и [math]\displaystyle{ b = y^k M \bmod p }[/math].
- Пара чисел [math]\displaystyle{ (a,b) }[/math] является шифротекстом.
Нетрудно заметить, что длина шифротекста в схеме Эль-Гамаля вдвое больше исходного сообщения [math]\displaystyle{ M }[/math].
Расшифрование
Зная закрытый ключ [math]\displaystyle{ x }[/math], исходное сообщение можно вычислить из шифротекста [math]\displaystyle{ (a,b) }[/math] по формуле:
- [math]\displaystyle{ M = b(a^x)^{-1} \bmod p. }[/math]
При этом нетрудно проверить, что
- [math]\displaystyle{ (a^x)^{-1} = g^{-kx} \bmod p }[/math]
и поэтому
- [math]\displaystyle{ b(a^x)^{-1} = (y^kM)g^{-xk}\equiv (g^{xk}M) g^{-xk}\equiv M \pmod{p} }[/math].
Для практических вычислений больше подходит следующая формула:
- [math]\displaystyle{ M = b(a^x)^{-1} = b a^{(p-1-x)} \pmod{p} }[/math]
Схема шифрования
Пример
- Шифрование
- Допустим, что нужно зашифровать сообщение [math]\displaystyle{ M=5 }[/math].
- Произведем генерацию ключей:
- Пусть [math]\displaystyle{ p=11, g=2 }[/math]. Выберем [math]\displaystyle{ x=8 }[/math] - случайное целое число [math]\displaystyle{ x }[/math] такое,что [math]\displaystyle{ 1 \lt x \lt p }[/math].
- Вычислим [math]\displaystyle{ y= g^x\bmod{p}=2^8\bmod{11}=3 }[/math].
- Итак, открытым ключом является тройка [math]\displaystyle{ (p,g,y)=(11,2,3) }[/math],а закрытым ключом - число [math]\displaystyle{ x=8 }[/math].
- Выбираем случайное целое число [math]\displaystyle{ k }[/math] такое, что 1 < k < (p − 1). Пусть [math]\displaystyle{ k=9 }[/math].
- Вычисляем число [math]\displaystyle{ a=g^k\bmod{p}=2^9 \bmod{11}=512 \bmod{11}=6 }[/math].
- Вычисляем число [math]\displaystyle{ b=y^k M\bmod{p}=3^9 5 \bmod{11}=19683 \cdot 5 \bmod{11}=9 }[/math].
- Полученная пара [math]\displaystyle{ (a,b)=(6,9) }[/math] является шифротекстом.
- Расшифрование
- Необходимо получить сообщение [math]\displaystyle{ M=5 }[/math] по известному шифротексту [math]\displaystyle{ (a,b)=(6,9) }[/math] и закрытому ключу [math]\displaystyle{ x=8 }[/math].
- Вычисляем M по формуле: [math]\displaystyle{ M=b(a^x)^{-1}\bmod{p}=9(6^8)^{-1}\mod{11}=5 }[/math]
- Получили исходное сообщение [math]\displaystyle{ M=5 }[/math].
Так как в схему Эль-Гамаля вводится случайная величина [math]\displaystyle{ k }[/math],то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа [math]\displaystyle{ k }[/math] такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение [math]\displaystyle{ M }[/math] и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины [math]\displaystyle{ k }[/math] для шифровки различных сообщений [math]\displaystyle{ M }[/math] и [math]\displaystyle{ M' }[/math]. Если использовать одинаковые [math]\displaystyle{ k }[/math], то для соответствующих шифротекстов [math]\displaystyle{ (a,b) }[/math] и [math]\displaystyle{ (a',b') }[/math] выполняется соотношение [math]\displaystyle{ b(b')^{-1}=M(M')^{-1} }[/math]. Из этого выражения можно легко вычислить [math]\displaystyle{ M' }[/math], если известно [math]\displaystyle{ M }[/math].
Работа в режиме подписи
Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции [math]\displaystyle{ h(\cdot) }[/math], значения которой лежат в интервале [math]\displaystyle{ \left( 1, p - 1 \right) }[/math].
![Цифровая подпись по схеме Эль-Гамаля](https://cdn.xn--h1ajim.xn--p1ai/thumb.php?f=%D0%A6%D0%B8%D1%84%D1%80%D0%BE%D0%B2%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D0%BF%D0%B8%D1%81%D1%8C_%D0%BF%D0%BE_%D1%81%D1%85%D0%B5%D0%BC%D0%B5_%D0%AD%D0%BB%D1%8C-%D0%93%D0%B0%D0%BC%D0%B0%D0%BB%D1%8F.gif&width=500)
Подпись сообщений
Для подписи сообщения [math]\displaystyle{ M }[/math] выполняются следующие операции:
- Вычисляется дайджест сообщения [math]\displaystyle{ M }[/math]: [math]\displaystyle{ m = h(M). }[/math](Хеш функция может быть любая).
- Выбирается случайное число [math]\displaystyle{ 1\lt k \lt p-1 }[/math] взаимно простое с [math]\displaystyle{ p - 1 }[/math] и вычисляется [math]\displaystyle{ r = g^k\,\bmod\,p. }[/math]
- Вычисляется число [math]\displaystyle{ s \, = \, (m-x r)k^{-1} \pmod{p-1} }[/math], где [math]\displaystyle{ k^{-1} }[/math] это мультипликативное обратное [math]\displaystyle{ k }[/math] по модулю [math]\displaystyle{ p - 1 }[/math], которое можно найти, например, с помощью расширенного алгоритма Евклида.
- Подписью сообщения [math]\displaystyle{ M }[/math] является пара [math]\displaystyle{ \left( r,s \right) }[/math].
Проверка подписи
Зная открытый ключ [math]\displaystyle{ \left( p,g,y \right) }[/math], подпись [math]\displaystyle{ \left( r,s \right) }[/math] сообщения [math]\displaystyle{ M }[/math] проверяется следующим образом:
- Проверяется выполнимость условий: [math]\displaystyle{ 0\lt r\lt p }[/math] и [math]\displaystyle{ 0\lt s\lt p-1 }[/math].
- Если хотя бы одно из них не выполняется,то подпись считается неверной.
- Вычисляется дайджест [math]\displaystyle{ m = h(M). }[/math]
- Подпись считается верной, если выполняется сравнение:
- [math]\displaystyle{ y^r r^s \equiv g^m \pmod{p}. }[/math]
Корректность проверки
Рассматриваемый алгоритм корректен в том смысле, что подпись, вычисленная по указанным выше правилам, будет принята при ее проверке.
Преобразуя определение [math]\displaystyle{ s }[/math], имеем
- [math]\displaystyle{ m \, \equiv \, x r + s k \pmod{p-1}. }[/math]
Далее, из Малой теоремы Ферма следует, что
- [math]\displaystyle{ \begin{align} g^{m} & \equiv g^{xr} g^{ks} \\ & \equiv (g^{x})^r (g^{k})^s \\ & \equiv (y)^r (r)^s \pmod p.\\ \end{align} }[/math]
Пример
- Подпись сообщения.
- Допустим,что нужно подписать сообщение [math]\displaystyle{ M=baaqab }[/math].
- Произведем генерацию ключей:
- Пусть [math]\displaystyle{ p=23 }[/math] [math]\displaystyle{ g=5 }[/math] переменные, которые известны некоторому сообществу.
- Секретный ключ [math]\displaystyle{ x=7 }[/math] — случайное целое число [math]\displaystyle{ x }[/math] такое, что [math]\displaystyle{ 1 \lt x \lt p }[/math].
- Вычисляем открытый ключ [math]\displaystyle{ y }[/math]: [math]\displaystyle{ y=g^x\bmod p=5^7 \bmod 23=17 }[/math].
- Итак,открытым ключом является тройка [math]\displaystyle{ (p,g,y)=(23,5,17) }[/math].
- Теперь вычисляем хеш-функцию: [math]\displaystyle{ h(M)=h(baaqab)=m=3 }[/math].
- Выберем случайное целое число [math]\displaystyle{ k }[/math] такое, что выполняется условие [math]\displaystyle{ 1 \lt k \lt p-1 }[/math]. Пусть [math]\displaystyle{ k=5 }[/math].
- Вычисляем r = g^k mod p = 5^5 mod 23 = 20.
- Находим [math]\displaystyle{ k^{-1} }[/math]. Такое число существует, так как НОД[math]\displaystyle{ (k, p-1)=1 }[/math]. Его можно найти с помощью расширенного алгоритма Евклида. Получим [math]\displaystyle{ k^{-1} = 5^{-1} \pmod{22} = 9 }[/math]
- Находим число [math]\displaystyle{ s \, \equiv \, (m-x r)k^{-1} \pmod{p-1} }[/math]. Получим [math]\displaystyle{ s=21 }[/math], так как [math]\displaystyle{ s = \, (3 - 7 \cdot 20)5^{-1} \pmod{22} = 21 }[/math]
- Итак, мы подписали сообщение: [math]\displaystyle{ \lt baaqab,20,21\gt }[/math].
- Проверка подлинности полученного сообщения.
- Вычисляем хеш-функцию: [math]\displaystyle{ h(M)=h(baaqab)=m=3 }[/math].
- Проверяем сравнение [math]\displaystyle{ y^r \cdot r^s\pmod{p} \equiv g^m \pmod{p} }[/math].
- Вычислим левую часть по модулю 23: [math]\displaystyle{ 17^{20} \cdot 20^{21} \bmod 23=16 \cdot 15 \bmod 23=10 }[/math].
- Вычислим правую часть по модулю 23: [math]\displaystyle{ 5^3\bmod 23=10 }[/math].
- Так как правая и левая части равны, то это означает что подпись верна.
- Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле [math]\displaystyle{ \mathbb{Z}_p }[/math]. Следует сделать несколько комментариев:
- Случайное число [math]\displaystyle{ k }[/math] должно сразу после вычисления подписи уничтожаться, так как если злоумышленник знает случайное число [math]\displaystyle{ k }[/math] и саму подпись, то он легко может найти секретный ключ по формуле: [math]\displaystyle{ x=(m-ks)r^{-1} \bmod (p-1) }[/math] и полностью подделать подпись.
Число [math]\displaystyle{ k }[/math] должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.
- Использование свертки [math]\displaystyle{ m=h(M) }[/math] объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа [math]\displaystyle{ i,j }[/math],удовлетворяющие условиям [math]\displaystyle{ 0\lt i\lt {p-1} , 0\lt j\lt {p-1} }[/math], НОД(j,p-1)=1 и предположить что
- [math]\displaystyle{ r=g^i \cdot y^{-j} \bmod p }[/math]
- [math]\displaystyle{ s=r \cdot j^{-1} \bmod (p-1) }[/math]
- [math]\displaystyle{ m=r \cdot i \cdot j^{-1} \bmod (p-1) }[/math]
то легко удостовериться в том,что пара [math]\displaystyle{ (r,s) }[/math] является верной цифровой подписью для сообщения [math]\displaystyle{ x=M }[/math].
- Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: [math]\displaystyle{ y^A \cdot r^B=g^C(modp) }[/math], в котором тройка [math]\displaystyle{ (A,B,C) }[/math] принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при [math]\displaystyle{ A=r }[/math], [math]\displaystyle{ B=s }[/math], [math]\displaystyle{ C=m }[/math].На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения [math]\displaystyle{ A=r }[/math], [math]\displaystyle{ B=-s }[/math], [math]\displaystyle{ C=m }[/math], а в Российском стандарте: [math]\displaystyle{ A=-x }[/math], [math]\displaystyle{ B=-m }[/math], [math]\displaystyle{ C=s }[/math].
- Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел [math]\displaystyle{ (s,m) }[/math] на пару чисел [math]\displaystyle{ (s \bmod q,m \bmod q }[/math]),где [math]\displaystyle{ q }[/math] является каким-то простым делителем числа [math]\displaystyle{ (p-1) }[/math]. При этом сравнение для проверки подписи по модулю [math]\displaystyle{ p }[/math] нужно заменить на новое сравнение по модулю [math]\displaystyle{ q }[/math]: [math]\displaystyle{ (~y^A \cdot r^B) \bmod p = g^C \pmod{q} }[/math]. Так сделано в американском стандарте DSS (Digital Signature Standard).
Криптостойкость и особенности
В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:
- [math]\displaystyle{ y \equiv g^x\pmod{p}. }[/math]
ГОСТ Р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 | Современное направление. Разрабатывается многими ведущими математиками |
Примечания
Литература
- Шаблон:Source
- Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии.[уточнить]
- Б. А. Фороузан. Схема цифровой подписи Эль-Гамаля // Управление ключами шифрования и безопасность сети / Пер. А. Н. Берлин. — Курс лекций.
- Шаблон:Source