On properties of W-permutations over the residue ring.pdf В настоящее время в большинстве итерационных алгоритмов блочного шифрования сложение с раундовым ключом осуществляется над n-мерным векторным пространством над полем GF(2) или над кольцом вычетов z2n. Примерами таких алгоритмов являются ГОСТ 28147-89, BelT и FEAL. Одним из основных методов анализа алгоритмов блочного шифрования является разностный метод и его модификации. Необходимость формального описания ряда модификаций разностного метода накладывает дополнительные ограничения на свойства преобразований, являющихся компонентами раундовой функции. Одним из таких является условие +^-марковости s-боксов [1], а кроме того, условие +w-марковости раундовой функции. Однако на практике для многих алгоритмов блочного шифрования данные условие выявить «трудно». Поэтому вводятся понятия, смягчающие данные требования, которые «легче» применять на практике. Пусть n - множество натуральных чисел; zn - кольцо вычетов по модулю n е n, n ^ 2; S(zn) -симметрическая группа на zn; ab = 6(a) -образ элемента а е zn при действии на него подстановкой 6 е S(zn). Для произвольной подстановки 6 е S(zn) положим Рв>е(6) = 2_n|{a е zn : (0 + a)b = e + ab}|, 0,e е zn, Pe,w(6) = E Рв,в' (6), 0 е zn, W С zn. в' ew Определение 1. Пусть W С zn. Назовём 6 е S(zn) W-подстановкой, если для любых элементов 0, 0 е W выполняется равенство pe,w(6) = pe' w(6). Для подстановки g е S(zn) через EDg обозначим множество, состоящее из всех таких подмножеств W С zn, что для любого элемента а е W существует элемент в е zn, удовлетворяющий условию (а + e)g - вg е W. Доказано, что любая подстановка g е S(zn) является W-подстановкой для некоторого подмножества W С EDg. Отсюда следует оценка снизу мощности множества EDg, а именно |EDg | ^ |~n/2~|. Доказана замкнутость множества EDg относительно операции объединения подмножеств. Так, если g е S(zn), то для любых подмножеств W, W' С EDg выполняется включение W U W С EDg. Кроме того, показано существование ровно n таких подстановок g е S(zn), что |EDg| = n(n - 1)/2. Теорема 1. Пусть g - произвольная подстановка из S (zn) и подмножество W1 С С EDg таково, что |W1| = [n/2], 0 E W1. Тогда для каждого a E W1 выполняется равенство p^w (g) = (g), где a' = n - a и j {n - a : a E W1}, если n нечётно, W 2 = \ I {n - a : a E W1}\{n/2}, если n чётно.

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