Протоколы MTI

Протоколы MTI — семейство протоколов распределения ключей, разработанные Т. Мацумото (T. Matsumoto), И. Такасита (Y. Takashita) и Х. Имаи (H. Imai) и названные по именам авторов. Протоколы MTI делятся на три класса протоколов: MTI/A, MTI/B, MTI/C.

Протокол распределения ключей решает задачу распределения секретных ключей шифрования между общающимися сторонами. Множество таких протоколов делится на следующие три типа:

1. протоколы обмена уже сгенерированными ключами;
2. протоколы совместной выработки общего ключа (открытое распределение ключей);
3. протоколы предварительного распределения ключей.

Протоколы MTI относятся к протоколам открытого распределения ключей.

В основе протоколов открытого распределения ключей лежит обмен сообщениями между пользователями, по результатам которого каждый пользователь вычисляет секретный сеансовый ключ. При этом вычисление сеансового ключа до обмена сообщениями невозможно. Поэтому данные протоколы еще называют динамическими протоколами распределения ключей в отличие от статических протоколов, в которых ключи известны еще до самого сеанса связи. Кроме того, создание сеансовых ключей в протоколах открытого распределения требует от пользователей знания только открытых ключей, т.е. позволяет паре пользователей системы выработать общий секретный ключ, не обмениваясь закрытыми ключами. Именно это привело к тому, что такие протоколы сразу же после своего появления в 1976 году привлекли к себе внимание международного сообщества.

ИсторияПравить

Идея построения протоколов открытого распределения ключей была впервые высказана Уитфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) на «Национальной Компьютерной Конференции» в июне 1976 года. И в ноябре 1976 года ими же в работе «Новые направления в криптографии» (англ. New Directions in Cryptography) был предложен первый протокол открытого распределения ключей, названный по именам авторов (протокол Диффи-Хеллмана).

Первый в своем роде, протокол Диффи-Хеллмана был уязвим для некоторых типов атак, в частности, для атак «человек посередине». Для решения данной проблемы необходимо было обеспечить пользователей механизмом аутентификации. Таким механизмом стал опубликованный в августе 1977 года в колонке «Математические игры» журнала Scientific American алгоритм асимметричного шифрования RSA, который позволил решить проблему общения через открытый канал.

В 1984 году Тахером Эль-Гамалем был предложен усовершенствованный протокол Диффи-Хеллмана с возможностью односторонней аутентификации, когда только одна из общающихся сторон может проверить подлинность другой. В отличие от RSA протокол Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

В феврале 1986 года Т. Мацумото, И. Такасима и Х. Имаи представили решение проблемы взаимной аутентификации без использования RSA. В разработанных ими протоколах MTI выражение для вычисления общего секретного ключа содержит как открытые, так и закрытые ключи легальных пользователей. Это решение позволяет провести аутентификацию одновременно с вычислением общего секретного ключа (нелегальный пользователь не может вычислить значение секретного ключа).

На настоящий момент протоколы MTI включены в стандарт ISO/IEC 11770-3.

Описание протоколов MTIПравить

Рассмотрим процесс обмена информацией между сторонами A и B. Ниже представлены обозначения, которые будут использованы при описании работы протоколов MTI.

$p$$p$	большое простое число (не менее 1024 бит).
$q$$q$	простое число (порядка 160 бит), являющееся делителем числа $p-<!--\; -\; -->1$$p-1$ .
$G$$G$	подгруппа группы ${\mathbb{Z}}_p^{\ast <!--\; \ast \; -->}$$\mathbb {Z} _{p}^{*}$  (обычно порядка $q$$q$ , но иногда совпадает с ${\mathbb{Z}}_p^{\ast <!--\; \ast \; -->}$$\mathbb {Z} _{p}^{*}$ )
$g$$g$	порождающий элемент подгруппы $G$$G$
$a$$a$ , $b$$b$	закрытые ключи сторон A и B
$A$$A$ , $B$$B$	открытые ключи сторон A и B : $A=g^{a}modp$$A=g^{a}\ mod\ p$ , $B=g^{b}modp$$\ B=g^{b}\ mod\ p$ .
$R_A$$R_{A}$ , $R_B$$R_{B}$	случайные целые числа, обычно той же величины, что и порядок группы $G$$G$ , выбираемые сторонами A и B соответственно
$M_A$$M_{A}$ , $M_B$$M_{B}$	сообщения, отправляемые от A к B и от B к A соответственно.
$K$$K$	секретный сеансовый ключ, вычисленный сторонами A и B
$(a,b)$$(a,b)$	наибольший общий делитель чисел $a$$a$  и $b$$b$

