A method for building a cryptographic generator of sequences with specified index of unrepeatability.pdf Введение При криптографическом анализе DES-алгоритма введено понятие слабого ключа, т.е. основного ключа, порождающего 16 одинаковых раундовых ключей. В [1, с. 298] для r-раундового блочного алгоритма использовано понятие ^-слабого ключа, порождающего ровно ^ различных раундовых ключей, 1 ^ ^ < r. Показано, что при определённых условиях использование слабых ключей ослабляет криптографические свойства итеративного блочного шифра. Поэтому представляет интерес задача построения ключевого расписания, генерирующего при любом основном ключе r различных раундовых ключей. Для решения применим теоретико-автоматный подход. Основные обозначения: - Vn - множество двоичных n-мерных векторов, n Е N; - Vn,o - множество ненулевых двоичных n-мерных векторов, n Е N; - ЛРСтах-n - линейный регистр левого сдвига длины n максимального периода, n Е N. 1. Бесповторность последовательностей и автономных автоматов Пусть X^ = {x0,x1,...} - конечная или бесконечная последовательность над X и |X | = k. В последовательности X^ i-й r-граммой называется слово (x*, Xj+1,..., x*+r-1) длины r в алфавите X, i = 0,1, 2,...; r-грамму назовём бесповторной, если она не содержит одинаковых символов. Последовательность r-грамм последовательности X^ обозначим X^. Последовательность назовём r-бесповторной, если все её r-граммы бесповторные. Чисто периодическая последовательность X^ с длиной периода t является r-бесповторной, если бесповторными являются её i-е r-граммы при i = 0,... , t - 1. Показателем бесповторности X^ (обозначение urp X^) назовём наибольшее натуральное r, при котором последовательность X^ является r-бесповторной. Очевидно, urp X^ ^ k, и если последовательность X^ r-бесповторная, то она и r'-бесповторная при любом r' ^ r. Автономный автомат A = (S, Y, h, f), где S - множество состояний, Y - выходной алфавит, h - функция переходов, f - функция выходов, называется r-бесповторным, если при любом начальном состоянии A генерирует бесповторное выходное слово длины r. Показатель бесповторности инициального автомата As определим как показатель бесповторности выходной последовательности при начальном состоянии s Е S и обозначим urp As. Показателем бесповторности автомата A назовём urp A = min{urp As}. sGS 2. Примеры r-бесповторных автономных автоматов A = (S, Y, h, f) 1. Пусть S = Vn,0, Y = V., h - подстановка двоичного линейного регистра левого сдвига с примитивным характеристическим многочленом, f (y1,... ,yn) = (y1,... ,yr), r ^ n. Автомат генерирует r-граммы линейной рекуррентной последовательности X^ (порядка n) максимального периода. Следовательно, urp X^ = 2n - 1 при r ^ n. 2. Пусть S = Vn, Y = V, h - полноцикловая подстановка двоичного нелинейного регистра сдвига длины n, f(y1,...,yn) = (y1,...,yr), r ^ n. Автомат генерирует r-граммы нормальной рекуррентной последовательности (де Брейна). Отсюда urp X^ = 2n при r ^ n. Для построения ключевого расписания r-раундового блочного шифра без слабых ключей представляет интерес построение r-бесповторного автомата, где Л > l ^ r, r ^ 32 (здесь Л - длина основного бинарного ключа, l - длина раундовых бинарных ключей). Для построения такого автомата рассмотрим криптографический генератор «1-2 шага». 3. Криптографический генератор «1-2 шага» Рассмотрим автономный автомат A = (Vn,0 х Vm,o, Vm,o, h, "0) с множеством состояний Vn,0 х Vm,o, выходным алфавитом Vm,o, функцией переходов h и функцией выходов -0. При состоянии автомата s = (y1,... , yn, x1,..., xm) выполнено ^(s) = = (x1,...,xm) и h(s) = (8(y1,... , yn),ga+1(x1,... , xm)), где 8 и g суть подстановки, реализуемые ЛРСтах-n и ЛРСшах-m соответственно, а = /(y1,... ,yn), / - равновероятная булева функция, в простейшем случае /(y1,... ,yn) = yn. Таким образом, «продвижение» генерирующего ЛРСшах-m в состоянии s равно а +1, то есть 1 или 2 в зависимости от знака а, выработанного управляющим ЛРСтах-n. После 2n - 1 тактов «продвижение» генерирующего ЛРСшах-m равно т = 2n + 2n-1 - 1 - /(0,... , 0) при любом начальном состоянии s Е V^,o х Vm,o. Обозначим: X^(s) - выходная последовательность автомата A при начальном состоянии s; X^(s,t) - подпоследовательность последовательности X^(s), составленная из первых t символов. Известно [1, с. 317], что длина периода последовательности X^(s) равна t = (2n - 1)(2m - 1)/а при любом начальном состоянии s, где а = (т, 2m - 1). Теорема 1. При любом начальном состоянии s последовательность X^(s, 2m-1) автомата A является бесповторной. Справедливость теоремы следует из того, что X^(s, 2m-1) есть бесповторная выборка (размера 2m-1) с переменным шагом 1 - 2 из периодического отрезка последовательности состояний ЛРСшах-m. Отметим, что на основе автомата A можно построить ключевое расписание, удовлетворяющее указанным требованиям. Для этого следует положить: состояние s - основной ключ, длина основного бинарного ключа Л = m + n, длина раундовых бинарных ключей l = m, где m > 5. Тогда при любом числе раундов r ^ 32 выполнено условие бесповторности последовательности раундовых бинарных ключей. В частности, параметры ключевого расписания алгоритма DES достигаются при m = 48, n = 8, а параметры ключевого расписания алгоритма ГОСТ 28147-89 - при m = 32, n = 224.

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