Маркант. Михаил Евгеньевич Масленников
взаимно-однозначное отображение некоторого множества в себя. Множество всевозможных подстановок принято называть симметрической группой. Так, любая подстановка из симметрической группы S256 – это взаимно-однозначное отображение кольца вычетов Z/256 в себя.
Имея всего 256 байт памяти легко реализовать на них любую подстановку π из S256. Для этого для любого x ϵ Z/256 в ячейку памяти по адресу x надо записать значение π(x).
В алгебре под произведением подстановок понимают их последовательное применение слева направо.
Операцию сложения с переносом двух байт x и y тоже можно рассматривать как подстановку gx ϵ S256: gx(y) = (x + y)mod 256. Если через g обозначить полноцикловую подстановку g = g1 = (0,1,2,…,255), то, полагая, что g0 – это единичная подстановка, когда все элементы отображаются сами в себя, получаем, что при любом x ϵ Z/256 gx = gx .
Множество всевозможных преобразований {g0, g1,…,g255} образуют циклическую группу, которую в НИР «Проба» было принято обозначать G = <g>, а множество {g0π, g1π,…,g255π} – через Gπ.
Предположим, что у нас есть цепочка байт x1, x2,…xk и произвольная подстановка π из S256. Что можно сказать о подстановках gx1π gx2π… gxkπ?
Одним из первых и очень важным результатом НИР «Проба» было доказательство, что при случайном и равновероятном выборе π из S256 группа, порожденная множеством Gπ, с большой вероятностью совпадает со всей симметрической группой S256. Что это означало на практике?
Возьмем простейший типовой узел, реализованный с помощью побайтных преобразований.
Рис. 1. Типовой узел (Gπ)k
На вход узла подается входное слово – цепочка из k байт, каждый байт складывается по модулю 256 с результатом обработки предыдущих байт и заменяется по подстановке π. Таким образом, этот узел работает циклами, в каждом цикле по k тактов. Если предположить, что цепочка X = x1,x2,..,xk из k байт является ключом, то с помощью этого узла можно реализовать подстановку π1 = gx1π gx2π… gxkπ, зависящую от ключа X. Результаты НИР «Проба» показывают, что таким путем можно реализовать практически любую подстановку из S256.
Здесь хотелось бы обратить внимание на то, что группа <Gπ> будет совпадать с S256 не при любой π. Например, если π ϵ G, то это заведомо не так. Но вероятность получить «плохую» подстановку π при ее случайном и равновероятном выборе из S256 крайне мала.
А теперь давайте вернемся ко второй мировой войне и немецкому дисковому шифратору «Энигма». В нем было два типа ключей: долговременные и одноразовые. Долговременные ключи – это коммутации вращающихся роторов, а одноразовые – их начальное положение. Если коммутации вращающихся роторов неизвестны, то в этом случае криптографы бессильны. Коммутации роторов – это фактически подстановки на множестве букв немецкого алфавита. Число всевозможных подстановок в симметрической группе SN равно N! – N факториал, произведение всех чисел от 1 до N. При N = 26 имеем N! = 403 291 461 126 605 635 584 000 000 ≈ 4 * 1026. Если предположить, что в «Энигме» коммутации роторов выбирались