Общие сведения

Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т.Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P.
Задается большое простое число P и целое число A, 1 < A < P. Сообщения представляются целыми числами M из интервала 1 < M < P.

Шифрование сообщений

Протокол передачи сообщения M выглядит следующим образом.

• абоненты знают числа A и P;
• абоненты генерируют независимо друг от друга случайные числа:

Ka, Kb

• удовлетворяющих условию:

1 < K < P

• получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:

В = A ^Kb mоd(P)

• отправитель шифрует сообщение M и отправляет полученную последовательность получателю

C = M * B ^Ka mоd(P)

• получатель расшифровывает полученное сообщение

D = ( A ^Ka ) ^-Kb mоd(P)

M = C * D mоd(P)

В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200 знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5-7 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.

Подтверждение подлинности отправителя

Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т.ЭльГамаль предложил следующий протокол передачи подписанного сообщения M:

• абоненты знают числа A и P;
• отправитель генерирует случайное число и хранит его в секрете:

Ka

• удовлетворяющее условию:

1 < Ka < P

• вычисляет и передаёт получателю число B, определяемое последователньостью:

В = A ^Ka mоd(P)

Для сообщения M (1 < M < P):

• выбирает случайное число L (1 < L < P), удовлетворяющее условию

( L , P - 1 ) = 1

• вычисляет число

R = A ^L mоd(P)

• решает относительно S

M = Ka * R + L * S mоd(P)

• передаёт подписанное сообщение

[ M, R, S ]

• получатель проверяет правильность подписи

A M = ( B ^R ) *  ( R ^S ) mоd(P)

В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.