On the anisometric index of a transformation.pdf Многие методы криптоанализа основаны на существовании структур, сохраняемых или слабо рассеиваемых криптографическими преобразованиями. Такие структуры часто связаны с их группами автоморфизмов, например линейные структуры (векторные пространства) и аффинная группа, системы импримитивности и сплетения групп, метрические пространства и группы изометрий. Первые две используются в линейном и разностном методах, а также в методе гомоморфизмов. Для криптоанализа могут представлять интерес и другие структуры. Степень несохранения структуры при действии преобразования можно определять различными способами. В [1] в качестве такой меры для разбиения (структуры) W = {W0,... , Wr-1} с равномощными блоками n-мерного векторного пространства Vn над полем GF(2) выступает порядок W-примитивности, который относительно метрики Хемминга х на симметрической группе S (Vn) характеризует меру удалённости подстановки g £ S (Vn) от имприми-тивной группы IGw, описываемой операцией сплетения S(Wo) I Sr (элементами IGw являются все подстановки из S (Vn), сохраняющие разбиение W). Для подстановки g £ S (Vn) положим: 1) ад = g(a) для а £ Vn; 2) Wg = {вд : в £ W} для W С Vn. В [1] показано, что порядок W-примитивности подстановки g выражается через элементы матрицы c(W)(g) = (c(W\g)j, где c(W^(g) = |Wf П Wj| для i,j = 0,1, ... , r - 1, а также описаны подстановки с максимальным порядком W-примитивности. Порядок W-примитивности может возникать в методе гомоморфизмов или вероятностных гомоморфизмов, а также в разностном методе. Вместе с тем из классификации примитивных групп подстановок видно, что ряд классов характеризуется как группы изометрий метрик. Но в криптографии соответствующие подходы пока не нашли должного развития, хотя метрики могут естественным образом появляться в случае криптосистем, построенных на базе регистров сдвига [2]. В работе вводится мера, характеризующая степень рассеивания преобразованием метрической структуры, названная показателем неизометричности подстановки g Е S (Vn). Мера задаётся для произвольной метрики ^ на Vn условием pM(g) = (2n(2n - 1))-1 |{(а,а') Е V2 : Ма,а') = ,)}| , О ^ P^(g) ^ 1, причём pM(g) = 1 тогда и только тогда, когда g Е Isom(^). Доказано, что показатель неизометричности одинаков для всех подстановок из S (Vn), принадлежащих одному смежному классу по подгруппе Isom(^). Пусть Xх = X\ {0n} для подмножества X С Vn; ф - операция сложения в Vn 0n - нулевой вектор пространства Vn. Рассмотрим множество M+ всех (d + 1)-значных метрик на Vn, инвариантных относительно группы сдвигов пространства Vn и приниоо мающих каждое значение из множества {0,1,..., d}, = (J M^. Каждая метрика d= 1 ^ Е M+d [3] однозначно задаваема упорядоченным разбиением B = (B1,..., Bd) множества VX условием ^ : (а, а') м- j, если а ф а' Е Bj для j = 1,..., d и обозначается через . Для каждого g Е S(Vn) доказано равенство р,в (g) = 1 - (2n - 1)-1 Е(g), i= 1 где &,e(g) = 2-n |{а Е Vn : (а ф = ай ф e}| , Е Vn, рл,дЫ = E iMg^ A,Л С (S,s)e Лхд т. е. p

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