2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ошибка в теореме Шеннона
Сообщение22.02.2018, 13:47 


27/08/16
9426
В основополагающей работе Шеннона "Communication Theory of Secrecy Systems" (Shannon, C. E., “Communication Theory of Secrecy Systems”, Bell System Technical Journal, vol. 28(4), page 656–715, 1949. The material in this paper appeared in a confidential report “A Mathematical Theory of Cryptography” dated Sept.1, 1946, which has now been declassified) присутствует такая теорема:

Theorem 2. The product of two pure ciphers which commute is pure.

При этом pure cipher определён как шифр $T_k(m), m\in \mathbb{M}, k \in \mathbb{K}$ со следующим свойством: $$\forall i,j,k \exists s:\quad T_i\circ T_j^{-1}\circ T_k=T_s$$Данное определение специально отличается от определения группы, так как: "This, however, would be too restrictive".


Несложно придумать тривиальный контрпример к таким образом сформулированной этой теореме. Для того, чтобы не портить удовольствие тем, кто хочет поискать контрпример самостоятельно, помещаю контрпример под кат:

(шифр Юджина)

Пусть $\mathbb{M}=\mathbb{K}=\mathbb{Z}_8$. Определим перестановки $\mathbb{M}$ как $$P_k(m):=(m + k)\bmod 8$$$$S:=(0\to 1, 1\to 0, 2\to 2, 3\to 3, 4\to 4, 5\to 5, 6\to 6, 7\to 7)$$Пусть $$T_k:=S\circ P_k$$ Тогда, в определении Шеннона, $T$ - pure cipher, но $T^2$ - нет.

Данный контрпример был когда-то давным-давно выложен в sci.crypt, но столь древний Usenet уже даже Гуглом нормально не индексируется.

PS Сорри, ссылка на работу была неправильная.

 Профиль  
                  
 
 Re: Ошибка в теореме Шеннона
Сообщение24.02.2018, 03:26 
Модератор
Аватара пользователя


11/01/06
5660
realeugene, а что с доказательством у этой теоремы? Или Шеннон приводит её без доказательства?

 Профиль  
                  
 
 Re: Ошибка в теореме Шеннона
Сообщение24.02.2018, 09:41 


27/08/16
9426
В доказательстве подразумевается коммутация $T$ с $R^{-1}$$T^{-1}$ с $R$), что из коммутации самих шифров никак не следует. У шифра из контрпримера $T^{-1}T \ne T T^{-1}$.
Условие коммутации двух шифров $T$ и $R$ определено у Шеннона следующим образом: $\forany i, j \exists l, m : T_i R_j = R_l T_m$. Кстати, такое определение само по себе не симметрично, так что, знак равенства, возможно, Шеннон использовал тут зря. Т. е. из того, что $TR=RT$ согласно этому определению ещё не следует, что $RT=TR$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group