Трёхэтапный протокол

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

Трёхэта́пный протоко́л (англ. three-pass protocol) — криптографический протокол, который позволяет защищённо передать сообщение между двумя сторонами без необходимости обмена или распределения ни открытого, ни закрытого ключа. Этот протокол предполагает использование коммутативного шифра[1].

Основные сведения

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

Протокол использует функцию шифрования [math]\displaystyle{ E }[/math] и функцию расшифрования [math]\displaystyle{ D }[/math]. Иногда функция шифрования и расшифрования могут быть одной и той же. Функция шифрования использует ключ шифрования [math]\displaystyle{ e }[/math], чтобы изменить открытое сообщение [math]\displaystyle{ m }[/math] в зашифрованное, или шифротекст, [math]\displaystyle{ E(e, m) }[/math]. Для каждого ключа шифрования [math]\displaystyle{ e }[/math] имеется соответствующий ключ дешифрования [math]\displaystyle{ d }[/math], который позволяет восстановить исходный текст с помощью функции расшифрования, [math]\displaystyle{ D(d, E(e, m)) = m }[/math].

Для того, чтобы функции шифрования [math]\displaystyle{ E }[/math] и расшифрования [math]\displaystyle{ D }[/math] подходили для трёхэтапного протокола, для любого сообщения [math]\displaystyle{ m }[/math], любого ключа шифрования [math]\displaystyle{ e }[/math] с соответствующим ему ключом дешифрирования [math]\displaystyle{ k }[/math] должно выполняется [math]\displaystyle{ D(d, E(k, E(e, m))) = E(k, m) }[/math]. Другими словами должно расшифровываться первое шифрование с ключом [math]\displaystyle{ e }[/math], даже если сообщение зашифровано вторым ключом [math]\displaystyle{ k }[/math]. Такое свойство есть у коммутативного шифрования. Коммутативное шифрование — это шифрование, которое не зависит от порядка, то есть справедливо [math]\displaystyle{ E(a, E(b, m)) = E(b, E(a, m)) }[/math] для любых ключей [math]\displaystyle{ a }[/math] и [math]\displaystyle{ b }[/math] для всех сообщений [math]\displaystyle{ m }[/math]. Для коммутативного шифрование выполняется [math]\displaystyle{ D(d, E(k, E(e, m))) = D(d, E(e, E(k, m))) = E(k, m) }[/math].

Описание алгоритма

Схема трёхэтапного протокола

Предположим, Алиса хочет послать Бобу сообщение. Тогда трёхэтапный протокол работает следующим образом[1]:

  1. Алиса выбирает закрытый ключ шифрования [math]\displaystyle{ s }[/math] и соответствующий ключ расшифрования [math]\displaystyle{ t }[/math]. Алиса шифрует исходное сообщение [math]\displaystyle{ m }[/math] с помощью ключа [math]\displaystyle{ s }[/math] и отправляет шифротекст [math]\displaystyle{ E(s, m) }[/math] Бобу.
  2. Боб выбирает закрытый ключ шифрования [math]\displaystyle{ r }[/math] и соответствующий ключ расшифрования [math]\displaystyle{ q }[/math], а затем повторно шифрует первое сообщение [math]\displaystyle{ E(s, m) }[/math] с помощью ключа [math]\displaystyle{ r }[/math] и отправляет дважды зашифрованное сообщение [math]\displaystyle{ E(r, E(s, m)) }[/math] обратно Алисе.
  3. Алиса расшифровывает второе сообщение с помощью ключа [math]\displaystyle{ t }[/math]. Из-за коммутативности, описанной выше, получаем [math]\displaystyle{ D(t, E(r, E(s, m))) = E(r, m) }[/math], то есть сообщение, зашифрованное только закрытым ключом Боба. Алиса пересылает этот шифротекст Бобу.
  4. Боб расшифровывает третье сообщение с помощью ключа [math]\displaystyle{ q }[/math] и получает [math]\displaystyle{ D(q, E(r, m)) = m }[/math] исходное сообщение.

Стоит заметить, что все операции с использованием закрытых ключей Алисы [math]\displaystyle{ s }[/math] и [math]\displaystyle{ t }[/math] совершаются Алисой, а все операции с использованием закрытых ключей Боба [math]\displaystyle{ r }[/math] и [math]\displaystyle{ q }[/math] совершаются Бобом, то есть одной стороне обмена не нужно знать ключи другой.

