Условная стойкость шифра Эль Гамаля.
Шифр ElGamal – симметричный шифр, основанный на теоретико-числовой проблематике. Напомним его конструкцию.
Параметры системы: p – простое число, α– порождающий элемент группы Up;
Закрытый ключ для расшифрования: a – целое число, 1 ≤ a < p—1;
Открытый ключ для шифрования: β = αa mod p.
Пусть имеется открытый тест x Up. Для шифрования берут случайное число k Zp—1 и вычисляются y1=αk mod p, y2=xβk mod p. Затем пара (y1,y2) пересылается обладателю секретного ключа, а k уничтожается.
Для расшифрования необходимо вычислить x=y2(y1a)-1mod p.
Действительно, в результате расшифрования получим открытый текст:
y2(y1a)-1mod p=xβk(αka) -1 mod p= xαak(αka) -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 p=αak mod p=β mod p).
Обратно, пусть B есть алгоритм дешифрования для шифра ElGamal, то есть
B(p, α, β, y1, y2)=x=y2(y1 )-1 mod p.
Тогда проблема Диффи-Хеллмана решается следующим образом:
δ =B(p, α, γ, δ, 1)-1
□
Дата добавления: 2018-11-26; просмотров: 725;