Эль гамаль шифрование пример

Эль гамаль шифрование пример

Данная система является альтернативой алгоритму RSA и при равном значении ключа обеспечивает ту же криптостойкость. Эль-Гамаль (Taher Elgamal) усовершенствовал алгоритм Диффи-Хеллмана и получил алгоритмы для шифрования и для обеспечения аутентификации. Алгоритм основан на проблеме поиска дискретного логарифма. Если возводить целое число в степень достаточно легко, то восстановить целочисленный аргумент по значению (то есть найти логарифм) довольно трудно.

Для генерации пары ключей сначала выбирается простое число p и два случайных числа, g и x, оба меньше p. Затем вычисляется

Открытым ключом являются y, g и p. Величины g, и p можно сделать общими для группы пользователей. Закрытым ключом является x.

Для шифрования сообщения M сначала выбирается случайное число k,

взаимно простое с (p – 1). Затем вычисляются

Пара (a, b) является шифротекстом. Получаемый шифротекст в два раза длиннее открытого текста. Для дешифрирования (a, b) вычисляется

Так как a xg kx (mod p) и b/a xy k M/a xg xk M/ g kx = M (mod p), то все действительно так и получается. Или иначе:

a x mod p = y k mod p (g k mod p) x mod p = (g x mod p) k mod p.

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

Рассмотрим алгоритм криптосистемы Эль-Гамаля.

Выбираем открытый ключ p и g:

p простое число (может быть общим для группы пользователей),

выбираем случайное k, которое взаимно простое с p–1;

Приведем пример использования метода Эль-Гамаля для шифрования сообщения 2, 5, 7. Для простоты вычислений будем использовать маленькие числа (на практике используются числа существенно большие).

1. Выберем простое число p=19; g=5 (g x mod p=5 11 mod 19=6.

Читайте также:  Прямая линия по двум точкам

3. Шифруем сообщение a=g k mod p=5 13 mod 19=17,

4. Дешифрование сообщения

Необходимо отметить, что операции возведения в степень больших чисел достаточно трудоемки для современных процессоров, даже если они производятся по оптимизированным по времени алгоритмам. Так быстродействие RSA в тысячу раз ниже, чем у DES или ГОСТ 28147-89. Поэтому обычно весь текст сообщения кодируется обычным блочным шифром (симметричным алгоритмом), намного более быстрым, но с использованием ключа сеанса, а вот сам ключ сеанса шифруется как раз асимметричным алгоритмом с помощью открытого ключа получателя и помещается в начало файла. Такой механизм называют цифровым конвертом.

При использовании симметричной и асимметричной криптографии длины ключей должны выбираться так, чтобы вскрыть любой из компонентов системы было одинаково трудно. Необходимо отметить, что длина открытых ключей существенно больше ключей для симметричных алгоритмов (табл. 6).

Таблица. 6. Длины симметричных и открытых ключей
с аналогичной устойчивостью к вскрытию методом перебора

| следующая лекция ==>
Алгоритм RSA | Шифрование с использованием эллиптических кривых

Дата добавления: 2014-01-15 ; Просмотров: 4502 ; Нарушение авторских прав?

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

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

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

Читайте также:  Кандидат наук без аспирантуры

Пусть имеются абоненты А, В, С, . которые хотят передавать друг другу зашифрованные сообщения, не имея никаких защищенных каналов связи. Фактически здесь используется схема Диффи-Хеллмана, чтобы сформировать общий секретный ключ для двух абонентов, передающих друг другу сообщение, и затем сообщение шифруется путем умножения его на этот ключ. Для каждого следующего сообщения секретный ключ вычисляется заново.

Перейдем к точному описанию метода. Для всей группы абонентов выбираются некоторое большое простое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде (они могут использоваться всеми абонентами сети). Затем каждый абонент группы выбирает свое секретное число %%c_i%%, %%1

Алгоритмы шифрования с открытым ключом и ЭЦП были опубликованы Т. Эль-Гамалем (Taher Elgamal) в 1984 г. Криптографическая система Эль-Гамаля использует ту же математическую основу, что и рассмотренная ранее схема распределения ключей Диффи — Хеллмана. Шифрование фактически производится путем умножения сообщения на общий секретный ключ системы Диффи — Хеллмана.

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

Безопасность схемы Эль-Гамаля также основана на трудности вычисления дискретных логарифмов в конечном поле.

Пусть имеются абоненты А и В, которые хотят обмениваться секретными сообщениями, не имея защищенных каналов связи. Система Эль-Гамаля легко обобщается на случай нескольких абонентов. Для всей группы абонентов выбирается большое простое число р и число g, такое, что 1

Процесс передачи секретного сообщения М от абонента А к абоненту В:

1) А выбирает случайное число k.Q 13 mod 23 = 21.

Абонент А выбирает случайное число /г, например к = 7, и вычисляет:

Читайте также:  Наушники гарнитура jbl t110

А пересылает абоненту В пару (17, 12).

Абонент В вычисляет

Абонент В смог расшифровать переданное сообщение.

Ссылка на основную публикацию
Чтобы продолжить установку используйте параметр загрузки драйвера
Приветствую всех посетителей моего портала! Драйвера запоминающего устройства для установки – стандартное ПО, в использовании которого редко возникает необходимость. «Драйвер...
Что дает geforce experience
The server encountered an internal error or misconfiguration and was unable to complete your request. Please contact the server administrator...
Что дает перепрошивка смартфона
К моему большому сожалению, такой огромный пласт гик-культуры, как прошивка смартфонов, очень мало обозревается на IT-сайтах. Но бьюсь об заклад,...
Чтобы установить в системе новый язык нужно
Правильный ответ на вопрос: создать запись языка на странице «Языки», загрузить языковые файлы для данного языка через систему обновлений Другие...
Adblock detector