Условная стойкость шифра Эль Гамаля.


 

Шифр ElGamal – симметричный шифр, основанный на теоретико-числовой проблематике. Напомним его конструкцию.

Параметры системы: p – простое число, α– порождающий элемент группы Up;

Закрытый ключ для расшифрования: a – целое число, 1 ≤ a < p—1;

Открытый ключ для шифрования: β = αa mod p.

Пусть имеется открытый тест x Up. Для шифрования берут случайное число k Zp—1 и вычисляются y1k mod p, y2=xβk mod p. Затем пара (y1,y2) пересылается обладателю секретного ключа, а k уничтожается.

Для расшифрования необходимо вычислить x=y2(y1a)-1mod p.

Действительно, в результате расшифрования получим открытый текст:

y2(y1a)-1mod p=xβkka) -1 mod p= xαakka) -1mod p=xα0 mod p=x.

Проблема дешифрования заключается в вычислении сообщения по шифрограмме без использования секретного ключа.

Теорема

Проблема дешифрования для шифра ElGamal и проблема Диффи-Хеллмана вычислительно эквивалентны.

Доказательство:

Действительно, пусть A есть алгоритм решения проблемы Диффи-Хеллмана,

A(p, α, δ, γ)= mod p.

Тогда дешифрование для шифра ElGamal осуществляется следующим образом:

x=y2A(p, α, y1, β)-1

(поскольку A(p, α, y1, β)= A(p, α, αk, αa)= mod pak mod p=β mod p).

Обратно, пусть B есть алгоритм дешифрования для шифра ElGamal, то есть

B(p, α, β, y1, y2)=x=y2(y1 )-1 mod p.

Тогда проблема Диффи-Хеллмана решается следующим образом:

δ =B(p, α, γ, δ, 1)-1

 

 




Дата добавления: 2018-11-26; просмотров: 725;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.