крайне мала.
А теперь давайте вернемся ко второй мировой войне и немецкому дисковому шифратору «Энигма». В нем было два типа ключей: долговременные и одноразовые. Долговременные ключи – это коммутации вращающихся роторов, а одноразовые – их начальное положение. Если коммутации вращающихся роторов неизвестны, то в этом случае криптографы бессильны. Коммутации роторов – это фактически подстановки на множестве букв немецкого алфавита. Число всевозможных подстановок в симметрической группе 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}, находится число решений системы