!!§!! Вспомогательная страница к разделу
☞
((:crypto#криптография_с_открытым_ключом КРИПТОГРАФИЯ)).
Сложность --- повышенная. Предполагается знакомство с разделом
☞
((:modular:index#индекс ИНДЕКС (дискретный логарифм) )).
----
== Шифрование по алгоритму ЭльГамаля==
Создатель ключа
А
выбирает
* произвольное достаточно большое простое число $ p_{} $;
* произвольный ((:modular:index#первообразный_корень первообразный корень)) $ \Lambda_{} $ по основанию $ p_{} $;
* произвольное число $ a_{} $ и вычисляет $ Q=\Lambda^a \pmod{p} $.
Открытый (публичный) ключ шифрования состоит из трех чисел $ p,\Lambda, Q $. Секретный ключ дешифрования --- число $ a_{} $, т.е. ((:modular:index#индекс индекс (дискретный логарифм) )) $ \operatorname{ind}_{_{\Lambda}} Q $ числа $ Q_{} $ по модулю $ p_{} $ и основанию $ \Lambda $.
Корреспондент
Б
, желающий послать создателю ключа
А
открытый текст $ x_{} $, зашифрованный этим ключом, предпринимает следующие действия:
* выбирает случайное число $ k \in \{ 1,2,\dots, p-2 \} $;
* вычисляет $ \gamma=\Lambda^k \pmod{p} $;
* вычисляет $ c=xQ^k \pmod{p} $
и посылает
А
два числа $ c_{} $ и $ \gamma_{} $.
Получив эти числа, создатель ключа
А
для восстановления открытого текста $ x_{} $ должен прозвести следующие действия:
выразить $ x_{} $ из $ c=xQ^k \pmod{p} $ по формуле
$$x=cQ^{-k} \pmod{p}=$$
(но он не знает $ k_{} $, зато знает, что $ Q=\Lambda^a \pmod{p} $):
$$=c\left(\Lambda^a \right)^{-k} \pmod{p} =
c\left(\Lambda^k \right)^{-a} \pmod{p}=
$$
(число $ \Lambda^k $ ему сообщено корреспондентом
Б
)
$$
=c \gamma^{-a} \pmod{p}\equiv c \gamma^{p-1-a} \pmod{p} \ .
$$
(последнее сравнение следует из ((:modular#теорема_ферма теоремы Ферма)) ). Поскольку
все числа в этом выражении ему известны, то он получает искомый текст
$ x_{} $.
1.
В отличие от ((:crypto#алгоритм_rsa алгоритма RSA)), шифрование по ЭльГамалю дает удлинение шифротекста почти в два раза по сравнению
с текстом открытым: вместо $ x_{} $ посылается пара чисел $ (c,\gamma) $,
каждое из которых --- практически того же размера, что и $ x_{} $.
2.
Для шифрования каждого нового текста надо подбирать новое $ k_{} $.
3.
Участники переписки могут образовать закрытую для постороннего
контроля группу "внутренней рассылки", договорившись использовать
одинаковые для участников группы числа $ p_{} $ и $ \Lambda_{} $ (но разные
секретные $ a_{} $). При этом числа $ p_{} $ и $ \Lambda_{} $ тоже секретятся, и
тем самым усложняется задача криптоанализа переписки внутри группы.
!!П!! **Пример.**
$$p=276359384326756927539349639753936254367560234574543725346534764354257629,\ \Lambda=2, $$
$$ Q=267913333839598359953082878808980288593658415295490235452780248871637093 \ .$$