Математические методы криптографии
Сравнение экспонентов перемешивающих орграфов регистровых преобразований с одной и двумя обратными связями
А. М. Кореневаab a Национальный исследовательский ядерный университет "МИФИ", г. Москва
b ООО "Код Безопасности", г. Москва
Аннотация:
Обозначим
$\text{МАГ}(n,r,k)$ множество модифицированных аддитивных генераторов на основе регистров сдвига длины
$n$ с
$k$ обратными связями над множеством
$V_r$ булевых
$r$-мерных векторов,
$n>k\ge1$,
$r>1$. Пусть подстановка
$g$ множества
$V_r$ модифицирует обратную связь регистра из
$\text{МАГ}(n,r,1)$, подстановки
$g$ и
$\mu$ множества
$V_r$ модифицируют обратные связи регистра из
$\text{МАГ}(n,r,2)$,
$\Gamma(\varphi^g)$ и
$\Gamma(\varphi^{g,\mu})$ – перемешивающие орграфы преобразований соответствующих регистров. Проведён сравнительный анализ, в ходе которого показано, что соотношение экспонентов орграфов
$\Gamma(\varphi^{g,\mu})$ и
$\Gamma(\varphi^g)$ зависит не только от числа обратных связей, но и от расположения точек съёма на регистрах. Для большого количества вариантов точек съёма величина $\zeta=\exp\Gamma(\varphi^g)-\exp\Gamma(\varphi^{g,\mu})$ положительная и ограничена сверху величиной
$\exp\Gamma(\varphi^g)/2$. Описаны также те редкие случаи, когда величина
$\zeta$ отрицательная. Определены наименьшие значения
$\exp\Gamma(\varphi^g)$ и
$\exp\Gamma(\varphi^{g,\mu})$, равные
$n+1$ и
$\lceil n/2\rceil+1$ соответственно, и условия, при которых они достигаются.
Ключевые слова:
модифицированный аддитивный генератор, перемешивающие свойства, регистр сдвига, экспонент орграфа.
УДК:
519.17
DOI:
10.17223/2226308X/10/34