Конструкции неэндоморфных совершенных шифров | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/15

Конструкции неэндоморфных совершенных шифров

Исследуются совершенные по Шеннону (абсолютно стойкие к атаке по шифр-тексту) шифры. Получены достаточные условия того, что таблицы зашифрования неэндоморфных (эндоморфных) совершенных шифров не содержат латинских прямоугольников (квадратов). Приведён пример таких конструкций.

Constructions of non-endomorphic perfect ciphers.pdf Рассмотрим вероятностную модель Sb шифра [1]. Пусть X, Y - конечные множества соответственно шифрвеличин и шифробозначений, с которыми оперирует некоторый шифр замены, K - множество ключей, причём |X| = A, |Y| = |K| = п, где А > 1, ^ ^ A. Это означает, что открытые и шифрованные тексты представляются словами (t-граммами, t ^ 1) в алфавитах X и Y соответственно. Согласно [2, 3], под шифром Sb будем понимать совокупность множеств правил зашифрования и правил расшифрования с заданными распределениями вероятностей на множествах открытых текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. Описание эндоморфных (А = с минимально возможным числом ключей (|K| = = |Y|) совершенных шифров даёт теорема Шеннона, таблица зашифрования таких шифров - это латинский квадрат из равновероятных подстановок зашифрования [1]. Для неэндоморфных (А < минимальных совершенных шифров характерно большое многообразие таблиц зашифрования: они не сводятся только к латинским прямоугольникам размера ^ х А [4]. Для А = 2, например, таблицы зашифрования могут быть составлены и из неравновероятных инъекций. Однако если все ключи равновероятны, то данный совершенный шифр является выпуклой оболочкой латинских прямоугольников, содержащихся в его таблице зашифрования, согласно аналогу теоремы Биркгофа [5]. Если А > 2, то, даже для равновероятных инъекций зашифрования, неэндоморфный совершенный шифр может не содержать в своей таблице зашифрования латинских прямоугольников ^ х А [6]. Таким образом, при ^ > А возникает естественная задача описания минимальных по включению (т. е. шифров, содержащих минимально возможное множество ключей зашифрования с ненулевыми вероятностями) совершенных шифров, не сводящихся к латинским прямоугольникам размера ^ х А, которые можно рассматривать как непосредственное обобщение теоремы Шеннона. Данную задачу можно трактовать как задачу описания выпуклого полиэдра, соответствующего совершенным шифрам, через нахождение его вершин [5]. Подходом к решению такой задачи могут быть конструкции таблиц зашифрования, не содержащих латинских прямоугольников. Первым этапом решения задачи описания минимальных (по включению) совершенных шифров является построение таких конструкций для равновероятных ключей. При этом полезны достаточные условия отсутствия в таких таблицах латинских прямоугольников, тем более что в некоторых случаях эти условия оказываются необходимыми и достаточными. Более того, эти условия могут быть частью общей конструкции искомых таблиц зашифрования, так как любые два её столбца можно рассматривать как шифр с Л = 2, к которому применим аналог теоремы Биркгофа [5, 7]. Тем самым построение таблицы зашифрования при Л > 2 можно трактовать как расширение таблицы с Л = 2. Для равновероятных ключей латинские прямоугольники ^ х 2 всегда содержатся в таблице зашифрования с Л ^ 3 и поэтому достаточные условия должны включать в себя не менее трёх столбцов таблицы. Пример 1. Пусть таблица зашифрования с Л = 3 = |X|, где X = {x1,x2,x3} - множество (алфавит) шифрвеличин, содержит строки с ключами кг, kj, km с вероятностями pi,pj,pm соответственно и с шифробозначениями a,b,c, u,v,w е Y, где Y - множество шифробозначений, |Y | = k Xi X2 хз P ki a b u Pi kj v b c Pi km a w c pm Здесь шифробозначения a, b и c не входят в другие строки этой таблицы. Тогда данная таблица не может содержать латинских прямоугольников размеров ^ х 3. Действительно, если такой прямоугольник имеется, то он содержит либо строку ключа ki, либо строку ключа km, так как в столбце для шифрвеличины x1 шифробо-значение a больше не встречается. Если он содержит строку ki, то строка ключа km в него не входит, поэтому он должен содержать строку kj, так как в столбце x3 шиф-робозначение c больше не встречается. Тогда в столбце x2 шифробозначение b будет встречаться дважды, что невозможно в латинском прямоугольнике. Если же латинский прямоугольник содержит строку ключа ключа km, то строка ключа ki в него не входит из-за шифробозначения a в столбце x1. Тогда в нём содержится строка kj из-за шифробозначения b в столбце x2. Следовательно, в столбце x3 шифробозначение c будет встречаться дважды, что также невозможно в латинском прямоугольнике. Пример 1 иллюстрирует утверждение 1. Утверждение 1. Пусть a, b, c - различные шифробозначения, X = {x1, x2, x3} - множество шифрвеличин. При этом: 1) множество K ключей разбито на два непересекающихся подмножества K1 и K2, т. е. K = K1 U K2 и K1 П K2 = 0; 2) для любого ключа k е K1 шифрвеличина x2 на ключе k зашифровывается в шифробозначение b, т.е. ek(x2) = b; 3) существует такой ключ k е K1 , что шифрвеличина x1 на ключе k зашифровывается в шифробозначение a, т.е. ek(x1) = a; 4) для любого ключа k е K2 шифрвеличина x2 на ключе k зашифровывается в шифробозначение, отличное от шифробозначения b, т.е. ek(x2) = b; 5) существует единственный ключ k из K2, на котором шифрвеличина х1 зашифровывается шифробозначением а, а шифрвеличина х3 - шифробозначением с, т. е. ek(xi) = а и ek(x3) = с. Тогда таблица зашифрования не содержит латинских прямоугольников ^ х 3. Определение 1. Ключи k' и k" эквивалентны по шифрвеличине хг, если хг на ключах k' и k'' зашифровывается в одно и то же шифробозначение, т. е. k' = k'' ^ ek (хг) = ek" (хг). г Определение 2. Попарно различные ключи k1,k2,k3,..., kn-1, kn образуют цикл длины n, если выполняются условия k1 = k2 = k3 = ... = kn- 1 = kn = k1, i2 i3 i4 in-1 in ii где i2 = i3, i3 = i4, ..., in-1 = in, in = i1. Обозначим через [k]i смежный класс ключа k по отношению эквивалентности =: г [k]i = {k' G K : ek' (хг) = ek (хг)}. Утверждение 2. Пусть в таблице зашифрования с А = 3 = |X | ключи k1,k2, k3 образуют цикл длины три: k1 = k2 = k3 = k1, г2 г3 г1 где i1, i2, i3 -попарно различны, и при этом [k3]гз \\ [k1]i,2 = {k3}. Тогда инъекция ключа k1 не может быть строкой никакого латинского прямоугольника. Кроме того, если [k3]г1 С ([k1 ]г2 U fek) , то таблица зашифрования не содержит латинских прямоугольников. Из утверждения 2 следует достаточное условие отсутствия латинских квадратов в таблице зашифрования эндоморфного совершенного шифра с А ^ 3. Утверждение 3. Если в таблице зашифрования ключи k1,k2,...,kn образуют цикл нечётной длины, то данная таблица не содержит латинских прямоугольников. Таким образом, на основе отношения эквивалентности на множестве ключей получены достаточные условия того, что в таблице зашифрования неэндоморфных совершенных шифров отсутствуют латинские прямоугольники. В частности, получены достаточные условия того, что таблицы зашифрования эндоморфных совершенных шифров не содержат латинских квадратов.

