Михаил Масленников - Криптография и свобода

Оказалось, что если случайно и равновероятно выбрать из всей симметрической группы фиксированную подстановку π, то с вероятностью, близкой к 1, группа будет совпадать со всей симметрической группой, т.е. запретов не будет. Те подстановки π, для которых это не так, очень часто легко определяются, например, π=g, а также любая линейная подстановка, реализующая преобразование вида π(x) = ax+b, где a и b – фиксированные элементы из Z/2 n.

Дальше, естественно, стали возникать вопросы: а как скоро мы сможем достичь симметрической группы? Какова будет мощность слоя (Gπ) kпри некотором значении k, например, при k=2 или при k=3? При каком k множество (Gπ) kстанет 2-транзитивным , т.е. по имеющимся в нем подстановкам любая пара (y 1,y 2), в которой y 1≠y 2, сможет перейти в любую пару (z 1,z 2), в которой z 1≠z 2? Что в общем случае можно будет сказать про обобщение 2-транзитивности – m-транзитивность?

За свойство 2-транзитивности взялись основательно, чувствовалось, что здесь могут быть интересные криптографические зацепки: если 2-транзитивность отсутствует, то появляются запреты переходов биграмм текста, широкое поле деятельности для криптоаналитика. Например, если π - упомянутая выше линейная подстановка, то для любой пары (y 1,y 2) будет справедливо соотношение:

π(y 1)- π(y 2) = (ay 1+b) - (ay 2+b) = a(y 1-y 2)

В этом случае при применении подстановки π сохраняется соотношение между разностями знаков, а поэтому кратной транзитивности заведомо не будет.

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

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

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(π) для различных подстановок π. Здесь сразу же выделялись плохие подстановки – это линейные преобразования вида

π(x) = ax+b

В этом случае при любом фиксированном i≠0 система (2) имеет решение только при одном значении j≠0, такая матрица заведомо не будет положительной ни в какой степени и свойство 2-транзитивности недостижимо. Число нулей у такой матрицы будет максимальным .

А можно ли построить подстановки с минимально возможным числом нулей в матрице P(π)? Этот вопрос уже гораздо интереснее, простого и тривиального ответа на него нет. Пока. Но в следующих главах этой книги ситуация проясниться и в конечном итоге получится очень красивый результат.