Общие сведения
Криптографы со своей стороны вели поиски более эффективных систем открытого шифрования и в 1985 году Т. Эль-Гамаль (США) предложил следующую схему на основе возведения в степень по модулю большого простого числа P.
Задается большое простое число P и целое числоA, 1. Сообщения представляются целыми числами M из интервала 1.
Шифрование сообщений
Протокол передачи сообщения M выглядит следующим образом.
абоненты знают числа A и P;
абоненты генерируют независимо друг от друга случайные числа:
Ka, Kb удовлетворяющих условию: 1 получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:
В = AKbmоd (P).
отправитель шифрует сообщение M и отправляет полученную последовательность получателю.
C = M * BKamоd (P).
получатель расшифровывает полученное сообщение.
D = (AKa)-Kbmоd (P).
M = C * D mоd (P).
В этой системе открытого шифрования та же степень защиты, что для алгоритма RSA с модулем N из 200знаков, достигается уже при модуле P из 150 знаков. Это позволяет в 5−7раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.
Подтверждение подлинности отправителя
Для того, чтобы обеспечить при открытом шифровании по модулю простого числа P также и процедуру подтверждения подлинности отправителя Т. Эль-Гамаль предложил следующий протокол передачи подписанного сообщения M:
абоненты знают числа A и P;
отправитель генерирует случайное число и хранит его в секрете:
Ka удовлетворяющее условию: 1 вычисляет и передаёт получателю число B, определяемое последователньостью:
В = AKamоd (P).
Для сообщения M (1): выбирает случайное число L (1, удовлетворяющее условию (L, P — 1) = 1 вычисляет число.
R = ALmоd (P).
решает относительно S.
M=Ka*R+L*S mоd (P).
передаёт подписанное сообщение [M, R, S] получатель проверяет правильность подписи.
A M = (BR) * (RS) mоd (P).
В этой системе секретным ключом для подписывания сообщений является число X, а открытым ключом для проверки достоверности подписи число B. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.