Трёхэтапный протокол Шамира

Первым трёхэтапным протоколом был трёхэтапный протокол Шамира[2], разработанный в 1980-х годах. Так же этот протокол называют бесключевым протоколом Шамира (англ. Shamir No-Key Protocol), потому что по этому протоколу не происходит обмена каких-либо ключей, но стороны обмена должны иметь по 2 закрытых ключа для шифрования и расшифрования. Алгоритм Шамира использует возведение в степень по модулю большого простого числа как функцию и шифрования, и расшифрования, то есть [math]\displaystyle{ E(e, m) = m^e \bmod p }[/math] и [math]\displaystyle{ D(d, m) = m^d \bmod p }[/math], где [math]\displaystyle{ p }[/math] — большое простое число[4]. Для любого шифрования показатель степени [math]\displaystyle{ e }[/math] находится в отрезке [math]\displaystyle{ 1..p-1 }[/math] и для него справедливо [math]\displaystyle{ \text{НОД}(e, p-1) = 1 }[/math]. Соответствующий показатель для расшифрования [math]\displaystyle{ d }[/math] выбирается так, чтобы [math]\displaystyle{ {de}\bmod p-1 = 1 }[/math]. Из малой теоремы Ферма следует, что [math]\displaystyle{ D(d, E(e, m)) = m^{de}\bmod p = m }[/math].

Протокол Шамира обладает коммутативностью, так как [math]\displaystyle{ E(a, E(b, m)) = m^{ab}\bmod p = m^{ba}\bmod p = E(b, E(a, m)) }[/math].

Криптосистема Мэсси — Омуры

Криптосистема Мэсси — Омуры была предложена Джеймсом Мэсси и Джимом Омурой (англ. Jim K. Omura) в 1982 как улучшение протокола Шамира[5][6]. Метод Мэсси — Омуры использует возведение в степень в поле Галуа [math]\displaystyle{ GF(2^n) }[/math] как функцию и шифрования, и расшифрования, то есть [math]\displaystyle{ E(e, m) = m^e }[/math] и [math]\displaystyle{ D(d, m) = m^d }[/math], где вычисления проходят в поле Галуа. Для любого шифрования показатель степени [math]\displaystyle{ e }[/math] находится в отрезке [math]\displaystyle{ 1..{{2^n}-1} }[/math] и для него справедливо [math]\displaystyle{ \text{НОД}(e, 2^n-1) = 1 }[/math]. Соответствующий показатель для расшифрования [math]\displaystyle{ d }[/math] выбирается так, чтобы [math]\displaystyle{ de \bmod 2^n-1 = 1 }[/math]. Так как мультипликативная группа поля Галуа [math]\displaystyle{ GF(2^n) }[/math] имеет порядок [math]\displaystyle{ 2^n-1 }[/math], то из теоремы Лагранжа следует, что [math]\displaystyle{ D(d, E(e, m)) = m^{de} = m }[/math] для всех [math]\displaystyle{ m }[/math] в [math]\displaystyle{ GF(2^n)^* }[/math].

Каждый элемент поля Галуа [math]\displaystyle{ GF(2^n) }[/math] представлен как двоичный вектор нормального базиса, где каждый базисный вектор является квадратом предыдущего. То есть базисные вектора [math]\displaystyle{ v^1, v^2, v^4, v^8, \dots }[/math] где [math]\displaystyle{ v }[/math] — элемент поля с максимальным порядком. Используя данное представление, возведение в степень 2 можно производить с помощью циклического сдвига. Это значит, что возведение [math]\displaystyle{ m }[/math] в произвольную степень может быть выполнено с не более чем [math]\displaystyle{ n }[/math] сдвигами и [math]\displaystyle{ n }[/math] умножениями. Более того, несколько умножений могут выполняться параллельно. Это позволяет иметь более быстрые реализации в железе за счёт использования несколько умножителей[7].

Безопасность

Необходимое условие для безопасности трёхэтапного протокола состоит в том, чтобы злоумышленник не смог определить ничего об исходном сообщении [math]\displaystyle{ m }[/math] из трёх пересланных сообщений [math]\displaystyle{ E(s, m), E(r, E(s, m)), E(r, m) }[/math][8]. Это условие накладывает ограничение на выбор функций шифрования и расшифрования. Например коммутативная функция xor [math]\displaystyle{ E(s, m) = m \oplus s }[/math] не может использоваться в трёхэтапном протоколе, так как [math]\displaystyle{ (m \oplus s) \oplus (m \oplus s \oplus r) \oplus (m \oplus r) = m }[/math]. То есть, зная три пересланные сообщения, можно восстановить исходное сообщение[9].

