Геометрическая модель совершенных шифров с тремя шифрвеличинами | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/35

Геометрическая модель совершенных шифров с тремя шифрвеличинами

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

Geometric model of perfect ciphers with three cipher plaintext values.pdf Рассмотрим вероятностную модель Уд шифра [1-3]. Пусть X, Y - конечные множества соответственно шифрвеличин и шифробозначений, с которыми оперирует некоторый шифр замены; K - множество ключей, причём |X| = Л, |Y| = |K| = п, где Л > 1, ^ ^ Л. Это означает, что открытые и шифрованные тексты представляются словами (t-граммами, t ^ 1) в алфавитах X и Y соответственно. Согласно [2, 3], под шифром Уд будем понимать совокупность множеств правил зашифрования и правил расшифрования с заданными распределениями вероятностей на множествах открытых текстов и ключей. Шифры, для которых апостериорные вероятности открытых текстов совпадают с их априорными вероятностями, называются совершенными. В работе [1] полностью описаны эндоморфные (X = Y) совершенные шифры с минимально возможным числом ключей (|K| = |Y|). Согласно теореме К. Шеннона [1], эндоморф-ные совершенные шифры с минимально возможным числом ключей исчерпываются шифрами табличного гаммирования со случайной равновероятной гаммой. Данная работа является продолжением исследования [4] проблемы описания совершенных по Шеннону шифров. Здесь для обобщений теоремы Шеннона и построения примеров используется вероятностная модель Sb шифра, в которой, согласно подходу [2, 3], шифр задаётся распределением вероятностей ключей при £ =1. Для эндоморфного (X = Y) и неэндоморфного (|X| < |Y|) шифров перечисляются в некотором порядке все возможные птах = - 1) • ... • (^ - Л +1) инъекций зашифрования, соответствующие ключам k G K и их вероятностям Pk. При этом допускается, что некоторые вероятности Pk могут быть равны нулю. Это означает, что соответствующая инъекция не используется в данном шифре. Получившийся nmax-мерный набор P вероятностей Pk ключей будем рассматривать как точку птах-мер-ного пространства Rnmax. Распределение биграмм, триграмм и т.д. может задаваться распределениями вероятностей при £ = 2, 3,..., что приводит к усложнению геометрической модели. Задача описания шифров в вероятностной модели Sb приводит к описанию множества точек в пространстве Rnmax, которые являются распределениями вероятностей ключей того или иного шифра. По теореме Шеннона, минимальные по числу ключей эндоморфные совершенные шифры соответствуют тем точкам пространства Rnmax, у которых все координаты равны нулю, кроме Л ненулевых координат, равных 1/Л, а сам набор координат соответствует набору ключей (инъекций), образующих латинский квадрат. Поскольку множество точек пространства Rnmax, соответствующих совершенным шифрам, образует выпуклое множество (полиэдр [5]), то и выпуклая оболочка этих точек также соответствует совершенным шифрам. Однако могут быть совершенные шифры, соответствующие точкам вне этой выпуклой оболочки. В работе [4] показано, что в случае, когда мощность алфавита шифрвеличин равна двум, множество возможных значений априорных вероятностей шифробозначений = P{y = ys} = P{y = s}, где s = 1,...,^, допускает описание на основе теоремы Биркгофа о классификации дважды стохастических матриц [6]. В [4] описано выпуклое множество (полиэдр) матриц вероятностей ключей и множество вероятностей шифробозначений неэндоморфных совершенных шифров в случае, когда мощность множества шифрвеличин равна двум. Полиэдр описан через указание его вершин (экстремальных точек), которые представляют собой так называемые нормальные циклы. В [7] в терминах комбинаторного анализа выпуклых множеств многомерного пространства сформулированы и доказаны некоторые обобщения (аналоги) теоремы Шеннона для совершенных по Шеннону эндоморфных неминимальных (|K| > |Y|) шифров. В частности, показано, что для любого эндоморфного совершенного шифра с мощностью множества шифрвеличин Л = ^ = 3 искомый полиэдр - это отрезок в шестимерном пространстве. Построены примеры, показывающие, что минимальность шифра по числу ключей и минимальность по включению (т.е. шифры, содержащие минимально возможное множество ключей зашифрования с ненулевыми вероятностями) приводят к разным постановкам задач обобщения теоремы Шеннона. Неэндоморф-ные совершенные шифры с Л = 3 и ^ = 4 дополняются до эндоморфных, и притом единственным образом. Утверждение 1. При п = 5 или 6 не существует минимальных по включению совершенных шифров. Утверждение 2. При п = 7 существует 4! = 24 минимальных по включению совершенных шифров. Все такие шифры получены перестановкой столбцов в таблице зашифрования эндо-морфного совершенного шифра, составленной из единичной подстановки и всех шести полноцикловых подстановок группы S4 [7] (табл. 1). Утверждение 3. При п = 8 существует 4 • 4! = 96 минимальных по включению совершенных шифров. Рассмотрим восемь подстановок (табл.2), где {a,b,c,d} = {1, 2, 3, 4}. Данное множество подстановок не содержит латинских квадратов. Перестановкой столбцов и переименованием элементов a, b, c, d снова получаются восемь подстановок ключей с вероятностями 1j8. Та б л и ц а 1 Т а б л и ц а 2 № K Xi X2 хз x4 P k 1 ki a d b c 1/8 2 k2 a d c b 1/8 3 k3 b c d a 1/8 4 k4 b a d c 1/8 5 k5 c a b d 1/8 6 k6 c b a d 1/8 7 kr d b c a 1/8 8 kg d c a b 1/8 № K Xi X2 хз x4 Pk 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 k5 3 4 2 1 1/8 6 k6 2 3 4 1 1/8 7 kr 4 1 2 3 1/8 В случае равновероятных шифробозначений совершенный шифр с мощностью множества шифрвеличин, равной трём, и ^ > 4 может быть дополнен до эндоморфного, но не едиственным способом. Пример 1. Рассмотрим неэндоморфный шифр с множеством из трёх шифрвеличин. Пусть X = {xi,x2,x3} = {1, 2, 3} -множество шифрвеличин; Y = {y1,y2,y3, y4,y5} = {1, 2, 3, 4,5} - множество шифробозначений; K = {k1, k2,... , kn} - множество ключей. Таблица зашифрования данного шифра (табл. 3) не содержит латинских прямоугольников размера 5 х 3. Та б л и ц а 3 № K xi X2 X3 Pk 1 ki 1 2 3 1/5 2 k2 2 3 4 1/10 3 k3 2 1 5 1/10 4 k4 3 4 5 1/10 5 k5 3 5 1 1/10 6 k6 4 5 2 1/10 7 kr 4 3 1 1/10 8 kg 5 1 4 1/10 9 kg 5 4 2 1/10 Это совершенный эндоморфный шифр, дополняемый двумя способами (при фиксировании первой строки) до эндоморфного совершенного шифра с Л = ^ = 5 без латинских квадратов (табл.4 и 5). Таблица 4 Таблица 5 № K X1 X2 хз X4 X5 Pk 1 k1 1 2 3 4 5 1/5 2 k2 2 3 4 5 1 1/10 3 k3 2 1 5 3 4 1/10 4 k4 3 4 5 1 2 1/10 5 k5 3 5 1 2 4 1/10 6 k6 4 5 2 3 1 1/10 7 k7 4 3 1 5 2 1/10 8 k8 5 1 4 3 2 1/10 9 kg 5 4 2 1 3 1/10 Таким образом, в работе рассмотрена задача построения геометрической модели совершенных по Шеннону шифров с мощностью множества шифрвеличин равной трём. Показано, что не существует минимальных по включению совершенных шифров с четырьмя шифробозначениями и пятью или шестью ключами зашифрования. Определено количество минимальных по включению совершенных шифров, содержащих семь ключей зашифрования, а также количество совершенных шифров с числом ключей равным восьми. Построены примеры минимальных по включению совершенных шифров.

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

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

Авторы

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

Ссылки

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

Геометрическая модель совершенных шифров с тремя шифрвеличинами | ПДМ. Приложение. 2019. № 12. DOI: 10.17223/2226308X/12/35