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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Криптосистема Мэсси — Омуры

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

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

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

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

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

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

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

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

Литература

• 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.