From 95eca38f113413c68759cfa4afed8455b27df116 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sun, 2 Apr 2023 19:06:38 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?= =?UTF-8?q?=20=D0=B8=D1=81=D0=BF=D1=80=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B8?= =?UTF-8?q?=D1=8F=20=D0=B2=20=D0=BB=D0=B5=D0=BA=D1=86=D0=B8=D0=B8=20=D0=B4?= =?UTF-8?q?=D0=BE=20=D0=BA=D0=BE=D0=BD=D1=82=D1=80=D0=BE=D0=BB=D1=8C=D0=BD?= =?UTF-8?q?=D0=BE=D0=B9=20=D0=B8=20=D0=B4=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB?= =?UTF-8?q?=D0=B5=D0=BD=D0=B0=2023=20=D0=BB=D0=B5=D0=BA=D1=86=D0=B8=D1=8F.?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- cryptography/lectures/lecture17.tex | 31 +++----- cryptography/lectures/lecture18.tex | 4 +- cryptography/lectures/lecture21.tex | 6 +- cryptography/lectures/lecture22.tex | 2 +- cryptography/lectures/lecture23.tex | 153 ++++++++++++++++++++++++++++++++++++ 5 files changed, 170 insertions(+), 26 deletions(-) create mode 100644 cryptography/lectures/lecture23.tex (limited to 'cryptography/lectures') diff --git a/cryptography/lectures/lecture17.tex b/cryptography/lectures/lecture17.tex index 2687455..1ce6a4e 100644 --- a/cryptography/lectures/lecture17.tex +++ b/cryptography/lectures/lecture17.tex @@ -23,7 +23,7 @@ \end{itemize} и заданы функции шифрующего автомата \begin{itemize} - \item $x \to K \to S$, называется \emph{функцией инициализации}; + \item $z : K \to S$, называется \emph{функцией инициализации}; \item $g : S \times K \times X \to K$ --- функцией обновления ключа; \item $h : S \times K \times X \to S$ --- функцией переходов; \item $f : S \times K \times X \to Y$ --- функцией выходов. @@ -40,9 +40,10 @@ Блочный шифр в режиме CFB-m моделируется моноключевым шифрующим автоматом $A_\text{CFB}^m = (X, S, Y, K, z, h, f_m)$, где $X = Y = V_m, S = V_{2n}, z = -s1$ --- не зависящая от ключа $k$ синхропосылка, а функции $f_m$ и $h$ имеют вид +s_1$ --- не зависящая от ключа $k$ синхропосылка, а функции $f_m$ и $h$ имеют +вид \begin{align*} - f_m &= (s_t, k, x_t) = y_t = v^m(E_k(s_t)) \oplus x_t; \\ + f_m(s_t, k, x_t) &= y_t = v^m(E_k(s_t)) \oplus x_t; \\ h(s_t, k, x_t) &= s_{t + 1} = (w^m(s_t), y_t), t = 1, 2, \dots \end{align*} @@ -87,7 +88,7 @@ s1$ --- не зависящая от ключа $k$ синхропосылка, Y, K, z, h, f_m)$, где $X = Y = V_m, S = V_{2n}, z = s_1$ --- не зависящая от ключа $k$ синхропосылка, а функции выходов $f_m$ и переходов $h$ имеют вид \begin{align*} - f_m &= (s_t, k, x_t) = y_t = v^m(E_k(s_t)) \oplus x_t; \\ + f_m(s_t, k, x_t) &= y_t = v^m(E_k(s_t)) \oplus x_t; \\ h(s_t, k) &= s_{t + 1} = (w^m(s_t), v^m(E_k(s_t))), t = 1, 2, \dots \end{align*} @@ -118,14 +119,14 @@ Y, K, z, h, f_m)$, где $X = Y = V_m, S = V_{2n}, z = s_1$ --- не завис \begin{enumerate} \item Серьёзным недостатком режима простой замены является то, что зашифрование - одинаковых блоков исходного текста даёт идентичных блоки шифротекста. + одинаковых блоков исходного текста даёт идентичные блоки шифротекста. В результате криптоаналитик лишь на основе шифрованных данных может делать выводы о свойствах исходного текста. Если некоторые блоки открытого текста повторились, то во всех зашифрованных - сообщениях сообщениях, независимо от используемых ключей, на одинаковых - местах будут встречаться повторяющиеся блоки шифрованных текстов. + сообщениях, независимо от используемых ключей, на одинаковых местах будут + встречаться повторяющиеся блоки шифрованных текстов. Другой пример --- передача ключей в зашифрованном виде по линиям связи. \item @@ -160,7 +161,7 @@ Y, K, z, h, f_m)$, где $X = Y = V_m, S = V_{2n}, z = s_1$ --- не завис дополнительные возможности. \item С помощью метода встречи посередине, Р. Меркель и М. Хеллман показали, как - можно схему двукратного шифрования. + можно вскрыть схему двукратного шифрования. Предположим, что известны блок $M$ открытого текста и соответствующий ему блок $C$ шифрованного текста. Алгоритм вскрытия неизвестных ключей $k_1$ и @@ -170,17 +171,6 @@ Y, K, z, h, f_m)$, где $X = Y = V_m, S = V_{2n}, z = s_1$ --- не завис варианта $k$ ключа $k_1$ вычисляются значения $A(k) = E_k(M)$, после чего значения $k$ помещаются в память по адресу $A(k)$. - На втором этапе опробуются - - \item - Предположим, что известны блок $M$ открытого текста и соответствующий ему - блок $C$ шифрованного текста. Алгоритм вскрытия неизвестных ключей $k_1$ и - $k_2$ состоит из двух этапов. - - На первом этапе перебираются все возможные варианты ключа $k_1$. Для каждого - варианта $k$ ключа $k_1$ вычисляются значения $A(k) = E_k(M)$, после чего - значения $k$ помещаются в память по адресу $A(k)$. - На втором этапе опробуются возможные варианты ключа $k_2$. Для опробуемого варианту $k'$ ключа $k_2$ вычисляются значения $A(k') = D_{k'}(C)$ и производится обращение в память по адресу $A(k')$. Если по этому адресу @@ -229,9 +219,10 @@ Y, K, z, h, f_m)$, где $X = Y = V_m, S = V_{2n}, z = s_1$ --- не завис построении алгебраических и статистических методов вскрытия ключей алгоритма шифрования. + % TODO: что? Аналогичная ситуация возникает в случае, когда криптоаналитику удаётся получить результат зашифрования некоторого сообщения на разных ключах с - дополнительной информацией о различных использованных ключей. + дополнительной информацией о различных использованных ключах. Блочные шифры редко используются в режиме простой замены для шифрования длинных сообщений. diff --git a/cryptography/lectures/lecture18.tex b/cryptography/lectures/lecture18.tex index e952fdb..268fc24 100644 --- a/cryptography/lectures/lecture18.tex +++ b/cryptography/lectures/lecture18.tex @@ -99,7 +99,7 @@ При расшифровании все действия выполняются в обратном порядке, при этом следует использовать соотношения \begin{equation*} - R_{i - i} &= L_i, \\ + R_{i - 1} &= L_i, \\ L_{i - 1} &= R_i + f(L_i, k_i),\, i = \overline{16, 1}, \end{equation*} пользуясь которыми можно <<спуститься>> от $L_{16}$ и $R_{16}$ к $L_0$ и @@ -113,7 +113,7 @@ \item Восемь битов, находящихся в позициях 8, 16, \dots, 64 добавляются в ключ - таким образом, чтобы каждый байт содержал начётное число единиц. Это + таким образом, чтобы каждый байт содержал нечётное число единиц. Это используется для обнаружения ошибок при обмене и хранении ключей. \item diff --git a/cryptography/lectures/lecture21.tex b/cryptography/lectures/lecture21.tex index 688b6e2..678900d 100644 --- a/cryptography/lectures/lecture21.tex +++ b/cryptography/lectures/lecture21.tex @@ -92,13 +92,13 @@ \begin{equation*} g[k] : V_{32} \to V_{32}, - g[k](a) = (T(Vec_{32}(Int_{32}(a) \boxplus Int_{32}(k)))) \lll_{11} + g[k](a) = (t(Vec_{32}(Int_{32}(a) \boxplus Int_{32}(k)))) \lll_{11} \end{equation*} где $k, a \in V_{32}$; \begin{equation*} G[k] : V_{32} \times V_{32} \to V_{32} \times V_{32}, - G[K](a_1, a_0) = (a_0, g[k](a_0) \oplus a_1) + G[k](a_1, a_0) = (a_0, g[k](a_0) \oplus a_1) \end{equation*} где $k, a_0, a_1 \in V_{32}$; @@ -201,7 +201,7 @@ \begin{equation*} R : V_{128} \to V_{128}, R(a) = R(a_{15} \| \dots \| a_0) = - l(a_{15}, \dots, a_0) \| a_15 \| \dots \| a_1 + l(a_{15}, \dots, a_0) \| a_{15} \| \dots \| a_1 \end{equation*} где $a = a_{15} \| \dots \| a_0 \in V_{128}, a_i \in V_8, i = 0, 1, \dots, 15$. diff --git a/cryptography/lectures/lecture22.tex b/cryptography/lectures/lecture22.tex index 23c0842..1140816 100644 --- a/cryptography/lectures/lecture22.tex +++ b/cryptography/lectures/lecture22.tex @@ -1,6 +1,6 @@ % Лекция 22 (24.03.23) -\subsection{ГОСТ 34.13-2015} +\subsection{ГОСТ Р 34.13-2015} Национальный стандарт Российской Федерации ГОСТ Р 34.13-2015 <<Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров>> diff --git a/cryptography/lectures/lecture23.tex b/cryptography/lectures/lecture23.tex new file mode 100644 index 0000000..ed979e9 --- /dev/null +++ b/cryptography/lectures/lecture23.tex @@ -0,0 +1,153 @@ +\begin{itemize} + \item + \textbf{Зашифрование} + + Открытый текст $P \in V^*$ представляется в виде + $P = P_1 \| P_2 \| \dots \| P_q, P_i \in V_s$, $i = 1, 2, \dots, q - 1$, + $P_q \in V_r$, $r \leq s$. + + Блоки шифротекста вычисляются по следующему правилу: + \begin{align*} + &R_1 = IV, \\ + &\begin{cases} + C_i = P_i \oplus MSB_s(e_K(MSB_n(R_i))) \\ + R_{i + 1} = LSB_{m - s}(R_i) \| C_i \\ + i = 1, 2, \dots, q - 1 \\ + \end{cases} \\ + &C_q = P_q \oplus MSB_r(e_K(MSB_n(R_q))) + \end{align*} + + Результирующий шифртекста: $C = C_1 \| C_2 \| \dots \| C_q$. + + % TODO: рис 1 + + \item + \textbf{Расшифрование} + + Шифртекст представляется в виде: $C = C_1 \| C_2 \| \dots \| C_q$, $C_i \in + V_s$, $i = 1, 2, \dots, q - 1$, $C_q \in V_r$, $r \leq s$. + + Блоки открытого текста вычисляются по следующему правилу: + \begin{align*} + &R_1 = IV, \\ + &\begin{cases} + P_i = C_i \oplus MSB_s(e_K(MSB_n(R_i))) \\ + R_{i + 1} = LSB_{m - s}(R_i) \| C_i \\ + i = 1, 2, \dots, q - 1 \\ + \end{cases} \\ + &P_q = C_q \oplus MSB_r(e_K(MSB_n(R_q))) + \end{align*} + + Исходный (дополненный) открытый текст: $P = P_1 \| P_2 \| \dots \| P_q$. + + Если к исходному открытому тексту была применена процедура дополнения, то + после расшифрования следует произвести обратную процедуру. + + Для однозначного восстановления сообщения может потребоваться знание длины + исходного сообщения. + + % TODO: рис 2 +\end{itemize} + + +\paragraph{Режим выработки имитовставки.} + +Данный режим выработки имитовставки реализует конструкцию OMAC1 +(стандартизирован в ISO под названием CMAC). Параметр: длина имитовставки +(в битах) $0 < s \leq n$. + +\begin{itemize} + \item + \textbf{Выработка вспомогательных ключей.} + + При вычислении значения имитовставки используются вспомогательные ключи, + которые вычисляются с использованием ключа $K$. + + Длины вспомогательных ключей равны длине блока $n$ базового алгоритма + блочного шифрования. + + Процедура выработки вспомогательных ключей может быть представлена в + следующей форме + \begin{align*} + R &= e_K(0^n); \\ + K_1 &= \begin{cases} + R \ll 1, &\text{если } MSB_1(R) = 0, \\ + (R \ll 1) \oplus B_n, &\text{иначе} + \end{cases} \\ + K_2 &= \begin{cases} + K_1 \ll 1, &\text{если } MSB_1(K_1) = 0, \\ + (K_1 \ll 1) \oplus B_n, &\text{иначе} + \end{cases} + \end{align*} + где $B_{64} = 0^{59} \| 11011$, $B_{128} = 0^{120} \| 10000111$. + + Если значение $n$ отлично от 64 и 12, следует использовать следующую + процедуру определения значения константы $B_n$. + + Рассмотрим множество примитивных полиномов степени $n$ над полем $GF(2)$ с + наименьшим количеством ненулевых коэффициентов. + + Упорядочим это множество лексикографически по возрастанию векторов + коэффициентов и обозначим через $f_n(x)$ первый полином в этом упорядоченном + множестве. + + Рассмотрим поле $GF(2^n)[x]/(f_n(x))$, зафиксируем в нём степенной базис и + будем обозначать операцию умножения в этом поле символом $\otimes$. + + Вспомогательные ключи $K_1$ и $K_2$ вычисляются следующим образом: + \begin{equation*} + \begin{cases} + R = e_K(0^n), \\ + K_1 = Poly_n^{-1}(Poly_n(R) \otimes x), \\ + K_2 = Poly_n^{-1}(Poly_n(R) \otimes x^2). + \end{cases} + \end{equation*} + + Вспомогательные ключи $K_1, K_2$ и промежуточное значение $R$ наряду с + ключом $K$ являются секретными параметрами. + + Компрометация какого-либо из этих значений приводит к возможности построения + эффективных методов анализа всего алгоритма. + + \item + \textbf{Вычисление значения имитовставки.} + + Процедура вычисления значения имитовставки похожа на процедуру зашифрования + в режиме простой замены с зацеплением при $m = n$ и инициализации начального + заполнения регистра сдвига значением $0^n$: на вход алгоритму шифрования + подаётся результат покомпонентного сложения очередного блока текста и + результата зашифрования на предыдущем шаге. + + Основное отличие заключается в процедуре обработки последнего блока: + на вход базовому алгоритму блочного шифрования подаётся результат + покомпонентного сложения последнего блока, результата зашифрования на + предыдущем шаге и одного из вспомогательных ключей. + + Конкретный вспомогательный ключ выбирается в зависимости от того, является + ли последний блок исходного сообщения полным или нет. + + Значением имитовставки MAC является результат применения процедуры усечения + к выходу алгоритма шифрования при обработке последнего блока. + + Исходное сообщение $P \in V^*$, для которого требуется вычислить + имитовставку, представляется в виде: $P = P_1 \| P_2 \| \dots \| P_q$, где + $P_i \in V_n,\, i = 1, 2, \dots, q - 1$, $P_q \in V_r,\, r \leq n$. + + Процедура вычисления имитовставки описывается следующим образом: + \begin{align*} + C_0 &= 0^n, \\ + C_i &= e_K(P_i \oplus C_{i - 1}),\, i = 1, 2, \dots, q - 1, \\ + MAC &= MSB_s(e_K(P^*_q \oplus C_{q - 1} \oplus K^*)), + \end{align*} + где + \begin{equation*} + K^* = \begin{cases} + K_1, &\text{если } |P_q| = n, \\ + K_2, &\text{иначе}, + \end{cases} + \end{equation*} + $P^*_q$ --- последний блок сообщения, полученного в результате дополнения + исходного сообщения с помощью процедуры 3. + + % TODO: рис 3 +\end{itemize} -- cgit v1.2.3