Ключевые слова

совершенные шифры, эндоморфные шифры, неэндоморфные шифры, perfect ciphers, endomorphic ciphers, non-endomorphic ciphers

Авторы

ФИООрганизацияДополнительноE-mail
Медведева Наталья ВалерьевнаУральский государственный университет путей сообщениякандидат физико-математических наук, доцент, доцент кафедрыmedvedeva_n_v@mail.ru
Титов Сергей СергеевичУральский государственный университет путей сообщениядоктор физико-математических наук, профессорsergey.titov@usaaa.ru
Всего: 2

Ссылки

Шеннон К. Теория связи в секретных системах // Работы по теории информации и кибернетике. М.: Наука, 1963. С. 333-402.
Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. М.: Гелиос АРВ, 2001.
Зубов А. Ю. Совершенные шифры. М.: Гелиос АРВ, 2003.
Медведева Н. В., Титов С. С. Аналоги теоремы Шеннона для эндоморфных неминимальных шифров // Прикладная дискретная математика. Приложение. 2016. №9. С. 62-65.
Медведева Н. В., Титов С. С. Описание неэндоморфных максимальных совершенных шифров с двумя шифрвеличинами // Прикладная дискретная математика. 2015. №4 (30). С.43-55.
Медведева Н. В., Титов С. С. Геометрическая модель совершенных шифров с тремя шифрвеличинами // Прикладная дискретная математика. Приложение. 2019. №12. С.113-116.
Birkhoff G. D. Tres observations sobre el algebra lineal // Revista Universidad Nacional Tucuman. 1946. Ser.A. V.5. P. 147-151.
 Конструкции неэндоморфных совершенных шифров | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/15

Конструкции неэндоморфных совершенных шифров | ПДМ. Приложение. 2020. № 13. DOI: 10.17223/2226308X/13/15