Криптосистема Эль-Гамаля

3.3. Криптосистема Эль - Гамаля.

3.3.1. Описание     системы.

Генерация ключей:

Абонент A:

·  Генерирует простое число p и образующий элемент α мультипликативной группы Z_p^* .

·  Выбирает случайное a, 1<a£p-2 и вычисляет β = α^a mod p.

·  Открытым ключом объявляет тройку чисел (p, alpha, beta), в качестве секретного ключа сохраняет число a.

Шифрование:

Абонент B:

·  Получает авторизированную копию открытого ключа (p, α, β) абонента А.

·  Представляет сообщение, как число m из интервала [0, p-1] (в необходимых случаях разбивает его на блоки, являющиеся числами в этом интервале).

·  Выбирает случайно число k, 0<k<p-1. k – рандомизатор.  Рандомизатор должен меняться при каждом зашифровании, иначе можно вычислить открытый текст, если известен предыдущий. Шифртексты (C₁,C₂) и  (C₁’,C₂’) связаны следующим образом:  (C₂) (C₂’)^-1 º m (m’)^-1 (mod p).

·  Вычисляет d = α ^k mod p и e =m  β ^k mod p.

·  Посылает шифртекст (d,e) абоненту А.

Расшифрование:

Абонент A:

·  Используя секретный ключ a, вычисляет d^p-1-a mod p (d^p-1-a = d^-a = α^-ak).

·  Вычисляет сообщение m=(d^-a)e mod p.

Пример.

Генерация ключей:

Пусть p=127, тогда a =14, a=51, b = a^a mod p = 14⁵¹ mod 127=5.

Открытый ключ: (p, a, b)=(127,14,65). Секретный ключ: (a) = (51).

Шифрование:

Пусть m= 100

E(100)=(C₁,C₂)=( a^k mod p, mb^k mod p )=( 14¹¹ mod 127, 100 5¹¹ mod 127) =

= (78,100 54 mod 127) = (78,66), где k = 11 - рандомизатор.

Расшифрование:

D (78,66)= 66 (C₁ ^a) ^-1  mod p = 66 (78⁵¹ ) ^-1  mod 127= 66 (54 ) ^-1  mod 127=66 40 mod 127=100.