Все вычисления в дальнейшем проводятся в группе ${\mathbb{Z}}_p^{\ast <!--\; \ast \; -->}$$\mathbb {Z} _{p}^{*}$ .

MTI/A(0)Править

Алгоритм работы

1. Сторона $A$$A$  выбирает случайное число $R_A\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{A}\in \mathbb {Z} _{q}^{*}$  и отправляет $B$$B$  сообщение $M_A=g^{R_A}modp$$M_{A}=g^{R_{A}}{\bmod {p}}$ 
2. Сторона $B$$B$  выбирает случайное число $R_B\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{B}\in \mathbb {Z} _{q}^{*}$  и отправляет $A$$A$  сообщение $M_B=g^{R_B}modp$$M_{B}=g^{R_{B}}{\bmod {p}}$ 
3. Сторона $A$$A$  вычисляет сеансовый ключ: $K=B^{R_A}{M}_B^{a}modp=g^{a{R}_B+b{R}_A}modp$$K=B^{R_{A}}M_{B}^{a}{\bmod {p}}=g^{aR_{B}+bR_{A}}{\bmod {p}}$ 
4. Сторона $B$$B$  вычисляет сеансовый ключ: $K=A^{R_B}{M}_A^{b}modp=g^{a{R}_B+b{R}_A}modp$$K=A^{R_{B}}M_{A}^{b}{\bmod {p}}=g^{aR_{B}+bR_{A}}{\bmod {p}}$ 

Проводимые вычисления

$A:<!--\; :\; -->K=B^{R_A}{M}_B^{a}modp=(g^b{)}^{R_A}(g^{R_B}{)}^{a}modp=g^{a{R}_B+b{R}_A}modp$$A\colon K=B^{R_{A}}M_{B}^{a}{\bmod {p}}=(g^{b})^{R_{A}}(g^{R_{B}})^{a}{\bmod {p}}=g^{aR_{B}+bR_{A}}{\bmod {p}}$ 

$B:<!--\; :\; -->K=A^{R_B}{M}_A^{b}modp=(g^a{)}^{R_B}(g^{R_A}{)}^{b}modp=g^{a{R}_B+b{R}_A}modp$$B\colon K=A^{R_{B}}M_{A}^{b}{\bmod {p}}=(g^{a})^{R_{B}}(g^{R_{A}})^{b}{\bmod {p}}=g^{aR_{B}+bR_{A}}{\bmod {p}}$ 

MTI/B(0)Править

Алгоритм работы

1. Сторона $A$$A$  выбирает случайное число $R_A\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{A}\in \mathbb {Z} _{q}^{*}$  и отправляет $B$$B$  сообщение $M_A=B^{R_A}$$M_{A}=B^{R_{A}}$ 
2. Сторона $B$$B$  выбирает случайное число $R_B\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{B}\in \mathbb {Z} _{q}^{*}$  и отправляет $A$$A$  сообщение $M_B=A^{R_B}$$M_{B}=A^{R_{B}}$ 
3. Сторона $A$$A$  вычисляет сеансовый ключ: $K=M_B^{a^{-<!--\; -\; -->1}}{g}^{R_A}modp=g^{R_A+R_B}modp$$K=M_{B}^{{a}^{-1}}g^{R_{A}}{\bmod {p}}=g^{R_{A}+R_{B}}{\bmod {p}}$ 
4. Сторона $B$$B$  вычисляет сеансовый ключ: $K=M_A^{b^{-<!--\; -\; -->1}}{g}^{R_B}modp=g^{R_A+R_B}modp$$K=M_{A}^{{b}^{-1}}g^{R_{B}}{\bmod {p}}=g^{R_{A}+R_{B}}{\bmod {p}}$ 

Проводимые вычисления

$K=M_B^{a^{-<!--\; -\; -->1}}{g}^{R_A}=(A^{R_B}{)}^{a^{-<!--\; -\; -->1}}{g}^{R_A}=(g^{a{R}_B}{)}^{a^{-<!--\; -\; -->1}}{g}^{R_A}=g^{R_A+R_B}modp$$K=M_{B}^{a^{-1}}g^{R_{A}}=(A^{R_{B}})^{a^{-1}}g^{R_{A}}=(g^{{a}{R_{B}}})^{a^{-1}}g^{R_{A}}=g^{R_{A}+R_{B}}{\bmod {p}}$ 

