Маркант. Михаил Евгеньевич Масленников

взаимно-однозначное отображение некоторого множества в себя. Множество всевозможных подстановок принято называть симметрической группой. Так, любая подстановка из симметрической группы S₂₅₆ – это взаимно-однозначное отображение кольца вычетов Z/256 в себя.

      Имея всего 256 байт памяти легко реализовать на них любую подстановку π из S₂₅₆. Для этого для любого x ϵ Z/256 в ячейку памяти по адресу x надо записать значение π(x).

      В алгебре под произведением подстановок понимают их последовательное применение слева направо.

      Операцию сложения с переносом двух байт x и y тоже можно рассматривать как подстановку g_x ϵ S₂₅₆: g_x(y) = (x + y)mod 256. Если через g обозначить полноцикловую подстановку g = g₁ = (0,1,2,…,255), то, полагая, что g₀ – это единичная подстановка, когда все элементы отображаются сами в себя, получаем, что при любом x ϵ Z/256 g_x = g^x .

      Множество всевозможных преобразований {g₀, g₁,…,g₂₅₅} образуют циклическую группу, которую в НИР «Проба» было принято обозначать G = <g>, а множество {g₀π, g₁π,…,g₂₅₅π} – через Gπ.

      Предположим, что у нас есть цепочка байт x1, x2,…xk и произвольная подстановка π из S₂₅₆. Что можно сказать о подстановках g_x1π g_x2π… g_xkπ?

      Одним из первых и очень важным результатом НИР «Проба» было доказательство, что при случайном и равновероятном выборе π из S₂₅₆ группа, порожденная множеством Gπ, с большой вероятностью совпадает со всей симметрической группой S₂₅₆. Что это означало на практике?

      Возьмем простейший типовой узел, реализованный с помощью побайтных преобразований.

      Рис. 1. Типовой узел (Gπ)^k

      На вход узла подается входное слово – цепочка из k байт, каждый байт складывается по модулю 256 с результатом обработки предыдущих байт и заменяется по подстановке π. Таким образом, этот узел работает циклами, в каждом цикле по k тактов. Если предположить, что цепочка X = x1,x2,..,xk из k байт является ключом, то с помощью этого узла можно реализовать подстановку π1 = g_x1π g_x2π… g_xkπ, зависящую от ключа X. Результаты НИР «Проба» показывают, что таким путем можно реализовать практически любую подстановку из S₂₅₆.

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

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