On non-minimal perfect ciphers.pdf Цель современных криптографических методов защиты информации — создание шифров, не позволяющих раскрыть никаких сведений о соответствующих им открытых текстах. Систематически вопрос о теоретической стойкости шифров впервые исследовал К. Шеннон в своей фундаментальной работе [1], в которой рассмотрена вероятностная модель шифра. Пусть X, Y — конечные множества открытых и закрытых текстов, с которыми оперирует некоторый шифр замены, K — множество ключей, |X| = Л, |Y| = р, |K| = п, Л > 1, р > 1. Согласно [2, 3], под шифром будем понимать совокупность множеств правил зашифрования и расшифрования с заданными распределениями вероятностей на множествах /-грамм открытых текстов, закрытых текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. Такие шифры являются абсолютно стойкими к криптоатакам по шифртексту. Совершенным может быть лишь шифр с неограниченным ключом [3]. Шифры, для которых |X| = |Y|, называются эндоморфными [1]. К. Шеннон полностью описал эндоморфные совершенные шифры с минимальным возможным числом ключей (|K| = |Y|). Согласно [3], шифр называется сильно совершенным, если он остается совершенным для любого распределения P(X) вероятностей на множестве открытых текстов. Шифры, для которых |Y| < |K|, называются неминимальными. Шифры, для которых |K| = р ■ (р — 1) ■ ... ■ (р — Л + 1), то есть шифры, содержащие все инъекции X ^ Y, называются максимальными. Доказано Утверждение 1. Неминимальный совершенный шифр вкладывается в максимальный совершенный шифр. В утверждении 1 имеется в виду не только теоретико-множественное включение, но и теоретико-вероятностное включение в рамках рассматриваемой модели шифра. Кроме эндоморфных, существуют также неэндоморфные (|X| < |Y|) шифры с неравновероятными ключами, являющиеся сильно совершенными. Такие шифры обладают дополнительными свойствами, важнейшие из которых — имитостойкость и помехоустойчивость. Изучение неэндоморфных совершенных шифров в общем виде предполагает знание распределения вероятностей P (X1) на множестве /-грамм алфавита открытых текстов. В работе [4] рассматриваются комбинаторные аспекты проблематики совершенных шифров. В качестве стандартного аппарата исследования распределения вероятностей на /-граммах используются стохастические матрицы и однородные цепи Маркова. При этом проблематика описания совершенных шифров связана с классическими задачами описания статистически неопределённых систем [5]. Справедлива Теорема 1. Неэндоморфный совершенный шифр является сильно совершенным. Эквивалентность понятий совершенности и сильной совершенности для неэндо-морфных шифров даёт большие возможности для их изучения. В работе показано, что распределение вероятностей на множествах /-грамм закрытых текстов и ключей, при котором максимальный шифр будет совершенным, можно найти с помощью системы линейных уравнений. Данная система совместна, при этом её неизвестные принадлежат отрезку [0; 1]. Поэтому искомое распределение вероятностей в пространстве вероятностей представляет собой некоторое выпуклое тело P^ (многогранник) в многомерном евклидовом пространстве. Многогранник P^ описан как выпуклая оболочка вершин. Справедливо Утверждение 2. Если £1 < £2, то для соответствующих многогранников P^1 и P^2 выполняется условие P^1 С P^2, то есть многогранники P^ для £-грамм при разных £ вложены в друг друга. Итак, показано, что изучение неэндоморфных шифров сводится к изучению максимальных неэндоморфных шифров. При этом распределения вероятностей на /-граммах могут рассматриваться и как независимые, что характерно для блочных шифров, и как порождённые режимом гаммирования. Справедлива Теорема 2. Совершенными максимальными шифрами являются шифры с вероятностями ключей P(K^) из многогранника P^, и только они. Данная теорема является аналогом теоремы К. Шеннона, доказанным для общего класса неэндоморфных неминимальных шифров.

Скачать электронную версию публикации