Маркант - страница 4

Ключевым словом в НИР «Проба» было слово подстановка. В математике так принято называть взаимно-однозначное отображение некоторого множества в себя. Множество всевозможных подстановок принято называть симметрической группой. Так, любая подстановка из симметрической группы S_>256 – это взаимно-однозначное отображение кольца вычетов Z/256 в себя.

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

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

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

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

Предположим, что у нас есть цепочка байт x1, x2,…xk и произвольная подстановка π из S_>256. Что можно сказать о подстановках g_>x1π g_>x2π… g_>x>kπ?

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

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

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

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

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