|
Математические методы криптографии
О перемешивающих свойствах нестационарного регистра сдвига
Я. Э. Авезова АО «Позитив Текнолоджиз», г. Москва
Аннотация:
Для регистра сдвига длины $n$, функция обратной связи которого зависит от двоичного знака управляющей последовательности (на каждом такте реализуется одно из двух регистровых преобразований), исследовано минимальное число $\gamma$ тактов регистра, после которых достигнуто полное перемешивание, то есть существенная зависимость каждой координатной функции композиции преобразований от всех переменных. Эффект полного перемешивания оценен с помощью множества $\hat{\Gamma}$ перемешивающих $n$-вершинных орграфов регистровых преобразований, имеющих общий гамильтонов контур. Дана оценка экспонента $\exp\hat{\Gamma}$ примитивного множества $\hat{\Gamma}$, которая позволяет оценить снизу число $\gamma$:
$$
\exp\hat{\Gamma}\leq 2n-2+\textstyle\sum\limits_{\alpha=0}^1\left(F(n-S(\phi_\alpha))+d_\alpha+s_{m(\alpha)}^\alpha\right),
$$
где $S(\phi_\alpha)=\left\{s_1^\alpha,\ldots,s_{m(\alpha)}^\alpha\right\}$ — множество номеров существенных переменных функции обратной связи $\phi_\alpha(x_0,\ldots,x_{n-1})$;
$n-S(\phi_\alpha)=\{n-s_j^\alpha: j=1,\ldots,m(\alpha)\}$; $d_\alpha=\text{НОД}\{n-S(\phi_\alpha)\}$; $F(n-S(\phi_\alpha))=d_\alpha\Phi((n-S(\phi_\alpha))/d_\alpha)$; $\Phi((n-S(\phi_\alpha))/d_\alpha)$ — число Фробениуса.
Проведён вычислительный эксперимент при $n=6$ и $10$ по вычислению точного значения $\gamma$ с учётом управляющей последовательности. Установлено, что полное перемешивание возможно за число тактов, превышающее значение экспонента менее чем в $2$ раза.
Ключевые слова:
гамильтонов контур, примитивность множества орграфов, экспонент орграфа, экспонент множества орграфов.
Образец цитирования:
Я. Э. Авезова, “О перемешивающих свойствах нестационарного регистра сдвига”, ПДМ. Приложение, 2019, № 12, 80–83
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdma440 https://www.mathnet.ru/rus/pdma/y2019/i12/p80
|
|