Криптография и свобода - страница 54

s_>1 = π (π (t_>1+x_>1)+x_>2)

s_>2 = π (π (t_>2+x_>1)+x_>2)

имела бы решение относительно x_>1,x_>2, а, следовательно, поскольку π - подстановка, то и система

s_>1 = π (t_>1+x_>1)+x_>2 (1)

s_>2 = π (t_>2+x_>1)+x_>2

имела бы решение для любых заранее фиксированных s_>1,s_>2, t_>1,t_>2, в которых s_>1≠s_>2 и t_>1≠t_>2

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

x-y = i (2)

π(x) - π(y) = j

где i, j ≠ 0.

Если при каких-то i, j ≠ 0 p_>ij =0, то это означает, что при заранее фиксированных s_>1,s_>2, t_>1,t_>2, в которых s_>1≠s_>2 и t_>1≠t_>2, а также t_>1-t_>2 = i, s_>1-s_>2 = j, система (1) заведомо не имеет решения, ибо в противном случае имела бы решение и система (2).

Заметим, что p_>ij = p_>(2^>n_>-i)(2^>n_>-j). Действительно, каждому решению (x_>1,y_>1) системы (2) можно поставить во взаимно однозначное соответствие решение (x_>2,y_>2)=(y_>1,x_>1) системы

x-y = 2^>n-i

π(x) - π(y) = 2^>n-j

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

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

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

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

x-y = j (4)

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

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

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

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

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

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

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

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

Предположим, что некоторая i-я строка целиком ненулевая. Это означает, что среди значений j_>0,j_>1,…,j_>2^>n_>-1, получаемых по формуле

j_>k =π(k+i)- π(k) (7)

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

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

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

Тогда, в силу свойства p_>ij = p_>(2^>n_>-i)(2^>n_>-j) для любого значения i должно выполняться

p_>i2^>n-1 = p_>(2^>n_>-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^>n-3. В этом случае в матрице ровно две ненулевых строки, расположенных симметрично друг от друга, а в средней строке с номером 2^>n-1 ровно одно нулевое значение посередине: p_>(2^>n-1_>)(2^>n-1_>) = 0.

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

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