Клод Шеннон. Теория связи в секретных системах. Перемешивание.

25. Перемешивание.

В некоторых разделах теории вероятностей очень ценным оказалось понятие перемешивания. Пусть имеется пространство с мерой (или вероятностное пространство) и некоторое сохраняющее меру отображение F этого пространства в само себя, т.е. такое отображение, что мера отображенной области FR равна мере исходной области R. Отображение называется перемешиванием, если для любой функции, определенной на пространстве, и для любой области R интеграл от этой функции по области FⁿR стремится при n к интегралу от функции по всему пространству , умноженному на объем области R. Это означает, что первоначальная область R перемешивается с равномерной плотностью по всему пространству, если F применяется большое число раз. В общем случае FⁿR становится областью, состоящей из большого числа тонких волокон, распределенных по всему пространству . При увеличении n волокна становятся тоньше, а их плотность приближается к постоянной.

Перемешивание в этом точном смысле может осуществляться лишь в пространствах с бесконечным числом точек, так как в пространстве с конечным числом точек такое отображение должно быть периодическим. Однако можно понимать под перемешиванием, грубо говоря, такое отображение, которое распределяет любую разумно расположенную область довольно равномерно по всему пространству. Если до отображения область можно было бы описать в простых терминах, то после отображения потребовалось бы очень сложное описание.

В криптографии в качестве пространства рассматриваются все возможные сообщения длины N, а в качестве области R – высоковероятные сообщения. Эта последняя группа сообщений имеет довольно простую статистическую структуру. Если применить перемешивание, то высоковероятные сообщения рассеялись бы равномерно по всему пространству.

Хорошее перемешивание часто получается с помощью повторных произведений двух простых некоммутирующих операций. Хопф показал, например, что масса теста может быть перемешана с помощью такой последовательности операций. Тесто сначала раскатывается тонким слоем, затем скатывается, затем опять раскатывается и т.д..

В хорошем перемешивании пространства с естественными координатами X₁,...,X_s координата X_i переносится перемешиванием в точку X'_i с помощью соотношения

X_i' = f_i(X₁,...,X_s), i = 1,2,...,s,

причем функции f_i являются сложными, и зависят от всех переменных "чувствительным" образом. Небольшое изменение одного из переменных, скажем Х₃, значительно изменяет X_i'. Если Х₃ проходят всю область возможных значений, то X_i' должны описывать длинный извилистый путь по пространству.

Можно придумать различные способы перемешивания, применимые к статистическим последовательностям такого типа, которые встречаются в естественных языках. Один из таких способов, который кажется достаточно хорошим, заключается в том, что сначала применяется транспозиция, а затем попеременно применяются подстановка и одно из простых линейных преобразований (например, сложение смежных букв по модулю 26). Таким образом, можно взять

F = LSLSLT,

где T – транспозиция, L – линейная операция, и S – подстановка.

[Титульный лист] [Предыдущий раздел] [Следующий раздел]
[Начало осмотра] [Что нового] [Статьи] [Выпуски в "Байтах"] [Что скачать] [Криптоалгоритмы] [Глоссарий] [Ссылки] [Гостевая книга] [Форум] [Напиши мне]

Версия от 05.01.02. (c) 2002 Андрей Винокуров.