Протоколы MTI

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

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

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

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

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


История

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

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

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

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

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

Описание протоколов MTI[1]

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

[math]\displaystyle{ p }[/math] большое простое число (не менее 1024 бит).
[math]\displaystyle{ q }[/math] простое число (порядка 160 бит), являющееся делителем числа [math]\displaystyle{ p-1 }[/math].
[math]\displaystyle{ G }[/math] подгруппа группы [math]\displaystyle{ \Z_p^{*} }[/math] (обычно порядка [math]\displaystyle{ q }[/math], но иногда совпадает с [math]\displaystyle{ \Z_p^{*} }[/math])
[math]\displaystyle{ g }[/math] порождающий элемент подгруппы [math]\displaystyle{ G }[/math]
[math]\displaystyle{ a }[/math], [math]\displaystyle{ b }[/math] закрытые ключи сторон A и B
[math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] открытые ключи сторон A и B : [math]\displaystyle{ A = g^{a}\ mod\ p }[/math], [math]\displaystyle{ \ B = g^{b}\ mod\ p }[/math].
[math]\displaystyle{ R_A }[/math], [math]\displaystyle{ R_B }[/math] случайные целые числа, обычно той же величины, что и порядок группы [math]\displaystyle{ G }[/math], выбираемые сторонами A и B соответственно
[math]\displaystyle{ M_A }[/math], [math]\displaystyle{ M_B }[/math] сообщения, отправляемые от A к B и от B к A соответственно.
[math]\displaystyle{ K }[/math] секретный сеансовый ключ, вычисленный сторонами A и B
[math]\displaystyle{ (a,b) }[/math] наибольший общий делитель чисел [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math]

Все вычисления в дальнейшем проводятся в группе [math]\displaystyle{ \Z_p^{*} }[/math].

MTI/A(0)[8]

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

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ R_A \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ M_A = g^{R_A} \bmod p }[/math]
  2. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ R_B \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ M_B = g^{R_B} \bmod p }[/math]
  3. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = B^{R_A} M_B^{a} \bmod p = g^{a R_B + b R_A} \bmod p }[/math]
  4. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = A^{R_B} M_A^{b} \bmod p = g^{a R_B + b R_A} \bmod p }[/math]

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

[math]\displaystyle{ A \colon K = B^{R_A} M_B^{a} \bmod p = (g^{b})^{R_A} (g^{R_B})^{a} \bmod p = g^{a R_B + b R_A} \bmod p }[/math]
[math]\displaystyle{ B \colon K = A^{R_B} M_A^{b} \bmod p = (g^{a})^{R_B} (g^{R_A})^{b} \bmod p = g^{a R_B + b R_A} \bmod p }[/math]

MTI/B(0)

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

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ R_A \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ M_A = B^{R_A} }[/math]
  2. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ R_B \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ M_B = A^{R_B} }[/math]
  3. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_B ^{{a}^{-1}}g^{R_A} \bmod p = g^{R_A+R_B} \bmod p }[/math]
  4. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_A ^{{b}^{-1}}g^{R_B} \bmod p = g^{R_A+R_B} \bmod p }[/math]

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

[math]\displaystyle{ 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 }[/math]
[math]\displaystyle{ 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 }[/math]

MTI/C(0)[8]

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

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ R_A \in \Z_q^* }[/math] и отправляет B сообщение [math]\displaystyle{ M_A = B ^{R_A} }[/math]
  2. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ R_B \in \Z_q^* }[/math] и отправляет A сообщение [math]\displaystyle{ M_B = A ^{R_B } }[/math]
  3. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_B ^{a ^{-1} R_A} \bmod p = g^{R_A R_B } \bmod p }[/math]
  4. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_A ^{b ^{-1} R_B } \bmod p = g^{R_A R_B } \bmod p }[/math]

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

[math]\displaystyle{ 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} }[/math]
[math]\displaystyle{ 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} }[/math]

MTI/A(k)

Алгоритм работы[источник не указан 1869 дней]

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ R_A \in \Z_q^* }[/math] и отправляет B сообщение [math]\displaystyle{ M_A = g^{a^k R_A} }[/math]
  2. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ R_B \in \Z_q^* }[/math] и отправляет A сообщение [math]\displaystyle{ M_B = g^{b^k R_B} }[/math]
  3. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = B^{a^k R_A} M_B^{a} = g^{b a^k R_A + a b^k R_B} }[/math]
  4. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = A^{b^k R_B} M_A^{b} = g^{a b^k R_B + b a^k R_A} }[/math]

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

[math]\displaystyle{ A \colon 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} }[/math]
[math]\displaystyle{ B \colon 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} }[/math]

MTI/B(k)

