Ошибка в теореме Шеннона

[realeugene]

В основополагающей работе Шеннона "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 Сорри, ссылка на работу была неправильная.

[maxal]

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

[realeugene]

В доказательстве подразумевается коммутация $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$.