Криптографическая стойкость

Для функций шифрования, используемых в алгоритме Шамира и алгоритме Мэсси — Омуры, безопасность зависит от сложности вычисления дискретных логарифмов в конечном поле. Если злоумышленник может вычислить дискретные логарифмы в [math]\displaystyle{ GF(p) }[/math] для метода Шамира или [math]\displaystyle{ GF(2^n) }[/math] для метода Масси-Омура, то протокол может быть нарушен. Ключ [math]\displaystyle{ s }[/math] может быть вычислен из сообщений [math]\displaystyle{ m^r }[/math] и [math]\displaystyle{ m^{rs} }[/math]. Когда [math]\displaystyle{ s }[/math] известно, легко вычислить степень для расшифровки [math]\displaystyle{ t }[/math]. Затем злоумышленник может вычислить [math]\displaystyle{ m }[/math], возведя перехваченное сообщение [math]\displaystyle{ m^s }[/math] в степень [math]\displaystyle{ t }[/math]. В 1998 году показано, что при определённых предположениях взлом криптосистемы Мэсси — Омуры эквивалентен взлому криптосистемы Диффи — Хеллмана[10].

Аутентификация

Трёхэтапный протокол не предусматривает аутентификацию сторон обмена[11]. Поэтому без реализации сторонней аутентификации протокол уязвим для атаки посредника. Это значит, что если злоумышленник имеет возможность создавать ложные сообщения или перехватывать и заменять настоящие переданные сообщения, то обмен скомпрометирован.

Примечания

  1. ↑ 1,0 1,1 B. Schneier, 1996.
  2. ↑ 2,0 2,1 A.G. Konheim, 1981, с. 345.
  3. ↑ A. Menezes, P. van Oorschot, S. Vanstone, 1996, с. 535.
  4. ↑ A. Menezes, P. van Oorschot, S. Vanstone, 1996, с. 500.
  5. ↑ Patent, US4567600.
  6. ↑ A. Menezes, P. van Oorschot, S. Vanstone, 1996, с. 642.
  7. ↑ Лидл, Нидеррайтер, 1998, с. 601.
  8. ↑ A. G. Reinhold, 1991, с. 3—5.
  9. ↑ Yoshito Kanamori, Seong-Moo Yoo, 2009, с. 65—66.
  10. ↑ Sakurai, K.; Shizuya, H., 1998, pp. 29—43.
  11. ↑ A.G. Konheim, 1981, с. 346—7.

Литература

  • B. Schneier. Applied Cryptography: "Protocols, algorithms, and source codes in C". — 2nd Edition. — New York: John Wiley & Sons, 1996.
  • Лидл Р., Нидеррайтер Г. Конечные поля. В 2-х тт. — Москва: Мир, 1998. — 430 с. — ISBN 5-03-000065-8.
  • Sakurai, K.; Shizuya, H. A structural comparison of the computational difficulty of breaking discrete log cryptosystems (англ.) // Journal of Cryptology : Article. — 1998. — No. 11. — P. 29—43. — ISSN 09332790.
  • A. G. Reinhold. Strong Cryptography — The Global Tide of Change (англ.) // Cato Institute : Article. — 1991. — No. 51. — P. 3—5.
  • U.S. Patent 4 567 600, U.S. patent on the Massey-Omura cryptosystem
  • A.G. Konheim. Cryptography. — New York: John Wiley & Sons, 1981. — С. 345—7.
  • Yoshito Kanamori, Seong-Moo Yoo. Quantum three-pass protocol: Key distribution using quantum superposition states (англ.) // International Journal of Network Security & Its Applications (IJNSA) : Article. — 2009. — No. 2. — P. 65—66.
  • A. Menezes, P. van Oorschot, S. Vanstone. Handbook of Applied Cryptography. — 5th printing. — CRC Press, 1996. — С. 500, 535, 642. — 816 с. — ISBN 0-8493-8523-7.


Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Трёхэтапный_протокол&oldid=5861396