Рассмотрим множество подстановок (GП)2. Это множество реализует всевозможные преобразования произвольного значения t в значение s по формуле s = П (П (t+x1)+x2) при всевозможных x1,x2. Если бы это множество было 2-транзитивным, то для любых заранее фиксированных s1,s2, t1,t2 , в которых s1<>s2 и t1<>t2, система уравнений:

s1 = П (П (t1+x1)+x2)

s2 = П (П (t2+x1)+x2)

имела бы решение относительно x1,x2, а, следовательно, поскольку П – подстановка, то и система

s1 = П (t1+x1)+x2 (1)

s2 = П (t2+x1)+x2

имела бы решение для любых заранее фиксированных s1,s2, t1,t2, в которых s1<>s2 и t1<>t2

Отсюда, вычитая одно уравнение из другого, мы приходим к одной очень важной криптографической характеристике подстановки П – матрице частот встречаемости разностей переходов ненулевых биграмм P(П) размера (2n-1)x(2n-1), а именно, на пересечении i-ой строки и j-го столбца в этой матрице стоит значение pij – число решений системы уравнений относительно x и y:

x-y = i (2)

П(x) – П(y) = j

где i, j <> 0.

Если при каких-то i, j <> 0 pij =0, то это означает, что при заранее фиксированных s1,s2, t1,t2, в которых s1<>s2 и t1<>t2, а также t1-t2 = i, s1-s2 = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).

Заметим, что pij = p(2n-i)(2n-j). Действительно, каждому решению (x1,y1) системы (2) можно поставить во взаимно однозначное соответствие решение (x2,y2)=(y1,x1) системы

x-y = 2n-i

П(x) – П(y) = 2n-j

если домножить на –1 оба уравнения (2).

Из системы (2) очевидно вытекает, что число ее решений равно числу значений y, при которых

П(y+i) – П(y) = j (3)

Если каждому решению (x1,y1) системы (2) поставить во взаимно-однозначное соответствие пару (x2,y2) = (П-1(x1),П-1(y1)), то такая пара будет решением системы

x-y = j (4)

П-1(x) – П-1(y) = i

Следовательно, число решений системы (2) будет равно числу значений y, при которых

П-1(y+j) – П-1(y) = i (5)

Из (3) очевидно вытекает, что сумма всех элементов pij в i-ой строке при любом i равна 2n. Аналогично, из (5) вытекает, что сумма всех элементов pij в j-ом столбце при любом j равна 2n.

Поскольку размер P(П) равен (2n-1)x(2n-1), то из условия, что сумма всех элементов pij в i-ой строке при любом i равна 2n следует, что если бы P(П) не содержала нулей, то в любой ее строке все элементы были бы равны 1, кроме одного, равного 2. Аналогично получаем, что в этом случае в любом столбце должны быть все элементы 1, кроме одного, равного 2.

Если при некотором y выполняется

П(y+2n-1) – П(y) = 2n-1, (6)

то, поскольку 2n–2n-1 = 2n-1, то (6) будет справедливо и при значении y1 = y+2n-1. Таким образом, элемент p(2n-1)(2n-1) не может быть нечетным.

Предположим, что некоторая i-я строка целиком ненулевая. Это означает, что среди значений j0,j1,…,j2n-1, получаемых по формуле

jk =П(k+i)- П(k) (7)

содержатся все ненулевые элементы из Z/2n, а какой-то один элемент встретился ровно 2 раза.

Просуммируем соотношение (7) по всем k от 0 до 2n-1. Поскольку П – подстановка, то в правой части суммы получается 0, следовательно, сумма всех значений jk также должна быть нулевой.

Но среди j0,j1,…,j2n-1 содержатся все ненулевые элементы из Z/2n, а какой-то один элемент встретился ровно 2 раза. Поскольку сумма (по модулю 2n) всех ненулевых элементов кольца Z/2n равна 2n-1(2n-1) = 2n-1, то элементом, встретившимся два раза, должно быть 2n-1.

Тогда, в силу свойства pij = p(2n-i)(2n-j) для любого значения i должно выполняться

pi2n-1 = p(2n-i)2n-1 = 2

и при i<>2n-1 получается, что в 2n-1 столбце как минимум 2 элемента равны 2. Следовательно, если некоторая i-я строка при i<>2n-1 целиком ненулевая, то 2n-1 столбец заведомо содержит хотя бы один нулевой элемент, т.е. множество (GП)2 не является 2-транзитивным ни при какой подстановке П.

И еще отсюда сразу же вытекает, что общее число нулей в матрице P(П) не может быть меньше, чем 2n-3. В этом случае в матрице ровно две ненулевых строки, расположенных симметрично друг от друга, а в средней строке с номером 2n-1 ровно одно нулевое значение посередине: p(2n-1)(2n-1) = 0.

Подобными же методами легко показать, что в общем случае множество (GП)k является 2-транзитивным при k>2 в том и только том случае, когда матрица P(П)k-1 не содержит нулей. В частности, множество (GП)3 является 2-транзитивным тогда и только тогда, когда матрица P(П)2 не содержит нулей.

Стало ясно, в каком направлении вести математические раскопки теории шифров на новой элементной базе: изучать матрицы P(П) для различных подстановок П. Здесь сразу же выделялись плохие подстановки – это линейные преобразования вида