Шифр Эль-Гамаля. 
Криптографические методы защиты информации

Алгоритмы шифрования с открытым ключом и ЭЦП были опубликованы Т. Эль-Гамалем (Taher Elgamal) в 1984 г. Криптографическая система Эль-Гамаля использует ту же математическую основу, что и рассмотренная ранее схема распределения ключей Диффи — Хеллмана. Шифрование фактически производится путем умножения сообщения на общий секретный ключ системы Диффи — Хеллмана.

В отличие от шифра Шамира шифр Эль-Гамаля является одноступенчатым, т. е. решает задачу передачи зашифрованного сообщения всего за одну пересылку.

Безопасность схемы Эль-Гамаля также основана на трудности вычисления дискретных логарифмов в конечном поле.

Пусть имеются абоненты, А и В, которые хотят обмениваться секретными сообщениями, не имея защищенных каналов связи. Система Эль-Гамаля легко обобщается на случай нескольких абонентов. Для всей группы абонентов выбирается большое простое число р и число g, такое, что 1 < g

1, все числа из множества {1,2, …, р — 1} могут быть представлены как различные степени g по модулю р. Выбор чисел р и g производится так же, как и в системе Диффи — Хеллмана.

Числа р и g передаются абонентам в открытом виде и могут использоваться всеми абонентами сети. Затем каждый абонент группы выбирает свой личный ключ — случайное число х: 1 < x_i < р — 1, которое держится в секрете. Затем вычисляются открытые ключи у;.

В результате может быть сформирован справочник открытых ключей абонентов наподобие телефонного справочника (рис. 3.5).

Рис. 3.5. Справочник ключей абонентов системы Эль-Гамаля.

Как и в шифре Шамира, предполагается, что сообщение представлено в виде числа М < р.

Процесс передачи секретного сообщения М от абонента, А к абоненту В:

1) А выбирает случайное число k.Q вычисляет числа:

А передает пару чисел (г, s) абоненту В. Пара (г, s) является шифротекстом;

2) абонент В, получив пару (г, s), вычисляет.

Покажем, что М' = М. Подставив в выражение для вычисления М выражения для S, г и у_в, получим.

так как по теореме Ферма modр = Hmod р = 1.

Значения г и s могут передаваться открыто, поскольку получение на их основе секретного значения к практически невозможно (утверждение базируется на вычислительной сложности задачи дискретного логарифмирования при больших значениях р).

Любой абонент, знающий открытый ключ абонента В, может посылать ему зашифрованные сообщения. Однако никто другой, кроме абонента В, не сможет вычислить значения Ми прочитать эти сообщения, так как в вычислениях используется секретный ключ абонента В. Вычисление секретного ключах, на основе известного открытого ключа у_и также является задачей дискретного логарифмирования и практически неосуществимо при больших р.

Следует отметить, что объем криптограммы в два раза превышает объем открытого сообщения, зато требуется только одна передача данных (при условии, что таблица-справочник открытых ключей заранее известна всем абонентам).

Особенностью криптосистемы Эль-Гамаля является участие в процессе шифрования случайного числа к, поэтому при повторном шифровании одного и того же открытого сообщения криптограммы будут различны.

Пример 3.22.

Требуется передать сообщение М = 15 от абонента, А к В с использованием шифра Эль-Гамаля. Выбраны параметры р = 23, g = 5 (так же, как и в примере 3.1.

для системы Диффи — Хеллмаиа). Пусть В выбрал секретный ключ х_в = 13.

и опубликовал открытый ключ г/_в = 5¹³ mod 23 = 21.

Абонент, А выбирает случайное число /г, например к = 7, и вычисляет:

А пересылает абоненту В пару (17, 12).

Абонент В вычисляет.

Абонент В смог расшифровать переданное сообщение.