Non-endomorphic perfect ciphers with two elements in plaintext alphabet.pdf Впервые вероятностная модель шифра рассмотрена в фундаментальной работе К. Шеннона [1]. Пусть X, Y - конечные множества соответственно шифрвеличин и шифробозначений, с которыми оперирует некоторый шифр замены, K - множество ключей, причём |X| = Л, |Y| = |K| = п, где ^ ^ Л > 1. Согласно [2, 3], под шифром Sb будем понимать совокупность множеств правил зашифрования и расшифрования с заданными распределениями вероятностей на множествах £-грамм открытых текстов, шифрованных текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. Изучение неэндоморфных (|X| < |Y|) совершенных шифров в общем виде предполагает знание распределения вероятностей на множестве £-грамм алфавита открытых текстов. В качестве стандартного аппарата исследования распределения вероятностей на £-граммах используются дважды стохастические матрицы [4]. Шифры, содержащие все инъекции из X в Y, называются максимальными. В [5] показано, что неминимальный (|K| > |Y|) совершенный шифр вкладывается в максимальный совершенный шифр. Данная работа является продолжением [5]. Здесь описаны матрицы вероятностей ключей неэндоморфных совершенных шифров и множества вероятностей шифробо-значений в случае, когда мощность множества шифрвеличин равна двум. Рассмотрим неэндоморфный максимальный совершенный шифр в случае, когда мощность множества шифрвеличин равна двум. Пусть X = {x^x2}; Y = {y1,y2, ... ,Ум} = {1, 2,..., K = {fcb k2,..., kn}. Здесь |X| = Л = 2, |Y| = ц ^ 2, |K| = п = = - 1). Зашифрование открытого текста x = xi2... xi£, где xj G X, т.е. j G {1, 2}, заключается в замене каждой шифрвеличины xj некоторым шифробозначением yj в соответствии со случайно выбранным одним из |K| = A|X| = AM = - 2)! = = - 1) = п всех инъективных отображений : X ^ Y, индексированных ключами k G K. Инъективное отображение ek, k G K, при котором ek(x1) = ys = s и ek(x2) = = yt = t, будем также обозначать est, где s, t = 1,..., Пусть Pst - вероятность того, что при зашифровании шифрвеличины Xij , ^ j G G {1, 2}, будет выбрано инъективное отображение est: Pst = P{est(x1) = s & est(x2) = t}, где s = t. Если s = t, то, в силу инъективности, Pst = 0. Обозначим через P = ||Pst||Mt=1 квадратную матрицу порядка такую, что Vs (Jt Pt = Ps) , Vt (Jt Pst = Pt) , P1 + ... + Pm = 1. (1) Отметим, что, как указано в [3], совершенный по Шеннону шифр является сильно совершенным, т. е. не зависит от распределения на множестве шифрвеличин. Поэтому распределения вероятностей на множестве шифробозначений, индуцированные априорными распределениями вероятностей на множестве ключей, будем называть априорными. Требуется описать множество возможных значений априорных вероятностей шифробозначений ps = P{y = s}, s = 1,... , и найти общий вид матрицы P, удовлетворяющей условию (1) совершенности шифра, в зависимости от значений вероятностей ps. Согласно подходу [2, 3], для вероятностной модели SB шифра это достаточно сделать при £ =1. Для решения поставленной задачи будем использовать критерий совершенности шифра (2.2.4) из [3], который равносилен условию (1). В частности, в примере 2.2.10 из [3] X = {x1,x2}, Y = {y1,y2,y3} = {1, 2, 3}, K = = {k1, k2,..., k6}, т. е. при Л = 2, ^ = 3, п = 6 таблица зашифрования имеет следующий вид: K\X xi X2 Pst = P{est(xi) = s & est(x2) = t} ki 1 2 P12 = P{k = k1} = 19/80 k2 1 3 P13 = P{k = k2} = 3/20 кз 2 1 P21 = P{k = кз} = 21/80 k4 2 3 P23 = P{k = k4} = 1/10 k5 3 1 P31 = P{k = k5} = 1/8 ke 3 2 P32 = P{k = ke} = 1/8 При этом выполняются равенства: Р1 = P{y = 1|x = X!} = Pi2 + Pis = 31/80; p = P{y = 1|x = X2} = P21 + P31 = 31/80; P2 = P{y = 2|x = Xi} = P21 + P23 = 29/80; P2 = P{y = 2|x = X2} = P12 + P32 = 29/80; Ps = P{y = 3|x = xi} = P31 + P32 = 1/4; ps = P{y = 3|x = X2} = Pis + P23 = 1/4, т.е. априорные и апостериорные (условные) вероятности шифробозначений i = = 1, 2, 3, равны. Это, согласно критерию (2.2.4) из [3], означает, что матрица P11 P12 P13 0 19/80 3/20 P21 P22 P23 I =1 21/80 0 1/10 P31 P32 P33 1/8 1/8 0 ||Pst ||3,t=1 P удовлетворяет условию (1) совершенности шифра. Для матрицы P с неотрицательными элементами, удовлетворяющей условию (1) в силу теоремы Биркгофа [4] справедливы равенства Е pz pZ , Е P 1, Pz Z С{1,2,...,^}, Z=0 Z С{1,2,...,^}, Z=0 где Z - непустое множество номеров строк и столбцов; pz ^ 0 и Pz - главные подматрицы равновероятных распределений. Теорема 1. Матрица P с неотрицательными элементами, удовлетворяющая условию (1), лежит в выпуклой оболочке главных подматриц Pz равновероятных распределений и определяется формулой (2). При Л = 2 и ^ = 3 матрица P в общем случае определяется формулой 0 1 + 0 1 0 001 100 000 10 00 b + 3 p = a 3 + 2 1 2 1 0 0 0 0 0 1 000 100 d +d + 2 1 00 2 1 0 1 0 0 1 100 010 / 0 a/3 + c/2c b/3 + d/2 1 I = I b/3 + c/2 0 a/3 + e/2 0 J \ a/3 + d/2 b/3 + e/2 0 где a, b, c, d, e ^ 0 - произвольные параметры, такие, что a + b + c + d + e = 1. Отметим, что для любых a,e ^ 0, где 2a + 3e = 3/5, и однозначно по ним определённым параметрам b = a + 3/40, c = e + 11/40, d = e + 1/20, получаются числовые значения примера 2.2.10 из [3]. В частности, они получаются при крайних значениях параметров: a = 0, e = 1/5 и a = 3/10, e = 0. Теорема 2. Набор чисел p1,... ,рм при ^ ^ 2 может быть набором априорных вероятностей шифробозначений совершенного шифра в модели Уд с мощностью множества шифрвеличин, равной двум, тогда и только тогда, когда эти числа удовлетворяют условиям 1 P1 + ... + Рм = 1, 0 ^ Pi ^ 2 (i Таким образом, описаны матрицы вероятностей ключей неэндоморфных совершенных шифров и множества вероятностей шифробозначений в случае, когда мощность множества шифрвеличин равна двум. Отметим, что при Л > 2 эта задача сильно усложняется ввиду отсутствия аналога теоремы Биркгофа о дважды стохастических матрицах.

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