Криптография и свобода

А если π - не линейная, а произвольная подстановка? При каком минимальном значении k множество (Gπ)^k может достичь свойства 2-транзитивности? Всего имеется 2ⁿ(2ⁿ-1) различных пар (z₁,z₂), в которых z₁≠z₂, а количество различных подстановок в (Gπ)^k не превосходит (2ⁿ)^k. Следовательно, свойства 2-транзитивности можно достичь только при k≥2. Можно ли при k=2?

Рассмотрим множество подстановок (Gπ)². Это множество реализует всевозможные преобразования произвольного значения t в значение s по формуле s = π (π (t+x₁)+x₂) при всевозможных x₁,x₂. Если бы это множество было 2-транзитивным, то для любых заранее фиксированных s₁,s₂, t₁,t₂ , в которых s₁≠s₂ и t₁≠t₂, система уравнений:

s₁ = π (π (t₁+x₁)+x₂)

s₂ = π (π (t₂+x₁)+x₂)

имела бы решение относительно x₁,x₂, а, следовательно, поскольку π - подстановка, то и система

s₁ = π (t₁+x₁)+x₂ (1)

s₂ = π (t₂+x₁)+x₂

имела бы решение для любых заранее фиксированных s₁,s₂, t₁,t₂, в которых s₁≠s₂ и t₁≠t₂

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

x-y = i (2)

π(x) - π(y) = j

где i, j ≠ 0.

Если при каких-то i, j ≠ 0 p_ij =0, то это означает, что при заранее фиксированных s₁,s₂, t₁,t₂, в которых s₁≠s₂ и t₁≠t₂, а также t₁-t₂ = i, s₁-s₂ = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).

Заметим, что p_ij = p₍₂ⁿ_-i)(2ⁿ_-j). Действительно, каждому решению (x₁,y₁) системы (2) можно поставить во взаимно однозначное соответствие решение (x₂,y₂)=(y₁,x₁) системы

x-y = 2ⁿ-i

π(x) - π(y) = 2ⁿ-j

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

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

π(y+i) - π(y) = j (3)

Если каждому решению (x₁,y₁) системы (2) поставить во взаимно-однозначное соответствие пару (x₂,y₂) = (π^-1(x₁),π^-1(y₁)), то такая пара будет решением системы

x-y = j (4)

π^-1(x) - π^-1(y) = i

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

π^-1(y+j) - π^-1(y) = i (5)

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

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

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

π(y+2^n-1) - π(y) = 2^n-1, (6)

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

Предположим, что некоторая i-я строка целиком ненулевая. Это означает, что среди значений j₀,j₁,…,j₂ⁿ_-1, получаемых по формуле

j_k =π(k+i)- π(k) (7)

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

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

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

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

p_i2^n-1 = p₍₂ⁿ_-i)2^n-1 = 2

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

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

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