Уральский государственный университет путей сообщения (Екатеринбург) Исследуется проблема описания совершенных по Шеннону (абсолютно стойких к атаке по шифртексту) шифров. В терминах комбинаторного анализа выпуклых множеств многомерного пространства сформулированы и доказаны некоторые обобщения (аналоги) теоремы Шеннона для совершенных по Шеннону неминимальных шифров. Построены примеры, подчеркивающие нетривиальность данной задачи. Ключевые слова: совершенные шифры; неэндоморфные шифры; неминимальные шифры.
Существование неэндоморфных (jXj < jY j) совершенных шифров [3, пример 2.2.10], а также шифров,
минимальных не по числу ключей, а по включению (т. е. шифров, содержащих минимально возможное
множество ключей зашифрования с ненулевыми вероятностями) оправдывает получение аналогов
(обобщений) теоремы Шеннона для других совершенных шифров. К этому также приводит задача изучения
минимальных (по включению) транзитивных шифров, так как совершенный шифр является транзитивным.
Допускает обобщение и само понятие совершенного по Шеннону шифра, что подтверждается изучением
современных аналогов совершенных шифров [
Данная работа является продолжением исследования [
Постановка задачи Рассмотрим неэндоморфный неминимальный совершенный шифр. Пусть X = fx1; x2; : : : ; x¸g = f1; 2; :::; ¸g множество шифрвеличин; Y = fy1; y2; : : : ; y¹g = f1; 2; : : : ; ¹g множество шифробозначений, с которыми оперирует некоторый шифр замены; K = fk1; k2; : : : ; k¼g множество ключей. Здесь jXj = ¸, jY j = ¹ ¸ ¸, jKj = ¼ ¸ ¹:
Для обобщений теоремы Шеннона и построения примеров шифров будем использовать вероятностную
модель §B, в которой, согласно подходу [
Как для эндоморфного шифра (¸ = ¹), так и для неэндоморфного (¸ < ¹), перечисляются в некотором порядке все возможные ¼ = ¹(¹ ¡ 1):::(¹ ¡ ¸ + 1) подстановки (инъекции) зашифрования, соответствующие ключам k 2 K и их вероятностям Pk. Получившийся ¼-мерный набор P вероятностей Pk ключей будем рассматривать как точку ¼-мерного пространства R¼. Распределение биграмм, триграмм и т. д. может задаваться распределениями вероятностей и при ` = 2; 3; :::
Задача описания шифров в вероятностной модели §B приводит к описанию множества точек в ¼-мерном
пространстве R¼, которые являются распределениями вероятностей того или иного шифра. В работах [
По теореме Шеннона, минимальные по числу ключей эндоморфные совершенные шифры соответствуют тем точкам пространства R¼, у которых все координаты равны нулю, кроме ¸ ненулевых координат, равных 1=¸, а сам набор координат соответствует набору ключей, подстановки которых образуют латинский квадрат. Поскольку множество точек ¼-мерного пространства R¼, соответствующих совершенным шифрам, образует выпуклое множество (полиэдр), то и выпуклая оболочка точек, соответствующих латинским квадратам (шифрам Шеннона), также соответствует совершенным шифрам.
Требуется установить: будет ли полученный таким образом полиэдр множеством распределений всех эндоморфных совершенных шифров и сводится ли задача описания минимальных (по включению) совершенных шифров к задаче описания минимальных (по включению) транзитивных шифров. 3
Об описании эндоморфных совершенных шифров Для ¸ = ¹ 2 f2; 3g ответ на поставленный вопрос – положительный. При ¸ = ¹ = 2 – это классический шифр Вернама с суммированием бита открытого текста и бита ключевого потока по модулю 2. При ¸ = ¹ = 3 и K = fk1; k2; :::; k6g таблица зашифрования со всеми ¼ = 3! = 6 подстановками из X = fx1; x2; x3g в Y = f1; 2; 3g – это таблица 1, в которой точки P(1) и P(2) соответствуют латинским квадратам.
Утверждение 1. Любой эндоморфных совершенный шифр с мощностью множества шифрвеличин, равной трем, задается распределением вероятностей
P = ® P(1) +¯ P(2) = ® µ 1 3
1 1 ¶T ; 0; 0; ; ; 0 3 3
µ 1 1 + ¯ 0; ; ; 0; 0; 3 3 1 ¶T 3 = µ ® ¯ ¯ ® ® ¯ ¶T
; ; ; ; ; 3 3 3 3 3 3 ; ®; ¯ ¸ 0; ® + ¯ = 1; лежащим в выпуклой оболочке точек P(1); P(2) 2 R6: Согласно Утверждению 1, для ¸ = ¹ = 3 искомое выпуклое множество (полиэдр) – отрезок в шестимерном пространстве.
Утверждение 2. Априорные вероятности шифробозначений эндоморфного совершенного шифра одинаковы и равны ¸1 .
Доказательство. Для данного шифра условия совершенности по Шеннону в вероятностной модели
шифра §B (т. е. условие для `-грамм при ` = 1) [
2 ::: ¸ ¶ y1 y2 ::: y¸ единица в нижней строке значений стоит на m-ом месте; а поскольку для каждой такой подстановки существует единственное такое m 2 f1; 2; :::; ¸g, то эта вероятность входит ровно один раз в первые ¸ уравнений. Ввиду того, что сумма всех вероятностей ключей равна единице, получаем, суммируя первые ¸ уравнений, что 1 = ¸p1, откуда p1 = ¸1 . Повторяя это рассуждение для каждой априорной вероятности pi; i = 1; 2; :::; ¸ шифробозначений, находим 1 p1 = p2 = ::: = p¸ = ; ¸ что и требовалось доказать.
При ¸ = ¹ > 3 выпуклая оболочка совершенных по Шеннону шифров с минимальным числом ключей является лишь частью множества точек, соответствующих совершенным шифрам, как показывает следующее
Утверждение 3. При ¸ = ¹ = 4 существуют минимальные (по включению) совершенные шифры, не содержащие в себе наборов ключей (подстановок), образующих латинский квадрат.
Таблица 2: Совершенный шифр при ¸ = ¹ = 4 Легко проверяется, что это – совершенный эндоморфный шифр. Здесь полноцикловые подстановки f группы S4 обладают свойством – для каждой подстановки f имеется ровно четыре различные другие полноцикловые подстановки gi такие, что f (i) = gi(i); i = 1; 2; 3; 4. Следовательно, максимальные четырехстолбцовые латинские прямоугольники в этой таблице состоят из трех строк вида e; f; f ¡1, и латинских квадратов – нет.
Утверждение 4. Совершенный шифр – транзитивный [
Доказательство. Рассмотрим таблицы 3, 4 зашифрования эндоморфных шифров при ¸ = ¹ = 4 с произвольными неизвестными вероятностями ключей. Это минимальные (по включению) транзитивные шифры, которые не могут быть совершенными ни при каких распределениях вероятностей ключей. Причем из их таблиц зашифрования невозможно извлечь латинский квадрат.
Таблица 3: Транзитивный шифр при ¸ = ¹ = 4 № K 1 k1 2 k2 3 k3 4 k4 5 k5 Утверждение 5. При ¸ = ¹ > 3 существуют шифры с равновероятными ключами, не лежащие в выпуклой оболочке совершенных по Шеннону неминимальных по числу ключей шифров.
Доказательство. Рассмотрим совершенный эндоморфный шифр при ¸ = ¹ = 4 с равновероятными ключами и таблицей 5 зашифрования, не содержащей латинских квадратов и составленной из биекций (подстановок) группы S4.
Действительно, в таблице 5 можно исключить или первую, или вторую строку. Если исключить первую, то вторая обязательно должна быть, а значит нужно исключить четвертую строку, чтобы шифробозначение 4 встречалось в столбце для x2 один раз. Следовательно, нужно оставить третью строку, иначе в столбце для x1 не будет шифробозначения 2. Вследствие этого получаем, что в столбце для x3 шифробозначение 3 будет встречаться дважды, т. е. латинского квадрата не будет. Если же исключить вторую строку, то должна остаться первая, а значит нужно исключить восьмую строку, иначе шифробозначение 3 будет встречаться дважды в столбце для x2. Следовательно, седьмая строка должна остаться, иначе в столбце для x1 не будет шифробозначения 4. Вследствие этого нужно будет убрать шестую строку, иначе шифробозначение 2 в столбце для x2 будет повторяться. Тогда получим, что в столбце для x4 шифробозначения 1 не будет, т. е. останется не латинский квадрат. Это означает, что равновероятность ключей также не приводит к прямому обобщению теоремы Шеннона.
Согласно Утверждению 5, обобщение теоремы Шеннона в рассматриваемой постановке задачи неверно.
Существуют шифры, выходящие за пределы рассматриваемой оболочки [
Об описании неэндоморфных совершенных шифров Справедливо утверждение о дополнении неэндоморфного совершенного шифра до эндоморфного.
Утверждение 6. Латинский прямоугольник размерами n £ (n ¡ 1), т. е. n строк, (n ¡ 1) столбцов, заполненный величинами 1; 2; :::; n, однозначно дополняется до латинского квадрата размерами n £ n.
Доказательство. Поскольку в строках латинского прямоугольника размера n £ (n ¡ 1) величины 1; 2; :::; n не повторяются, то оставшуюся величину можно однозначно поместить в n-ый столбец. Получившийся квадрат не будет латинским, если в последнем столбце будут повторения.
Если на пересечении этого n-го столбца и каких либо двух строк находится одна и та же величина y, то некоторая величина x 6= y из множества f1; 2; :::; ng не встречается в этом столбце. Тогда эта величина x должна встретиться в каждой из n строк точно по одному разу в первых (n¡1)-ой позициях. Следовательно, в исходном латинском прямоугольнике величина x входит n раз. Но так как столбцов в нём n ¡ 1, то x входит в какой-либо столбец два раза, что противоречит тому, что прямоугольник является латинским.
Утверждение 7. Любой неэндоморфный совершенный шифр с мощностью множества шифрвеличин, равной ¸, мощностью множества шифробозначений, равной ¹ = ¸ + 1, и одинаковыми априорными вероятностями шифробозначений, равными 1=¹ = 1=(¸+1), может быть расширен до эндоморфного совершенного шифра с мощностью множества шифрвеличин и шифробозначений, равными ¸ + 1.
Доказательство. Пусть дан неэндоморфный совершенный шифр с jXj = ¸, jY j = ¹ = ¸ + 1 и X = fx1; x2; :::; x¸g. Равенство 1=(¸ + 1) априорных вероятностей шифробозначений является необходимым условием, покажем, что оно является также и достаточным условием расширения данного шифра до ~ совершенного эндоморфного шифра с jXj = jY j = ¸ + 1.
Однозначно расширить данный шифр до эндоморфного шифра при jX~ j = jY j = ¸+1 можно добавлением биекции e~ такой, что, если e – инъекция зашифрования исходного шифра, т. е.
e : X ! Y; jXj = ¸; jY j = ¹ = ¸ + 1; то e~ : X~ = X [ fx¸+1g ! Y так, что e~(x) = ½ e(x) при x 2 X;
y; где fyg = Y ne(X) при x = x¸+1; имеем e~ : X~ ! Y (биекция), где X~ = fx1; x2; :::; x¸; x¸+1g.
Однозначно определенный таким образом шифр является совершенным, когда сумма вероятностей, соответствующих одному и тому же шифробозначению, равна 1=(¸ + 1) для каждого шифробозначения. Найдем
Pfe~(x¸+1) = yg = Pfy 2= e(X)g = Pfe(x1) 6= y & e(x2) 6= y & ::: & e(x¸) 6= yg = µ 1 = 1¡[Pfe(x1) = yg+Pfe(x2) = yg+:::+Pfe(x¸) = yg] = 1¡ ¸ + 1 + 1 ¸ + 1 + ::: +
1 ¶ ¸ + 1
¸ = 1¡ ¸ + 1 =
1 ¸ + 1 ; т. е. расширенный единственным образом шифр будет совершенным. Таким образом, рассмотрена задача обобщения теоремы Шеннона для совершенных по Шеннону шифров, в том числе неэндоморфных. Нетривиальность задачи подчеркивают содержащиеся в работе контрпримеры, показывающие, что даже для эндоморфных совершенных по Шеннону неминимальных шифров нет прямого обобщения (аналога) теоремы Шеннона. Построенные в работе примеры также показывают, что минимальность по числу ключей и минимальность по включению приводят к разным постановкам задач, требующих проведения дополнительных исследований для формулировки соответствующих аналогов теоремы Шеннона. Список литературы [1] K. Shannon. The theory of secret communication systems. Works on information theory and cybernetics.
М.: Nauka, 333–402, 1963. Natal’ya V. Medvedeva Ural State University of Railway Transport (Yekaterinburg, Russia)
Abstract. The article is devoted to the problem of description of general perfect ciphers (which are absolutely immune against the attack on ciphertext, according to Shannon). In terms of combinatorial analysis of convex sets in multidimensional space some analogs of the theorem of Shannon for non-minimal ciphers are formulated and proved. The examples emphasizing non-triviality of this task are constructed.
Keywords: perfect ciphers, non-endomorphic ciphers, non-minimal ciphers.