УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ☞ КРИПТОГРАФИЯ. Сложность — повышенная. Предполагается знакомство с разделом ☞ ИНДЕКС (дискретный логарифм) .


Шифрование по алгоритму ЭльГамаля

Создатель ключа А выбирает

  • произвольное достаточно большое простое число p_{};
  • произвольный первообразный корень \Lambda_{} по основанию p_{};
  • произвольное число a_{} и вычисляет Q=\Lambda^a \pmod{p}.

Открытый (публичный) ключ шифрования состоит из трех чисел p,\Lambda, Q. Секретный ключ дешифрования — число a_{}, т.е. индекс (дискретный логарифм) \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} \ .

(последнее сравнение следует из теоремы Ферма ). Поскольку все числа в этом выражении ему известны, то он получает искомый текст x_{}.

§

1. В отличие от алгоритма RSA, шифрование по ЭльГамалю дает удлинение шифротекста почти в два раза по сравнению с текстом открытым: вместо x_{} посылается пара чисел (c,\gamma), каждое из которых — практически того же размера, что и x_{}.

2. Для шифрования каждого нового текста надо подбирать новое k_{}.

3. Участники переписки могут образовать закрытую для постороннего контроля группу «внутренней рассылки», договорившись использовать одинаковые для участников группы числа p_{} и \Lambda_{} (но разные секретные a_{}). При этом числа p_{} и \Lambda_{} тоже секретятся, и тем самым усложняется задача криптоанализа переписки внутри группы.

П

Пример.

p=276359384326756927539349639753936254367560234574543725346534764354257629,\ \Lambda=2,
Q=267913333839598359953082878808980288593658415295490235452780248871637093 \ .


2012/06/17 16:33 редактировал au