$K=M_A^{b^{-<!--\; -\; -->1}}{g}^{R_B}=(B^{R_A}{)}^{b^{-<!--\; -\; -->1}}{g}^{R_B}=(g^{b{R}_A}{)}^{b^{-<!--\; -\; -->1}}{g}^{R_B}=g^{R_A+R_B}modp$$K=M_{A}^{b^{-1}}g^{R_{B}}=(B^{R_{A}})^{b^{-1}}g^{R_{B}}=(g^{{b}{R_{A}}})^{b^{-1}}g^{R_{B}}=g^{R_{A}+R_{B}}{\bmod {p}}$ 

MTI/C(0)Править

Алгоритм работы

1. Сторона $A$$A$  выбирает случайное число $R_A\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{A}\in \mathbb {Z} _{q}^{*}$  и отправляет B сообщение $M_A=B^{R_A}$$M_{A}=B^{R_{A}}$ 
2. Сторона $B$$B$  выбирает случайное число $R_B\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{B}\in \mathbb {Z} _{q}^{*}$  и отправляет A сообщение $M_B=A^{R_B}$$M_{B}=A^{R_{B}}$ 
3. Сторона $A$$A$  вычисляет сеансовый ключ: $K=M_B^{a^{-<!--\; -\; -->1}{R}_A}modp=g^{R_A{R}_B}modp$$K=M_{B}^{a^{-1}R_{A}}{\bmod {p}}=g^{R_{A}R_{B}}{\bmod {p}}$ 
4. Сторона $B$$B$  вычисляет сеансовый ключ: $K=M_A^{b^{-<!--\; -\; -->1}{R}_B}modp=g^{R_A{R}_B}modp$$K=M_{A}^{b^{-1}R_{B}}{\bmod {p}}=g^{R_{A}R_{B}}{\bmod {p}}$ 

Проводимые вычисления

$K=M_B^{a^{-<!--\; -\; -->1}{R}_A}=(A^{R_B}{)}^{a^{-<!--\; -\; -->1}{R}_A}=(g^{a{R}_B}{)}^{a^{-<!--\; -\; -->1}{R}_A}=g^{R_A{R}_B}$$K=M_{B}^{a^{-1}R_{A}}=(A^{R_{B}})^{a^{-1}R_{A}}=(g^{aR_{B}})^{a^{-1}R_{A}}=g^{R_{A}R_{B}}$ 

$K=M_A^{b^{-<!--\; -\; -->1}{R}_B}=(B^{R_A}{)}^{b^{-<!--\; -\; -->1}{R}_B}=(g^{b{R}_A}{)}^{b^{-<!--\; -\; -->1}{R}_B}=g^{R_A{R}_B}$$K=M_{A}^{b^{-1}R_{B}}=(B^{R_{A}})^{b^{-1}R_{B}}=(g^{bR_{A}})^{b^{-1}R_{B}}=g^{R_{A}R_{B}}$ 

MTI/A(k)Править

Алгоритм работы

1. Сторона $A$$A$  выбирает случайное число $R_A\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{A}\in \mathbb {Z} _{q}^{*}$  и отправляет B сообщение $M_A=g^{a^k{R}_A}$$M_{A}=g^{a^{k}R_{A}}$ 
2. Сторона $B$$B$  выбирает случайное число $R_B\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{B}\in \mathbb {Z} _{q}^{*}$  и отправляет A сообщение $M_B=g^{b^k{R}_B}$$M_{B}=g^{b^{k}R_{B}}$ 
3. Сторона $A$$A$  вычисляет сеансовый ключ: $K=B^{a^k{R}_A}{M}_B^a=g^{b{a}^k{R}_A+a{b}^k{R}_B}$$K=B^{a^{k}R_{A}}M_{B}^{a}=g^{ba^{k}R_{A}+ab^{k}R_{B}}$ 
4. Сторона $B$$B$  вычисляет сеансовый ключ: $K=A^{b^k{R}_B}{M}_A^b=g^{a{b}^k{R}_B+b{a}^k{R}_A}$$K=A^{b^{k}R_{B}}M_{A}^{b}=g^{ab^{k}R_{B}+ba^{k}R_{A}}$ 

Проводимые вычисления

$A:<!--\; :\; -->K=B^{a^k{R}_A}{M}_B^a=(g^b{)}^{a^k{R}_A}(g^{b^k{R}_B}{)}^a=g^{a{b}^k{R}_B+b{a}^k{R}_A}$$A\colon K=B^{a^{k}R_{A}}M_{B}^{a}=(g^{b})^{a^{k}R_{A}}(g^{b^{k}R_{B}})^{a}=g^{ab^{k}R_{B}+ba^{k}R_{A}}$ 