Алгоритм работы[источник не указан 1869 дней]

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ R_A \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ M_A = B^{a^k R_A} }[/math]
  2. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ R_B \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ M_B = A^{b^k R_B} }[/math]
  3. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_B^{a^{-1}}g^{a^k R_A} = g^{a^k R_A+b^k R_B} }[/math]
  4. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_A^{b^{-1}}g^{b^k R_B} = g^{a^k R_A+b^k R_B} }[/math]

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

[math]\displaystyle{ 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} }[/math]
[math]\displaystyle{ 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} }[/math]

MTI/C(k)

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

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ R_A \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ M_A = B^{a^k R_A} }[/math]
  2. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ R_B \in \Z_q^* }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ M_B = A^{b^k R_B} }[/math]
  3. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_B^{a^{-1}a^k R_A} = g^{a^k R_Ab^k R_B} }[/math]
  4. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K = M_A^{b^{-1}b^k R_B} = g^{a^k R_Ab^k R_B} }[/math]

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

[math]\displaystyle{ 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} }[/math]
[math]\displaystyle{ 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} }[/math]

Анализ протоколов MTI[3]

Таблица протоколов MTI
Протокол [math]\displaystyle{ m_A }[/math] [math]\displaystyle{ m_B }[/math] [math]\displaystyle{ K_A }[/math] [math]\displaystyle{ K_B }[/math] [math]\displaystyle{ K_{AB} }[/math]
MTI/A(0) [math]\displaystyle{ g^{r_A} }[/math] [math]\displaystyle{ g^{r_B} }[/math] [math]\displaystyle{ y_B^{r_A} m_B^{x_A} }[/math] [math]\displaystyle{ y_A^{r_B} m_A^{x_B} }[/math] [math]\displaystyle{ g^{x_A r_B + x_B r_A} }[/math]
MTI/B(0) [math]\displaystyle{ y_B^{r_A} }[/math] [math]\displaystyle{ y_A^{r_B} }[/math] [math]\displaystyle{ m_B^{x_A^{-1}}g^{r_A} }[/math] [math]\displaystyle{ m_A^{x_B^{-1}}g^{r_B} }[/math] [math]\displaystyle{ g^{r_A+r_B} }[/math]
MTI/C(0) [math]\displaystyle{ y_B^{r_A} }[/math] [math]\displaystyle{ y_A^{r_B} }[/math] [math]\displaystyle{ m_B^{x_A^{-1} r_A} }[/math] [math]\displaystyle{ m_A^{x_B^{-1} r_B} }[/math] [math]\displaystyle{ g^{r_A r_B} }[/math]
MTI/A(k) [math]\displaystyle{ g^{x_A^k r_A} }[/math] [math]\displaystyle{ g^{x_B^k r_B} }[/math] [math]\displaystyle{ y_B^{x_A^k r_A}m_B^{x_A} }[/math] [math]\displaystyle{ y_A^{x_B^k r_B}m_A^{x_B} }[/math] [math]\displaystyle{ g^{x_A x_B^k r_B + x_B x_A^k r_A} }[/math]
MTI/B(k) [math]\displaystyle{ y_B^{x_A^k r_A} }[/math] [math]\displaystyle{ y_A^{x_B^k r_B} }[/math] [math]\displaystyle{ m_B^{x_A^{-1}}g^{x_A^k r_A} }[/math] [math]\displaystyle{ m_A^{x_B^{-1}}g^{x_B^k r_B} }[/math] [math]\displaystyle{ g^{x_A^k r_A+x_B^k r_B} }[/math]
MTI/C(k) [math]\displaystyle{ y_B^{x_A^k r_A} }[/math] [math]\displaystyle{ y_A^{x_B^k r_B} }[/math] [math]\displaystyle{ m_B^{x_A^{-1}x_A^k r_A} }[/math] [math]\displaystyle{ m_A^{x_B^{-1}x_B^k r_B} }[/math] [math]\displaystyle{ g^{x_A^k r_Ax_B^k r_B} }[/math]
  1. Протоколы MTI/A и MTI/B требуют от каждого пользователя вычисления трех экспонент, тогда как протоколы MTI/C требуют вычисления только двух экспонент. Протокол MTI/C(1) имеет также дополнительное преимущество, состоящее в том, что не требуется вычислять обратные элементы для [math]\displaystyle{ x_A }[/math] и [math]\displaystyle{ x_B }[/math]. С другой стороны эти значения не меняются в течение всего сеанса связи и поэтому могут быть рассчитаны заранее.
  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 противостоят пассивным атакам, однако уязвимы для активных атак[3]. Ниже представлены примеры активных атак на протоколы MTI.

