Криптосистема Эль-Гамаля
Автор: Петрушенко Анастасия Александровна
Рубрика: 1. Информатика и кибернетика
Опубликовано в
V международная научная конференция «Технические науки в России и за рубежом» (Москва, январь 2016)
Дата публикации: 04.12.2015
Статья просмотрена: 2373 раза
Библиографическое описание:
Петрушенко, А. А. Криптосистема Эль-Гамаля / А. А. Петрушенко. — Текст : непосредственный // Технические науки в России и за рубежом : материалы V Междунар. науч. конф. (г. Москва, январь 2016 г.). — Москва : Буки-Веди, 2016. — С. 8-10. — URL: https://moluch.ru/conf/tech/archive/164/9306/ (дата обращения: 17.08.2024).
Криптосистему Эль-Гамаля используют для того, чтоб сформировать электронную подпись, или для шифровки данных. В данной статье рассмотрены идея этого метода шифрования, описание алгоритма.
Ключевые слова: криптосистема Эль-Гамаля, шифр, схема, шифрование, дешифрование, алгоритм, открытый ключ, закрытый ключ.
Криптосистема Эль-Гамаля — это шифрование с открытым ключом, которая базируется на свойствах дискретного логарифма. Непосредственное ее преимущество над алгоритмом RSA в том, что в RSA есть возможность подделать цифровую подпись под некоторыми сообщениями, без определения секретного ключа, когда в методе шифрования Эль-Гамаля такая возможность отсутствует.
Шифр Эль-Гамаля лежит в основе бывших стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10–94).
Идея метода шифрования
Основная идея метода шифрования Эль-Гамаля заключается в том, что эффективного метода сравнивания ax==b (modp) не существует.
Обозначим через Z(n) вычеты по модулю n, через Z*(n)- мультипликативную группу обратимых элементов в Z(n), ab(modn) — возведение в степень b, принадлежащих Z(n).
Допустим, числа p и 2p+1 являются простыми, p>2, v — образующая мультипликативная группа Z*(p), а w — Z*(2p+1).
Лемма: если v — образующая Z*(p), то v0=(p+(p+1) v)(mod 2p) — образующая мультипликативная группа Z*(2p). А эта группа изоморфна Z*(p), поскольку если p является простым числом, то группа Z*(p) изоморфна Z(p-1).
Описание алгоритма
Для генерации пары ключей следует выбрать простое число p:
{ bool check = true;
if ((num % 10) % 2 == 0 && num!= 2)
{ TxtResult.Text = _mesNo;
return;}
BigInteger sqrtnum = Sqrt(num);
int del = 3;
while (del <= sqrtnum)
{ if (num % del == 0)
{ TxtResult.Text = _mesNo;
return;}
del += 2;}}
TxtResult.Text = _mesYes;
}static BigInteger Sqrt(BigInteger n)
{BigInteger x = n, y = n;
do{
y = x;
x = (y + (n / y)) / 2; }
while (y > x);
returnx; }
Листинг 1. Проверка на простое число p
Затем нужно выбрать два случайных числа g и x, которые строго меньше p: (g < p, x < p)
{ Random random = new Random();
k = random.Next(0, 10000);
if (GetNOD(k, p — 1) == 1)
{ g = random.Next(0, (int)p);
x = random.Next(0, (int)p);
break;}
Листинг 2. Задание двух случайных элементов q и x.
Далее нужно получить значение y из выражения: y = g xmodp.
ReturnValue ret = new ReturnValue();
num1 = BigInteger.Abs(num1);
num2 = BigInteger.Abs(num2);
BigInteger i = num2, x = 0, y = 1;
while (num1 > 0)
{ BigInteger q = i / num1, x1 = num1;
num1 = i % x1;
i = x1;
x1 = y;
y = x — q * x1;
x = x1;}
x %= num2;
if (x < 0) x = (x + num2) % num2;
ret.SetValue(x);
if (x!= 1)
{ ret.SetGetBoolValue(true);}
else
{ ret.SetGetBoolValue(false);}
returnret;
Листинг 3. Получение значения y.
Тройка чисел (y, g, p) является открытым ключом, причем g и p можно сделать общими для группы пользователей, х в свою очередь является закрытым ключом.
Для того, чтобы подписать сообщение M, вначале нужно выбирать случайное число k, так что бы НОД (k, p — 1) = 1
num1 = BigInteger.Abs(num1);
num2 = BigInteger.Abs(num2);
if (num1 * num2 == 0 {
return 1;}
while (num1!= num2)
{ if (num1 > num2)
{ num1 -= num2;}
else
{ num2 -= num1;}}
return num1;
Листинг 4. Выбор случайного значения k.
Значение k в дальнейшем сохраняется в секрете. Далее вычисляется значение a из выражения a = g kmodp.
Следом для нахождения b помощью расширенного метода Евклида решается уравнение: M = (xa + kb) mod (p — 1).
Подписью является пара чисел (a, b). Для того, чтоб убедиться в ее верности, необходимо проверить справедливость следующего равенства:
y a * ab mod p = g M mod p.
for (int i = 0; i < M.Length; i++)
{ if (((BigInteger.ModPow(y, a, p) * BigInteger.ModPow(a, b [i], p)) % p) == (BigInteger.ModPow(g, M [i], p)))
{ res.SetCheckValue(BigInteger.ModPow(g, M [i], p)); }
else
{ res.SetCheckValue(0);
break;}}
Листинг 5. Верно ли равенство.
Для каждой процедуры подписания необходимо новое значение k, которое выбирается случайным образом. Компрометация значения k дает возможность по перехваченным значениям M, a и b восстановить за полиномиальное время значение секретного ключа x.
![](https://moluch.ru/conf/blmcbn/9306/9306.001.png)
Рис. 1. Пример шифрования цифровой подписью Эль-Гамаля
Заключение
В качестве иллюстрации к статье можно привести пример шифрования методом Эль-Гамаля (Рисунок 1).
Следует добавить, алгоритм Эль-Гамаля является криптосистемой с открытым ключом, которые в настоящее время считаются наиболее эффективными.
Литература:
- С. Бабичев. Криптография без секретов. 2012
- С. Сингх. Книга шифров. Тайно истории шифров и их расшифровки. М.: Аст, Астрель, 2006. 447 с.
- Б. А. Фороузан. Схема цифровой подписи Эль-Гамаля. Управления ключами шифрования безопасности и безопасности сети.
Ключевые слова
алгоритм, схема, шифрование, шифр, шифрование, дешифрование, криптосистема Эль-Гамаля, открытый ключ, закрытый ключПохожие статьи
Исследование криптосистем с открытым ключом на основе...
RSA, открытый ключ, простое число, криптосистема Эль-Гамаля, образующая мультипликативная группа, секретный ключ, DSA, описание алгоритма, закрытый ключ, листинг.
Оценка стойкости криптосистемы Эль-Гамаля
Ключевые слова: криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма.
С тех пор было изобретено много систем открытых ключей шифрования (например, RSA, ElGamal, обмена ключами Диффи-Хеллмана, эллиптических кривых и т. д.).
Способ хранения закрытого ключа криптосистемы цифровой...
Ключевые слова: криптосистема Эль-Гамаля, шифр, схема, шифрование, дешифрование, алгоритм, открытый ключ, закрытый ключ. Защита данных путем полного шифрования внешних дисков...
Реализация алгоритма шифрования RSA на языке...
RSA, MISHA, открытый ключ, закрытый ключ, открытый текст, число, односторонняя функция, дешифрование данных, пар чисел, числовой
Исследование криптосистем с открытым ключом на основе... RSA — криптографический алгоритм с открытым ключом.
Роль больших простых чисел в современной криптографии
RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор, AES. Криптография. Основные методы и проблемы.
Обзор видов атак по побочным каналам на криптографические...
Оценка стойкости криптосистемы Эль-Гамаля | Статья в сборнике... Секретный ключ криптографии, также известный как секретный. С тех пор было изобретено много систем открытых ключей шифрования (например, RSA, ElGamal, обмена.
Реализация Windows-приложения, выполняющего шифрование...
Криптография с открытым ключом. Криптосистема RSA.
КD — закрытый ключ, используемый для дешифрования данных. Е (m) — односторонняя функция позволяющая зашифровать открытый текст m с использованием ключа КЕ.
Анализ алгоритма RSA. Некоторые распространённые...
Каждый ключ — это часть информации. В состав ключа, используемого в криптографической системе RSA, входит пара, принадлежащая множеству целых чисел. Каждый участник создаёт свой открытый и секретный ключ самостоятельно.
Пост-квантовый алгоритм электронно-цифровой подписи на...
Секретный ключ криптографии, также известный как секретный ключ или симметричный ключ шифрования, имеет. криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма. Способ хранения закрытого ключа криптосистемы...
Похожие статьи
Исследование криптосистем с открытым ключом на основе...
RSA, открытый ключ, простое число, криптосистема Эль-Гамаля, образующая мультипликативная группа, секретный ключ, DSA, описание алгоритма, закрытый ключ, листинг.
Оценка стойкости криптосистемы Эль-Гамаля
Ключевые слова: криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма.
С тех пор было изобретено много систем открытых ключей шифрования (например, RSA, ElGamal, обмена ключами Диффи-Хеллмана, эллиптических кривых и т. д.).
Способ хранения закрытого ключа криптосистемы цифровой...
Ключевые слова: криптосистема Эль-Гамаля, шифр, схема, шифрование, дешифрование, алгоритм, открытый ключ, закрытый ключ. Защита данных путем полного шифрования внешних дисков...
Реализация алгоритма шифрования RSA на языке...
RSA, MISHA, открытый ключ, закрытый ключ, открытый текст, число, односторонняя функция, дешифрование данных, пар чисел, числовой
Исследование криптосистем с открытым ключом на основе... RSA — криптографический алгоритм с открытым ключом.
Роль больших простых чисел в современной криптографии
RSA, число, простое число, тест, выбор показателей, случайный сеансовый ключ, случайный образ, секретный показатель, простой перебор, AES. Криптография. Основные методы и проблемы.
Обзор видов атак по побочным каналам на криптографические...
Оценка стойкости криптосистемы Эль-Гамаля | Статья в сборнике... Секретный ключ криптографии, также известный как секретный. С тех пор было изобретено много систем открытых ключей шифрования (например, RSA, ElGamal, обмена.
Реализация Windows-приложения, выполняющего шифрование...
Криптография с открытым ключом. Криптосистема RSA.
КD — закрытый ключ, используемый для дешифрования данных. Е (m) — односторонняя функция позволяющая зашифровать открытый текст m с использованием ключа КЕ.
Анализ алгоритма RSA. Некоторые распространённые...
Каждый ключ — это часть информации. В состав ключа, используемого в криптографической системе RSA, входит пара, принадлежащая множеству целых чисел. Каждый участник создаёт свой открытый и секретный ключ самостоятельно.
Пост-квантовый алгоритм электронно-цифровой подписи на...
Секретный ключ криптографии, также известный как секретный ключ или симметричный ключ шифрования, имеет. криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма. Способ хранения закрытого ключа криптосистемы...