Русская Википедия:Трёхэтапный протокол

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

Файл:Трёхэтапный протокол.png

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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