$B:<!--\; :\; -->K=A^{b^k{R}_B}{M}_A^b=(g^a{)}^{b^k{R}_B}(g^{a^k{R}_A}{)}^b=g^{a{b}^k{R}_B+b{a}^k{R}_A}$$B\colon K=A^{b^{k}R_{B}}M_{A}^{b}=(g^{a})^{b^{k}R_{B}}(g^{a^{k}R_{A}})^{b}=g^{ab^{k}R_{B}+ba^{k}R_{A}}$ 

MTI/B(k)Править

Алгоритм работы

1. Сторона $A$$A$  выбирает случайное число $R_A\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{A}\in \mathbb {Z} _{q}^{*}$  и отправляет $B$$B$  сообщение $M_A=B^{a^k{R}_A}$$M_{A}=B^{a^{k}R_{A}}$ 
2. Сторона $B$$B$  выбирает случайное число $R_B\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{B}\in \mathbb {Z} _{q}^{*}$  и отправляет $A$$A$  сообщение $M_B=A^{b^k{R}_B}$$M_{B}=A^{b^{k}R_{B}}$ 
3. Сторона $A$$A$  вычисляет сеансовый ключ: $K=M_B^{a^{-<!--\; -\; -->1}}{g}^{a^k{R}_A}=g^{a^k{R}_A+b^k{R}_B}$$K=M_{B}^{a^{-1}}g^{a^{k}R_{A}}=g^{a^{k}R_{A}+b^{k}R_{B}}$ 
4. Сторона $B$$B$  вычисляет сеансовый ключ: $K=M_A^{b^{-<!--\; -\; -->1}}{g}^{b^k{R}_B}=g^{a^k{R}_A+b^k{R}_B}$$K=M_{A}^{b^{-1}}g^{b^{k}R_{B}}=g^{a^{k}R_{A}+b^{k}R_{B}}$ 

Проводимые вычисления

$K=M_B^{a^{-<!--\; -\; -->1}}{g}^{a^k{R}_A}=(A^{b^k{R}_B}{)}^{a^{-<!--\; -\; -->1}}{g}^{a^k{R}_A}=(g^{a{b}^k{R}_B}{)}^{a^{-<!--\; -\; -->1}}{g}^{a^k{R}_A}=g^{a^k{R}_A+b^k{R}_B}$$K=M_{B}^{a^{-1}}g^{a^{k}R_{A}}=(A^{b^{k}R_{B}})^{a^{-1}}g^{a^{k}R_{A}}=(g^{ab^{k}R_{B}})^{a^{-1}}g^{a^{k}R_{A}}=g^{a^{k}R_{A}+b^{k}R_{B}}$ 

$K=M_A^{b^{-<!--\; -\; -->1}}{g}^{b^k{R}_B}=(B^{a^k{R}_A}{)}^{b^{-<!--\; -\; -->1}}{g}^{b^k{R}_B}=(g^{b{a}^k{R}_A}{)}^{b^{-<!--\; -\; -->1}}{g}^{b^k{R}_B}=g^{a^k{R}_A+b^k{R}_B}$$K=M_{A}^{b^{-1}}g^{b^{k}R_{B}}=(B^{a^{k}R_{A}})^{b^{-1}}g^{b^{k}R_{B}}=(g^{ba^{k}R_{A}})^{b^{-1}}g^{b^{k}R_{B}}=g^{a^{k}R_{A}+b^{k}R_{B}}$ 

MTI/C(k)Править

Алгоритм работы

1. Сторона $A$$A$  выбирает случайное число $R_A\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{A}\in \mathbb {Z} _{q}^{*}$  и отправляет $B$$B$  сообщение $M_A=B^{a^k{R}_A}$$M_{A}=B^{a^{k}R_{A}}$ 
2. Сторона $B$$B$  выбирает случайное число $R_B\in <!--\; \in \; -->{\mathbb{Z}}_q^{\ast <!--\; \ast \; -->}$$R_{B}\in \mathbb {Z} _{q}^{*}$  и отправляет $A$$A$  сообщение $M_B=A^{b^k{R}_B}$$M_{B}=A^{b^{k}R_{B}}$ 
3. Сторона $A$$A$  вычисляет сеансовый ключ: $K=M_B^{a^{-<!--\; -\; -->1}{a}^k{R}_A}=g^{a^k{R}_A{b}^k{R}_B}$$K=M_{B}^{a^{-1}a^{k}R_{A}}=g^{a^{k}R_{A}b^{k}R_{B}}$ 
4. Сторона $B$$B$  вычисляет сеансовый ключ: $K=M_A^{b^{-<!--\; -\; -->1}{b}^k{R}_B}=g^{a^k{R}_A{b}^k{R}_B}$$K=M_{A}^{b^{-1}b^{k}R_{B}}=g^{a^{k}R_{A}b^{k}R_{B}}$ 

