Алгоритм шифрования Эль-Гамаля

Рассмотрим способ шифрования Эль-Гамаля — рисунок 2.1, который использует вероятностный механизм преобразования исходного текста. Этот способ основан на процедурах возведения в дискретную степень и состоит в следующем. Аналогично методу открытого распределения ключей Диффи—Хеллмана, выбирается большое простое число P и любое число G, но меньше P, причем число P обязательно должно быть больше чем длина используемого алфавита. Далее выбирается секретный ключ — K (секретный), это число должно принадлежать множеству простых чисел и находиться в диапазоне от 1 до P-1. Затем по формуле (2.1) найдем открытый ключ — K (открытый):

(2.1).

После чего получатель посылает отправителю три числа (К_{открытый}; G; P), а К_{секретный} остается в секрете и хранится — его личный секретный ключ.

Рисунок 2.1 — Схема Эль-Гамаля.

Отправитель выбирает число K, которое меньше P-1 и взаимнопростое с P-1, то есть НОД (K, P-1) должен быть равен 1. Далее переходит к операции шифрования — формула (2.2):

(2.2).

где a и k — переменные, которые генерируются при каждой операции шифрования, b-зашифрованные данные, T_от — исходные данные. Любое сообщение можно разбить на фрагменты необходимого размера и каждый из них зашифровать отдельно, что повысит криптосктойкость.

Дешифруя сообщения получатель, используя свой K_{секретный}, должен произвести следующие вычисления — формула (2.3):

(2.3).

Для наглядного представления рассмотрим пример передачи сообщения между двумя абонентами — Аней и Борисом.

Пример:

Допустим, что Аня хочет отправить Борису слово «ШИФР», каждому символу сообщения соответствует порядковый номер в алфавите (Ш-23, И-8, Ф-19, Р-15), эти числа и будут являться T_{открытый}. Для этого Борис делает следующие шаги:

• 1. выбирает P=179 — простое;
• 2. выбирает G=47, 1
• 3. выбирает K_{секретный}=79 — простое K_{секретный}
• 4. вычисляет по формуле (2.1)K_{открытый}=47⁷⁹(Mod 179)=56;
• 5. отправляет (P; G; K_{открытый})=(179; 47; 56) Ане.

Затем Аня делает следующие шаги:

• 1. выбирает число K=29, 1< K< P-1 и взаимнопростое с P-1;
• 2. вычисляет по формуле (2.2) a=47²⁹(Mod 179)=110;
• 3. шифрует каждый символ по формуле (2.2):
• 1) Ш-23, b=56²⁹*23(Mod 179)=176;
• 2) И-8= b=56²⁹*8(Mod 179)=69;
• 3) Ф-19= b=56²⁹*19(Mod 179)=52;
• 4) Р-15= b=56²⁹*15(Mod 179)=107;
• 4. Отправляет (a, b) Борису.

Теперь сообщение «ШИФР» представляет собой следующую последовательность: 176 69 52 107.

Для расшифровки полученного сообщения Борису остается сделать обратные действия — формула (2.3), но с использованием своего секретного ключа:

• 1. получить порядковые номера зашифрованных символов:
• 1) 176*110^179−79−1(Mod 179)=23;
• 2) 69*110^179−79−1(Mod 179) =8;
• 3) 52*110^179−79−1(Mod 179)=19;
• 4) 107*110^179−79−1(Mod 179)=15;
• 2. выбрать из алфавита символы по соответствующим порядковым номерам:
• 1) 23-Ш;
• 2) 8-И;
• 3) 19-Ф;
• 4) 15-Р;

Расшифрованный текст соответствует исходному, следовательно, алгоритм работает корректно.