Трехпроходный протокол Шамира

Этот изобретенный Ади Шамиром но никогда не опубликованный протокол позволяет Алисе и Бобу безопасно обмениваться информацией, не используя предварительного обмена ни секретными, ни открытыми ключами [1008]. Он предполагает использование коммутативного симметричного шифра, для которого:

E_A(E_B(P)) = E_B(E_A(P))

Секретный ключ Алисы - A, а Боба - B. Алиса хочет послать сообщение M Бобу. Вто этот протокол.

(1) Алиса шифрует Mсвоим ключом и посылает его Бобу

C₁ = E_A(M)

(2) Боб шифрует C₁ своим ключом и посылает Алисе

C₂ = E_B(E_A(M))

(3) Алиса расшифровывает C₂ своим ключом и посылает Бобу

C₃ = D_A(E_B(E_A(M)))= D_A(E_A(E_B(M)))= E_B(M)

(4) Боб расшифровывает C₃ своим ключом, получая M.

Коммутативны и обладают совершенной безопасностью одноразовые блокноты, но с этим протоколом они работать не будут. При использовании одноразового блокнота три шифротекста будут выглядеть следующим образом be:

C₁ = M Å A

C₂ = M Å A Å B

C₃ = M Å B

Ева, записав эти три сообщения, которыми обмениваются Алиса и Боб, просто выполнит XOR всех этих шифротекстов и восстановит сообщение:

C₁ Å C₂ Å C₃ =(M Å A) Å (M Å A Å B) Å (M Å B) = M

Очевидно, что такой способ работать не будет.

Шамир (и независимо Джим Омура (Jim Omura)) описал похожий на RSA алгоритм шифрования, который будет работать с этим протоколом. Пусть pбудет большим большим простым числом, причем множитель p-1 является большим простым. Выберем ключ шифрования e, взаимно простой с p-1. Вычислим d, для которого выполняется de= 1 (mod p - 1). Для шифрования сообщения вычисляем

C= M^emod p

Для дешифрирования сообщения вычисляем

M= C^dmod p

По видимому, у Евы нет способа получить M, не решив проблему дискретного логарифма, но это никогда не было доказано.

Как и Diffie-Hellman, этот протокол позволяет Алисе начать секретный обмен информацией с Бобом, не зная ни одного из его ключей. При использовании алгоритма с открытым ключом Алиса должна знать открытый ключ Боба. Применяя трехпроходный алгоритм Шамира, она просто посылает Бобу шифротекст сообщения. То же действие с помощью алгоритма с открытым ключом выглядит следующим образом:

(1) Алиса запрашивает у Боба (или у KDC) его открытый ключ.

(2) Боб (или KDC) посылает Алисе свой открытый ключ.

(3) Алиса шифрует M открытым ключом Боба и посылает его Бобу.

Трехпроходный алгоритм Шамира не может устоять перед вскрытием "человек в середине".

COMSET

COMSET (COMmunications SETup, установление связи) это протокол одновременной идентификации и обмена ключом, разработанный для проекта RIPE [1305] (см. раздел 25.7). С помощью криптографии с открытыми ключами он позволяет Алисе и Бобу идентифицировать друг друга, при этом обмениваясь секретным ключом.

Математической основой COMSET служит схема Rabin [1283] (см. раздел 19.5). Сама схема впервые была предложена в [224]. См. подробности в [1305].