(8)Боб вычисляет k = Zy mod n

(9)Кэрол вычисляет k = Xе mod n

Секретный ключ k равен gxyz mod n, и никто из подслушивающих каналы связи не сможет вычислить это значение. Протокол можно легко расширить для четверых и более участников, просто добавляются участники и этапы вычислений.

Расширенный Diffie-Hellman

Diffie-Hellman также работает в коммутативных кольцах [1253]. З. Шмули (Z. Shmuley) и Кевин МакКерли (Kevin McCurley) изучили вариант алгоритма, в котором модуль является составным числом [1441, 1038]. В.С. Миллер (V. S. Miller) и Нил Коблиц (Neal Koblitz) расширили этот алгоритм, используя эллиптические кривые [1095, 867]. Тахер ЭльДжамаль (Taher ElGamal) использовал основополагающую идею для разработки алгоритма шифрования и цифровой подписи (см. раздел 19.6).

Этот алгоритм также работает в поле Галуа GF(2k) [1442, 1038]. В ряде реализаций используется именно этот подход [884, 1631, 1632], так как вычисления выполняются намного быстрее . Но и криптоаналитические вычисления выполняются намного быстрее , поэтому важно тщательно выбирать поле, достаточно большое, чтобы обеспечить нужную безопасность .

Этот вариант алгоритма Diffie-Hellman позволяет Алисе генерировать ключ и послать его Бобу [745].

(1)Алиса выбирает случайное большое целое число x и генерирует k = gx mod n

(2)Боб выбирает случайное большое целое число y и посылает Алисе Y = gy mod n

(3)Алиса посылает Бобу X = Y mod n

(4)Боб вычисляет z = y-1

k = X mod n

Если все выполнено правильно , k = k.

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

Обмен ключом без обмена ключом

Если у вас сообщество пользователей, каждый может опубликовать открытый ключ , X = gx mod n, в общей базе данных. Если Алиса захочет установить связь с Бобом , ей понадобится только получить открытый ключ Боба и генерировать их общий секретный ключ. Она может зашифровать сообщение этим ключом и послать его Бобу. Боб извлечет открытый ключ Алисы и вычислит общий секретный ключ .

Каждая пара пользователей может использовать уникальный секретный ключ , не требуется никаких предварительных обменов данными между пользователями . Открытые ключи должны пройти сертификацию, чтобы предотвратить мошеннические вскрытия, и должны регулярно меняться, но в любом случае это очень умная идея

Патенты

Алгоритм обмена ключами Diffie-Hellman запатентован в Соединенных Штатах [718] и Канаде [719]. Группа, называющаяся Public Key Partners (PKP, Партнеры по открытым ключам), получила вместе с другими патентами в области криптографии с открытыми ключами получила лицензию на этот патент (см. раздел 25.5). Срок действия патента США истекает 29 апреля 1997 года .

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

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

другу [500].

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

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

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

y,Ek(SB(x,y))

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

£k(SA(x,y))

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

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

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

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

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

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

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

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

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

C1 = M © A

C2 = M © A © B

C3 = M © B

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

C1 © C2 © C3 =(M © A) © (M © A © B) © (M © B) = 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 в качестве ключа:Она посылает Бобу

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

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

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

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

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