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

С чего начала кафедра математики на 4 факультете? С самого простейшего преобразования, осуществляемого с n-мерными двоичными векторами, с преобразования типа (GП)^k, где G – группа, порожденная циклическим сдвигом (G = , g =(0,1,…,2ⁿ-1)-циклическая подстановка), П – некоторая фиксированная подстановка из S₂ⁿ, а k – некоторое целое число.

Если здесь перейти от математических терминов из теории групп к обычной криптографической терминологии, то преобразование типа (GП)^k – это следующий узел.

Преобразования типа (GП)^k - это, фактически, множество подстановок вида g_x1П g_x2П… g_xkП, и задачей кафедры математики было обосновать какие-то свойства подобного множества, найти их зависимости от подстановки П. Типичная криптографическая ситуация – когда в таком узле входное слово x₁,x₂,…x_k является ключевым параметром, требуется найти подходы к его определению по нескольким известным переходам в реализуемой подстановке.

Кафедра начала с изучения группы , т.е. группы, порожденной двумя подстановками: циклическим сдвигом g и фиксированной произвольной подстановкой П. Это естественное обобщение преобразования (GП)^k, предельный случай. Свойства группы дают ответ на вопрос, что в принципе можно ожидать от нашего преобразования при увеличении длины k до бесконечности. Можем ли мы таким путем получить все подстановки или же есть какие-то запреты?

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

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

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

П(y₁)- П(y₂) = (ay₁+b) – (ay₂+b) = a(y₁-y₂)

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

А если П – не линейная, а произвольная подстановка? При каком минимальном значении 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)