Проводимые вычисления

$K=M_B^{a^{-<!--\; -\; -->1}{a}^k{R}_A}=(A^{b^k{R}_B}{)}^{a^{-<!--\; -\; -->1}{a}^k{R}_A}=(g^{a{b}^k{R}_B}{)}^{a^{-<!--\; -\; -->1}{a}^k{R}_A}=g^{a^k{R}_A{b}^k{R}_B}$$K=M_{B}^{a^{-1}a^{k}R_{A}}=(A^{b^{k}R_{B}})^{a^{-1}a^{k}R_{A}}=(g^{ab^{k}R_{B}})^{a^{-1}a^{k}R_{A}}=g^{a^{k}R_{A}b^{k}R_{B}}$ 

$K=M_A^{b^{-<!--\; -\; -->1}{b}^k{R}_B}=(B^{a^k{R}_A}{)}^{b^{-<!--\; -\; -->1}{b}^k{R}_B}=(g^{b{a}^k{R}_A}{)}^{b^{-<!--\; -\; -->1}{b}^k{R}_B}=g^{a^k{R}_A{b}^k{R}_B}$$K=M_{A}^{b^{-1}b^{k}R_{B}}=(B^{a^{k}R_{A}})^{b^{-1}b^{k}R_{B}}=(g^{ba^{k}R_{A}})^{b^{-1}b^{k}R_{B}}=g^{a^{k}R_{A}b^{k}R_{B}}$ 

Анализ протоколов MTIПравить

Таблица протоколов MTI

Протокол	$m_A$$m_{A}$	$m_B$$m_{B}$	$K_A$$K_{A}$	$K_B$$K_{B}$	$K_{AB}$$K_{AB}$
MTI/A(0)	$g^{r_A}$$g^{r_{A}}$	$g^{r_B}$$g^{r_{B}}$	$y_B^{r_A}{m}_B^{x_A}$$y_{B}^{r_{A}}m_{B}^{x_{A}}$	$y_A^{r_B}{m}_A^{x_B}$$y_{A}^{r_{B}}m_{A}^{x_{B}}$	$g^{x_A{r}_B+x_B{r}_A}$$g^{x_{A}r_{B}+x_{B}r_{A}}$
MTI/B(0)	$y_B^{r_A}$$y_{B}^{r_{A}}$	$y_A^{r_B}$$y_{A}^{r_{B}}$	$m_B^{x_A^{-<!--\; -\; -->1}}{g}^{r_A}$$m_{B}^{x_{A}^{-1}}g^{r_{A}}$	$m_A^{x_B^{-<!--\; -\; -->1}}{g}^{r_B}$$m_{A}^{x_{B}^{-1}}g^{r_{B}}$	$g^{r_A+r_B}$$g^{r_{A}+r_{B}}$
MTI/C(0)	$y_B^{r_A}$$y_{B}^{r_{A}}$	$y_A^{r_B}$$y_{A}^{r_{B}}$	$m_B^{x_A^{-<!--\; -\; -->1}{r}_A}$$m_{B}^{x_{A}^{-1}r_{A}}$	$m_A^{x_B^{-<!--\; -\; -->1}{r}_B}$$m_{A}^{x_{B}^{-1}r_{B}}$	$g^{r_A{r}_B}$$g^{r_{A}r_{B}}$
MTI/A(k)	$g^{x_A^k{r}_A}$$g^{x_{A}^{k}r_{A}}$	$g^{x_B^k{r}_B}$$g^{x_{B}^{k}r_{B}}$	$y_B^{x_A^k{r}_A}{m}_B^{x_A}$$y_{B}^{x_{A}^{k}r_{A}}m_{B}^{x_{A}}$	$y_A^{x_B^k{r}_B}{m}_A^{x_B}$$y_{A}^{x_{B}^{k}r_{B}}m_{A}^{x_{B}}$	$g^{x_A{x}_B^k{r}_B+x_B{x}_A^k{r}_A}$$g^{x_{A}x_{B}^{k}r_{B}+x_{B}x_{A}^{k}r_{A}}$
MTI/B(k)	$y_B^{x_A^k{r}_A}$$y_{B}^{x_{A}^{k}r_{A}}$	$y_A^{x_B^k{r}_B}$$y_{A}^{x_{B}^{k}r_{B}}$	$m_B^{x_A^{-<!--\; -\; -->1}}{g}^{x_A^k{r}_A}$$m_{B}^{x_{A}^{-1}}g^{x_{A}^{k}r_{A}}$	$m_A^{x_B^{-<!--\; -\; -->1}}{g}^{x_B^k{r}_B}$$m_{A}^{x_{B}^{-1}}g^{x_{B}^{k}r_{B}}$	$g^{x_A^k{r}_A+x_B^k{r}_B}$$g^{x_{A}^{k}r_{A}+x_{B}^{k}r_{B}}$
MTI/C(k)	$y_B^{x_A^k{r}_A}$$y_{B}^{x_{A}^{k}r_{A}}$	$y_A^{x_B^k{r}_B}$$y_{A}^{x_{B}^{k}r_{B}}$	$m_B^{x_A^{-<!--\; -\; -->1}{x}_A^k{r}_A}$$m_{B}^{x_{A}^{-1}x_{A}^{k}r_{A}}$	$m_A^{x_B^{-<!--\; -\; -->1}{x}_B^k{r}_B}$$m_{A}^{x_{B}^{-1}x_{B}^{k}r_{B}}$	$g^{x_A^k{r}_A{x}_B^k{r}_B}$$g^{x_{A}^{k}r_{A}x_{B}^{k}r_{B}}$

