Здесь хотелось бы обратить внимание на то, что группа будет совпадать с S_>256 не при любой π. Например, если π ϵ G, то это заведомо не так. Но вероятность получить «плохую» подстановку π при ее случайном и равновероятном выборе из S_>256 крайне мала.

А теперь давайте вернемся ко второй мировой войне и немецкому дисковому шифратору «Энигма». В нем было два типа ключей: долговременные и одноразовые. Долговременные ключи – это коммутации вращающихся роторов, а одноразовые – их начальное положение. Если коммутации вращающихся роторов неизвестны, то в этом случае криптографы бессильны. Коммутации роторов – это фактически подстановки на множестве букв немецкого алфавита. Число всевозможных подстановок в симметрической группе S_>N равно N! – N факториал, произведение всех чисел от 1 до N. При N = 26 имеем N! = 403 291 461 126 605 635 584 000 000 ≈ 4 * 10^>26. Если предположить, что в «Энигме» коммутации роторов выбирались случайно и равновероятно, то для перебора всевозможных значений коммутации только одного ротора потребовалась бы трудоемкость, непосильная даже для современных ЭВМ. Поэтому англичане могли читать «Энигму» только при условии, что какими-то путями им удалось захватить хотя бы один ее экземпляр и определить коммутации всех роторов.

Роторы в «Энигме» нельзя было сделать одноразовыми ключами по объективным причинам – это слишком сложно. А в НИР «Проба» показали, что в шифрах на новой элементной базе это сделать несложно.

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

Во многих криптографических задачах важную роль играет свойство 2-транзитивности некоторого множества подстановок. Множество подстановок (Gπ)^>k является 2-транзитивным, если для любых двух пар (x1,y1) и (x2,y2), таких что x1 ≠ y1 и x2 ≠ y2, найдется подстановка, переводящая пару (x1,y1) в (x2,y2).

В НИР «Проба» получили следующие результаты.

Минимальное значение k, при котором (Gπ)^>k является 2-транзитивным, равно 3.

При случайном и равновероятном выборе π из S_>256 с вероятностью, близкой к 1, множество (Gπ)^>3 будет 2-транзитивным.

Для любой подстановки π из S_>256 можно определить ее так называемую матрицу частот P(π) размера 255 х 255, у которой на пересечении строки с номером i со столбцом с номером j, i,j ϵ {1,2,…,255}, находится число решений системы

            x – y = i (mod 256)

            π(x) – π(y) = j (mod 256)

относительно неизвестных x, y ϵ Z/256.

В НИР «Проба» показали, что множество (Gπ)^>3 является 2-транзитивным тогда и только тогда, когда возведенная в квадрат матрица P(π) не содержит нулевых элементов. Чуть позже было доказано, что при случайном и равновероятном выборе π в матрице P(π) примерно 2/3 элементов – ненулевые, 1/3 – нули.

Темой моей дипломной работы в 1979 году было построение и анализ матриц P(π) для всех π из симметрической группы S_>8. Это 8! = 40320 подстановок. Такое построение позволяло подтвердить приведенные выше теоретические результаты.

Для Руты – 110, если она к тому времени была еще жива (сейчас точно не помню), это явно непосильная задача, матрицы строились вручную. Все теоретические результаты были подтверждены.