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 раз увеличить скорость обработки информации. Однако, в таком варианте открытого шифрования нет подтверждения подлинности сообщений.
1.2.3. Подтверждение подлинности отправителя
Для того, чтобы обеспечить при открытом шифровании по модулю простого числа 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. Процедура проверки подписи служит также и для проверки правильности расшифрования, если сообщения шифруются.
1.3. Алгоритм Шамира
1.3.1. Общее описание
Еще один интересный пример использования возведения в степень по модулю большого простого числа P для открытого шифрования предложил А.Shamir (один из авторов RSA). Как и в системе ЭльГамаля сообщения M представляются целыми числами из интервала 1 < M < P.
1.3.2. Передача сообщений
Передача сообщения происходит следующим образом:
абоненты знают числа P;
абоненты генерируют независимо друг от друга случайные числа:
Ka, Kb
удовлетворяющих условию:
1 < K < P
отправитель вычисляет значение и передаёт получателю:
C = M Ka mоd(P)
получатель вычисляет и передаёт отправителю число B, определяемое последовательностью:
D = C Kb mоd(P)
отправитель аннулирует свой шифр и отправляет полученную последовательность получателю
E=D(X-1) mоd(P) E = D Fa mоd(P)
где:
Fa = Ka -1
получатель расшифровывает полученное сообщение
M = E Fb mоd(P)
где:
Fb = Kb –1
1.3.3. Пример использования
Эта процедура ОШ может быть использована, например, для таких "экзотических" целей как игра в карты по телефону. Действительно, если игрок A желает "сдать" игроку B, скажем, 5 карт из 52 как при игре в покер, он зашифровывает обозначения всех карт и передает их игроку B:
Ca = Ma Ka mоd(P)
где
I=1,2, ,52
Игрок B выбирает из них 5, зашифровывает своим ключом 22 и возвращает игроку А:
Da = Ca Kb mоd(P)
где
I=1,2 .,5
Игрок A снимает с этих 5 карт свой шифр и выдает их игроку B. Игрок B расшифровывает полученные карты:
Ma = Ea Fb mоd (P)
При этом оставшаяся часть колоды C(6) .C(52) теперь находится у игрока B, но он не может раскрыть эти карты, т.к. они зашифрованы на ключе его партнера A. Остальные процедуры игры проделываются аналогично.
1.4. Кpиптосистемы на основе эллиптических уpавнений
Эллиптические кpивые - математический объект, котоpый может опpеделен над любым полем (конечным, действительным, pациональным или комплексным). В кpиптогpафии обычно используются конечные поля. Эллиптическая кpивая есть множество точек (x,y), удовлетвоpяющее следующему уpавнению: