Добавлены лекции 14 и 15

5 files changed, 301 insertions, 2 deletions

diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf
index d155bef..47583ab 100644
--- a/cryptography/cryptography.pdf
+++ b/cryptography/cryptography.pdf
diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex
index 61ddd36..98ef1f4 100644
--- a/cryptography/cryptography.tex
+++ b/cryptography/cryptography.tex
@@ -25,6 +25,7 @@
 \input{lectures/lecture11.tex}
 \input{lectures/lecture12.tex}
 \input{lectures/lecture13.tex}
-
+\input{lectures/lecture14.tex}
+\input{lectures/lecture15.tex}
 
 \end{document}
diff --git a/cryptography/lectures/lecture14.tex b/cryptography/lectures/lecture14.tex
new file mode 100644
index 0000000..301925f
--- /dev/null
+++ b/cryptography/lectures/lecture14.tex
@@ -0,0 +1,87 @@
+% Лекция 14 (05.12.22)
+
+\subsection{Усложнение ЛРП}
+
+В криптографических приложениях используют различные способы усложнения
+аналитического строения линейных реккурент.
+
+\paragraph{Фильтрующие генераторы.}
+
+Первый способ заключается в применении к элементам ЛРП некоторой функции $f$
+(см. рисунок).
+
+% TODO: рис. 1
+
+Подобные узлы усложнения ЛРП называются фильтрующими генераторами. Их
+результирующей последовательностью является нелинейно <<фильтрованное>>
+содержимое регистра сдвига.
+
+<<Фильтрующая>> функция $f$ должна выбираться так, чтобы выходная
+последовательность имела распределение близкое к равномерному и высокую линейную
+сложность.
+
+\paragraph{Комбинирующие генераторы.}
+
+Второе направление синтеза псевдослучайных последовательностей с высокой
+линейной сложностью связано с использованием в одной схеме нескольких регистров
+сдвига.
+
+Генератор псевдослучайных последовательностей, реализующий усложнение нескольких
+линейных рекуррент с помощью одной общей функции усложнения, получил название
+комбинирующего генератора (см. рисунок).
+
+% TODO: Рис. 2
+
+\paragraph{Композиции линейных регистров сдвига}
+
+Так называется схема, в которой выход одного из регистров подаётся на вход другого
+регистра (см. рисунок).
+
+% TODO: Рис. 3
+
+Функционирование такой схемы описывается следующим образом.
+
+Пусть $\nu$ --- ЛРП, вырабатываемая первым регистром сдвига, закон рекурсии
+которого определяется характеристическим многочленом $F(X)$.
+
+Пусть задано начальное состояние второго регистра сдвига, закон рекурсии
+которого определяется характеристическим многочленом $G(x) = x^m - \sum_{j =
+0}^{m - 1} g_j \cdot x^j$.
+
+Тогда выходная последовательность композиции регистров сдвига задаётся
+соотношением
+\begin{equation*}
+  w(i + m) = \sum_{j = 0}^{m - 1} w(i + j) g_j + v(i),\, i \geq 0
+\end{equation*}
+
+\paragraph{Схемы с элементами памяти}
+
+Один из наиболее широко известных классов датчиков псевдослучайных чисел,
+построенных с использованием памяти, составляют генераторы Макларена-Марсальи,
+которые были предложены Д. Марсальей и Д. Маклареном в 1965 году.
+
+Пусть имеется три последовательности и массив памяти. Элементы первой
+последовательности записываются в память по адресам, которые определяются
+элементами второй последовательности.
+
+Элементы выходной последовательности получаются при считывании значений,
+хранящихся в массиве памяти, в соответствии с элементами третьей
+последовательности.
+
+Таким образом, первая последовательность определяет, какие знаки заносятся в
+память, вторая управляется процессом записи этих элементов в память, а третья
+--- процессом считывания из памяти элементов выходной последовательности.
+
+На рисунке приведена схема работы генератора, когда процессами записи и
+считывания управляет одна и та же последовательность.
+
+% TODO: Рис. 4
+
+Пусть $u$ и $v$ --- последовательности над полем $P$, а выходная
+последовательность $\gamma$ вырабатывается с использованием $q$ ячеек памяти
+$R_0, \dots, R_{q - 1}$. Если $R_j(i)$ --- заполнение $j$-
+
+% TODO: Дописать
+
+\subsection{Поточная шифрсистема A5}
+
diff --git a/cryptography/lectures/lecture15.tex b/cryptography/lectures/lecture15.tex
new file mode 100644
index 0000000..f7c93bf
--- /dev/null
+++ b/cryptography/lectures/lecture15.tex
@@ -0,0 +1,211 @@
+% Лекция 15 (12.12.22)
+
+\subsection{Поточная шифрсистема RC4}
+
+RC4 представляет собой поточный шифр с переменной длиной ключа.
+
+Алгоритм разработан в 1987 году Р. Ривестом для компнии RSA Data Security
+
+Алгоритм работает в режиме обратной связи по выходу. Ключевая последовательность
+не зависит от исходного текста. Структура алгоритма включает блок замены
+размерностью $8 \times 8 : S_0, \dots, S_{255}$.
+
+Блок замены представляет собой зависимую от ключа переменной длины перестановку
+чисел $0, \dots, 255$.
+
+Имеется два счётчика $i$ и $j$, первоначально равные 0.
+
+Для генерирования псевдослучайного байта выполняются следующие действия
+\begin{align*}
+  i &= (i + 1) \pmod{256} \\
+  j &= (j + S_i) \pmod{256} \\
+    &\text{переставить } S_i \text{ и } S_j \\
+  t &= (S_i + S_j) \pmod{256} \\
+  k &= S_i \\
+\end{align*}
+
+Затем байт $k$ складывается по модулю 2 с байтом исходного текста для получения
+криптограммы.
+
+Блок замены инициализируется следующим образом. Сначала он заполняется линейно:
+$S_0 = 0, S_1 = 1, \dots S_{255} = 255$.
+
+Затем заполняется ещё один 256-байтовый массив ключом, при этом ключ может
+повторяться необходимое число раз для заполнения всего массива $k_0, \dots,
+k_{255}$.
+
+Счётчик $j$ устанавливается в 0. После этого производятся следующие действия:
+% TODO: оформить алгоритм
+for i = 0 to 255
+  j = (j + k_i + S_i) \pmod{256}
+  переставить $S_i$ и $S_j$.
+
+
+\subsection{Методы анализа поточных шифров}
+
+Некоторые методы анализа поточных шифров на примере шифров гаммирования:
+\begin{itemize}
+  \item Исследование вероятностных характеристик гаммы;
+  \item
+    Попытки линеаризации уравнений гаммообразования, то есть сведения задачи
+    нахождения ключей криптографических алгоритмов к решению некоторой системы
+    линейных уравнений;
+  \item
+    Применение методов анализа, основанные на наличии у функции усложнения
+    хороших приближений в классе линейных функций;
+  \item
+    Необходимо учитывать наличие между знаками гаммы зависимостей комбинаторного
+    характера.
+\end{itemize}
+
+
+\section{Блочные шифрсистемы}
+
+\emph{Блочный шифр} --- шифр, в котором открытый текст перед шифрованием
+разбивается на блоки, состояние из нескольких знаков, то есть исходное
+сообщение обрабатывается блоками.
+
+\subsection{Принципы построения}
+
+Как правило, алфавитом, на котором действует блочный шифр, является множество
+двоичных векторов-блоков открытого текста одинаковой длины (64, 128 и т. д.).
+
+К. Шеннон сформулировал общий принцип построения шифрующих преобразований ---
+принцип \emph{<<перемшивания>>}.
+
+Суть его состоит в требовании, чтобы применение шифрующего преобразования к
+наборам аргументов, отличающихся в незначительном числе позиций, приводило к
+существенному изменению результата.
+
+Обеспечить выполнение данного требования в сочетании с простотой реализации
+конкретного отображения в общем случае представляется затруднительным.
+
+Поэтому К. Шеннон предложил реализовывать сложные преобразования в виде
+суперпозиции нескольких простых некоммутирующих отображений, что используется
+при построении блочных шифров.
+
+Блочные шифры реализуются путём многократного применения к блокам открытого
+текста некоторых базовых преобразований.
+
+Обычно используются базовые преобразования двух типов:
+\begin{enumerate}
+  \item
+    <<Перемешивающие>> --- сложные в криптографическом отношении локальные
+    преобразования над отдельными частями шифруемых блоков.
+
+    Перемешивание усложняет восстановление взаимосвязи статистических 
+    аналитических свойств открытого текста и криптограммы;
+  \item
+    <<Рассеивающие>> --- простые преобразования, переставляющие между собой
+    части шифруемых блоков.
+
+    Рассеивание распространяет влияние одного знака открытого текста на большое
+    число знаков криптограммы, что позволяет сгладить влияние статистических
+    свойств открытого текста на свойства криптограммы.
+\end{enumerate} 
+
+Алгоритм шифрования выполняет некоторое число циклов (итераций). Каждый цикл в
+применении преобразований первого и второго типов.
+
+Такой принцип построения даёт возможность реализовать каждый цикл шифрования с
+использованием однотипных узлов, а также выполнять расшифрование путём обработки
+данных в обратном направлении.
+
+Удобной моделью для реализации базовых преобразований служат \emph{регистры
+сдвига}. При этом рассеивающие преобразования определяются функциями обратной
+связи, а перемешивающие --- сдвигами информации в регистре.
+
+
+\subsection{Структура алгоритмов}
+
+\paragraph{Сеть Фейстеля.}
+
+Для построения алгоритмов часто используется \emph{Сеть Фейстеля} (см. рисунок).
+
+% TODO: Рисунок 1 (везде индексы i)
+
+Преобразование, реализуемое сетью Фейстеля в $i$-м цикле шифрования имеет вид
+\begin{equation*}
+  \begin{cases}
+    Y_1 = X_2 \\
+    Y_2 = X_1 \oplus f_i(X_2, k_i)
+  \end{cases}
+\end{equation*}
+где $X$ --- входной блок, разделённый на две половины $X_1$ и $X_2$, а $(Y_1,
+Y_2)$ --- результат зашифрования блока $X$ на ключе $k_i$ с помощью функции
+$f_i$.
+
+Алгоритм шифрования реализуется несколькими итерациями преобразования сети
+Фейстеля с использованием ключа $k$.
+
+При этом очередная $i$-я итерация использует в качестве входного блока $X$
+результат предыдущей итерации и ключ $k_i$, вычисляемый определённым образом
+по ключу $k$.
+
+Функция $f_i$ может зависеть или не зависеть от номера итерации.
+
+Даже если $f_i$ не является обратимой функцией, преобразование сети Фейстеля
+обратимо:
+\begin{equation*}
+  \begin{cases}
+    X_1 = Y_2 \oplus f_i(Y_1, k_i) \\
+    X_2 = Y_1
+  \end{cases}
+\end{equation*}
+
+На сети Фейстеля основаны, например, алгоритмы шифрования DES, ГОСТ 28147-89,
+RC5.
+
+\paragraph{SP-сети.}
+
+В отличие от сети Фейстеля, SP-сети (Substitution-Permutation network,
+подстановочно-перестановочная сеть) обрабатывает за один раунд целиком
+шифруемый блок.
+
+Обработка данных сводится в основном к заменам и перестановкам зависящим от
+ключа $k_i$ (см. рисунок).
+
+% TODO: Рисунок 2
+
+SP-сети являются гораздо менее распространёнными, чем сети Фейстеля. На их базе,
+например, основаны алгоритмы шифрования Serpent, SAFER+.
+
+
+\subsection{S-блоки}
+
+Операторы подстановки в блочных шифрах называются S-боксами (блок подстановки,
+узлы замены).
+
+На вход в S-бокса подаётся $n$-битовый блок, а на выходе --- $m$-битовый блок,
+где $m$ может быть отлично от $n$.
+
+Пусть в S-боксе $x_1, x_2, \dots, x_n$ --- входы, $y_1, y_2, \dots, y_m$ ---
+выходы, тогда связь между ними задаёт система уравнений:
+\begin{equation*}
+  \begin{cases}
+    y_1 = f_1(x_1, x_2, \dots, x_n) \\
+    y_2 = f_2(x_1, x_2, \dots, x_n) \\
+    \dots \\
+    y_m = f_m(x_1, x_2, \dots, x_n) \\
+  \end{cases}
+\end{equation*}
+
+S-боксы делятся на линейные и нелинейные. В линейном S-боксе эту связь можно
+записать в виде линейных соотношений:
+\begin{equation*}
+  \begin{cases}
+    y_1 = a_{11} x_1 \oplus a_{12} x_2 \oplus \dots \oplus a_{1n} x_n \\
+    y_2 = a_{21} x_1 \oplus a_{22} x_2 \oplus \dots \oplus a_{2n} x_n \\
+    \dots \\
+    y_m = a_{m1} x_1 \oplus a_{m2} x_2 \oplus \dots \oplus a_{mn} x_n \\
+  \end{cases}
+\end{equation*}
+
+В нелинейном S-боксе нельзя задать линейные соотношения для каждого выхода.
+
+Пример S-бокса представлен на рисунке, где первый бит входа определяет строку,
+два следующих бита входа определяют столбец.
+
+Два бита на выходе --- это значение на пересечении выбранных строки и столбца.
+
+% TODO: Рисунок 3
diff --git a/cryptography/lectures/lecture2.tex b/cryptography/lectures/lecture2.tex
index 5bb4ca3..ea27291 100644
--- a/cryptography/lectures/lecture2.tex
+++ b/cryptography/lectures/lecture2.tex
@@ -67,7 +67,7 @@ $a'$ называется обратным к $a$ по модулю $n$ и об�
 называется \emph{группой}, если выполняется три условия:
 \begin{enumerate}
   \item
-    операция <<\cdot>> ассоциативна, то есть $\forall a, b, c \in G : a \cdot (b
+    операция <<$\cdot$>> ассоциативна, то есть $\forall a, b, c \in G : a \cdot (b
     \cdot c) = (a \cdot b) \cdot c$,
   \item
     $\exists e \in G : \forall g \in G$ выполняется равенство $g \cdot e =