Протокол MQV — старый добрый Диффи-Хеллман, но не совсем

Вот уже более 30 лет протокол распределения ключей Диффи-Хеллмана радует глаз простого криптомана своей простотой и надежностью. Для тех, кто эти последние 30 лет провел за занятиями более веселыми, нежели изучение криптографических протоколов, поясняю.
Протокол Диффи-Хеллмана был опубликован в 1976 году и послужил началом эры асимметричной криптографии. Суть его до гениального проста: Алиса и Боб хотят получить общий ключ для симметричной криптосистемы. Для этого они, договорившись, выбирают два больших числа g и p. Эти числа известны им обоим и держать их в секрете не имеет никакого смысла. Затем Алиса в тайне генерирует большое секретное число a, а Боб — большое число b. А далее за дело берется простая арифметика. Алиса посылает Бобу число
.
Боб в свою очередь высылает Алисе
.

Теперь, чтобы получить общий ключ Алиса вычисляет , а Боб находит .
Нетрудно проверить, что , т.к.
.
Гениальность идеи заключается в том, что для получения ключа K Алисе и Бобу не понадобится много времени, в то время, как злоумышленнику, чтобы найти K нужно уметь решать задачу дискретного логарифмирования.
Боясь утомить читателя общеизвестными фактами, перехожу сразу к сути дела. А что если абстрагироваться от теории и перейти к практике? То получим следующее.

Протокол Диффи-Хеллмана отлично противостоит пассивному нападению, но в случае реализации атаки «человек посередине» он не устоит. В самом деле, в протоколе ни Алиса, ни Боб не могут достоверно определить, кем является их собеседник, поэтому вполне возможно представить следующую ситуацию, при которой Боб и Алиса установили связь с Меллори, который Алисе выдает себя за Боба, а Бобу представляется Алисой. И тогда вместо протокола Диффи-Хеллмана получаем, что-то похожее на следующее:

Шаг	Алиса	Меллори	Боб
1
2
3
4

То есть, Меллори получает один ключ общий с Алисой(которая считает, что это Боб), и один ключ общий с Бобом(который считает, что это Алиса). А, следовательно, он может получать от Алисы любое сообщение для Боба расшифровать его ключом , прочитать, зашифровать ключом и передать Бобу. Таким образом, подлог может оставаться незамеченным очень долгое время.

ЭЦП в качестве защиты

Как бороться с такой уязвимостью? Самый логичный и простой ответ: нужна взаимная аутентификация. И тут на помощь приходит ЭЦП.
Если у Боба имеется открытый ключ Алисы, и он уверен на сто процентов, что это действительно ключ Алисы, то тогда для защиты от атаки «человек посередине» Алисе достаточно подписать своим закрытым ключом число на шаге 1. Теперь Меллори может сколько угодно пытаться выдать себя за Алису, но подделать ее подпись он не сможет, а Боба сразу начнут терзать «смутные сомненья».
Казалось бы решение найдено, протокол доработан, уязвимость устранена. Но… Как всегда есть одно но. И в данном случае в роли такового выступает чрезмерное увеличение размера сообщений за счет добавления подписи. Наглядно этот эффект демонстрирует следующая таблица:

Алгоритмы	Размер сообщения	Размер подписи	Общий размер
Диффи-Хеллман + DSA-подпись	1024 бит	320 бит	1344 бит
Диффи-Хеллман + RSA-подпись	1024	1024	2048
Диффи-Хеллман(на эллиптических кривых) + RSA-подпись	160	1024	1184
Диффи-Хеллман(на эллиптических кривых) + DSA-подпись(на эллиптических кривых)	160	320	480

Как видно из этой таблицы размер сообщений увеличивается в разы. Казалось бы, да и бог же с ними с этими лишними 320 битами, кому от них вред то будет? Но в криптографии не терпят полумер. Вот потому и был придуман протокол MQV, избавляющий Диффи-Хеллман от уязвимости и при этом не использующий ЭЦП.

Протокол MQV

Итак, протокол MQV – протокол распределения ключей, поддерживающий взаимную аутентификацию сторон и тем самым устраняющий уязвимость к атаке «человек посередине», присущей классическому Диффи-Хеллману. Помимо прочего, для аутентификации пользователей не используется никакая вспомогательная информация, наподобие ЭЦП, что позволяет существенно сократить размер передаваемых сообщений.

Протокол	Размер сообщения
MQV	1024 бит
MQV(на эллиптических кривых)	160 бит

Теперь о самом протоколе.
Алиса и Боб имеют каждый свою ключевую пару, состоящие из открытых и закрытых ключей: и . Разумеется, Бобу известен открытый ключ Алисы, а той в свою очередь известен открытый ключ Боба.
Далее, Алиса и Боб генерируют сеансовую пару ключей: и .
Затем происходит обмен как в классическом протоколе Диффи-Хеллмана:
Алиса к Бобу:
Боб к Алисе:
Теперь Алиса знает: A, B, C, D, a, .
А Бобу известны: A, B, C, D, b, .
Чтобы получить общий ключ K они должны проделать следующие операции.

Алиса:
Выбирает число l, равное размеру сообщения в битах деленному на 2. Так если используется EC-MQV и длина сообщения равна 160 бит, то l=80.
1. Задает
2. Находит
3. Задает
4. Вычисляет
5. Находит
6. Вычисляет
Боб проделывает те же действия, но со своими закрытыми ключами:
1. Задает
2. Находит
3. Задает
4. Вычисляет
5. Находит
6. Вычисляет
Получившиеся в результате вычислений числа и есть общий секретный ключ. Убедимся в этом:
, т.к. и ;
, т.к. ;
, т.к. и ;
, т.к. ;
.
Обратите внимание, что в преобразованиях используются секретные ключи как Алисы, так и Боба. Т.е. любой пользователь протокола может быть уверен, что кроме того человека, с которым он хочет установить соединение, получить общий ключ не удастся никому.
Несмотря на кажущуюся сложность, в скорости протокол MQV ничего не теряет по сравнению со схемой использующей ЭЦП, ведь и там и там используется одна и та же операция возведения в степень по модулю простого числа. Выгода же от использования протокола заключается в следующем. Это, во-первых, устойчивость к атаке «человек посередине», во-вторых, небольшой размер сообщений, а, в-третьих, удобная реализация протокола, избавляющая пользователя от необходимости подписывать каждое отправляемое сообщение.

upd:
Литература
1. Н. Смарт «криптография»(наиболее полное описание протокола MQV на русском из всех мною встреченных).
2. Болотов А. и др. «Элементарное введение в эллиптическую криптографию»(описание протокола на эллиптических кривых).
3. Ну и ссылка на википедию.