1. Протоколы MTI/A и MTI/B требуют от каждого пользователя вычисления трех экспонент, тогда как протоколы MTI/C требуют вычисления только двух экспонент. Протокол MTI/C(1) имеет также дополнительное преимущество, состоящее в том, что не требуется вычислять обратные элементы для $x_A$$x_{A}$  и $x_B$$x_B$ . С другой стороны эти значения не меняются в течение всего сеанса связи и поэтому могут быть рассчитаны заранее.
2. Все стороны в протоколах MTI проводят аналогичные операции, причем работа протоколов не зависит от того, в каком порядке посылаются сообщения от одной стороны к другой.
3. Протоколы MTI/B и MTI/C требуют знания открытых ключей других сторон, для чего может потребоваться дополнительным обмен сообщениями (если информация об открытых ключах не помещается в отправляемых по сети сообщениях). Протоколы MTI/A знания открытых ключей не требуют, что позволяет избежать дополнительных передач и временных задержек.
4. Все три класса протоколов обеспечивают взаимную неявную аутентификацию ключей (mutual implicit key authentication), но не обеспечивают подтверждения правильности ключей (key confirmation) и аутентификацию сторон (entitiy authentication).

Сравнение протоколов распределения ключей

Протокол	Аутентификация ключа	Аутентификация источников	Подтверждение ключа	Число сообщений
протокол Диффи-Хеллмана	отсутствует	отсутствует	отсутствует	2
протокол Эль-Гамаля	односторонняя	отсутствует	отсутствует	1
MTI/A	взаимная неявная	отсутствует	отсутствует	2
MTI/B,C	взаимная неявная	отсутствует	отсутствует	2
STS	взаимная явная	взаимная	отсутствует	3

Атаки на протоколы MTIПравить

Протоколы MTI противостоят пассивным атакам, однако уязвимы для активных атак. Ниже представлены примеры активных атак на протоколы MTI.

Атака по малой подгруппе на протоколы MTI/CПравить

Атака по подгруппе (Small Subgroup Attack) применяется к классу протоколов MTI/C в том случае, если группа $G$$G$  совпадает с группой $Z_p^{\ast <!--\; \ast \; -->}$$Z_{p}^{*}$ , как и предполагается в оригинальном протоколе. Предполагается, что криптоаналитику $E$$E$  известно разложение числа $p-<!--\; -\; -->1$$p-1$  на простые множители. Пусть $s$$s$  — наименьший простой множитель в разложении числа $p-<!--\; -\; -->1$$p-1$ . Обозначим $w=(p-<!--\; -\; -->1)/s$$w=(p-1)/s$ . Атака заключается в возведении всех сообщений в степень $w$$w$ , что переводит передаваемые элементы в малую подгруппу $G^{\prime }$$G'$  группы $G$$G$ .

Действительно, $A$$A$  и $B$$B$  обмениваются сообщениями вида $g^r$$g^{r}$ . Возведение элемента $g^r$$g^{r}$  в степень $w$$w$ , дает порождающий элемент $g^{wr}$$g^{wr}$  подгруппы $G^{\prime }$$G'$  порядка $\frac{p-<!--\; -\; -->1}{(wr,p-<!--\; -\; -->1)}$${\frac {p-1}{(wr,p-1)}}$ . При этом этот порядок равен $1$$1$  либо когда $s=1$$s = 1$  и, соответственно, $w=p-<!--\; -\; -->1$$w=p-1$ , либо когда $r$$r$  в своем разложении на простые множители содержит число $s$$s$ , т.е. $(r,s)=s$$(r,s)=s$ . Во всех остальных случаях порядок подгруппы $G^{\prime }$$G'$  будет равен $s$$s$ .

