Трехпроходной протокол

В криптографии трехпроходной протокол для отправки сообщений представляет собой структуру, которая позволяет одной стороне безопасно отправлять сообщение второй стороне без необходимости обмениваться или распространять ключи шифрования . Такие протоколы сообщений не следует путать с различными другими алгоритмами, использующими 3 прохода для аутентификации .

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

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

Чтобы функция шифрования и функция дешифрования были пригодны для трехпроходного протокола, они должны обладать свойством, что для любого сообщения m любой ключ шифрования e с соответствующим ключом дешифрования d и любой независимый ключ шифрования 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)))$ ⁠ .

Трехпроходной протокол работает следующим образом:

Отправитель выбирает закрытый ключ шифрования s и соответствующий ключ дешифрования t . Отправитель шифрует сообщение m ключом s и отправляет зашифрованное сообщение ⁠ $E(s,m)$ ⁠ получателю.
Получатель выбирает закрытый ключ шифрования r и соответствующий ключ дешифрования q и супершифрует первое сообщение ⁠ $E(s,m)$ ⁠ с ключом r и отправляет дважды зашифрованное сообщение ⁠ $E(r,E(s,m))$ ⁠ обратно отправителю.
Отправитель расшифровывает второе сообщение ключом t . Из-за описанного выше свойства коммутативности ⁠ $D(t,E(r,E(s,m)))=E(r,m)$ ⁠ — сообщение, зашифрованное только с помощью закрытого ключа получателя. Отправитель отправляет это получателю.

Теперь получатель может расшифровать сообщение, используя ключ q , а именно ⁠ $D(q,E(r,m))=m$ ⁠ исходное сообщение.

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

Трехпроходной протокол Шамира

Первым трехпроходным протоколом был трехпроходный протокол Шамира , разработанный примерно в 1980 году. Его также называют протоколом Шамира без ключа , поскольку отправитель и получатель не обмениваются ключами, однако протокол требует, чтобы отправитель и получатель имели два закрытых ключа для шифрования и дешифрования сообщений. Алгоритм Шамира использует возведение в степень по модулю большого простого числа в качестве функций шифрования и дешифрования. То есть E ( e , m ) = m ^и mod p и D ( d , м ) знак равно м ^д mod p , где p — большое простое число. Для любого показателя шифрования e в диапазоне 1.. p -1 с НОД( e , p -1) = 1. Соответствующий показатель дешифрования d выбирается такой, что de ≡ 1 (mod p -1). следует Из Малой теоремы Ферма , что D ( d , E ( e , m )) = m ^из мод п = м .

Протокол Шамира обладает желаемым свойством коммутативности, поскольку E ( a , E ( b , m )) = m ^аб мод р = м ^нет mod p знак равно E ( б , E ( а , м )).

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

Криптосистема Мэсси-Омуры была предложена Джеймсом Мэсси и Джимом К. Омурой в 1982 году как возможное улучшение протокола Шамира. Метод Мэсси–Омуры использует возведение в степень в поле Галуа GF(2 ^н) как функции шифрования и дешифрования. То есть E ( e,m )= m ^и и D ( d,m )= m ^д где расчеты проводятся в поле Галуа. Для любого показателя шифрования e с 0 < e <2 ^н-1 и НОД( e ,2 ^н-1)=1 соответствующий показатель дешифрования равен d такой, что de ≡ 1 (mod 2 ^н-1). Поскольку мультипликативная группа поля Галуа GF(2 ^н) имеет порядок 2 ^н-1 Из теоремы Лагранжа следует, что m ^из= m для всех m в GF(2 ^н) ^* .

Каждый элемент поля Галуа GF(2 ^н) представляется как двоичный вектор по нормальному базису , в котором каждый базисный вектор является квадратом предыдущего. То есть базисные векторы v ¹, v ², v ⁴, v ⁸, ... где v — элемент поля максимального порядка . Используя это представление, возведение в степень по степени 2 можно выполнить с помощью циклических сдвигов . Это означает, что возведение m в произвольную степень можно выполнить не более чем за n сдвигов и n умножений. Более того, несколько умножений можно выполнять параллельно. Это позволяет ускорить аппаратную реализацию за счет необходимости реализации нескольких умножителей.

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

Необходимым условием безопасности трехпроходного алгоритма является то, что злоумышленник не может определить какую-либо информацию о сообщении m из трех переданных сообщений ⁠ $E(s,m)$ ⁠ , ⁠ $E(r,E(s,m))$ ⁠ и ⁠ $E(r,m)$ ⁠ .

Для функций шифрования, используемых в алгоритме Шамира и алгоритме Мэсси-Омуры, описанном выше, безопасность зависит от сложности вычисления дискретных логарифмов в конечном поле. Если бы злоумышленник мог вычислить дискретные логарифмы в GF( p ) для метода Шамира или GF(2 ^н) для метода Мэсси-Омуры, то протокол может быть нарушен. Ключ s можно вычислить из сообщений m ^р и м ^РС. Зная s , легко вычислить показатель степени дешифрования t . Тогда злоумышленник сможет вычислить m, вызвав перехваченное сообщение m. ^с в степень t . К. Сакураи и Х. Шизуя показывают, что при определенных предположениях взлом криптосистемы Мэсси–Омуры эквивалентен предположению Диффи–Хеллмана .

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

Описанный выше трехпроходный протокол не обеспечивает никакой аутентификации . Следовательно, без какой-либо дополнительной аутентификации протокол подвержен атаке «человек посередине», если у противника есть возможность создавать ложные сообщения или перехватывать и заменять подлинные переданные сообщения.

Ссылки

Патент США 4 567 600 , патент США на криптосистему Мэсси – Омуры.
Конхейм, Алан Г. (1981). Криптография: учебник для начинающих . стр. 346–347.
Менезес, А.; ВанОоршот, П.; Ванстон, С. (1996). Справочник по прикладной криптографии . стр. 500, 642.
Сакурай, К.; Шизуя, Х. (1998). «Структурное сравнение вычислительной сложности взлома криптосистем с дискретным журналированием» . Журнал криптологии . 11 : 29–43. дои : 10.1007/s001459900033 .