To the task of description minimal by inclusion perfect ciphers.pdf Рассматривается вероятностная модель Ев шифра [1]. Пусть X, Y - конечные множества соответственно шифрвеличин и шифробозначений, с которыми оперирует некоторый шифр замены, K - множество ключей, причём |X| = A, |Y| = ц, |К| = п, где A > 1, ц A. Открытые и шифрованные тексты представляются словами (^-граммами, £ 1) в алфавитах X и Y соответственно. Согласно [2, 3], под шифром Ев будем по нимать совокупность множеств правил зашифрования и правил расшифрования с заданными распределениями вероятностей на множествах открытых текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. Получение строгих доказуемых оценок стойкости для каждого конкретного шифра - это очень сложная, актуальная и до конца не решённая проблема криптоанализа. Различают теоретическую и практическую стойкость шифров (оцениваемую через ресурсы, требуемые на взлом), которую естественно описывать как вероятность успеха в противодействии атакам различного вида. Здесь впечатляющим результатом представляется теорема Шеннона [1] о совершенных (абсолютно стойких к атакам по шифртексту) шифрах, которую можно (нестрого) сформулировать так: атака по шифртексту на совершенный шифр бессмысленна, так как пассивный злоумышленник, перехватив зашифрованный текст, не получает никакой информации (кроме длины сообщения) об исходном открытом тексте. Но совершенный шифр не стоек к атакам активного злоумышленника (который может подменить или модифицировать сообщение). Перспективным является изучение шифров, близких к совершенным, в том числе «приближённо совершенных» [4, 5]. Для таких шифров теорему Шеннона можно переформулировать - в виде теоремы А. Ю. Зубова - следующим образом: атака по шифртексту на почти совершенный шифр почти бессмысленна. При этом такие шифры приобретают дополнительные полезные свойства. Современные аналоги совершенных шифров пытаются бороться с атаками имитации и подмены, отказываясь от эн-доморфности (Л = ц), внося информационную избыточность за счёт имитовставок и других приёмов, в том числе повышающих помехоустойчивость. Однако эта проблематика в данный момент не считается центральной - например, потому, что имеется много других более актуальных назревших нерешённых задач. Тем более что она признаётся достаточно сложной, но остающейся в поле зрения исследователей в связи с другими смежными комбинаторными задачами. Кроме этого, данные исследования могут быть применены для обобщений на почти совершенные шифры. Описание эндоморфных с минимально возможным числом ключей (|K| = |Y |) совершенных шифров даётся теоремой Шеннона, таблица зашифрования таких шифров - это латинский квадрат из равновероятных подстановок зашифрования [1]. Для неэндоморфных (Л < ц) минимальных совершенных шифров характерно большое многообразие таблиц зашифрования: они не сводятся только к латинским прямоугольникам размера ц х Л [6]. Для Л = 2, например, таблицы зашифрования могут быть составлены и из неравновероятных инъекций. Однако если все ключи равновероятны, то данный совершенный шифр является выпуклой оболочкой латинских прямоугольников, содержащихся в его таблице зашифрования, согласно аналогу теоремы Биркгофа [7]. Если Л > 2, то даже для равновероятных инъекций зашифрования неэндоморфный совершенный шифр может не содержать в своей таблице зашифрования латинских прямоугольников ц х Л [8]. Описание минимальных по включению (т. е. шифров, содержащих минимально возможное множество ключей зашифрования с ненулевыми вероятностями) неэндоморфных совершенных шифров, не сводящихся к латинским прямоугольникам размера ц х Л, может быть осуществлено с помощью конструкций таблиц зашифрования, не содержащих латинских прямоугольников. Первый этап реализации данного подхода - это построение таких конструкций для шифробозначений, априорные вероятности которых считаются равными. В работе [9] на основе отношения эквивалентности на множестве ключей получены достаточные условия того, что в таблице зашифрования неэндоморфных (эндоморфных) совершенных шифров отсутствуют латинские прямоугольники (квадраты). В частности, получены достаточные условия того, что таблицы зашифрования эндоморфных совершенных шифров не содержат латинских квадратов. Определение 1 [9]. Ключи к1 и к11 эквивалентны по шифрвеличине xi, если xi на ключах к1 и к11 зашифровывается в одно и то же шифробозначение, т. е. к' = к” О ey(xi) = ey(xi), i при этом в обозначении эквивалентности ключей используется биекция: i о xi. Определение 2 [9]. Попарно различные ключи к1,к2,к3,... ,кп-1,кп образуют цикл длины n, если выполняются условия к1 = к2 = к3 = ... = кп-1 = кп = к1, i2 i3 i4 in-1 in i1 где i2 = i3 , i3 = i4 , . . . , in-1 = in , in = i1 . Следующим за минимальными по Шеннону шифрами по количеству ключей идёт класс минимальных по включению шифров, в которых для каждой пары (x, y ) шифр-величины x и шифробозначения y имеется не более двух ключей k, на которых x зашифровывается в y . В каждом столбце таблицы зашифрования каждое шифробо-значение y встречается, следовательно, не более двух раз. При ц = 4 такие таблицы построены для семи и восьми ключей [8]. При ц = 5 такие таблицы тоже могут быть построены. Пример 1. Рассмотрим эндоморфный шифр с множеством из пяти шифр-величин. Пусть X = {x1, x2, x3, x4, x5} = {1, 2, 3, 4, 5} -множество шифрвели-чин; Y = {y1,y2,y3,y4,y5} = {1,2, 3,4,5} - множество шифробозначений; K = = {k1,k2,... ,kn} -множество ключей. Таблицы зашифрования (табл. 1 и 2) совершенного эндоморфного шифра с Л = ц = = 5 и вероятностями ключей P1 = 0,2 и P2 = . . . = P9 = 0,1 не содержат латинских квадратов. Та б л и ц а 1 № п/п K Xi X2 хз X4 X5 Pk 1 ki 1 2 3 4 5 0,2 2 k2 2 3 4 5 1 0,1 3 кз 2 5 1 3 4 0,1 4 к4 3 4 5 1 2 0,1 5 к5 3 1 2 5 4 0,1 6 кб 4 5 2 3 1 0,1 7 к7 4 3 5 1 2 0,1 8 к8 5 1 4 2 3 0,1 9 к9 5 4 1 2 3 0,1 Та б л и ц а 2 № п/п K Xi X2 хз X4 X5 Pk 1 ki 1 2 3 4 5 0,2 2 k2 2 3 4 5 1 0,1 3 кз 2 5 1 3 4 0,1 4 к4 3 4 5 1 2 0,1 5 к5 3 1 2 5 4 0,1 6 кб 4 5 1 3 2 0,1 7 к7 4 3 5 2 1 0,1 8 к8 5 1 4 2 3 0,1 9 к9 5 4 2 1 3 0,1 Для шифров, в которых для каждой пары (x, y) шифрвеличины x и шифробозначе-ния y имеется не более двух ключей k, на которых x зашифровывается в y, естественно определить граф на множестве ключей, а именно: два различных ключа (соответствующих разным инъекциям зашифрования) соединим ребром, если существует такая пара (x, y), что на обоих этих ключах шифрвеличина x зашифровывается в y. Пример 2. Рассмотрим графы, соответствующие шифрам с табл. 1 и 2. Ясно, что ключи k с вероятностью Pk = 0,2 представляют собой изолированные вершины. Шифру с табл. 1 соответствует граф эквивалентности ключей, изображённый на рис. 1. Из рис. 1 и табл. 1 видно, что ключи k2, k3, k5 образуют цикл длины три: k2 = кз = k5 = к2; 245 а ключи k3, k4, k6, k7, k9 образуют цикл длины пять: k9 k3 k6 k7 k4 k9. 9 1 3 4 6 2 7 5,1,2 4 4 9 Рис. 1. Граф 1 Шифру с табл. 2 соответствует граф эквивалентности ключей, изображённый на рис. 2. Из рис. 2 и табл. 2 видно, что ключи k2 , k3 , k5 образуют цикл длины три: k2 = кз = k5 = k2; 245 а ключи k2, k4, k5, k8, k9 образуют цикл длины пять: k2. 4,1 5,3 4 k2 = k5 = k4 = k9 = k8 = 5 3 4 , 1 5 , 3 4 Рис. 2. Граф 2 Утверждение 1. Пусть в некоторой неодноэлементной связной компоненте графа эквивалентности ключей шифра существует цикл нечётной длины. Тогда данный шифр минимален по включению. Таким образом, в работе предложен графовый подход к исследованию и описанию совершенных шифров, их аналогов и обобщений. В рамках предлагаемого подхода доказано утверждение (достаточное условие минимальности шифра по включению), которое может служить основой для дальнейших обобщений; приведены примеры, иллюстрирующие эффективность подхода. Полученные результаты могут быть применены и для изучения почти совершенных шифров.

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