Разное



Алгоритм ЭльГамаля


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

Криптографы со своей стороны вели
поиски более эффективных систем открытого
шифрования и в 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. Процедура
проверки подписи служит также и для проверки
правильности расшифрования, если сообщения
шифруются.

 

Оставит комментарий