Ниже описан процесс атаки на протокол MTI/C(0). Криптоаналитик $E$$E$  находится между сторонами $A$$A$  и $B$$B$  (man-in-the-middle).

1. Сторона $A$$A$  выбирает случайное число $r_A{\in <!--\; \in \; -->}_R{Z}_q^{\ast <!--\; \ast \; -->}$$r_{A}\in _{R}Z_{q}^{*}$  и отправляет $B$$B$  сообщение $m_A=y_B^{r_A}$$m_{A}=y_{B}^{r_{A}}$ 
2. Криптоаналитик $E$$E$  перехватывает сообщение от $A$$A$  и отправляет $B$$B$  сообщение $m_A^w=y_B^{r_{A}w}$$m_{A}^{w}=y_{B}^{r_{A}w}$ 
3. Сторона $B$$B$  выбирает случайное число $r_B{\in <!--\; \in \; -->}_R{Z}_q^{\ast <!--\; \ast \; -->}$$r_{B}\in _{R}Z_{q}^{*}$  и отправляет $A$$A$  сообщение $m_B=y_A^{r_B}$$m_{B}=y_{A}^{r_{B}}$ 
4. Криптоаналитик $E$$E$  перехватывает сообщение от $B$$B$  и отправляет $A$$A$  сообщение $m_B^w=y_A^{r_{B}w}$$m_{B}^{w}=y_{A}^{r_{B}w}$ 
5. Сторона $A$$A$  вычисляет сеансовый ключ: $K_{AB}=m_B^{x_A^{-<!--\; -\; -->1}{r}_A}=g^{r_A{r}_{B}w}$$K_{AB}=m_{B}^{x_{A}^{-1}r_{A}}=g^{r_{A}r_{B}w}$ 
6. Сторона $B$$B$  вычисляет сеансовый ключ: $K_{AB}=m_A^{x_B^{-<!--\; -\; -->1}{r}_B}=g^{r_A{r}_{B}w}$$K_{AB}=m_{A}^{x_{B}^{-1}r_{B}}=g^{r_{A}r_{B}w}$ 

Полученный секретный сеансовый ключ $K_{AB}$$K_{AB}$ , как и полученные сообщения, является элементом малой подгруппы $G^{\prime }$$G'$  группы $G$$G$ . Поэтому криптоаналитик $E$$E$  может найти ключ $K_{AB}$$K_{AB}$  полным перебором, проверяя элементы подгруппы $G^{\prime }$$G'$  в качестве ключей в общении между $A$$A$  и $B$$B$ . При этом чем меньше множитель $s$$s$ , тем быстрее проходит атака.

Атака на подгруппу может быть предотвращена путём выбора подгруппы $G$$G$  группы $Z_p^{\ast <!--\; \ast \; -->}$$Z_{p}^{*}$  простого порядка $q$$q$ . Т.к. при этом длина $q$$q$  составляет порядка 160 бит, то полный перебор оказывается слишком сложной задачей для криптоаналитика $E$$E$ . Так же необходимо проверять, что полученные в сообщениях элементы лежат в группе $G$$G$  и не равны единице.

Атака с неизвестным общим ключомПравить

Атака с неизвестным общим ключом требуют от криптоаналитика $E$$E$  получить сертификат на долговременный открытый ключ $y_E$$y_{E}$ , который связан с открытым ключом стороны $A$$A$  по формуле $:<!--\; :\; -->y_E=y_A^{x_E}=g^{x_A{x}_E}$$\colon y_{E}=y_{A}^{x_{E}}=g^{x_{A}x_{E}}$ . Это значит, что $E$$E$  не знает секретный ключ $x_A{x}_E$$x_{A}x_{E}$ , соответствующий открытому ключу $y_E$$y_{E}$ .

Атака с неизвестным общим ключом осуществляется путём выполнения следующей последовательности действий.

