Общее описание

Еще один интересный пример использования возведения в степень по модулю большого простого числа P для открытого шифрования предложил А.Shamir (один из авторов RSA). Как и в системе ЭльГамаля сообщения M представляются целыми числами из интервала 1 < M < P.

Передача сообщений

Передача сообщения происходит следующим образом:

• абоненты знают числа 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

Пример использования

Эта процедура ОШ может быть использована, например, для таких "экзотических" целей как игра в карты по телефону.
Действительно, если игрок 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. Остальные процедуры игры проделываются аналогично.