Шифр Шамира

Система Диффи-Хеллмана

Передача секретной информации по открытым каналам

Рассмотрим системы передачи секретной информации, которые совсем не используют закрытых каналов связи. В этих системах произошел отказ от классической схемы секретной связи рис 5.1. Схема стала соответствовать рис 7.1.

Была открыта в 70-х годах 20 века. Это была первая система, которая не использовала закрытых каналов связи. Секретные ключи для последующего шифрования информации передавались по открытому каналу связи. Точнее, ключи не передавались, а вычислялись.

Рассмотрим сеть связи с М абонентами, где М – большое число. Желательно организовать секретную связь для каждой пары абонентов. Каждая пара должна иметь свой секретный ключ. Всего потребуется М*(М-1)/2 ˜ М²/2 ключей. Для сети из 100 абонентов требуется 5000 ключей, для 10000 абонентов – 50 млн ключей. При большом числе абонентов система с секретными ключами получается громоздкой и дорогостоящей. Диффи и Хеллман предложили распространять открытые ключи и вычислять секретные. Система состоит в следующем.

Пусть строится система связи абонентов А, В, С,… У каждого абонента есть открытая и секретная информация. Для всей системы выбирается большое простое число р и число g<p. Все числа от 1 до р-1 могут быть представлены как различные степени g^x mod p. Т.е. для выбранных р и g не нарушается взаимно-однозначное соответствие между xи y.Числа р и g известны всем. Абоненты выбирают большие числа XA, XB, XCи хранят их в секрете. Каждый абонент вычисляет числоY, YA=g^XAmodp,… и открыто передает его другим абонентам.В результате получается следующая таблица.

Абонент	Секретный ключ	Открытый ключ
A	XA	YA
B	XB	YB
C	XC	YC
	Каждый знает только свой	Знают все

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

ZAB=YB^XA mod p и никуда не передает.

Никто, кроме А, сделать этого не может, т.к. XAизвестно только ему. Абонент В вычисляет

ZBA=YA^XB mod p и никуда не передает.

Утверждение:

ZAB=ZBA.

Теперь А и В могут использовать этот ZAB=ZBAкак общий секретный ключ для шифрования. Противник не может перехватить этот ключ, т.к. он не передавался ни по каким каналам связи.

Свойства системы:

1) Секретные ключи не передаются ни по каким каналам связи.

2) Противник не сможет вычислить ZAB и ZBA, т.к. ему неизвестны XA, XB. Он может попытаться вычислить XA, XB по известным YA,YB, р, g, но это практически невозможно.

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

Допустим, A хочет передать абоненту B сообщение m. Никто не должен знать содержания сообщения. Абонент A выбирает случайное большое простое число p>m и открыто передает его. Затем A выбирает число c_A и вычисляет d_A такое, что (c_A*d_A) mod(p-1) = 1, d_A = c_A^-1mod(p-1). Эти числа А держит в секрете. Рекомендуется число c_A выбирать среди взаимно-простых чисел с (p-1). Для каждого c_A существует единственное число d_A. Абонент B выбирает аналогично число c_B и вычисляет d_B такое, что d_B = c_B^-1mod(p-1). и держит их в секрете.

Шифр Шамира состоит из 4 шагов:

Шаг 1.Абонент А вычисляет x₁ = m^CAmod p и посылает к В.

Шаг 2. Абонент В, получив х₁, вычисляет x₂ = х₁^CBmod p и передает его к А.

Шаг 3. Абонент А вычисляет x₃ = х₂^dAmod p и посылает его к В.

Шаг 4.Абонент В вычисляет x₄ = х₃^dBmod p.

Свойства протокола Шамира:

· х₄ = m, т.е. вычислено исходное сообщение.

· противник не может вычислить исходное сообщение, т. к. ему неизвестны c_B и c_A. Он не может их вычислить – это практически невозможно.

Пример.

Пусть A хочет передать B сообщение m = 10. A выбирает p = 23 и c_A = 7 (взаимно простое с 22) и вычисляет d_A = 19. Аналогично B выбирает c_B = 5 и вычисляет d_B = 9. Переходим к протоколу Шамира.

Шаг 1. x₁ = 10⁷mod 23 = 14.

Шаг 2. x₂ = 14⁵mod 23 = 15.

Шаг 3. x₃ = 15¹⁹mod 23 = 19.

Шаг 4.x₄ = 19⁹mod 23 = 10.

Таким образом, B получил исходное сообщение m = 10.

Другой пример. m = 11.

Шаг 1. x₁ = 11⁷mod 23 = 7.

Шаг 2. x₂ = 7⁵mod 23 = 17.

Шаг 3. x₃ = 17¹⁹mod 23 = 5.

Шаг 4.x₄ = 5⁹mod 23 = 11.

Абонент B получил исходное сообщение m = 11.

Еще пример.

p = 53, c_A = 17, d_A = 19, c_B = 33, d_B = 41, m = 24.

Тогда

x₁ = 49, x₂ = 46, x₃ = 36, x₄ = 24.

Дата добавления: 2014-01-04