diff options
Diffstat (limited to 'cryptography')
| -rw-r--r-- | cryptography/cryptography.pdf | bin | 2312545 -> 2401109 bytes | |||
| -rw-r--r-- | cryptography/cryptography.tex | 9 | ||||
| -rw-r--r-- | cryptography/lectures/lecture17.tex | 234 | ||||
| -rw-r--r-- | cryptography/lectures/lecture18.tex | 260 | ||||
| -rw-r--r-- | cryptography/lectures/lecture19.tex | 77 | ||||
| -rw-r--r-- | cryptography/lectures/lecture20.tex | 236 | ||||
| -rw-r--r-- | cryptography/lectures/lecture21.tex | 276 | ||||
| -rw-r--r-- | cryptography/lectures/lecture22.tex | 216 |
8 files changed, 1308 insertions, 0 deletions
diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf Binary files differindex 2b89d40..475e369 100644 --- a/cryptography/cryptography.pdf +++ b/cryptography/cryptography.pdf diff --git a/cryptography/cryptography.tex b/cryptography/cryptography.tex index f82063c..11bd380 100644 --- a/cryptography/cryptography.tex +++ b/cryptography/cryptography.tex @@ -15,6 +15,7 @@ \thispagestyle{empty} \newpage +% Семестр 1 \input{lectures/lecture1.tex} \input{lectures/lecture2.tex} \input{lectures/lecture3.tex} @@ -32,4 +33,12 @@ \input{lectures/lecture15.tex} \input{lectures/lecture16.tex} +% Семестр 2 +\input{lectures/lecture17.tex} +\input{lectures/lecture18.tex} +\input{lectures/lecture19.tex} +\input{lectures/lecture20.tex} +\input{lectures/lecture21.tex} +\input{lectures/lecture22.tex} + \end{document} diff --git a/cryptography/lectures/lecture17.tex b/cryptography/lectures/lecture17.tex new file mode 100644 index 0000000..b5fa730 --- /dev/null +++ b/cryptography/lectures/lecture17.tex @@ -0,0 +1,234 @@ +% Лекция 17 (10.02.23) + +\paragraph{Cipher Feedback.} + +Режим CFB (Cipher Feedback, гаммирование с обратной связью по шифротексту) +удобен в ситуациях, когда требуется шифровать символы поступающего потока, не +дожидаясь формирования целого блока данных. + +Через CFB-m обозначается режим шифрования, в котором блоки открытого и +шифрованного текстов имеют длину $m$ битов ($m$ --- параметр), $1 \leq m \leq +2n$. Для сообщения, состоящего из байтов, удобно взять $m = 8$. + +% Уточнение + +[Автоматные модели симметричных криптосистем. \emph{Шифрующим автоматом} +называется система $A_\text{ш} = (X, S, Y, K, z, g, h, f)$, где конечные +множества +\begin{itemize} + \item $X$ --- алфавит открытого текста; + \item $S$ --- множество состояний (внутренний алфавит); + \item $Y$ --- алфавит шифрованного текста; + \item $K$ --- ключевое множество шифрующего автомата; +\end{itemize} +и заданы функции шифрующего автомата +\begin{itemize} + \item $x \to 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$ --- функцией выходов. +\end{itemize} + +Элементы множества $K$ называются \emph{ключами шифрующего автомата}. + +Если функция $g(s, k, x)$ отлична от тождественного отображения множества $K$, +то есть значение ключа шифрующего автомата зависит от номера такта, то шифрующий +автомат называется \emph{мультиключевым}. В противном случае шифрующий автомат +называется \emph{моноключевым}.] + +% Конец уточнения + +Блочный шифр в режиме 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$ имеют вид +\begin{align*} + 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*} + +На рисунке показана схема зашифрования (в левой части) и расшифрования (в +правой части) в режиме CFB-m. В обеих процедурах базовый режим используется +только для шифрования (реализации подстановки $E^{-1}_k$ не требуется). + +% TODO: рис.1 + +Как и в режиме CBC, синхропосылка может передаваться в линию связи в открытом +виде. Однако необходимо исключить повторение синхропосылки в различных +сообщениях, шифруемых одинаковым ключом. + +Искажение одного бита в блоке $x_t$ влечёт искажение одного бита в $y_t$ и в +среднем половины битов во всех блоках шифротекста, начиная с $y_{t + 1}$, но +при расшифровании получается открытый текст с той же единственной ошибкой. + +Искажение $i$-го бита в блоке $y_t$ влечёт искажение $i$-го бита в блоке $x_t$. +Затем ошибка поступает в регистр состояний и искажает в среднем половину битов +в каждом из следующих $l$ блоков, где $\left[\frac{2n}{m}\right] \leq l \leq +\left] \frac{2n}{m} \right[$. + +В дальнейшем блоки расшифровываются корректно. + +Режим CFB самостоятельно восстанавливается после ошибок синхронизации. + + +\paragraph{Output Feedback.} + +Блочный шифр в режиме OFB (Output Feedback, \emph{гаммирование} или +\emph{внутренняя обратная связь}) можно рассматривать как синхронный шифр +гаммирования, обрабатывающий $m$-битовые блоки открытого или шифрованного текста +(обозначение --- OFB-m). + +Этот шифр моделируется моноключевым шифрующим автоматом $A_\text{OFB}^m = (X, S, +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; \\ + h(s_t, k) &= s_{t + 1} = (w^m(s_t), v^m(E_k(s_t))), t = 1, 2, \dots +\end{align*} + +На рисунке показана схема зашифрования (в левой части) и расшифрования (в правой +части) в режиме OFB-m. В обеих процедурах базовый режим используется только для +зашифрования. + +% TODO: рис. 2 + +При использовании режима OFB важно сохранять синхронизм. Для этого необходимо +предусмотреть средство контроля над синхронизмом и средство восстановления +синхронизма в случае его потери. + +Рекомендации по синхропосылке те же, что и в режимах CBC и CFB-m. + +В режиме OFB ошибки не распространяются. + + +\subsection{Методы анализа блочных шифрсистем} + +Рассмотрим эксплуатацию блочных шифров в режиме простой замены. + +\begin{enumerate} + \item + Серьёзным недостатком режима простой замены является то, что зашифрование + одинаковых блоков исходного текста даёт идентичных блоки шифротекста. + + В результате криптоаналитик лишь на основе шифрованных данных может делать + выводы о свойствах исходного текста. + + Если некоторые блоки открытого текста повторились, то во всех зашифрованных + сообщениях сообщениях, независимо от используемых ключей, на одинаковых + местах будут встречаться повторяющиеся блоки шифрованных текстов. + + Другой пример --- передача ключей в зашифрованном виде по линиям связи. + \item + При достаточно большой длине шифртекста можно применять методы анализа, + использующие статистические характеристики открытых текстов. + + Например, вычисляя частоты появления блоков в шифрованном тексте и проводя + опробование часто повторяющихся блоков, начиная с наиболее вероятных + сочетаний в открытом тексте, можно составить словарь соответствия между + блоками открытого и шифрованного текстов. + + Далее, развивая текст по смыслу с учётом избыточности открытых текстов, + найденные блоки открытого текста можно дополнять соседними блоками. + + При этом одновременно восстанавливается открытый текст и дополняется словарь + соответствия. Этот метод эффективен, когда наблюдается стандартность + переписки. + \item + При шифровании осмысленных текстов в открытом тексте могут появляться + не все сочетания знаков, что проявляется в фактическом сокращении числа + используемых соответствий между блоками открытого и шифрованного текстов. + + Однако эта слабость легко устранима, если перед шифрованием применить к + открытому тексту процедуру сжатия информации. + \item + Проблема последнего неполного блока данных при шифровании текстов, длины + которых не кратны размеру блока. При использовании блочного шифра этот + неполный блок должен быть каким-либо дополнен до стандартной длины. + + Если при этом алгоритм дополнения выбран неудачно, то при определении + соответствующего блока открытого текста у криптоаналитика появляются + дополнительные возможности. + \item + С помощью метода встречи посередине, Р. Меркель и М. Хеллман показали, как + можно схему двукратного шифрования. + + Предположим, что известны блок $M$ открытого текста и соответствующий ему + блок $C$ шифрованного текста. Алгоритм вскрытия неизвестных ключей $k_1$ и + $k_2$ состоит из двух этапов. + + На первом этапе перебираются все возможные варианты ключа $k_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')$. Если по этому адресу + памяти записи отсутствуют, то происходит переход к опробованию следующего + варианта $k'$ ключа $k_2$. Если же по адресу $A(k')$ в память хранится + ключ $k$, то образуется допустимая пара ключей $(k, k')$, удовлетворяющая + равенству $C = E_{k'}(E_k(M))$. + + Таким образом, вместо $|K|^2$ операций требуется $2|K|$ опробований и + столько же обращений к памяти, таким образом затраты метода встречи + посередине составляют порядка $4|K|$ операций. + + \item + Идея метода \emph{линейного анализа} состоит в \emph{линеаризации} + уравнений шифрования, то есть замене сложных преобразований, описывающих + алгоритм шифрования, их приближениями в классе линейных функций. Под + приближением в классе линейных функций (или \emph{линейным аналогом}) + понимается линейная функция, значения которой для достаточно большого + числа наборов аргументов совпадают со значениями данной функции шифрования. + + Таким образом, линейный анализ сводит задачу определения ключей к решению + системы линейных уравнений, в которой правые части уравнений известны с + некоторой вероятностью. Если распределение значений правых частей уравнений + системы отлично от равномерного распределения, и имеется достаточно большое + число уравнений, то решение такой системы линейных уравнений может быть + найдено статистическими методами. + + Проблема построения блочных шифров, для которых удаётся доказать отсутствие + линейных аналогов, является весьма сложной задачей современной прикладной + криптографии. + + \item + Методы \emph{дифференциального (разностного) анализа} строятся в + предположении, что криптоаналитик имеет для анализа несколько текстов, + зашифрованных на одном ключе, и дополнительно предполагается известной + информация о том, как различаются между собой открытые тексты. + + В этом случае криптоаналитик получает информацию о том, как заданные отличия + в открытых текстах проявляются в шифротекстах, или, другими словами, как + разность аргументов шифрующего преобразования отражается на изменении его + значений. + + Поскольку шифрующее преобразование однозначно определяется ключом, то + информация о зависимостях между разностями значений аргументов и разностями + соответствующих значений функции шифрования может быть использована при + построении алгебраических и статистических методов вскрытия ключей алгоритма + шифрования. + + Аналогичная ситуация возникает в случае, когда криптоаналитику удаётся + получить результат зашифрования некоторого сообщения на разных ключах с + дополнительной информацией о различных использованных ключей. + + Блочные шифры редко используются в режиме простой замены для шифрования + длинных сообщений. + + Режим простой замены применяется в основном в системах передачи ключей и в + платёжных системах, где сообщения состоят из небольшого числа блоков. + + Чаще блочные шифры используются в режиме шифрования с обратной связью, когда + очередной блок шифра зависит не только от ключа, но и от предшествующих + блоков шифротекста. +\end{enumerate} diff --git a/cryptography/lectures/lecture18.tex b/cryptography/lectures/lecture18.tex new file mode 100644 index 0000000..610a91d --- /dev/null +++ b/cryptography/lectures/lecture18.tex @@ -0,0 +1,260 @@ +% Лекция 18 (17.02.23) + +\subsection{DES} + +В 1973--1974 гг. Национальное бюро стандартов США объявило открытый конкурс на +создание общедоступного алгоритма шифрования с гарантированной надёжностью. + +Оценку представленных кандидатов осуществляло Агентство Национальной +Безопасности США. + +В январе 1977 года предложенный фирмой IBM и оказавшийся победителем конкурса +<<Алгоритм шифрования для защиты данных ЭВМ>> был зарегистрирован в качестве +государственного стандарта США: Data Encryption Standard (Стандарт шифрования +данных, DES). + +Сразу же после создания DES были созданы чипы для быстрого аппаратного +шифрования. Вся структура DES была полностью опубликована при его введении в +качестве стандарта. Создание шифра DES была полностью опубликована при его +введении в качестве стандарта. + +Создание шифра DES (главным идеологом проекта был Х. Фейстель (1915--1990)) +явилось выдающимся научно-техническим достижением, оказавшим глубокое влияние +на дальнейшее развитие криптографии и на её использование в интересах широких +деловых кругов. + +Достоинства: простота ключевой системы, высокая скорость аппаратной и +программной реализации, достаточно высокая криптографическая стойкость алгоритма +шифрования при заданной длине ключа. + +Алгоритм DES является блочным шифром. Открытый текст, представленный в двоичном +виде, разбивается на блоки длины 64 бита, которые переводятся в такой же длины +блоки криптограммы с помощью чередования перестановочных и подстановочных +шифров. + +Обозначения: +\begin{itemize} + \item $L_i$, $R_i$ --- левая и правая половины 64-битного блока $L_i R_i$; + \item $\oplus$ --- операция побитового сложения вектор-блоков по модулю 2; + \item $k_i$ --- 48-битовые ключи; + \item $f$ --- функции шифрования; + \item $IP$ --- начальная перестановка степени 64. +\end{itemize} + +\begin{remark} + Все приводимые таблицы являются стандартными и должны использоваться при + реализации алгоритма DES в неизменном виде. Все перестановки и коды в таблицах + подобраны разработчиками таким образом, чтобы максимально затруднить процесс + вскрытия шифра путём подбора ключа. +\end{remark} + +\begin{enumerate} + \item + При зашифровании очередного блока $T$ его биты подвергаются начальной + перестановке $IP$ согласно таблице \ref{tbl:ip-permutation}. + + \begin{table}[h] + \centering + \caption{Начальная перестановка $IP$} + \begin{tabular}{|c|c|c|c|c|c|c|c|} + \hline + 58 & 50 & 42 & 34 & 26 & 18 & 10 & 2 \\ \hline + 60 & 52 & 44 & 36 & 28 & 20 & 12 & 4 \\ \hline + 62 & 54 & 46 & 38 & 30 & 22 & 14 & 6 \\ \hline + 64 & 56 & 48 & 40 & 32 & 24 & 16 & 8 \\ \hline + 57 & 49 & 41 & 33 & 25 & 17 & 9 & 1 \\ \hline + 59 & 51 & 43 & 35 & 27 & 19 & 11 & 3 \\ \hline + 61 & 53 & 45 & 37 & 29 & 21 & 13 & 5 \\ \hline + 63 & 55 & 47 & 39 & 31 & 23 & 15 & 7 \\ \hline + \end{tabular} + \label{tbl:ip-permutation} + \end{table} + + Полученный после перестановки блок $IP(T)$ разделяется на две половины: + $L_0$, состоящую из 32 старших бит, и $R_0$, состоящую из 32 младших бит. + После этого следуют 16 раундов шифрования с использованием секретного ключа + $k$. + + Пусть $T_{i - 1} = L_{i - 1} R_{i - 1}$ --- результат $(i - 1)$-й итерации. + Тогда результат $i$-й итерации $T_i = L_i R_i$ определяется формулами: + \begin{align*} + L_i &= R_{i - 1} \\ + R_i &= L_{i - 1} \oplus f(R_{i - 1}, k_i), i = \overline{1, 16} + \end{align*} + + Функция $f$ называется \emph{функцией шифрования}. Её аргументами являются + 32-битовый вектор $R_{i - 1}$ и 48-битовый ключ $k_i$, который является + результатом преобразования 56-битового ключа шифра $k$. + + % TODO: рисунок 1, в конце поменять местами R_16 и L_16 + + Результатом последней итерации является блок $T_{16} = L_{16} R_{16}$. По + окончании шифрования осуществляется восстановление позиций битов применением + к $T_{16}$ обратной перестановки $IP^{-1}$. + + При расшифровании все действия выполняются в обратном порядке, при этом + следует использовать соотношения + \begin{equation*} + R_{i - i} &= L_i, \\ + L_{i - 1} &= R_i + f(L_i, k_i),\, i = \overline{16, 1}, + \end{equation*} + пользуясь которыми можно <<спуститься>> от $L_{16}$ и $R_{16}$ к $L_0$ и + $R_0$. + + На каждой итерации используется текущее значение ключа $k_i$ (48 бит), + получаемое из исходного ключа $k$ следующим образом. + + Сначала пользователи выбирают сам ключ $k$, содержащий 56 случайных значащих + битов. + + \item + Восемь битов, находящихся в позициях 8, 16, \dots, 64 добавляются в ключ + таким образом, чтобы каждый байт содержал начётное число единиц. Это + используется для обнаружения ошибок при обмене и хранении ключей. + + \item + Значащие 56 бит ключа подвергаются перестановке, приведённой в таблице + \ref{tbl:des-permutation} + \begin{table}[H] + \centering + \caption{} + \begin{tabular}{|c|c|c|c|c|c|c|} + \hline + 57 & 49 & 41 & 33 & 25 & 17 & 9 \\ \hline + 1 & 58 & 50 & 42 & 34 & 26 & 18 \\ \hline + 10 & 2 & 59 & 51 & 43 & 35 & 27 \\ \hline + 19 & 11 & 3 & 60 & 52 & 44 & 36 \\ \hline + 63 & 55 & 47 & 39 & 31 & 23 & 15 \\ \hline + 7 & 62 & 54 & 46 & 38 & 30 & 22 \\ \hline + 14 & 6 & 61 & 53 & 45 & 37 & 29 \\ \hline + 21 & 13 & 5 & 28 & 20 & 12 & 4 \\ \hline + \end{tabular} + \label{tbl:des-permutation} + \end{table} + + Эта перестановка определяется двумя блоками $C_0$ и $D_0$ по 28 бит в каждом + (они занимают соответственно верхнюю и нижнюю половину таблицы). + + Затем индуктивно определяются блоки $C_i$ и $D_i$, $i = \overline{1, + 16}$. Если уже определены $C_{i - 1}$ и $D_{i - 1}$, то $C_i$ и $D_i$ + получаются из них циклическим сдвигом влево на одну или две позиции в + зависимости от номера раунда. При $i = 1, 2, 9, 16$ сдвиг на одну позицию, + при остальных значениях --- на две. После сдвигов по заданному способу + строится 48"=битовый раундовый ключ. + + \item + Теперь определим ключи $k_i$, $1 \leq i \leq 16$. Ключ $k_i$ состоит из 48 + битов, выбираемых из битов блока $C_i D_i$ согласно таблице + \ref{tbl:des-key-blocks} + \begin{table}[H] + \centering + \caption{} + \begin{tabular}{|c|c|c|c|c|c|c|} + \hline + 14 & 17 & 11 & 24 & 1 & 5 \\ \hline + 3 & 28 & 15 & 6 & 21 & 10 \\ \hline + 23 & 19 & 12 & 4 & 26 & 8 \\ \hline + 16 & 7 & 27 & 20 & 13 & 2 \\ \hline + 41 & 52 & 31 & 37 & 47 & 55 \\ \hline + 30 & 40 & 51 & 45 & 33 & 48 \\ \hline + 44 & 49 & 39 & 56 & 34 & 53 \\ \hline + 46 & 42 & 50 & 36 & 29 & 32 \\ \hline + \end{tabular} + \label{tbl:des-key-blocks} + \end{table} + + Первыми тремя битами в $k_i$ являются биты 14, 17, 11 из блока $C_i D_i$. + Заметим, что 8 из 56 бит (с номерами 9, 18, 22, 25, 35, 38, 43, 54) из + $C_i D_i$ отсутствуют в $k_i$. + + \item + Центральной частью шифра является предложенная Х. Фейстелем функция $f(R_{i + - 1}, k_i)$. + + % TODO: рисунок 2 + + Для вычисления значения функции $f$ используются: функция расширения $E$; + преобразование $S$, составленное из восьми преобразования S-блоков $S1, S2, + \dots, S8$; перестановка $P$. + + Аргументами функции $f$ являются вектор $R_{i - 1}$ (32 бита) и вектор + $k_i$ (48 бит). Функция $E$ <<расширяет>> 32-битовый вектор $R_{i - 1}$ до + 48-битового вектора $R_{i - 1}$, при этом порядок следования битов в $E(R_{i + - 1})$ указан в таблице \ref{tbl:des-feistel} + + \begin{table}[H] + \centering + \caption{} + \begin{tabular}{|c|c|c|c|c|c|c|} + \hline + 32 & 1 & 2 & 3 & 4 & 5 \\ \hline + 4 & 5 & 6 & 7 & 8 & 9 \\ \hline + 8 & 9 & 10 & 11 & 12 & 13 \\ \hline + 12 & 13 & 14 & 15 & 16 & 17 \\ \hline + 16 & 17 & 18 & 19 & 20 & 21 \\ \hline + 20 & 21 & 22 & 23 & 24 & 25 \\ \hline + 24 & 25 & 26 & 27 & 28 & 29 \\ \hline + 28 & 29 & 30 & 31 & 32 & 1 \\ \hline + \end{tabular} + \label{tbl:des-feistel} + \end{table} + + Полученный результат складывается побитно по модулю 2 с текущим значением + ключа $k_i$ и затем разбивается на 8 последовательных 6-битовых групп, + каждая из которых подаётся на вход соответствующего подстановочного + шифратора, так называемого S-бокса (substitution boxes --- таблицы замены, + $S1, S2, \dots, S8$). + + S-бокс представляет собой таблицу размерности $4 \times 16$ с нумерацией + строк $0, 1, 2, 3$ и столбцов от 0 до 15. + + В каждой строке стоит своя перестановка столбцовых номеров. + \begin{table}[H] + \centering + \caption{} + \begin{tabular}{|c|cccccccccccccccc|} + \hline + S7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline + 0 & 4 & 11 & 2 & 14 & 15 & 0 & 8 & 13 & 3 & 12 & 9 & 7 & 5 & 10 & 6 & 1 \\ + 1 & 13 & 0 & 11 & 7 & 4 & 9 & 1 & 10 & 14 & 3 & 5 & 12 & 2 & 15 & 8 & 6 \\ + 2 & 1 & 4 & 11 & 13 & 12 & 3 & 7 & 14 & 10 & 15 & 6 & 8 & 0 & 5 & 9 & 2 \\ + 3 & 6 & 11 & 13 & 8 & 1 & 4 & 10 & 7 & 9 & 5 & 0 & 15 & 14 & 2 & 3 & 12 \\ \hline + \end{tabular} + \label{tbl:des-feistel-sbox} + \end{table} + На вход S-бокса подаётся 6-разрядный двоичный блок $a_0 a_1 a_2 a_3 a_4 a_5$. + + Первый и последний его символы $a_0 a_5$ определяют строку S-бокса, средние + $a_1 a_2 a_3 a_4$ --- его столбец. Стоящее на пересечении строки и столбца + число даёт в двоичной записи 4-разрядный выходной блок. Переработка + 6-буквенных двоичных блоков в 4-буквенные и является функцией S-бокса. + + \begin{example} + Пусть на вход S-бокса 7 подаётся двоичное слово 001011. Оно выделяет + в таблице строку с номером 1 (01) и столбец с номером 5 (0101). На их + пересечении стоит число 9. Его двоичная запись 1001 и появляется на + выходе. + \end{example} + + Полученные восемь 4-битовых выходных вектора соединяются в один 32-битный. + + \item + Значение $f(R_{i - 1}, k_i)$ получается применением перестановки битов $P$, + заданной таблицей к результирующему 32-битовому блоку. + \begin{table}[H] + \centering + \caption{} + \begin{tabular}{|c|c|c|c|} + \hline + 16 & 7 & 20 & 21 \\ \hline + 29 & 12 & 28 & 17 \\ \hline + 1 & 15 & 23 & 26 \\ \hline + 5 & 18 & 31 & 10 \\ \hline + 2 & 8 & 24 & 14 \\ \hline + 32 & 27 & 3 & 9 \\ \hline + 19 & 13 & 30 & 6 \\ \hline + 22 & 11 & 4 & 25 \\ \hline + \end{tabular} + \label{tbl:des-feistel-sbox} + \end{table} +\end{enumerate} diff --git a/cryptography/lectures/lecture19.tex b/cryptography/lectures/lecture19.tex new file mode 100644 index 0000000..15f1d2e --- /dev/null +++ b/cryptography/lectures/lecture19.tex @@ -0,0 +1,77 @@ +% Лекция 19 (03.03.23) + +Все используемые в DES перестановки и подстановки известны. Неизвестен только +секретный 56-разрядный ключ $K$, принадлежащий пользователю. Таким образом, в +DES реализован идеал Керкхофса: о шифре известно всё, кроме ключа. + +Для прямого взлома DES нужно перебрать $2^{56}$ возможных ключей. + +В июле 1998 года, затратив более 250000 долларов, компания EFF предъявила +суперкомпьютер <<DES-взломщик>>, изготовленный с использованием 1536 чипов, +обеспечивавших проверку 28 миллиардов ключей в секунду. С его помощью +контрольная DES-криптограмма была дешифрована за 56 часов. + +В январе 1999 года, присоединив ещё 100000 объединённых в сеть персональных +компьютеров, EFF справилась с этой задачей уже за 22 часа. + +В январе 2000 года правительство США признало алгоритм DES ненадёжным. + + +\subsection{AES} + +В 1997 году NIST объявило открытый международный конкурс на новый шифр, +названный AES (Advanced Encryption Standard, Усовершенствованный стандарт +шифрования). + +Требования к кандидатам на AES: +\begin{enumerate} + \item Криптоалгоритм должен быть открыто опубликован. + \item + Он должен быть блочным шифром, допускающим размеры ключей --- 128, 192, 256 + битов. + \item + Криптоалгоритм должен быть предназначен как для аппаратной, так и для + программной реализации. + \item Криптоалгоритм не должен быть запатентован. + \item + Он должен быть подвергнут специальному изучению на стойкость, стоимость, + скорость шифрования и на реализуемость в смарт-картах. +\end{enumerate} + +% TODO: что-то дописать может быть... + +%% Начало дополнительной информации +[Для каждого простого числа $p$ и натурального числа $n$ существует одно и с +точностью до изоморфизма только одно поле с количеством элементов $p^n$. Такое +поле принято обозначать в честь Э. Галуа через $GF(p^n)$. Любое конечное поле +является полем Галуа для подходящих $p$ и $n$. Поле $GF(p)$ --- это поле +вычетов $\Z_p$. + +Элементы поля $GF(p^n)$ при $n > 1$ можно рассматривать как многочлены над +полем вычетов $\Z_p$. Для многочленов вводится понятие деления с остатком: +разделить многочлен $a(x)$ на многочлен $m(x)$ степени $n$ --- это значит +представить $a(x)$ в виде +\begin{equation*} + a(x) = q(x) m(x) + r(x) +\end{equation*} +где степень многочлена $r(x)$ строго меньше $n$. + +По аналогии с целыми числами вводится понятие сравнимости многочленов по модулю +заданного многочлена $m(x)$. + +Роль полной системы вычетов по модулю многочлена $m(x)$ степени $n$ выполняет +множество всех возможных остатков от деления многочленов над $\Z_p$ на $m(x)$, +то есть это будет +\begin{equation*} + \set{r(x) = r_0 + r_1 x + \dots + r_{n - 1} x^{n - 1}, r_0, r_1, \dots, r_{n - + 1} \in \Z_p} +\end{equation*} + +Очевидно, что таких остатков имеется $p^n$. Множество вычетов по модулю +фиксированного многочлена $m(x)$ степени $n$ с операциями сложения и умножения +многочленов по модулю $m(x)$ образуют коммутативное кольцо. + +Это кольцо будет полем тогда и только тогда, когда $m(x)$ неприводимый многочлен +над $\Z_p$, то есть неразлагающийся на произведения многочленов меньших +степеней.] +%% Конец дополнительной информации diff --git a/cryptography/lectures/lecture20.tex b/cryptography/lectures/lecture20.tex new file mode 100644 index 0000000..9efc760 --- /dev/null +++ b/cryptography/lectures/lecture20.tex @@ -0,0 +1,236 @@ +% Лекция 20 (10.03.23) + +Шифр AES является чисто алгебраической криптосистемой. В шифре AES +обрабатываются блоки длины 128 бит. Возможная длина ключа --- 128, 192 или 256 +бит. При 128-битном ключе осуществляется 10 раундов шифрования. Обрабатываемый +128-битный блок разбивается на 16 блоков. + +Они образуют поле $GF(2^8)$, то есть интерпретируются как многочлены степени 8 +над полем вычетов $\Z_2 = GF(2)$. + +\begin{example} + $11001110 = x + x^2 + x^3 + x^6 + x^7$ +\end{example} + +Сложение $+$ --- это обычное сложение многочленов над $\Z_2$, иначе говоря, +поразрядное сложение байтов по модулю 2. + +\begin{example} + $01010111 + 10000011 = 11010100$ +\end{example} + +Чтобы получить произведение $\cdot$ байтов, их перемножают как многочлены над +$\Z_2$ и берут остаток от деления результата на неприводимый многочлен $m(x) = +x^8 + x^4 + x^3 + x + 1$. + +% TODO: пример 1??? +\begin{example} + $01010111 \cdot 10000011 = \dots = 11000001$ +\end{example} + +Все блоки, проходящие через алгоритм, называются состояниями (States), входной +блок --- это начальное состояние (Initial State). Состояние представляется в +виде массива байтов размерности $4 \times 4$. + +Таблица --- Состояние. +\begin{table}[H] + \centering + \begin{tabular}{|c|c|c|c|} + \hline + $S_{00}$ & $S_{01}$ & $S_{02}$ & $S_{03}$ \\ \hline + $S_{10}$ & $S_{11}$ & $S_{12}$ & $S_{13}$ \\ \hline + $S_{20}$ & $S_{21}$ & $S_{22}$ & $S_{23}$ \\ \hline + $S_{30}$ & $S_{31}$ & $S_{32}$ & $S_{33}$ \\ \hline + \end{tabular} +\end{table} + +Ключ шифрования и раундовый 128-битные ключи (Key) также представляются в виде +массивов байтов. + +Таблица --- Ключ. +\begin{table}[H] + \centering + \begin{tabular}{|c|c|c|c|} + \hline + $K_{00}$ & $K_{01}$ & $K_{02}$ & $K_{03}$ \\ \hline + $K_{10}$ & $K_{11}$ & $K_{12}$ & $K_{13}$ \\ \hline + $K_{20}$ & $K_{21}$ & $K_{22}$ & $K_{23}$ \\ \hline + $K_{30}$ & $K_{31}$ & $K_{32}$ & $K_{33}$ \\ \hline + \end{tabular} +\end{table} + +Раундовое преобразование состоит из четырёх операций: +\begin{enumerate} + \item Замена байтов SubBytes; + \item Сдвиг строк ShiftRows; + \item Перемешивание столбцов MixColumns; + \item Прибавление раундового ключа AddRoundKey. +\end{enumerate} + +\paragraph{Замена байтов SubBytes.} + +Над байтом-аргументом осуществляются следующие действия: +\begin{enumerate} + \item + В поле $GF(2^8)$ для этого байта берётся обратный элемент (для нуля им + считается ноль); + \item + К полученному байту $b$, рассматриваемому как вектор-столбец над $\Z_2$, + применяется преобразование + \begin{equation*} + b\ = \fn{SubBytes}(b) = Ab + c + \end{equation*} + где + \begin{equation*} + A = \begin{vmatrix} + 1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ + 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ + 1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ + 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 \\ + 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ + 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ + 0 & 0 & 1 & 1 & 1 & 1 & 1 & 0 \\ + 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ + \end{vmatrix},\, + c = \begin{vmatrix} + 1 \\ + 1 \\ + 0 \\ + 0 \\ + 0 \\ + 1 \\ + 1 \\ + 0 \\ + \end{vmatrix} + \end{equation*} +\end{enumerate} + + +\paragraph{Сдвиг строк ShiftRows.} + +В аргументе-состоянии первая строка остаётся неизменной, вторая сдвигается +циклически влево на 1 байт, третья --- на 2 байта, четвёртая --- на 3 байта. + +\begin{table}[H] + \centering + \caption{State} + \begin{tabular}{|c|c|c|c|} + \hline + $S_{00}$ & $S_{01}$ & $S_{02}$ & $S_{03}$ \\ \hline + $S_{10}$ & $S_{11}$ & $S_{12}$ & $S_{13}$ \\ \hline + $S_{20}$ & $S_{21}$ & $S_{22}$ & $S_{23}$ \\ \hline + $S_{30}$ & $S_{31}$ & $S_{32}$ & $S_{33}$ \\ \hline + \end{tabular} +\end{table} + +\begin{table}[H] + \centering + \caption{ShiftRows(State)} + \begin{tabular}{|c|c|c|c|} + \hline + $S_{00}$ & $S_{01}$ & $S_{02}$ & $S_{03}$ \\ \hline + $S_{11}$ & $S_{12}$ & $S_{13}$ & $S_{10}$ \\ \hline + $S_{22}$ & $S_{23}$ & $S_{20}$ & $S_{21}$ \\ \hline + $S_{33}$ & $S_{30}$ & $S_{31}$ & $S_{32}$ \\ \hline + \end{tabular} +\end{table} + +\paragraph{Перемешивание столбцов MixColumns.} + +Образ столбца-аргумента $s_i, 0 \leq i \leq 3$, из состояния вычисляется как +произведение над $GF(2^8): s'_i = \fn{MixColumns}(s_i) = S s_i$, где +\begin{equation*} + S = \begin{vmatrix} + \set{2} & \set{3} & \set{1} & \set{1} \\ + \set{1} & \set{2} & \set{3} & \set{1} \\ + \set{1} & \set{1} & \set{2} & \set{3} \\ + \set{3} & \set{1} & \set{1} & \set{2} \\ + \end{vmatrix} +\end{equation*} +где $\set{n}$ --- двоичная восьмибитовая запись числа $n$. + +Применение операции ко всем четырём столбцам состояния обозначается +$\fn{MixColumns}(\fn{State})$. + + +\paragraph{Прибавление раундового ключа AddRoundKey.} + +Поразрядно по модулю 2 к состоянию прибавляется раундовый ключ. + +Как осуществляется выработка раундовых ключей (KeySchedule)? + +Первым этапом является расширение ключа (KeyExpansion). + +Расширенный ключ в AES представляет собой линейный массив длиной 1408 битов, +разбитый на 44 слова, состоящих из 4 байтов каждое. + +\begin{equation*} + \underbrace{w_0 w_1 w_2 w_3}_{K_0} \underbrace{w_4 w_5 w_6 w_7}_{K_1} w_8 \dots w_{39} + \underbrace{w_{40} w_{41} w_{42} w_{43}}_{K_{10}} +\end{equation*} + +При этом первые 4 слова --- ключ шифрования $K = K_0$. Все остальные слова +определяются рекурсивно из слов с меньшими индексами: +\begin{enumerate} + \item Если $4 \nmid i$, то $w_i = w_{i - 1} \oplus w_{i - 4}$; + \item Пусть $4 \mid i$. +\end{enumerate} + +В слове $w_{i - 1}$ осуществляется побайтовый сдвиг $w_{i - 1} = b_0 b_1 b_2 b_3 +\mapsto b_1 b_2 b_3 b_0 = \fn{RotWord}(w_{i - 1}) = w'_{i - 1}$. + +В итоге, $w_i = \fn{SubWord}(\fn{RotWord}(w_{i - 1})) \oplus \fn{Rcon} \left( +\frac{i}{4} \right) \oplus w_{i - 4}$. Здесь $\fn{Rcon}(j)$ --- раундовая +константа, равная $2^{j - 1}$. + +Выбор раундового ключа (Round Key Selection) для раунда с номером $i$ +производится выделением из расширенного ключа массива слов +\begin{equation*} + w_{4i} w_{4i + 1} w_{4i + 2} w_{4i + 3} +\end{equation*} + +Схема шифрования: +% TODO: рисунок 1 (опечатка 2 раунд -> 9 раунд) + +Все четыре преобразования SubBytes, ShiftRows, MixColumns, AddRoundKey обратимы +(у последнего обратное совпадает с ним самим). + +При дешифровании к выходному блоку криптограммы в обратной по отношению +к шифрованию последовательности выполняются инверсии соответствующих +преобразований. При этом меняется и порядок использования раундовых ключей +$(K_{10}, K_9, \dots, K_1, K_1)$. + + +\subsection{ГОСТ Р 34.12-2015} + +В конце 1989 года был открыт и зарегистрирован в качестве государственного +стандарта шифрования ГОСТ 28147-89 <<Система обработки информации. Защита +криптографическая. Алгоритм криптографического преобразования>>. + +Данный блочный шифр был разработан в 1978 году группой советских криптографов +во главе с И. А. Заботиным в 8-м главном управлении КГБ СССР. + +Он был предназначен для шифрования сообщений, содержащих высшие грифы +секретности (государственная тайна) и сам имел гриф <<совершенно секретно>>. + +В 1988 году гриф шифра был понижен до <<секретно>>, в 1989 году --- для +служебного пользования. + +В 2015 году утверждён новый национальный стандарт РФ ГОСТ Р 34.12-2015 +<<Информационная технология. Криптографическая защита информации. Блочные +шифры>>. + +Разработан Центром защиты информации и специальной связи ФСБ России с участием +ОАО <<ИнфоТеКС>>. Утверждён и введён в действие Приказом Федерального агентства +по техническому регулированию и метрологии от 19 июня 2015 г. №749-ст. + +Настоящий стандарт содержит описание алгоритмов блочного шифрования, которые +применяются в криптографических методах защиты информации. + +Необходимость разработки стандарта вызвана потребностью в создании блочных +шифров с различными длинами блока, соответствующих современным требованиям к +криптографической стойкости и эксплуатационными качествам. + +В настоящем стандарте приведено описание двух базовых блочных шифров с длинами +блоков $n = 128$ бит (<<Кузнечик>>) и $n = 64$ бит (<<Магма>>) и длинами ключей +$k = 256$ бит. diff --git a/cryptography/lectures/lecture21.tex b/cryptography/lectures/lecture21.tex new file mode 100644 index 0000000..688b6e2 --- /dev/null +++ b/cryptography/lectures/lecture21.tex @@ -0,0 +1,276 @@ +% Лекция 21 (17.03.23) + +Введём обозначения: +\begin{itemize} + \item + $V^*$ --- множество всех двоичных строк конечной длины, включая пустую + строку; + \item + $V_s$ --- множество всех двоичных строк длины $s$, где $s$ --- целое + неотрицательное число, нумерация подстрок и компонент строки осуществляется + справа налево, начиная с нуля; + \item + $U \times W$ --- прямое (декартово) произведение множества $U$ и + множества $W$; + \item + $|A|$ --- число компонент (длина) строки $A \in V^*$ (если $A$ --- пустая + строка, то $|A| = 0$); + \item + $A \| B$ --- конкатенация строк $A, B \in V^*$; + \item + $A \lll_{11}$ --- циклический сдвиг строки $A \in V_{32}$ на 11 компонент в + сторону компонент, имеющих большие номера; + \item + $\oplus$ --- операция покомпонентного сложения по модулю 2 двух двоичных + строк одинаковой длины; + \item + $Z_{2^s}$ --- кольцо вычетов по модулю $2^s$; + \item + $\boxplus$ --- операция сложения в кольце $\Z_{2^{32}}$; + \item + $\mathbb{F}$ --- конечное поле $GF(2)[x] / p(x)$, где $p(x) = x^8 + x^7 + + x^6 + x + 1 \in GF(2)[x]$; элементы поля $\mathbb{F}$ представляются целыми + числами, причём элементу $z_0 + z_1 \cdot \theta + \dots z_7 \cdot \theta^7 + \in \mathbb{F}$ соответствует число $z_0 + 2 \cdot z_1 + \dots + 2^7 \cdot + z_7$, где $z_i \in \set{0, 1},\, i = 0, 1, \dots, 7$ и $\theta$ обозначает + класс вычетов по модулю $p(x)$, содержащий $x$; + \item + $Vec_s : Z_{2^s} \to V_s$ --- биективное отображение, сопоставляющее + элементу кольца $Z_{2^s}$ его двоичное представление; + \item + $Int_s : V_s \to Z_{2^s}$ --- отображение, обратное к отображению $Vec_s$; + \item + $\Delta : V_8 \to \mathbb{F}$ --- биективное отображение, сопоставляющее + двоичной строке из $V_8$ элемент поля $\mathbb{F}$ следующим образом: + строке $z_7 \| \dots \| z_1 \| z_0$, $z_i \in \set{0, 1}$, $i = 0, 1, \dots, + 7$, соответствует элемент $z_0 + z_1 \cdot \theta + \dots + z_7 \cdot + \theta^7 \in \mathbb{F}$; + \item + $\triangledown : \mathbb{F} \to V_8$ --- отображение, обратное к + отображению $\Delta$. + \item + $\Phi \Psi$ --- произведение отображений, при котором отображение $\Psi$ + действует первым; + \item + $\Phi^s$ --- композиция отображений $\Phi^{s - 1}$ и $\Phi$, причём + $\Phi^1 = \Phi$. +\end{itemize} + + +\paragraph{Шифр <<Магма>>.} + +Это по сути шифр ГОСТ 28147-89 с фиксированным набором подстановок (таблицы +замены $S$). + +\begin{enumerate} + \item + \textbf{Значения параметров.} + + В качестве нелинейного биективного преобразования выступают подстановки + $\pi_i = Vec_4 \pi_i' Int_4 : V_4 \to V_4$, где $\pi_i' : Z_{2^4} \to + Z_{2^4}$, $i = 0, 1, \dots, 7$. Значения подстановок $\pi_i'$ записаны + в стандарте в виде массивов: + \begin{equation*} + \pi_i' = (\pi_i'(0), \pi_i'(1), \dots, \pi_i'(15)),\, i = 0, 1, \dots, 7 + \end{equation*} + + Например, + \begin{equation*} + \pi_6' = (8, 14, 2, 5, 6, 8, 1, 12, 15, 4, 11, 0, 13, 10, 3, 7) + \end{equation*} + + \item + \textbf{Преобразования.} + + При реализации алгоритмов шифрования и расшифрования используются + следующие преобразования: + \begin{equation*} + t : V_{32} \to V_{32}, t(a) = t(a_7 \| \dots \| a_0) = + \pi_7(a_7) \| \dots \| \pi_0(a_0) + \end{equation*} + где $a = a_7 \| \dots \| a_0 \in V_{32}$, $a_i \in V_4$, $i = 0, \dots, 7$. + + \begin{equation*} + g[k] : V_{32} \to V_{32}, + 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) + \end{equation*} + где $k, a_0, a_1 \in V_{32}$; + + \begin{equation*} + G^*[k] : V_{32} \times V_{32} \to V_{64}, + G^*[k](a_1, a_0) = (g[k](a_0) \oplus a_1) \| a_0 + \end{equation*} + где $k, a_0, a_1 \in V_{32}$. + + \item + \textbf{Алгоритм развёртывания ключа.} + + Итерационные ключи $K_i \in V_{32}$, $i = 1, 2, \dots, 32$, вырабатываются + на основе исходного ключа $K = k_{255} \| \dots \| k_0 \in V_{256}$, + $k_i \in V_1$, $i = 0, 1, \dots, 255$, и определяются равенствами: + \begin{align*} + K_1 &= k_{255} \| \dots \| k_{224}; \\ + K_2 &= k_{223} \| \dots \| k_{192}; \\ + &\dots \\ + K_8 &= k_{31} \| \dots \| k_{0}; \\ + K_{i + 8} &= K_i,\, i = 1, 2, \dots, 8; \\ + K_{i + 16} &= K_i,\, i = 1, 2, \dots, 8; \\ + K_{i + 24} &= K_{9 - i},\, i = 1, 2, \dots, 8; \\ + \end{align*} + + \item + \textbf{Базовый алгоритм шифрования.} + + \begin{enumerate} + \item + Алгоритм зашифрования в зависимости от значений итерационных ключей + $K_i \in V_{32}$, $i = 1, 2, \dots, 32$, реализует подстановку + $E_{K_1, \dots, K_{32}}$, заданную на множестве $V_{64}$ в + соответствии с равенством + \begin{equation*} + E_{K_1, \dots, K_{32}}(a) = G^*[K_{32}] G[K_{31}] \dots + G[K_2] G[K_1](a_1, a_0) + \end{equation*} + где $a = a_1 \| a_0 \in V_{64},\, a_0, a_1 \in V_{32}$. + + \item + Алгоритм расшифрования в зависимости от значений итерационных ключей + $K_i \in V_{32},\, i = 1, 2, \dots, 32$, реализует подстановку + $D_{K_1, \dots, K_{32}}$, заданную на множестве $V_{64}$ в + соответствии с равенством + \begin{equation*} + D_{K_1, \dots, K_{32}}(a) = G^*[K_1] G[K_2] \dots + G[K_{31}] G[K_{32}](a_1, a_0) + \end{equation*} + где $a = a_1 \| a_0 \in V_{64},\, a_0, a_1 \in V_{32}$. + \end{enumerate} + Сложность алгоритма $c = 2^{256}$. +\end{enumerate} + + +\paragraph{Шифр <<Кузнечик>>.} + +\begin{enumerate} + \item + \textbf{Значения параметров.} + + \begin{enumerate} + \item + В качестве нелинейного биективного преобразования выступает подстановка + $\pi = Vec_8 \pi' Int_8 : V_8 \to V_8$, где $\pi' : Z_{2^8} \to Z_{2^8}$. + Значения подстановки $\pi'$ записаны в стандарте в виде массива: + \begin{align*} + \pi' &= (\pi'(0), \pi'(1), \dots, \pi'(255)) \\ + \pi' &= (252, 238, 221, \dots, 75, 99, 182) + \end{align*} + \item + Линейное преобразование задаётся отображением $l : V_8^{16} \to + V_8$, которое определяется следующим образом: + \begin{align*} + l(a_{15}, \dots, a_0) &= + \triangledown(148 \cdot \Delta(a_{15}) + 32 \cdot \Delta(a_{14}) + 133 \cdot \Delta(a_{13}) +\\ + &+ 16 \cdot \Delta(a_{12}) + 194 \cdot \Delta(a_{11}) + 192 \cdot \Delta(a_{10}) +\\ + &+ 1 \cdot \Delta(a_9) + 251 \cdot \Delta(a_8) + 1 \Delta(a_7) + 192 \cdot \Delta(a_6) +\\ + &+ 194 \cdot \Delta(a_5) + 16 \cdot \Delta(a_4) + 133 \cdot \Delta(a_3) +\\ + &+ 32 \cdot \Delta(a_2) + 148 \cdot \Delta(a_1) + 1 \cdot \Delta(a_0)) + \end{align*} + для любых $a_i \in V_8$, $i = 0, 1, \dots, 15$, где операции + сложения и умножения осуществляются в поле $\mathbb{F}$, а константы + являются элементами поля в указанном ранее смысле. + \end{enumerate} + \item + \textbf{Преобразования.} + + При реализации алгоритмов шифрования используются следующие преобразования: + \begin{equation*} + X[k] : V_{128} \to V_{128}, X[k](a) = k \oplus a + \end{equation*} + где $k, a \in V_{128}$. + + \begin{equation*} + S : V_{128} \to V_{128}, S(a) = S(a_{15} \| \dots \| a_0) = + \pi(a_{15}) \| \dots \| \pi(a_0) + \end{equation*} + где $a = a_{15} \| \dots \| a_0 \in V_{128}, a_i \in V_8, i = 0, 1, \dots, 15$. + + \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 + \end{equation*} + где $a = a_{15} \| \dots \| a_0 \in V_{128}, a_i \in V_8, i = 0, 1, \dots, 15$. + + $R^{-1} : V_{128} \to V_{128}$ --- преобразование, обратное к преобразованию + $R$, которое может быть вычислено, например, следующим образом: + \begin{equation*} + R^{-1}(a) = R^{-1}(a_{15} \| \dots \| a_0) = a_{14} \| a_{13} \| \dots \| + a_0 \| l(a_{14}, a_{13}, \dots, a_0, a_{15}) + \end{equation*} + где $a = a_{15} \| \dots \| a_0 \in V_{128}, a_i \in V_8, i = 0, 1, \dots, 15$. + + \begin{equation*} + L : V_{128} \to V_{128}, L(a) = R^{16}(a) + \end{equation*} + где $a \in V_{128}$. + + \begin{equation*} + L^{-1} : V_{128} \to V_{128}, L^{-1}(a) = (R^{-1})^{16}(a) + \end{equation*} + где $a \in V_{128}$. + + \begin{equation*} + F[k] : V_{128} \times V_{128} \to V_{128} \times V_{128}, + F[k](a_1, a_0) = (LSX[k](a_1) \oplus a_0, a_1) + \end{equation*} + где $k, a_0, a_1 \in V_{128}$. + \item + \textbf{Алгоритм развёртывания ключа.} + + Алгоритм развёртывания ключа использует итерационные константы $C_i \in + V_{128},\, i = 1, 2, \dots, 32$, которые определены следующим образом: + $C_i = L(Vec_{128}(i)),\, i = 1, 2, \dots, 32$. + + Итерационные ключи $K_i \in V_{128},\, i = 1, 2, \dots, 10$, вырабатываются + на основе исходного ключа $K = k_{255} \| \dots \| k_0 \in V_{256},\, + k_i \in V_1,\, i = 0, 1, \dots, 255$, и определяются следующим образом: + \begin{align*} + K_1 &= k_{255} \| \dots \| k_{128}; \\ + K_2 &= k_{127} \| \dots \| k_0; \\ + (K_{2i + 1}, K_{2i + 2}) &= F[C_{8(i - 1) + 8} \dots F[C_{8(i - 1) + 1}]( + K_{2i - 1}, K_{2i}),\, i = 1, 2, 3, 4 + \end{align*} + + \item + \textbf{Базовый алгоритм шифрования.} + + \begin{enumerate} + \item + Алгоритм зашифрования в зависимости от значений итерационных ключей + $K_i \in V_{128},\, i = 1, 2, \dots, 10$, реализует подстановку + $E_{K_1, \dots, K_{10}}$, заданную на множестве $V_{128}$ в + соответствии с равенством + \begin{equation*} + E_{K_1, \dots, K_{10}} = X[K_{10}] LSX[K_9] \dots LSX[K_2] LSX[K_1] + (a) + \end{equation*} + где $a \in V_{128}$. + + \item + Алгоритм расшифрования в зависимости от значений итерационных ключей + $K_i \in V_{128},\, i = 1, 2, \dots, 10$, реализует подстановку + $D_{K_1, \dots, K_{10}}$, заданную на множестве $V_{128}$ в + соответствии с равенством + \begin{equation*} + D_{K_1, \dots, K_{10}}(a) = X[K_1] S^{-1} L^{-1} X[K_2] \dots + S^{-1} L^{-1} X[K_9] S^{-1} L^{-1} X[K_{10}](a) + \end{equation*} + где $a \in V_{128}$. + \end{enumerate} + Сложность алгоритма $c = 2^{256}$. +\end{enumerate} + diff --git a/cryptography/lectures/lecture22.tex b/cryptography/lectures/lecture22.tex new file mode 100644 index 0000000..5b0e949 --- /dev/null +++ b/cryptography/lectures/lecture22.tex @@ -0,0 +1,216 @@ +% Лекция 22 (24.03.23) + +\subsection{ГОСТ 34.13-2015} + +Национальный стандарт Российской Федерации ГОСТ Р 34.13-2015 <<Информационная +технология. Криптографическая защита информации. Режимы работы блочных шифров>> +разработан Центром защиты информации и специальной связи ФСБ России с участием +ОАО <<ИнфоТеКС>>, утверждён и введён в действие Приказом Федерального агентства +по техническому регулированию и метрологии от 19 нюня 2015 г. №750-ст. + +Данный стандарт содержит описание режимов работы блочных шифров. Данные режимы +работы блочных шифров определяют правила криптографического преобразования +данных и выработки имитовставки для сообщений произвольного размера. + +Настоящий стандарт определяет следующие режимы работы алгоритмов блочного +шифрования: +\begin{itemize} + \item режим простой замены (Electronic Codebook, ECB); + \item режим гаммирования (Counter, CTR); + \item режим гаммирования с обратной связью по выходу (Output Feedback, OFB); + \item режим простой замены с зацеплением (Cipher Block Chaining, CBC); + \item режим гаммирования с обратной связью по шифртексту (Cipher Feedback, CFB); + \item режим выработки имитовставки (Message Authentication Code algorithm). +\end{itemize} + +Данные режимы могут использоваться в качестве режимов для блочных шифров с +произвольной длиной блока $n$. + + +\subsubsection{Обозначения} + +\begin{enumerate} + \item $\boxplus_s$ --- операция сложения в кольце $\Z_{2^s}$; + \item + $MSB_s : V^* \backslash \cup_{i = 0}^{s - 1} V_i \to V_s$ --- отображение, + ставящее в соответствие строке $z_{m - 1} \| \dots \| z_1 \| z_0$, $m \geq + s$, строку $z_{m - 1} \| \dots \| z_{m - s + 1} \| z_{m - s}$, $z_i \in + V_1$, $i = 0, 1, \dots, m - 1$; + \item $T_s = MSB_s$; + \item + $LSB_s : V^* \backslash \cup_{i = 0}^{s - 1} V_i \to V_s$ --- отображение, + ставящее в соответствие строке $z_{m - 1} \| \dots \| z_1 \| z_0$, $m \geq + s$, строку $z_{s - 1} \| \dots \| z_1 \| z_0$, $z_i \in V_1$, $i = 0, 1, + \dots, m - 1$; + \item + $A \ll r$ --- операция логического сдвига строки $A$ на $r$ компонент в + сторону компонент, имеющих большие номера. Если $A \in V_s$, то + $A \ll r \in V_s$, причём + \begin{equation*} + A \ll r = \begin{cases} + LSB_{s - r}(A) \| 0^r, &\text{если } r < s, \\ + 0^s, &\text{если } r \geq s; + \end{cases} + \end{equation*} + \item + $Poly_s : V_s \to GF(2)[x]$ --- отображение, ставящее в соответствие строке + $z = (z_{s - 1} \| \dots \| z_0) \in V_s$ многочлен $Poly_s(z) = + \sum_{i = 0}^{s - 1} z_i x^i$; + \item $k$ --- параметр алгоритма блочного шифрования, называемый длиной ключа; + \item $n$ --- параметр алгоритма блочного шифрования, называемый длиной блока; + \item + $E : V_n \times V_k \to V_n$ --- отображение, реализующее базовый алгоритм + блочного шифрования и осуществляющее преобразование блока открытого текста + $P \in V_n$ с использованием ключа (шифрования) $K \in V_k$ в блок + шифртекста $C \in V_n : E(P, K) = C$; + \item + $e_K : V_n \to V_n$ --- отображение, реализующее шифрование с использованием + ключа $K \in V_k$, то есть $e_K(P) = E(P, K)$ для всех $P \in V_n$; + \item + $d_K : V_n \to V_n$ --- отображение, реализующее расшифрование с использованием + ключа $K \in V_k$, то есть $d_K = e_K^{-1}$. +\end{enumerate} + + +\subsubsection{Дополнение сообщения} + +Отдельные из описанных режимов работы могут осуществлять криптографическое +преобразование сообщений произвольной длины, для других режимов требуется, +чтобы длина сообщения была кратна некоторой величине $l$. + +В последнем случае при работе с сообщениями произвольной длины необходимо +применение процедуры дополнения сообщения до требуемой длины. + +Пусть $P \in V^*$ --- исходное сообщение, подлежащее зашифрованию. +\begin{enumerate} + \item + Пусть $|P| \equiv r \pmod{l}$. Положим + \begin{equation*} + P^* = \begin{cases} + P, &\text{если } r = 0, \\ + P \| 0^{l - r}, &\text{иначе}. + \end{cases} + \end{equation*} + + Описанная процедура в некоторых случаях не обеспечивает однозначного + восстановления исходного сообщения. Например, результаты дополнения + сообщения $P_1$, такого что $|P_1| = l \cdot q - 1$ для некоторого $q$, + и $P_2 = P_1 \| 0$ будут одинаковы. + \item + Пусть $|P| \equiv r \pmod{l}$. Положим $P^* = P \| 1 \| 0^{l - r - 1}$. + + Данная процедура обеспечивает однозначное восстановление исходного + сообщения. При этом если длина исходного сообщения кратна $l$, то длина + дополненного сообщения будет увеличена. + \item + Пусть $|P| \equiv r \pmod{l}$. В зависимости от значения $r$ возможны + случаи: + \begin{itemize} + \item если $r = n$, то последний блок не изменяется $P^* = P$; + \item если $r < n$, то применяется процедура 2. + \end{itemize} + + Данная процедура обязательна для режима выработки имитовставки. +\end{enumerate} + + +\subsubsection{Режимы работы алгоритмов блочного шифрования} + +\paragraph{Режим гаммирования с обратной связью по выходу.} + +Параметры: целочисленные величины $s$ и $m$, $0 < s \leq n$, $n \leq m$, +$m = n \cdot z$, $z \geq 1$ --- целое число. + +При использовании режима не требуется применение процедуры дополнения +сообщения. При шифровании на одном ключе для каждого отдельного открытого +текста используется значение уникальной или непредсказуемой (случайной или +псевдослучайной) синхропосылки $IV \in V_m$. При шифровании используется +двоичный регистр сдвига $R$ длины $m$. Начальным заполнением регистра является +значение синхропосылки $IV$. + +Зашифрование в режиме заключается в покомпонентном сложении открытого текста с +гаммой шифра, которая вырабатывается блоками длины $s$. + +При вычислении очередного блока гаммы выполняется зашифрование $n$ разрядов +регистра сдвига с большими номерами базовым алгоритмом блочного шифрования. + +Затем заполнение регистра сдвигается на $n$ бит в сторону разрядов с большими +номерами, при этом в разряды с меньшими номерами записывается полученный выход +базового алгоритма блочного шифрования. + +Блок гаммы вычисляется путём усечения выхода базового алгоритма блочного +шифрования. + +\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} + Y_i = e_K(MSB_n(R_i)), \\ + C_i = P_i \oplus T_s(Y_i), i = 1, 2, \dots, q - 1, \\ + R_{i + 1} = LSB_{m - n}(R_i) \| Y_i, + \end{cases} \\ + &Y_q = e_K(MSB_n(R_q)), \\ + &C_q = P_q \oplus T_r(Y_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} + Y_i = e_K(MSB_n(R_i)), \\ + P_i = C_i \oplus T_s(Y_i), i = 1, 2, \dots, q - 1, \\ + R_{i + 1} = LSB_{m - n}(R_i) \| Y_i, + \end{cases} \\ + &Y_q = e_K(MSB_n(R_q)), \\ + &P_q = C_q \oplus T_r(Y_q). + \end{align*} + + Исходный открытый текст: $P = P_1 \| P_2 \| \dots \| P_q$. + + % TODO: рис 2 +\end{itemize} + + +\paragraph{Режим гаммирования с обратной связью по шифртексту.} + +Параметры: целочисленные величины $s$ и $m$, $0 < s \leq n$, $n \leq m$. + +Если в конкретной системе обработки информации на длину исходного сообщения +$P$ накладывается ограничение $|P| = s \cdot q$, то к исходному сообщению, при +необходимости, должна быть предварительно применена процедура дополнения. + +При шифровании на одном ключе для каждого отдельного открытого текста +используется значение непредсказуемой (случайной или псевдослучайной) +синхропосылки $IV \in V_m$. + +% TODO: пропуск + +Начальным заполнением регистра является значение синхропосылки $IV$. + +Зашифрование заключается в покомпонентном сложении открытого текста с гаммой +шифра, которая вырабатывается блоками длины $s$. + +При вычислении очередного блока гаммы выполняется зашифрование $n$ разрядов +регистра сдвига с большими номерами базовым алгоритмом блочного шифрования с +последующим усечением. + +Затем заполнение регистра сдвигается на $s$ разрядов в сторону разрядов +с большими номерами, при этом в разряды с меньшими номерами записывается +полученный блок шифртекста, являющийся результатом покомпонентного сложения +гаммы шифра и блока открытого текста. |