Добавлены лекции 26 и 28

4 files changed, 298 insertions, 0 deletions

diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf
index 99b17fa..ee20c11 100644
--- a/cryptography/cryptography.pdf
+++ b/cryptography/cryptography.pdf
diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex
index a244ed7..04b5af5 100644
--- a/cryptography/cryptography.tex
+++ b/cryptography/cryptography.tex
@@ -43,5 +43,8 @@
 \input{lectures/lecture23.tex}
 \input{lectures/lecture24.tex}
 \input{lectures/lecture25.tex}
+\input{lectures/lecture26.tex}
+% \input{lectures/lecture27.tex}
+\input{lectures/lecture28.tex}
 
 \end{document}
diff --git a/cryptography/lectures/lecture26.tex b/cryptography/lectures/lecture26.tex
new file mode 100644
index 0000000..0aa81f0
--- /dev/null
+++ b/cryptography/lectures/lecture26.tex
@@ -0,0 +1,170 @@
+% Лекция 25 (21.04.23)
+
+% TODO: УБРАТЬ ИЗ СЛОВАРЯ КОНКАТЕНЦИЮ
+Стартовый вектор хэширования длины 128 бит представляет собой конкатенацию
+четырёх констант: $01234557 \| 89abcdef \| fedcba98 \| 76543210$. При вычислении
+используется накопитель, содержащий четыре 32-разрядных слова A, B, C, D.
+Исходным заполнением накопителя являются слова стартового вектора хэширования.
+
+Обработка 16-словного блока $M_i$, $1 \leq i \leq n$, осуществляется за четыре
+цикла, каждый из которых включает в себя 16 шагов.
+
+На каждом шаге $j$-го цикла, $1 \leq j \leq 4$, выполняются операции:
+\begin{align*}
+  t &:= B + (A + f_j(B, C, D) + M_i[z[i]] + y[i]), \\
+  (A, B, C, D) &:= (D, B + t \lll s[i], B, C).
+\end{align*}
+где $M_i[z[i]]$ --- слово, выбранное из $M_i$ в соответствии с перестановкой
+$z$; $X \lll k$ --- циклический сдвиг слова $X$ влево на $k$ бит; <<+>> ---
+операция сложения по модулю $2^{32}$.
+
+Таким образом, на каждом шаге выполняются четыре операции сложения и одна
+операция сдвига, вычисляется значение одной цикловой функции.
+
+Выходом каждой итерации является конкатенация текущих значений четырёх слов
+накопителя.
+
+После обработки блока $M_n$ итоговым сжатым образом аргумента будет
+128-разрядная строка из четырёх слов: $A \| B \| C \| D$.
+
+Поскольку нелинейнойсть операции $f_i$ мала, нелинейные свойства итогового
+преобразования определяются влиянием переносов при сложении.
+
+Хэш-функция MD5 считается небезопасной и желательно отказаться от её
+использования.
+
+
+\paragraph{SHA.}
+
+Защищённый алгоритм хэширования (Secure Hash Algorithm --- SHA) разработан
+Управлением национальной безопасности США (National Security Agency --- NSA)
+и стандартизирован институтом NIST в 1995 году.
+
+Первая версия этого алгоритма называлась просто SHA (теперь её часто называют
+SHA0) и имела весьма существенный недостаток. В NSA обнаружили этот недостаток
+и разработали метод его исправления. Это было опубликовано NIST в качестве
+улучшенной версии алгоритма SHA под названием SHA1. Тем не менее NIST не привёл
+никаких сведений о найденном недостатке.
+
+Через три года два французских исследователя Шабо и Жу опубликовали статью
+о слабом месте алгоритма SHA0. Эта ошибка была исправлена в алгоритме SHA1,
+поэтому можно предположить, что речь идёт именно о том загадочном недостатке,
+который был обнаружен NSA.
+
+SHA1 --- это 160-битовая функция хэширования, основанная на алгоритме MD4.
+Функция SHA1 использует 160-битовое промежуточное состояние, которое разбивается
+на пять 32-битовых слов. Как и MD5, она состоит из четырёх раундов, представляющих
+собой комбинацию элементарных операций над 32-битовыми словами.
+
+Вместо того чтобы обрабатывать каждый блок сообщения по четыре раза, SHA1
+использует линейную рекуррентную функцию, чтобы <<растянуть>> 16 слов блока
+сообщения до нужных ей 80 слов.
+
+Это обобщение метода, используемого в MD4. В MD5 каждый бит сообщения
+используется функцией перемешивания по четыре раза. В SHA1 наличие линейной
+рекуррентной функции гарантирует, что каждый бит сообщения используется
+функцией перемешивания по меньшей мере 10 раз.
+
+Что интересно, единственным отличием SHA1 от SHA0 стало добавление к линейной
+рекуррентной функции циклического сдвига на один бит.
+
+Сегодня подбор серверного ключа аутентификации SHA1, то есть \emph{коллизия с
+выбранным префиксом} (данная методика позволяет для любых сообщений $x$ и $y$
+найти такие последовательности $q_1$ и $q_2$, что $H(x \| q_1) = H(y \| q_2)$),
+на арендованном кластере GPU обойдётся в \$45 тыс.
+
+Это делает атаку доступной не только для государственных спецслужб, но и для
+коммерческих клиентов, поэтому список пользователей SHA1 становится меньше. SHA1
+считается уязвимым и содержащим дефекты в алгоритме и рекомендуется перейти на
+более надёжные альтернативы.
+
+Хеш-функции SHA2 была разработана Агентством национальной безопасности США и
+опубликована Национальным институтом стандартов и технологий (NIST) в качестве
+стандарта FIPS PUB 180-2 в августе 2002 года. В этот стандарт также вошла
+хеш-функция SHA1.
+
+SHA2 имеет четыре варианта: SHA-256, SHA-384 и SHA-512, которые называются в
+соответствии с количеством битов в выходных данных.
+
+D 2007 году был объявлен конкурс на новый стандарт криптографических функций
+хэширования США SHA3.
+
+
+\paragraph{Стандарт ГОСТ Р 34.11-2012}
+
+Первый отечественный стандарт хэш-функции был принят в 1994 году. Это ГОСТ
+Р 34.11-94, в котором определена хэш-функция $h : \set{0, 1}^* \to \set{0,
+1}^{256}$
+
+В 2012 году российский стандарт хэш-функции стандарт хэш-функции был
+модифицирован Центром защиты информации и специальной связи ФСБ России при
+участии ОАО <<ИнфоТеКС>> (<<Информационные технологии и коммуникационные
+системы>>) и приказом Федерального агентства по техническому регулированию
+и метрологии от 7 августа 2012 г. №216-ст новый стандарт ГОСТ Р 34.11-2012
+<<Информационная технология. Криптографическая защита информации. Функция
+хэширования>> был введён в действие с 1 января 2013 года.
+
+Необходимость разработки настоящего стандарта вызвана потребностью в создании
+хэш-функции, соответствующей современным требованиям к криптографической
+стойкости и требованиям стандарта ГОСТ Р 34.10-2012 на электронную цифровую
+подпись.
+
+Данный стандарт определяет две функции хэширования $h : \set{0, 1}^* \to
+\set{0, 1}^n$ с длинами хэш-кода $n = 256$ бит и $n = 512$ бит.
+
+Неофициальные названия: <<Стрибог-256>> и <<Стрибог-512>>.
+
+\begin{enumerate}
+  \item
+    \textbf{Значение параметров.}
+
+    \begin{enumerate}
+      \item
+        Значение инициализационного вектора IV для функции хэширования с длиной
+        хэш-кода 512 бит равно $0^{512}$, для функции хэширования с длиной
+        хэш-кода 256 равно $(00000001)^{64}$.
+      \item
+        Нелинейное биективное преобразование множества двоичных векторов
+        $\set{0, 1}^8$ задаётся подстановкой $\pi = \fn{Vec}_8 \pi' \fn{Int}_8 :
+        \set{0, 1}^8 \to \set{0, 1}^8$, где $\pi' : Z_{2^8} \to Z_{2^8}$.
+        Значение подстановки $\pi'$ заданы в стандарте в виде массива
+        $\pi' = (\pi'(0), \pi'(1), \dots, \pi'(255))$, в котором в определённом
+        порядке записаны числа от 0 до 255. Например, $\pi'(22) = 153$.
+      \item
+        Значение перестановки $\tau \in S_{64}$ записаны в стандарте в виде
+        массива $\tau = (\tau(0), \tau(1), \dots, \tau(63))$, в котором в
+        определённом порядке записаны числа от 0 до 63. Например, $\tau(22) =
+        50$.
+      \item
+        Линейное преобразование $l$ множества двоичных векторов $\set{0,
+        1}^{64}$ задаётся умножением справа на матрицу $A$ над полем $GF(2)$,
+        строки которой заданы в стандарте последовательно в шестнадцатеричном
+        виде. Например, 22 строка матрицы $A = 8a174a9ec8121e5d$.
+      \item
+        Итерационные константы $C_i$, $i = 1, \dots, 12$, записаны в стандарте
+        в шестнадцатеричном виде. Значение константы, записанное в виде
+        $a_{127} \dots a_0$, где $a_i \in \Z_{16},\, i = 0, \dots, 127$, есть
+        $\fn{Vec}_4(a_{127}) \| \dots \| \fn{Vec}_4(a_0)$.
+    \end{enumerate}
+
+  \item
+    \textbf{Преобразования.}
+
+    % TODO: дописать
+    \begin{enumerate}
+      \item
+        $X[k] : \set{0, 1}^{512} \to \set{0, 1}^{512}, X[k](a) = k \oplus a,\,
+        k, a \in \set{0, 1}^{512}$.
+      \item
+        $S : \set{0, 1}^{512} \to \set{0, 1}^{512},\, S(a) = S(a_{64} \| \dots \|
+        a_0) = \pi(a_{63}) \| \dots \| \pi(a_0)$, где $a \in \set{0, 1}^{512},
+        a_i \in \set{0, 1}^8$, $i = 0, \dots, 63$.
+      \item
+        $P : \set{0, 1}^{512} \to \set{0, 1}^{512},\, P(a) = P(a_{63} \| \dots \|
+        a_0) = a_{t(63)} \| \dots \| a_{\tau(0)}$, где $a \in \set{0, 1}^{512},
+        a_i \in \set{0, 1}^8$, $i = 0, \dots, 63$.
+      \item
+        $L : \set{0, 1}^{512} \to \set{0, 1}^{512},\, L(a) = L(a_7 \| \dots \|
+        a_0) = l(a_7) \| \dots \| l(a_0)$, где $a \in \set{0, 1}^{512}, a_i \in$
+    \end{enumerate}
+\end{enumerate}
diff --git a/cryptography/lectures/lecture28.tex b/cryptography/lectures/lecture28.tex
new file mode 100644
index 0000000..8d097a4
--- /dev/null
+++ b/cryptography/lectures/lecture28.tex
@@ -0,0 +1,125 @@
+% Лекция 28 (05.05.23)
+
+% TODO: дописать
+
+В 1977--78 годах, работая в Массачусетском технологическом институте, они
+создали шифр, названный RSA (по первым буквам фамилий), который произвёл
+переворот в криптографии и открыл новый период в сфере защиты информации.
+
+В настоящее время RSA --- самый распространённый метод шифрования используемый
+в компьютерных сетях. В этом шифре осуществлена другая казавшаяся несбыточной мечта
+криптографов: возможность защищённой связи без передачи секретного ключа.
+
+\begin{enumerate}
+  \item
+    Пусть имеется компьютерная сеть, абоненты которой хотят обмениваться
+    информацией, не предназначенной для непредусмотренных пользователей.
+
+    Абонент A выбирает два больших (примерно по 100--300 цифр) простых числа
+    $p$ и $q$, находит их произведение $n = pq$.
+
+    Затем вычисляется $\varphi(n) = \varphi(pq) = \varphi(p) \varphi(q) = (p -
+    1)(q - 1)$.
+
+    Затем в кольце $\Z_{\varphi(n)}$ подбирает целое число $e > 1$ взаимно
+    простое с $\varphi(n)$. Затем он опубликовывает пару $(n, e)$ --- это его
+    \emph{открытый ключ}, он применяется для шифрования сообщений.
+
+  \item
+    Предположим, что другой абонент B желает отправить для A секретное
+    сообщение. Он переводит открытый текст в числовую форму $m$ (например,
+    заменяя a на 01, b --- на 02, $\dots$, z --- на 26, а пробел между словами
+    --- на 00). Если полученное число $m$ превышает $n$, его можно разбить на
+    последовательные части, каждая меньше $n$, так что для простоты пусть $m <
+    n$. Далее B вычисляет $c = m^e \pmod{n}$. Это криптограмма, которую он и
+    посылает абоненту A.
+
+  \item
+    Для того, чтобы её прочитать, A уже заготовил свой \emph{закрытый ключ} ---
+    число $d$, удовлетворяющее двум требованиям: $1 < d < n$ и $ed \equiv 1
+    \pmod{\varphi(n)}$.
+
+    Так как $e$ взаимно просто с $\varphi(n)$, то это сравнение имеет решение,
+    то есть такое число существует и притом только одно. Теперь A вычисляет
+    $c^d \pmod{n}$ и получает $m$.
+\end{enumerate}
+
+\begin{theorem}[Корректность метода шифрования RSA, Ривест, 1978 г.]
+  По построению шифра RSA $c^d \pmod{n} = m$.
+\end{theorem}
+
+\begin{example}
+  $p = 3, q = 11, n = pq = 3 \cdot 11 = 33$.
+
+  $\varphi(n) = \varphi(pq) = \varphi(p) \varphi(q) = (p - 1) (q - 1) = 2 \cdot
+  10 = 20$.
+
+  $e = 7$ (из кольца $Z_{20}$).
+
+  То есть открытый ключ --- (33, 7).
+
+  $ex = 7x \equiv 1 \pmod{20}$.
+
+  $d = 3; m = 2$.
+\end{example}
+
+Составим криптограмму:
+\begin{equation*}
+  c = m^e \pmod{n} = 2^7 \pmod{33} = 128 \pmod{33} = 29
+\end{equation*}
+
+Таким образом, Боб посылает Алисе криптограмму $c = 29$.
+
+Теперь $m = c^d \pmod{n} = 29^3 \pmod{33} = 2$.
+
+Стойкость шифра RSA основана на задаче разложения на множители для больших
+составных чисел, которая в настоящее время вычислительно (эффективно) не
+разрешима.
+
+
+\subsection{Криптосистема Эль-Гамаля}
+
+Криптосистема Эль-Гамаля была предложена в 1985 году. Криптографическая
+стойкость данной системы основа на сложности проблемы дискретных логарифмов.
+
+\begin{enumerate}
+  \item
+    \textbf{Формирование системы.}
+
+    \begin{enumerate}
+      \item
+        Все участники разделяют в качестве системных параметров простое число
+        $p$ и образующий элемент $\alpha$ и мультипликативной группы $\Z^*_p$;
+      \item
+        Каждый участник $P$ случайным образом выбирает целое число $x_p$, $1
+        \leq x_p \leq p - 2$, которое держит в секрете;
+      \item
+        Каждый участник P вычисляет $y_p = \alpha^{x_p} \pmod{p}$ и
+        объявляет $y_p$ публичным ключом.
+    \end{enumerate}
+
+  \item
+    \textbf{Шифрование сообщения для Боба.}
+
+    Предположим, Алиса хочет послать секретное сообщение Бобу. Сообщение
+    представлено целым числом $0 \leq m \leq p - 1$.
+    \begin{enumerate}
+      \item Алиса выбирает случайное секретное число $0 \leq r \leq p - 1$;
+      \item Алиса вычисляет $R = \alpha^r \pmod{p}$;
+      \item Алиса вычисляет $S = m \cdot y_B^r \pmod{p}$;
+      \item Алиса посылает Бобу пару $(R, S)$.
+    \end{enumerate}
+
+  \item
+    \textbf{Расшифрование сообщения Бобом.}
+    
+    \begin{enumerate}
+      \item
+        Боб получает пару $(R, S)$ и, используя своё секретное $x_B$,
+        восстанавливает сообщение $m$ путём следующего вычисления:
+        \begin{equation*}
+          \frac{s}{R^{x_B}} = m
+        \end{equation*}
+    \end{enumerate}
+\end{enumerate}
+