Analogues of the shannon theorem for non-minimal endomorphic perfect ciphers.pdf В основе изучения совершенных шифров лежит математическая модель шифра. Впервые вероятностная модель шифра рассмотрена в фундаментальной работе К. Шеннона [1]. Пусть X, Y - конечные множества соответственно шифрвеличин и шифробозначений, с которыми оперирует некоторый шифр замены; K - множество ключей, причём |X| = Л, |Y| = |K| = п, где Л > 1, ^ ^ Л. Это означает, что открытые и шифрованные тексты представляются словами (£-граммами, £ ^ 1) в алфавитах X и Y соответственно. Согласно [2, 3], под шифром Sb будем понимать совокупность множеств правил зашифрования и правил расшифрования с заданными распределениями вероятностей на множествах открытых текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. В работе [1] полностью описаны эндо-морфные (|X| = |Y|) совершенные шифры с минимально возможным числом ключей (|K| = |Y|). Согласно теореме К. Шеннона [1], эндоморфные совершенные шифры с минимально возможным числом ключей исчерпываются шифрами табличного гам-мирования со случайной равновероятной гаммой. Существование неэндоморфных (|X| < |Y|) шифров [3, пример 2.2.10], а также шифров, минимальных не по числу ключей, а по включению (т. е. шифров, содержащих минимально возможное множество ключей зашифрования с ненулевыми вероятностями), оправдывает получение аналогов (обобщений) теоремы Шеннона для других совершенных шифров. К этому также приводит и задача изучения минимальных (по включению) транзитивных шифров, так как совершенный шифр является транзитивным. Допускает обобщение и само понятие совершенного по Шеннону шифра, что подтверждается изучением современных аналогов совершенных шифров [3]. В данной работе для обобщений теоремы Шеннона и построения примеров шифров используется вероятностная модель Sb, в которой, согласно подходу [2, 3], шифр задаётся распределением вероятностей ключей при £ = 1. Для эндоморфного (Л = шифра перечисляются в некотором порядке все возможные п = Л! подстановок зашифрования, соответствующих ключам k е K и определённым им вероятностям ключей. При этом допускается, что некоторые вероятности могут быть равны нулю - это означает, что соответствующая подстановка не используется в данном шифре. Получившийся п-мерный набор P вероятностей Pk ключей будем рассматривать как точку п-мерного пространства . Распределение биграмм, триграмм и т.д. может задаваться распределениями вероятностей при £ = 2, 3,... Задача описания шифров в вероятностной модели Sb приводит к описанию множества точек в пространстве , которые являются распределениями вероятностей ключей того или иного шифра. В работах [4-6] описано множество (полиэдр) матриц вероятностей ключей и множество вероятностей шифробозначений неэндоморфных совершенных шифров в случае, когда мощность Л множества шифрвеличин равна двум. По теореме Шеннона, минимальные по числу ключей эндоморфные совершенные шифры соответствуют тем точкам пространства , у которых все координаты равны нулю, кроме Л ненулевых координат, равных 1/Л, а сам набор координат соответствует набору ключей (подстановок), образующих латинский квадрат. Поскольку множество точек пространства , соответствующих совершенным шифрам, образует выпуклое множество (полиэдр), то и выпуклая оболочка этих точек также соответствует совершенным шифрам. Возникает вопрос: будет ли полученный таким образом полиэдр множеством распределений всех эндоморфных совершенных шифров? Для Л = ^ е {2, 3} ответ положительный. При Л = ^ = 2 - это классический шифр Вернама со сложением по модулю 2. При Л = ^ = 3 и K = {k1,k2,...,k6} имеем следующую таблицу зашифрования со всеми п = 3! = 6 подстановками из X = {х1,х2,хз} в Y = {1, 2, 3}, в которой точки P(1) и P(2) соответствуют латинским квадратам (табл. 1). Таблица 1 № K XI X2 хз Pfc P(i) Pfc P(2) Pfc 1 k 1 2 3 Pi 1/3 0 2 k2 1 3 2 P2 0 1/3 3 кз 2 1 3 Рз 0 1/3 4 2 3 1 Р4 1/3 0 5 к 3 1 2 Р5 1/3 0 6 кб 3 2 1 Рб 0 1/3 Утверждение 1. Любой эндоморфных совершенный шифр с мощностью множества шифрвеличин, равной трём, задаётся распределением вероятностей _(1) _(2) (1 11 \T п( 11 1 \T (а в в а а вV P = а P(1) +в P(2) = а -, 0, 0,-,-, 0 + в 0,-,-, 0, 0,- = -,-,-,-,-,- , и V3' ' '3'3' у ^33 з) V3 3 3 3 3 3/ ' а, в ^ 0, а + в = 1, лежащим в выпуклой оболочке точек P(1), P(2) Е R6. Это утверждение означает, что искомое выпуклое множество (полиэдр) - отрезок в шестимерном пространстве. При А = ^ > 3 выпуклая оболочка совершенных по Шеннону шифров с минимальным числом ключей является лишь частью множества точек, соответствующих совершенным шифрам. Например, при А = ^ = 4 существуют минимальные (по включению) совершенные шифры, не содержащие в себе наборов ключей (подстановок), образующих латинский квадрат. Пример 1. Рассмотрим эндоморфный шифр в случае, когда мощность множества шифрвеличин равна четырём. Пусть X = {ж1,ж2,ж3,ж4} - множество шифрвеличин; Y = {1, 2, 3, 4} -множество шифробозначений, K = {k1, k2,..., } -множество ключей. Таблица зашифрования данного шифра, составленная из единичной и всех шести одноцикловых подстановок группы S4, приведена в табл. 2. Таблица 2 № K Xi X2 хз X4 Pfc 1 ki 1 2 3 4 1/4 2 k2 2 4 1 3 1/8 3 кз 3 1 4 2 1/8 4 k4 4 3 1 2 1/8 5 k,5 3 4 2 1 1/8 6 кб 2 3 4 1 1/8 7 kr 4 1 2 3 1/8 Это совершенный эндоморфный шифр. Здесь одноцикловые подстановки f группы S4 обладают свойством: для каждой подстановки f имеется ровно четыре различных других одноцикловых подстановок g, таких, что f (i) = g(i), i = 1, 2, 3, 4. Следовательно, максимальные четырехстолбцовые латинские прямоугольники в этой таблице состоят из трёх строк вида e, f, f-1 и латинских квадратов нет. Пример 2. Рассмотрим таблицы зашифрования эндоморфных шифров при Л ^ = 4 с произвольными вероятностями ключей (табл. 3 и 4). Таблица 3 Таблица 4 № K Xl X2 X3 x4 1 hi 1 4 3 2 2 k2 1 3 2 4 3 h3 2 1 3 4 4 h4 3 2 4 1 5 h5 4 2 1 3 № K Xl X2 X3 X4 1 hi 4 1 2 3 2 h2 3 4 1 2 3 h3 2 3 4 1 4 h4 1 2 4 3 5 h5 4 1 3 2 6 he 2 3 1 4 Это минимальные (по включению) транзитивные шифры, которые не могут быть совершенными ни при каких распределениях вероятностей ключей, причём из их таблиц зашифрования невозможно извлечь латинский квадрат. Таким образом, в работе рассмотрена задача обобщения теоремы Шеннона для эндоморфных совершенных шифров. Построены примеры, показывающие, что минимальность шифра по числу ключей и минимальность по включению приводят к разным постановкам задач.

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