Estimates for exponents of mixing graphs relating to some modifications of additive generators.pdf Введение Положительным криптографическим свойством генератора гаммы {71,...,7^ ... } является полное перемешивание входных данных, то есть зависимость знаков вырабатываемой гаммы от всех знаков начального состояния. Полное перемешивание достигается для знаков гаммы 7^, как правило, при i ^ ехрГ(^), где ^ - преобразование множества внутренних состояний генератора; Г(^) -перемешивающий граф преобразования ехрГ(^) -экспонент графа Г(^). Если ехрГ(^) = t, то начальный отрезок гаммы {71,... , 7t-1} часто называют «холостым ходом» и обычно не используют в ключевой последовательности. Таким образом, определение экспонентов перемешивающих графов криптографических преобразований является важной задачей анализа и синтеза криптографических систем. Сделана оценка экспонентов перемешивающих графов преобразований, соответствующих некоторым модификациям аддитивных генераторов (аддитивные генераторы называют также запаздывающими генераторами Фибоначчи). Интерес к модификациям вызван тем, что оригинальные схемы аддитивных генераторов полного перемешивания не достигают и вообще признаны нестойкими. В то же время на основе аддитивных генераторов построен ряд алгоритмов: Fish, Pike, Mush [1]. Обзор результатов по экспонентам графов, полученных до 2012 г., дан в [2]. Для перемешивающих графов биективных регистров сдвига над множеством двоичных векторов, к которым относятся, в частности, аддитивные генераторы и рассматриваемые модификации, общие оценки уточнены в [3,4]. В работе эти оценки получают дальнейшее уточнение за счёт особенностей аддитивных генераторов и их модификаций. 1. Аддитивные генераторы Генераторы построены на основе принципа, использованного в линейных регистрах сдвига, но оперируют с числами в кольце вычетов Z/2r, где r > 1. Обозначим n длину регистра, ячейки регистра сдвига занумеруем числами 0,... ,n - 1. Обозначим X0, X1,..., Xn-1 числа из Z/2r, образующие начальное состояние генератора. При i ^ n знак гаммы Xj образуется по формуле n X = Y, aXj+i-n mod 2r, (1) j=0 где a0,...,an-1 Е {0,1}. Следовательно, аддитивный генератор есть регистр сдвига n- 1 длины n с функцией обратной связи /(y0,... ,yn-1) = ajУ mod 2r. Так как a0 = 1 j=0 (в противном случае длина регистра меньше n), /(y1,... ,yn) биективна по переменной y0, то есть регистр реализует подстановку множества состояний [5, теорема5.5]. Для изучения перемешивающих свойств подстановки генератора используем двоичное представление $(Xj) числа Xj, i ^ 0, являющееся r-мерным вектором пространства V (младшим битом является r-й бит), состояние генератора является rn-мерным вектором пространства VTn. 2. Перемешивающие свойства модифицированного генератора. Критерий полного перемешивания - примитивность перемешивающего орграфа подстановки; необходимым условием является сильная связность орграфа. Заметим, что для регистра сдвига, определяемого законом рекурсии (1), перемешивающий граф не сильносвязный. Для достижения сильной связности модифицируем аддитивный генератор с помощью инволюции I множества V: I(xi,... , xr) = (xr,... ,xi). Тогда при i ^ n 5(Xi) = I ^ |Xi-„ + ajXj+i-^ mod 2r Используем обозначения и результаты работ [3,4]. Пусть ^ - подстановка регистра сдвига. Состояние регистра в текущий момент времени задано двоичной матрицей размера r х n, где k-й столбец матрицы, обозначаемый y+i = = (xi+rfc,...,xr+rfc)T (T - транспонирование), записан в k-й ячейке регистра сдвига, k = 0,1,... , n - 1. Подстановка ^ задается системой rn булевых координатных функций {

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