Схема Эль-Гамаля
Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом, основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1985 году.[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.
Содержание
Генерация ключей
- Генерируется случайное простое число <math>p</math>.
- Выбирается целое число <math>g</math> — первообразный корень <math>p</math>.
- Выбирается случайное целое число <math>x</math> такое, что <math>1 < x < p</math>.
- Вычисляется <math>y = g^x\,\bmod\,p</math>.
- Открытым ключом является тройка <math>\left( p,g,y \right)</math>, закрытым ключом — число <math>x</math>.
Работа в режиме шифрования
- Шифросистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.
Шифрование
Сообщение <math>M</math> должно быть меньше числа <math>p</math>. Сообщение шифруется следующим образом:
- Выбирается сессионный ключ — случайное целое число <math>k</math> такое, что <math>1 < k < p - 1</math>
- Вычисляются числа <math>a = g^k\,\bmod\,p</math> и <math>b = y^k M\,\bmod\,p</math>.
- Пара чисел <math>\left( a, b \right)</math> является шифротекстом.
Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения <math>M</math> вдвое.
Расшифрование
Зная закрытый ключ <math>x</math>, исходное сообщение можно вычислить из шифротекста <math>\left( a, b \right)</math> по формуле:
- <math>M = b(a^x)^{-1}\,\bmod\,p.</math>
При этом нетрудно проверить, что
- <math>(a^x)^{-1}\equiv g^{-kx}\pmod{p}</math>
и поэтому
- <math>b(a^x)^{-1}\equiv (y^kM)g^{-xk}\equiv (g^{xk}M) g^{-xk}\equiv M \pmod{p}</math>.
Для практических вычислений больше подходит следующая формула:
- <math>M = b(a^x)^{-1}\,\bmod\,p = b \cdot a^{(p-1-x)}\,\bmod\,p </math>
Схема шифрования
Пример
- Шифрование
- Допустим, что нужно зашифровать сообщение <math>M=5</math>.
- Произведем генерацию ключей:
- Пусть <math>p=11, g=2</math>. Выберем <math>x=8</math> - случайное целое число <math>x</math> такое,что <math>1 < x < p</math>.
- Вычислим <math>y= g^x\bmod{p}=2^8\bmod{11}=3</math>.
- Итак, открытым ключом является тройка <math>(p,g,y)=(11,2,3)</math>,а закрытым ключом - число <math>x=8</math>.
- Выбираем случайное целое число <math>k</math> такое, что 1 < k < (p − 1). Пусть <math>k=9</math>.
- Вычисляем число <math>a=g^k\bmod{p}=2^9 \bmod{11}=512 \bmod{11}=6</math>.
- Вычисляем число <math>b=y^k M\bmod{p}=3^9 5 \bmod{11}=19683 \cdot 5 \bmod{11}=9</math>.
- Полученная пара <math>(a,b)=(6,9)</math> является шифротекстом.
- Расшифрование
- Необходимо получить сообщение <math>M=5</math> по известному шифротексту <math>(a,b)=(6,9)</math> и закрытому ключу <math>x=8</math>.
- Вычисляем M по формуле: <math>M=b(a^x)^{-1}\bmod{p}=9(6^8)^{-1}\mod{11}=5</math>
- Получили исходное сообщение <math>M=5</math>.
Так как в схему Эль-Гамаля вводится случайная величина <math>k</math>,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа <math>k</math> такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение <math>M</math> и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины <math>k</math> для шифровки различных сообщений <math>M</math> и <math>M'</math>. Если использовать одинаковые <math>k</math>, то для соответствующих шифротекстов <math>(a,b)</math> и <math>(a',b')</math> выполняется соотношение <math>b(b')^{-1}=M(M')^{-1}</math>. Из этого выражения можно легко вычислить <math>M'</math>, если известно <math>M</math>.
Работа в режиме подписи
Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции <math>h(\cdot)</math>, значения которой лежат в интервале <math>\left( 1, p - 1 \right)</math>.
Подпись сообщений
Для подписи сообщения <math>M</math> выполняются следующие операции:
- Вычисляется дайджест сообщения <math>M</math>: <math>m = h(M).</math>
- Выбирается случайное число <math>1< k < p-1</math> взаимно простое с <math>p - 1</math> и вычисляется <math>r = g^k\,\bmod\,p.</math>
- Вычисляется число <math> s \, \equiv \, (m-x r)k^{-1} \pmod{p-1}</math>.
- Подписью сообщения <math>M</math> является пара <math>\left( r,s \right)</math>.
Проверка подписи
Зная открытый ключ <math>\left( p,g,y \right)</math>, подпись <math>\left( r,s \right)</math> сообщения <math>M</math> проверяется следующим образом:
- Проверяется выполнимость условий: <math>0<r<p</math> и <math>0<s<p-1</math>. Если хотя бы одно из них не выполняется,то подпись считается неверной.
- Вычисляется дайджест <math>m = h(M).</math>
- Подпись считается верной, если выполняется сравнение:
- <math>(y^r r^s)mod{p} \equiv g^m \pmod{p}.</math>
Пример
- Подпись сообщения.
- Допустим,что нужно подписать сообщение <math>M=baaqab</math>.
- Произведем генерацию ключей:
- Пусть <math>p=23</math> <math>g=5</math> переменные, которые известны некоторому сообществу. Секретный ключ <math>x=7</math> — случайное целое число <math>x</math> такое, что <math>1 < x < p</math>.
- Вычисляем открытый ключ <math>y</math>: <math>y=g^x\bmod p=5^7 \bmod 23=17</math>.
- Итак,открытым ключом является тройка <math>(p,g,y)=(23,5,17)</math>.
- Теперь вычисляем хэш-функцию: <math>h(M)=h(baaqab)=m=3</math>.
- Выберем случайное число <math>k</math> такое, что выполняется условие <math>1 < k < p-1</math>. Пусть <math>k=5</math>.
- Вычисляем <math>r=g^k modp=5^5 \bmod 23=20</math>.
- Находим число <math> s \, \equiv \, (m-x r)k^{-1} \pmod{p-1}</math>. Такое <math>s</math> существует, так как НОД(k,p-1)=1. Получим что <math>s=21</math>.
- Итак, мы подписали сообщение: <math><baaqab,20,21></math>.
- Проверка подлинности полученного сообщения.
- Вычисляем хэш-функцию: <math>h(M)=h(baaqab)=m=3</math>.
- Проверяем сравнение <math>y^r \cdot r^s\equiv g^m \pmod{p}</math>.
- Вычислим левую часть по модулю 23: <math>17^{20} \cdot 20^{21} \bmod 23=16 \cdot 15 \bmod 23=10</math>.
- Вычислим правую часть по модулю 23: <math>5^3\bmod 23=10</math>.
- Так как правая и левая части равны, то это означает что подпись верна.
- Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле <math>\mathbb{Z}_p</math>. Следует сделать несколько комментариев:
- Случайное число <math>k</math> должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число <math>k</math> и саму подпись, то он легко может найти секретный ключ по формуле: <math>x=(m-ks)r^{-1} \bmod (p-1)</math> и полностью подделать подпись.
Число <math>k</math> должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.
- Использование свертки <math>m=h(M)</math> объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа <math>i,j</math>,удовлетворяющие условиям <math>0<i<{p-1} , 0<j<{p-1}</math>, НОД(j,p-1)=1 и предположить что
- <math>r=g^i \cdot y^{-j} \bmod p</math>
- <math>s=r \cdot j^{-1} \bmod (p-1)</math>
- <math>m=r \cdot i \cdot j^{-1} \bmod (p-1)</math>
то легко удостовериться в том,что пара <math>(r,s)</math> является верной цифровой подписью для сообщения <math>x=M</math>.
- Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: <math>y^A \cdot r^B=g^C(modp)</math>, в котором тройка <math>(A,B,C)</math> принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при <math>A=r</math>,<math>B=s</math>, <math>C=m</math>.На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения <math>A=r</math>, <math>B=-s</math>,<math>C=m</math>, а в Российском стандарте: <math>A=-x</math>, <math>B=-m</math>, <math>C=s</math>.
- Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел <math>(s,m)</math> на пару чисел <math>(s \bmod q,m \bmod q</math>),где <math>q</math> является каким-то простым делителем числа <math>(p-1)</math>. При этом сравнение для проверки подписи по модулю <math>p</math> нужно заменить на новое сравнение по модулю <math>q</math>: <math>(~y^A \cdot r^B) \bmod p = g^C \pmod{q}</math>. Так сделано в американском стандарте DSS (Digital Signature Standard).
Криптостойкость и особенности
В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:
- <math>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 | Современное направление. Разрабатывается многими ведущими математиками |
Примечания
- ↑ Taher ElGamal (1985). «[caislab.kaist.ac.kr/lecture/2010/spring/cs548/basic/B02.pdf 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.
Ссылки
- Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии.
- Б. А. Фороузан. [www.intuit.ru/department/security/manencryptk/3/4.html#sect22 Схема цифровой подписи Эль-Гамаля] // [www.intuit.ru/department/security/manencryptk/ Управление ключами шифрования и безопасность сети] / Пер. А. Н. Берлин. — Курс лекций.
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone. [www.cacr.math.uwaterloo.ca/hac/about/chap11.pdf 11.5.2 The ElGamal signature scheme] // [www.cacr.math.uwaterloo.ca/hac/ Handbook of applied cryptography].
| ||||||
