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

составляет всего 2! = 2, всего две подстановки: тривиальная единичная (ничего не меняется) и инверсия, когда 0 переходит в 1, а 1 – в 0. Мощность же симметрической группы S_>256 составляет 256! – совершенно фантастическое число. Введение подстановки в регистр сдвига, работающий с байтами, а не с битами, переворачивает все привычные методы криптографического анализа. Совершенно другие операции, а следовательно, нужны и другие подходы к анализу и оценке стойкости таких схем, чем те, которые использовались в традиционных двоичных «балалайках».

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

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

Преобразования типа (Gπ)^>k - это, фактически множество подстановок вида g_>x1π g_>x2π… g_>xkπ, и задачей кафедры математики было обосновать какие-то свойства подобного множества, найти их зависимости от подстановки π. Типичная криптографическая ситуация – когда в таком узле входное слово x_>1,x_>2,…x_>k является ключевым параметром, требуется найти подходы к его определению по нескольким известным переходам в реализуемой подстановке.

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

Оказалось, что если случайно и равновероятно выбрать из всей симметрической группы фиксированную подстановку π, то с вероятностью, близкой к 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