Атака по малой подгруппе на протоколы MTI/C[1]

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

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

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

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ r_A \in_R Z_q^* }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ m_A = y_B ^ { r_A } }[/math]
  2. Криптоаналитик [math]\displaystyle{ E }[/math] перехватывает сообщение от [math]\displaystyle{ A }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ m_A ^ w = y_B ^ { r_A w } }[/math]
  3. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ r_B \in_R Z_q^* }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ m_B = y_A ^ { r_B } }[/math]
  4. Криптоаналитик [math]\displaystyle{ E }[/math] перехватывает сообщение от [math]\displaystyle{ B }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ m_B ^ w = y_A ^{ r_B w } }[/math]
  5. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K_{AB} = m_B^{x_A^{-1} r_A} = g^{r_A r_B w} }[/math]
  6. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K_{AB} = m_A^{x_B^{-1} r_B} = g^{r_A r_B w} }[/math]

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

Атака на подгруппу может быть предотвращена путём выбора подгруппы [math]\displaystyle{ G }[/math] группы [math]\displaystyle{ Z_p^* }[/math] простого порядка [math]\displaystyle{ q }[/math]. Т.к. при этом длина [math]\displaystyle{ q }[/math] составляет порядка 160 бит, то полный перебор оказывается слишком сложной задачей для криптоаналитика [math]\displaystyle{ E }[/math]. Так же необходимо проверять, что полученные в сообщениях элементы лежат в группе [math]\displaystyle{ G }[/math] и не равны единице.

Атака с неизвестным общим ключом[1][3][9]

Атака с неизвестным общим ключом требуют от криптоаналитика [math]\displaystyle{ E }[/math] получить сертификат на долговременный открытый ключ [math]\displaystyle{ y_E }[/math], который связан с открытым ключом стороны [math]\displaystyle{ A }[/math] по формуле [math]\displaystyle{ \colon y_E = y_A^{x_E} = g^{x_A x_E} }[/math]. Это значит, что [math]\displaystyle{ E }[/math] не знает секретный ключ [math]\displaystyle{ x_A x_E }[/math], соответствующий открытому ключу [math]\displaystyle{ y_E }[/math].

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

  1. Сторона [math]\displaystyle{ A }[/math] выбирает случайное число [math]\displaystyle{ r_A \in_R Z_q^* }[/math] и отправляет [math]\displaystyle{ B }[/math] сообщение [math]\displaystyle{ m_A = y_B^{r_A} }[/math]
  2. Криптоаналитик [math]\displaystyle{ E }[/math] передает сообщение [math]\displaystyle{ y_B^{r_A} }[/math] от [math]\displaystyle{ A }[/math] к [math]\displaystyle{ B }[/math] в неизменном виде.
  3. Сторона [math]\displaystyle{ B }[/math] выбирает случайное число [math]\displaystyle{ r_B \in_R Z_q^* }[/math] и отправляет [math]\displaystyle{ E }[/math] сообщение [math]\displaystyle{ y_E^{r_B} }[/math]
  4. Криптоаналитик [math]\displaystyle{ E }[/math] получает сообщение от [math]\displaystyle{ B }[/math] и отправляет [math]\displaystyle{ A }[/math] сообщение [math]\displaystyle{ y_E^{r_B x_E^{-1}} }[/math]
  5. Сторона [math]\displaystyle{ A }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K_{AB} = (y_E^{r_B x_E^{-1}})^{x_A ^{-1}}g^{r_A } = g^{r_A +r_B} }[/math]
  6. Сторона [math]\displaystyle{ B }[/math] вычисляет сеансовый ключ: [math]\displaystyle{ K_{AB} = (y_B^{r_A})^{{x_B}^{-1}}g^{r_A} = g^{r_A +r_B} }[/math]

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

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

Чтобы избежать данной атаки, необходимо потребовать от сертификационных центров проводить проверку того, что стороны, запрашивающие сертификат на некоторый открытый ключ [math]\displaystyle{ y_E }[/math], знают соответствующий закрытый ключ [math]\displaystyle{ x_E }[/math].

Примечания

  1. ↑ 1,0 1,1 1,2 1,3 1,4 Boyd, Mathuria, 2003, pp. 147-155.
  2. ↑ 2,0 2,1 Алферов, Зубов, Кузьмин и др., 2002, с. 378, 387–396.
  3. ↑ 3,0 3,1 3,2 3,3 Menezes, Oorschot, Vanstone, 1996, 515-519.
  4. ↑ Diffie, Hellman, 1976.
  5. ↑ Gardner, 1977.
  6. ↑ Elgamal, 1985.
  7. ↑ Matsumoto, Takashima, Imai, 1986.
  8. ↑ 8,0 8,1 Ratna Dutta, Rana Barua. Overview of Key Agreement Protocols. — С. 9-10.
  9. ↑ Черемушкин А. В. Криптографические протоколы: основные свойства и уязвимости // Прикладная дискретная математика : Приложение. — 2009. — № 2. — С. 115-150. Архивировано 3 ноября 2013 года.

Литература

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Протоколы_MTI&oldid=5857312