The criterion of minimum perfect ciphers with respect to inclusion.pdf В рамках вероятностной модели шифра Ев [1] рассмотрим произвольный совершенный по Шеннону шифр. Пусть X, Y - конечные множества соответственно шифр-величин и шифробозначений, с которыми оперирует некоторый шифр замены, K - множество ключей, |Х | = Л, |Y | = ц, |К | = п, где Л > 1, ц Л, п ц. Это означает, что открытые и шифрованные тексты представляются словами (^-граммами, £ 1) в алфавитах X и Y соответственно. Согласно [2, 3], под шифром Ев будем понимать совокупность множеств правил зашифрования и правил расшифрования с заданными распределениями вероятностей на множествах открытых текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. Описание эндоморфных (Л = ц) с минимально возможным числом ключей (|K| = = | Y| ) совершенных шифров даётся теоремой Шеннона, таблица зашифрования таких шифров - это латинский квадрат из равновероятных подстановок зашифрования [1]. При описании неэндоморфных (Л < ц) совершенных шифров, как показано в [4], возникает естественная задача описания минимальных по включению (т. е. содержащих минимально возможное множество ключей зашифрования с ненулевыми вероятностями) совершенных шифров, не сводящихся к латинским прямоугольникам размера цх Л, которые можно рассматривать как непосредственное обобщение теоремы Шеннона. На первом этапе реализации данного подхода в работах [4, 5] получены достаточные условия того, что в таблице зашифрования как неэндоморфных, так и эндоморфных совершенных шифров с равновероятными ключами отсутствуют латинские соответственно прямоугольники и квадраты. В [5] на основе графового подхода к исследованию и описанию совершенных шифров, их аналогов и обобщений сформулировано достаточное условие минимальности шифра по включению. Пусть дана таблица зашифрования совершенного шифра Ев с Л столбцами, п строками и ц шифробозначениями yj, j = 1, 2,... , ц, где п ц Л > 1. Обозначим через P = (P1, P2,..., Pn )T вектор-столбец вероятностей Pk ключей k (k = 1, 2,...,п), через pj - априорные вероятности шифробозначений yj (j = 1, 2,... , ц) данного шифра. Для исходной таблицы зашифрования построим соответствующую ей (0, 1)-матрицу A с п строками и Лц столбцами следующим образом: 1) каждому столбцу xi таблицы зашифрования поставим в соответствие ц столбцов и занумеруем все получившиеся Лц столбцы индексами (i, j), где i = 1, 2, . . . , Л, j = 1, 2, . . . , ц; 2) на пересечении строки k (k = 1, 2, и столбца (i,j) поставим единицу тогда и только тогда, когда ek(xi) = yj, т. е. если шифрвеличина xi на ключе k зашифровывается в шифробозначение yj . В противном случае ставим нуль. Соответствие таблицы зашифрования и матрицы A, можно считать, получено посредством замены каждого i-го столбца в таблице зашифрования на ц столбцов матрицы A, индексированных парами (i,j), где i = 1,2,..., Л, j = 1,2,...,ц. Столбцы матрицы A можно упорядочить и занумеровать, например, естественным образом, присвоив индексу (i, j) номер m = (i - 1)ц + j, так что Лц m 1. Используя (0,1)-матрицу A, для которой Ak,(i,j) = 1 ek(xi) = yj, условие совер шенности шифра можно записать в виде системы линейных уравнений PkAk’(i’j) = pj (i = 1,2,...,Л, j = 1,2,...,ц) (1) k=1 с дополнительным условием Pk = 1. (2) k=1 К матрице A добавим столбец из п единиц. При предлагаемом способе упорядочивания столбцов этому столбцу естественно присвоить номер m = 0 и считать его добавленным к матрице A слева. В вектор правых частей добавим 1 (в соответствии с уравнением (2)). Получившуюся матрицу размером п строк на 1 + Лц столбцов обозначим через A, а вектор правых частей - через p = (1,p1,... ,pM,... ,p1,... ,pM)T, при этом rank A С п. Теорема 1. Множество ключей шифра минимально тогда и только тогда, когда ранг матрицы A максимальный (равный п). Доказательство. Рассматривая вероятности Pk ключей как неизвестные ненулевые искомые величины уравнений (1), а вероятности pj - как их правые части, по теореме Кронекера - Капелли заключаем, что, поскольку система имеет решение, ранг матрицы A4 равен рангу расширенной (посредством вектора p4 = = (1,pi,... ,pM,... , p1,... ,pjU)T) матрицы. Максимально возможный ранг матрицы >1 равен количеству её строк - п. Предположим, что данный шифр не является минимальным по включению. Докажем, что тогда ранг матрицы A4 меньше п. Действительно, пусть существует шифр с вероятностями ключей Pk с теми же правыми частями pj, в котором отсутствуют некоторые ключи из данного набора. Этот факт можно отразить в системе уравнений (1), (2), положив вероятности отсутствующих ключей равными нулю. Так, пусть без ограничения общности ключ k = п отсутствует, тогда система уравнений (1), (2) имеет решение, в котором РП = 0. Заметим, что неизвестные Pk = Pk - Pk (k = 1,... , п) не все равны нулю (например, Pn = 0) и удовлетворяют однородной системе уравнений, откуда следует, что в матрице A4 не может быть невырожденной квадратной подматрицы максимального размера п на п, т. е. её ранг строго меньше п. Обратно, пусть ранг матрицы A4 строго меньше п. Докажем, что данный шифр не является минимальным по включению. Действительно, в этом случае одна из строк матрицы A4 (без ограничения общности пусть это п-я строка) есть линейная комбинация остальных. Пусть П-1 An,(i,j) qkAk’(i’j), qk G R (i 1, 2,...,Л j 1, 2, ... , ц). k=1 Для каждого t G [0,1] введём новые неизвестные Pzk = Pk +qkt Pn (k = 1,... ,n - 1), РП = (1 - t) Pn, где q1 + q2 + ... + qn-1 = 1 из-за столбца единиц в матрице A. В силу тождества 12 Pk Ak,(i,j) = Pk Ak,(i,j) + Pn An,(i,j) = Pk Ak,(i,j) + [t Pn +(1 - t) Pn]An,(i,j) k=1 k=1 n-1 + (1 - t) pn An,(i,j) = Pk Ak,(i,j) + t Pn Г qkAk,(i,j) k=1 = S (Pk +tqk Pn)Ak,(i,j) + (1 - t) Pn An,(i,j) = / I Pk Ak,(i,j) k=1 эти новые неизвестные P'k удовлетворяют той же системе уравнений. Поскольку P'k = = Pk > 0 при t = 0 и линейная функция непрерывна, имеем Pk > 0 при всех достаточно малых t > 0. Ввиду того, что A является (0,1)-матрицей и все координаты вектора p положительны, среди чисел qk должны быть и положительные; для таких ключей k имеем Pk > 0 для всех t > 0. Если для всех k = 1,... , п - 1 имеем Pk > 0 при всех t G [0,1], то при t =1 получаем РП = 0, Pzk > 0 (k = 1,... , п - 1), причём П-1 П-1 Е Pk = I- Pk = 1 k=1 k=1 для любого t ввиду равенства П- 1 qk = 1. k=1 Следовательно, величины Pk (k = 1,..., п - 1) могут рассматриваться как вероятности ключей собственного подмножества ключей данного шифра, так как Pn = 0. Если же Pk = 0 при некотором k = k0 и t = t0, 0 < t0 < 1, то, выбрав t0 наименьшим по всем таким k, получим тоже собственное подмножество ключей с ненулевыми вероятностями Pk, что доказывает неминимальность данного шифра по включению. ■ Отметим, что для эндоморфного шифра равенство q1 + ... + qn-1 = 1 выполняется уже при рассмотрении матрицы A без использования столбца из единиц. Замечание 1. Из критерия минимальности по включению совершенных шифров следуют необходимые условия: 1) для минимальности по включению множества ключей шифра необходимо выполнение неравенства п Л//.; 2) для эндоморфного минимального по включению совершенного шифра выполняется неравенство п Л(Л - 1). Полученные теоретические результаты могут быть положены в основу классификации минимальных совершенных шифров и исследований почти совершенных шифров [6, 7]. Таким образом, сформулирован и доказан критерий минимальности множества ключей совершенных шифров: множество ключей минимально, если и только если ранг бинарной матрицы, состоящей из п столбцов и 1 + Л//. столбцов, максимален и равен количеству ключей, содержащихся в таблице зашифрования. Получены также необходимые условия минимальности по включению совершенных шифров.

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