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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Криптосистемы с открытым ключом
Алгоритмы	Факторизация целых чисел Криптосистема Бенало Блюма — Гольдвассер Cayley–Purser Дамгорда — Юрика GMR Гольдвассер — Микали Накаша — Штерна Пэйе Рабина RSA Окамото — Утиямы Schmidt–Samoa Дискретное логарифмирование BLS Крамера – Шоупа Протокол Диффи — Хеллмана DSA ECDH Curve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Обмен зашифрованными ключами Схема Эль-Гамаля signature scheme MQV Схема Шнорра SPEKE SRP STS Криптография на решётках NTRUEncrypt NTRUSign Обмен ключами на основе обучения с ошибками Подпись на основе обучения с ошибками в кольце BLISS NewHope Другие AE CEILIDH EPOC Скрытые уравнения поля IES Подпись Лэмпорта McEliece Ранцевая криптосистема Меркла — Хеллмана Naccache–Stern knapsack cryptosystem Трёхэтапный протокол XTR
Теория	Дискретное логарифмирование на эллиптической кривой Эллиптическая криптография Hash-based cryptography Некоммутативная криптография RSA problem Односторонняя функция с потайным входом
Стандарты	CRYPTREC IEEE P1363 NESSIE NSA Suite B Post-Quantum Cryptography
Темы	Электронная подпись OAEP Fingerprint PKI Web of trust Размер ключа Identity-based cryptography Постквантовая криптография OpenPGP card