diff options
| -rw-r--r-- | cryptography/cryptography.pdf | bin | 690840 -> 701003 bytes | |||
| -rw-r--r-- | cryptography/cryptography.tex | 2 | ||||
| -rw-r--r-- | cryptography/lectures/lecture13.tex | 138 |
3 files changed, 140 insertions, 0 deletions
diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf Binary files differindex 2c757e1..8c0b130 100644 --- a/cryptography/cryptography.pdf +++ b/cryptography/cryptography.pdf diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex index 0333a2d..61ddd36 100644 --- a/cryptography/cryptography.tex +++ b/cryptography/cryptography.tex @@ -24,5 +24,7 @@ \input{lectures/lecture10.tex} \input{lectures/lecture11.tex} \input{lectures/lecture12.tex} +\input{lectures/lecture13.tex} + \end{document} diff --git a/cryptography/lectures/lecture13.tex b/cryptography/lectures/lecture13.tex new file mode 100644 index 0000000..bd2b326 --- /dev/null +++ b/cryptography/lectures/lecture13.tex @@ -0,0 +1,138 @@ +% Лекция 13 (28.11.22) + +Таким образом, задача построение рассматриваемого шифра сводится к выбору +множества шифрующих преобразований $\set{\varphi_\alpha}$ и отображения $\psi$, +задающего распределитель. + +В соответствии с этим поточная шифрсистема представляется в виде двух основных +блоков: +\begin{itemize} + \item + \emph{Управляющий блок} --- отвечает за выработку распределителя, то есть + вырабатывает последовательность номеров шифрующих преобразований, которая + называется \emph{управляющей последовательностью} (или \emph{управляющей + гаммой}); + \item + \emph{Шифрующий блок} --- в соответствии со знаком управляющей + последовательности реализует алгоритм шифрования текущего знака. +\end{itemize} + +Достаточно, чтобы в каждом такте шифрующий блок обеспечивал возможность +шифрования лишь текущего знака $a_j$ открытого текста в соответствии с (12). + +Обычно управляющая гамма представляет собой псевдослучайную последовательность, +удовлетворяющую некоторой рекуррентной зависимости. + +В общем случае рекуррентная последовательность на заданном множестве $A$ +определяется формулой $$x(i + m) = f(x(i), \dots, x(i + m - 1)),\, i \geq 0,$$ +в которой $f : A^m \to A$ --- некоторая функция от $m$ переменных. + +Для получения рекуррентных последовательностей используются различные датчики +псевдослучайных чисел, например: +\begin{enumerate} + \item + Линейный конгруэнтный генератор над кольцом или полем: + $$x(i + 1) = a \cdot x(i) + b,\, i \geq 0$$ + \item + Обобщение линейного генератора: $$x(i + 1) = f(x(i)),\, i \geq 0,$$ где + $f : A \to A$ --- произвольное отображение, легко вычисляемое для любого + аргумента; + \item + Линейные регистры сдвига (ЛРС), на которых основаны большинство датчиков. +\end{enumerate} + +Требования к управляющему блоку: +\begin{itemize} + \item + Период управляющей гаммы должен превышать максимально возможную длину + открытых сообщений, подлежащих шифрованию; + \item + Статистические свойства управляющей гаммы должны приближаться к свойствам + случайной равновероятной последовательности; + \item + В управляющей гамме должны отсутствовать простые аналитические зависимости + между близко расположенными знаками; + \item + Криптографический алгоритм получения знаков управляющей гаммы должен + обеспечивать высокую сложность определения секретного ключа. +\end{itemize} + +Требование к шифрующему блоку: применение алгоритма шифрования должно носить +универсальный характер и не зависеть от вида шифруемой информации. + + +\subsection{Линейные регистры сдвига} + +В криптографических приложениях широкое распространение получили линейные +регистры сдвига над конечными полями и кольцами. + +\emph{Последовательностью} над полем $P$ называется любая функция $u : \N_0 \to +P$, заданная на множестве целых неотрицательных чисел и принимающая значения в +поле. + +Последовательность $u$ называется \emph{линейной рекуррентной +последовательностью (ЛРП) порядка $m > 0$ над полем $P$}, если существуют +константы $f_0, \dots, f_{m - 1} \in P$ такие, что +\begin{equation*} + u(i + m) = \sum_{j = 0}^{m - 2} f_j \cdot u(i + j),\, i \geq 0. +\end{equation*} + +ЛРП реализуется схемой линейного регистра сдвига, изображённой на рисунке. +\textbf{TODO: Рисунок 1} + +В очередном такте работы регистра значения, содержащиеся в ячейках накопителя, +умножаются на соответствующие коэффициента $f_j$ и суммируются, после чего +происходит (левый) сдвиг информации в регистре, а в освободившуюся крайнюю +ячейку записывается вычисленное значение суммы (операции сложения и умножения +выполняются в поле $P$). + +Равенство, выражающее зависимость между знаками линейной рекуррентной +последовательности, называется \emph{законом рекурсии}, многочлен $F(x) = x^m - +\sum_{j = 0}^{m - 1} f_j \cdot x^j$ --- \emph{характеристическим многочленом} +ЛРП $u$, а вектор $u(\overline{0, m - 1}) = (u(0), \dots, u(m - 1))$ --- \emph{% +начальным вектором} ЛРП (или \emph{начальным заполнением} ЛРС). + +Характеристический многочлен ЛРП $u$, имеющий наименьшую степень, называется её +\emph{минимальным многочленом}, а степень минимального многочлена --- \emph{% +линейной сложностью} ЛРП $u$ (она определяет минимальную длину ЛРС, реализующую +данную последовательность). + +\emph{Периодом} последовательности $u$ называется наименьшее натуральное число +$t$, для которого существует натуральное число $\lambda > 0$ такое, что для всех +$i \geq 0$ справедливо равенство $u(\lambda + i + t) = u(\lambda + i)$. + +Когда $P$ --- конечное поле из $q$ элементов, максимальное значение периода ЛРП +порядка $m$ равно $q^m - 1$. + +Последовательности, имеющие максимально возможный период, называются линейными +рекуррентными последовательностями \emph{максимального периода} или просто +\emph{максимальными линейными рекуррентными последовательностями}. + +Значения периодов ЛРП определяется свойствами их минимальных многочленов. В +частности, для того, чтобы ЛРП порядка $m$ над полем из $q$ элементов имела +максимальный период, необходимо и достаточно, чтобы её минимальный многочлен был +\emph{примитивным}, то есть +\begin{enumerate} + \item $F(x)$ --- неприводимый над полем $P$; + \item + $\text{ord}\, F(x) = q^m - 1$, то есть $F(x)$ делит многочлен $x^{q^m - 1} - + 1$ и не делит ни один из многочленов вида $x^d - 1$, где $d$ делит $q^m - 1$ + и $d \neq q^m - 1$. +\end{enumerate} + +Закон рекурсии даёт удобный способ вычисления очередного знака ЛРП через +предыдущие, но при изучении её свойств предпочтительной формой задания является +формула общего члена последовательности, представляющая собой аналитическое +выражение члена последовательности в виде функции от его номера. + +Пусть $p = GF(q)$ и $Q$ --- поле из $q^m$ элементов, являющееся расширением поля +$P$. Тогда функцией \emph{<<след>> из поля $Q$ в поле $P$} называется +отображение $\text{tr}_q^{q^m}(a) : Q \to P$ вида +\begin{equation*} + \text{tr}_q^{q^m}(a) = a + a^q + a^{q^2} + \dots + a^{q^{m - 1}} +\end{equation*} + +\begin{theorem} + Пусть $F(x) = x^m - \sum_{j = 0}^{m - 1} +\end{theorem} + |