1. Сторона $A$$A$  выбирает случайное число $r_A{\in <!--\; \in \; -->}_R{Z}_q^{\ast <!--\; \ast \; -->}$$r_{A}\in _{R}Z_{q}^{*}$  и отправляет $B$$B$  сообщение $m_A=y_B^{r_A}$$m_{A}=y_{B}^{r_{A}}$ 
2. Криптоаналитик $E$$E$  передает сообщение $y_B^{r_A}$$y_{B}^{r_{A}}$  от $A$$A$  к $B$$B$  в неизменном виде.
3. Сторона $B$$B$  выбирает случайное число $r_B{\in <!--\; \in \; -->}_R{Z}_q^{\ast <!--\; \ast \; -->}$$r_{B}\in _{R}Z_{q}^{*}$  и отправляет $E$$E$  сообщение $y_E^{r_B}$$y_{E}^{r_{B}}$ 
4. Криптоаналитик $E$$E$  получает сообщение от $B$$B$  и отправляет $A$$A$  сообщение $y_E^{r_B{x}_E^{-<!--\; -\; -->1}}$$y_{E}^{r_{B}x_{E}^{-1}}$ 
5. Сторона $A$$A$  вычисляет сеансовый ключ: $K_{AB}=(y_E^{r_B{x}_E^{-<!--\; -\; -->1}}{)}^{x_A^{-<!--\; -\; -->1}}{g}^{r_A}=g^{r_A+r_B}$$K_{AB}=(y_{E}^{r_{B}x_{E}^{-1}})^{x_{A}^{-1}}g^{r_{A}}=g^{r_{A}+r_{B}}$ 
6. Сторона $B$$B$  вычисляет сеансовый ключ: $K_{AB}=(y_B^{r_A}{)}^{{x_B}^{-<!--\; -\; -->1}}{g}^{r_A}=g^{r_A+r_B}$$K_{AB}=(y_{B}^{r_{A}})^{{x_{B}}^{-1}}g^{r_{A}}=g^{r_{A}+r_{B}}$ 

Секретные ключи, вычисленные сторонами $A$$A$  и $B$$B$ , одинаковы и равны $g^{r_A+r_B}$$g^{r_{A}+r_{B}}$ . При этом $A$$A$  считает, что разделяет его с $B$$B$ , в то время как $B$$B$  считает, что разделяет ключ с $E$$E$ .

Несмотря на то, что $E$$E$  не в состоянии вычислить секретный сеансовый ключ $K_{AB}$$K_{AB}$  без дополнительной информации, сторона $E$$E$  тем не менее приводит $B$$B$  к ошибочному мнению.

Чтобы избежать данной атаки, необходимо потребовать от сертификационных центров проводить проверку того, что стороны, запрашивающие сертификат на некоторый открытый ключ $y_E$$y_{E}$ , знают соответствующий закрытый ключ $x_E$$x_{E}$ .

ЛитератураПравить

• Diffie W., Hellman M. E. New Directions in Cryptography (англ.) // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1976.1055638
• Gardner M. A New Kind of Cipher that Would Take Millions of Years to Break (англ.) // Sci. Amer. — NYC: NPG, 1977. — Vol. 237, Iss. 2. — P. 120—124. — 5 p. — ISSN 0036-8733; 1946-7087 — doi:10.1038/SCIENTIFICAMERICAN0877-120
• Elgamal T. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (англ.) // IEEE Trans. Inf. Theory / F. Kschischang — IEEE, 1985. — Vol. 31, Iss. 4. — P. 469—472. — ISSN 0018-9448; 1557-9654 — doi:10.1109/TIT.1985.1057074; doi:10.1007/3-540-39568-7_2
• Matsumoto T., Takashima Y., Imai H. On Seeking Smart Public-key Distribution Systems (англ.) // Transactions of the Institute of Electronics and Communication Engineers of Japan. Section E — Elsevier BV, 1986. — Vol. 69, Iss. 2. — P. 99—106. — ISSN 0387-236X
• Boyd C., Mathuria A. 5.3 MTI Protocols // Protocols for Authentication and Key Establishment (англ.) — Springer Science+Business Media, 2003. — P. 147—155. — 321 p. — (Information Security and Cryptography) — ISBN 978-3-540-43107-7 — ISSN 1619-7100; 2197-845X — doi:10.1007/978-3-662-09527-0
• Черемушкин А. В. Криптографические протоколы: основные свойства и уязвимости // Прикладная дискретная математика : Приложение. — 2009. — № 2. — С. 115-150. Архивировано 3 ноября 2013 года.
• Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Глава 15. Протоколы распределения ключей // Основы криптографии: Учебное пособие — 2-е изд., испр. и доп. — М.: Гелиос АРВ, 2002. — С. 378, 387—396. — ISBN 978-5-85438-137-6
• Ratna Dutta, Rana Barua. Overview of Key Agreement Protocols. — С. 9-10. (недоступная ссылка)
• Sebastien Kunz-Jacques, David Pointcheval. About the Security of MTI/C0 and MQV. — 2006.
• Menezes A. J., Oorschot P. v., Vanstone S. A. 12.6.1 Diffie-Hellman and related key agreement protocols // Handbook of Applied Cryptography (англ.) — CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0