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

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

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

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

Протокол использует функцию шифрования $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)$.

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

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

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

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$ совершаются Бобом, то есть одной стороне обмена не нужно знать ключи другой.

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

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

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

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

Шаблон:CatmainКриптосистема Мэсси — Омуры была предложена Джеймсом Мэсси и Шаблон:Iw в 1982 как улучшение протокола ШамираШаблон:Sfn. Метод Мэсси — Омуры использует возведение в степень в поле Галуа $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{mod2}^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$ умножениями. Более того, несколько умножений могут выполняться параллельно. Это позволяет иметь более быстрые реализации в железе за счёт использования несколько умножителейШаблон:Sfn.

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

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

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:US patent, U.S. patent on the Massey-Omura cryptosystem
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга