22.2 Протокол "точка-точка"

Обмен ключами Diffie-Hellman чувствителен к вскрытию "человек в середине" . Одним из способов предотвратить это, является необходимость для Алисы и Боба подписывать сообщения, которые они посылают друг

другу [500].

Этот протокол предполагает, что у Алисы есть сертифицированный открытый ключ Боба, а у Боба есть се р-тифицированный открытый ключ Алисы. Эти сертификаты подписаны некоторым заслуживающим доверия органом власти, непосредственно не участвующим в протоколе . Вот как Алиса и Боб генерируют секретный ключ k.

(1) Алиса генерирует случайное число x и посылает его Бобу.

(2) Боб генерирует случайное число y. Используя протокол Diffie-Hellman, он вычисляет общий ключ k на базе x и y. Он подписывает x и y и шифрует подпись ключом k. Затем он посылает получившееся вместе с y Алисе.

y,Ek(SB(xy))

(3) Алиса также вычисляет k. Она расшифровывает оставшуюся часть сообщения Боба и проверяет его подпись. Затем она посылает Бобу подписанное сообщение, состоящее из x и y, зашифрованных общим ключом k.

Ek(SA(xy))

(4) Боб расшифровывает сообщение и проверяет подпись Алисы.

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

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

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

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

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

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

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

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

C1 = M ® A

C2 = M ® A ® В

C3 = M ® В

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

C1 ® C2 ® C3 =(M ® A) ® (M ® A ® В) ® (M ® В) = M

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

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

C = Me mod p

Для дешифрирования сообщения вычисляем M = Cd mod p

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

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

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

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

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

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

22.4 COMSET

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

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

22.5 Обмен зашифрованными ключами

Протокол обмена зашифрованными ключами (Encrypted Key Exchange, EKE) был разработан Стивом Бел-ловином (Steve Bellovin) и Майклом Мерриттом (Michael Merritt) [109]. Он обеспечивает безопасность и проверку подлинности в компьютерных сетях, по новому используя и симметричную криптографию, и криптогр а-фию с открытыми ключами: общий секретный ключ используется для шифрования генерированного случа й-ным образом открытого ключа.

Базовый протокол EKE

Алиса и Боб (два пользователя, клиент и сервер, или кто угодно) имеют общий пароль P. Используя следующий протокол, они могут проверить подлинность друг друга и генерировать общий сеансовый ключ K.

(1) Алиса Случайным образом генерирует пару "открытый ключ/закрытый ключ" . Она шифрует открытый ключ K с помощью симметричного алгоритма, используя P в качестве ключа: Ep(K). Она пос1лает Бобу

A, Ep(K)

(2) Боб знает P. Он расшифровывает сообщение, получая Затем он генерирует случайный сеансовый ключ K шифрует его открытым ключом, который он получил от Алисы, а затем используя P качестве ключа. Он посылает Алисе

(3) Алиса расшифровывает сообщение, получая K. Она генерирует случайную строку RA, шифрует ее с помощью K и посылает Бобу

(4) Боб расшифровывает сообщение, получая RA. Он генерирует другую случайную строку, RB, шифрует обе строки ключом K и посылает Алисе результат.

Ek(Ra,Rb;

(5) Алиса расшифровывает сообщение, получая Ra и Rb. Если строка Ra, полученная от Боба, - это та самая строка, которую она послала Бобу на этапе (3), она, используя K, шифрует Rb и пос1лает ее Бобу.

Ek(Rb;

(6) Боб расшифровывает сообщение, получая Rb. Если строка Rb, полученная от Алисы, - это та самая строка, которую он послал ей на этапе (4), завершен. Теперь обе стороны могут обмениваться информацией, и с-пользуя K в качестве сеансового ключа.

На этапе (3) и Алиса, и Боб знают K и K. K - это сеансовый ключ, он может быть использован для шифров а-ния всех других сообщений, которыми обмениваются Алиса и Боб. Ева, сидя между Алисой и Бобом, знает только EP(K), EP(E(K) и несколько сообщений, зашифрованных K. В других протоколах Ева могла бы попробовать угадать P (люди все время любят выбирать плохие пароли, и если Ева достаточно умна, она может этот пароль) и затем проверить свои предположения. В рассматриваемом протоколе Ева не может проверять свои предположения, не вскрыв при этом и алгоритм с открытым ключом . И, если K и K выбираются случайным образом, то эта проблема будет непреодолимой.

Ответная часть протокола, этапы (3) - (6), обеспечивает подтверждение. Этапы (3) - (5) доказывают Алисе, что Боб знает K, этапы (4) - (6) доказывают Бобу, что Алиса знает K. Обмен метками времени, используемый в протоколе Kerberos, решает ту же задачу.

EKE может быть реализован с множеством алгоритмов с открытыми ключами : RSA, ElGamal, Diffie-Hellman. Проблемы с безопасностью возникают при реализации EKE с алгоритмом рюкзака (даже без учета проблем безопасности, присущих самим алгоритмам рюкзака ): нормальное распределение шифротекста соо б-щений сводит на нет преимущества EKE.

Реализация EKE с помощью RSA

Алгоритм RSA кажется идеальным для такого использования, но есть ряд тонких проблем . Авторы рекомендуют шифровать на этапе (1) только показатель степени, посылая модуль . Объяснение этого совета и другие тонкости, связанные с использованием RSA, можно найти [109].

Реализация EKE с помощью ElGamal

Реализация EKE на базе алгоритма ElGamal проста, можно даже упростить основной протокол. Используя обозначения из раздела 19.6, g и p служат частями открытого ключа, общими для всех пользователей . Закрытым ключом является случайное число r. Открытым - gr mod На этапе (1) Алиса посылает Бобу следующее сообщение

Алиса, gr mod p

Обратите внимание, что этот открытый ключ не нужно шифровать с помощью P. В общем случае это неверно, но это так для алгоритма ElGamal algorithm. Подробности в [109].

Боб выбирает случайное число R (для алгоритма ElGamal, независимо от других случайных чисел, выбира е-мых для EKE), и сообщение, которое он посылает Алисе на этапе (2), выглядит так

Ep(gR mod ,p, KgrR mod ,p)

Существующие ограничения на выбор переменных для ElGamal были приведены в разделе 19.6.

Реализация EKE с помощью Diffie-Hellman

При использовании протокола Diffie-Hellman K генерируется автоматически. Окончательный протокол еще проще. Значения g и n определяются для всех пользователей сети.

(1) Алиса выбирает случайное число rA и пос1лает Бобу A, grA mod n

При использовании Diffie-Hellman Алисе не нужно шифровать с помощью P свое первое сообщение.

(2) Боб выбирает случайное число гв и вычисляет

K= grA *Гв mod n

Он генерирует случайную строку RB, затем вычисляет и пос1лает Алисе: Ep( grB mod n),EK(RB)

(3) Алиса расшифровывает первую половину сообщения Боба, получая grB mod n. Затем она вычисляет K и

использует его для шифрования RB. Она генерирует другую случайную строку RA,, шифрует обе строки ключом K и посылает результат Бобу.

Ek(Ra, ,Rb)

(4) Боб расшифровывает сообщение, получая RA, и RB. Если полученная от Алисы строка RB совпадает с той, которую он посылал ей на этапе (2), он шифрует RA ключом K и посылает результат Алисе.

Ek(Ra)