forked from vlsergey/infosec
-
Notifications
You must be signed in to change notification settings - Fork 0
/
generators_with_multiple_shift_registers.tex
17 lines (12 loc) · 3.2 KB
/
generators_with_multiple_shift_registers.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
\subsection[Генераторы с несколькими регистрами сдвига]{Генераторы с несколькими регистрами \protect\\ сдвига}
\selectlanguage{russian}
Первый способ улучшения криптографических свойств последовательности состоит в создании композиционных генераторов из нескольких регистров сдвига при определённом способе выбора параметров. Схема такого генератора показана на рис.~\ref{fig:generators}. Здесь $L_i, ~ i = 1, 2, \dots, M$ -- регистры сдвига с линейной обратной связью. Вырабатываемые ими двоичные символы $x_{1,i}, x_{2,i}, \dots, x_{M,i}$ поступают синхронно на устройство преобразования, задаваемое булевой функцией $f(x_{1,i}, x_{2,i}, \dots, x_{M,i})$. В булевой функции и аргументы, и значения функции принимают значения $0$ или $1$.
Число ячеек в $i$-м регистре равно $L_{i}$, причём $\gcd(L_i, L_j)=1$ для $i \neq j$, где $\gcd$ -- наибольший общий делитель. Общее число ячеек $L = \sum\limits_{i=1}^M L_i$. Булева функция $f$ должна включать слагаемое по одному из входов, то есть $f = \dots + x_i + \dots$, для того чтобы двоичные символы на выходе этой функции были равновероятными. Период этого генератора может достигать величины (немного меньше)
\[ T \simeq 2^L. \]
\begin{figure}[!ht]
\centering
\includegraphics[width=0.7\textwidth]{pic/generators}
\caption{Генератор с несколькими регистрами сдвига\label{fig:generators}}
\end{figure}
Таким образом, увеличение числа регистров сдвига с обратной связью увеличивает период последовательности.
Одним из способов оценки криптостойкости генератора является оценка длины регистра с линейной обратной связью эквивалентного по порождаемой последовательности. Такой эквивалентный РСЛОС находится с помощью алгоритма Берлекэмпа~---~Мэсси\index{алгоритм!Берлекэмпа~---~Мэсси} декодирования циклических кодов. В лучшем случае длина эквивалентного регистра соизмерима с периодом последовательности, порождённой нелинейным генератором. В общем случае определение эквивалентной длины является сложной задачей.