diff options
Diffstat (limited to 'cryptography/lectures')
| -rw-r--r-- | cryptography/lectures/lecture14.tex | 96 | ||||
| -rw-r--r-- | cryptography/lectures/lecture15.tex | 49 |
2 files changed, 117 insertions, 28 deletions
diff --git a/cryptography/lectures/lecture14.tex b/cryptography/lectures/lecture14.tex index 301925f..1d84680 100644 --- a/cryptography/lectures/lecture14.tex +++ b/cryptography/lectures/lecture14.tex @@ -9,8 +9,10 @@ Первый способ заключается в применении к элементам ЛРП некоторой функции $f$ (см. рисунок). - -% TODO: рис. 1 +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{lecture14/lrs} +\end{figure} Подобные узлы усложнения ЛРП называются фильтрующими генераторами. Их результирующей последовательностью является нелинейно <<фильтрованное>> @@ -29,15 +31,19 @@ Генератор псевдослучайных последовательностей, реализующий усложнение нескольких линейных рекуррент с помощью одной общей функции усложнения, получил название комбинирующего генератора (см. рисунок). - -% TODO: Рис. 2 +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{lecture14/combine} +\end{figure} \paragraph{Композиции линейных регистров сдвига} -Так называется схема, в которой выход одного из регистров подаётся на вход другого -регистра (см. рисунок). - -% TODO: Рис. 3 +Так называется схема, в которой выход одного из регистров подаётся на вход +другого регистра (см. рисунок). +\begin{figure}[H] + \centering + \includegraphics[width=\textwidth]{lecture14/compose} +\end{figure} Функционирование такой схемы описывается следующим образом. @@ -74,14 +80,78 @@ На рисунке приведена схема работы генератора, когда процессами записи и считывания управляет одна и та же последовательность. - -% TODO: Рис. 4 +\begin{figure}[H] + \centering + \includegraphics[width=0.5\textwidth]{lecture14/memory} +\end{figure} Пусть $u$ и $v$ --- последовательности над полем $P$, а выходная последовательность $\gamma$ вырабатывается с использованием $q$ ячеек памяти -$R_0, \dots, R_{q - 1}$. Если $R_j(i)$ --- заполнение $j$- - -% TODO: Дописать +$R_0, \dots, R_{q - 1}$. Если $R_j(i)$ --- заполнение $j$-й ячейки памяти перед +началом $i$-го такта работы схемы, то преобразование информации в $i$-м такте +описывается формулами +\begin{align*} + \gamma(i) &= R_{v(i)}(i), \\ + R_j(i + 1) &= \begin{cases} + R_j(i), &\text{если } j \neq v(i) \\ + u(i), &\text{если } j = v(i) + \end{cases} +\end{align*} + +Таким образом, последовательность $v$ определяет адреса, по которым в память +записываются элементы последовательности $u$. + +%% NOTE: Теорема 6 +\begin{theorem} + Пусть $\tau$ --- период последовательности $u$, $t$ --- период + последовательности $v$, причём $\text{НОД}(\tau, t) = 1, \, t < \tau$. Тогда + для значения периода $T$ выходной последовательности $\gamma$ выполняется + равенство $T = \tau s$, где $s = \frac{t}{d},\, d \leq e^\frac{q}{e}$. +\end{theorem} \subsection{Поточная шифрсистема A5} +A5 --- шифрсистема гаммирования, применяемая для шифрования телефонных сеансов +в системе GSM, а именно канала <<телефон --- базовая станция>>. + +Поточная шифрсистема A5/1 --- одна из разновидностей алгоритма A5. Генератор +A5/1 состоит из трёх ЛРС над $GF(2)$ длины 19, 22 и 23 с характеристическими +многочленами соответственно +\begin{align*} + f_1(x) &= x^{19} + x^5 + x^2 + x + 1, \\ + f_2(x) &= x^{22} + x + 1, \\ + f_3(x) &= x^{23} + x^{15} + x^2 + x + 1. \\ +\end{align*} + +Сумма битов, снимаемых с трёх ЛРС образует гамму генератора. + +Нелинейность алгоритма (они придают системе принципиально новые свойства) +достигается за счёт неравномерного движения всех ЛРС, контролируемого блоком +управления движения (БУД). После вычисления знака гаммы происходит сдвиг +некоторых (не менее чем двух) регистров. Сдвиг зависит от значения трёх битов: +10-го бита ЛРС-1, 11-го бита ЛРС-2 и 12-го бита ЛРС-3 --- и определяется по +правилу: если все три бита одинаковы, то сдвигаются все регистры, в противном +случае сдвигаются два регистра, чьи биты совпадают. + +Криптосистема генератора шифра A5/1 представлена на рисунке: +\begin{figure}[H] + \centering + \includegraphics[width=0.7\textwidth]{lecture14/a5_1} + \caption{Криптосистема A5/1} +\end{figure} + +Открытый текст представляет собой набор 114-битовых блоков. Перед шифрованием +каждого блока происходит перезагрузка состояний регистров, которая определяется +однозначно передаваемым в линию несекретным номером блока и секретным 64-битовым +сеансовым ключом шифра. Определение сеансового ключа шифра равносильно +определению состояния регистров после перезагрузки, так как сеансовый ключ +восстанавливается однозначно по состоянию регистров и по номеру блока из решения +линейной системы уравнений от 64 переменных над полем $GF(2)$. + +После перезагрузки регистров осуществляется 100 тактов холостого прогона, +то есть 100 первых знаков гаммы игнорируются. В последующие 114 тактов +вырабатываемые генератором биты используются для гаммирования блока открытого +текста. + +Поточная шифрсистема A5/2 отличается пониженной криптостойкостью за счёт +добавления ещё одного регистра (17 бит) управляющего сдвигами остальных. diff --git a/cryptography/lectures/lecture15.tex b/cryptography/lectures/lecture15.tex index f7c93bf..ad5785e 100644 --- a/cryptography/lectures/lecture15.tex +++ b/cryptography/lectures/lecture15.tex @@ -35,11 +35,12 @@ $S_0 = 0, S_1 = 1, \dots S_{255} = 255$. k_{255}$. Счётчик $j$ устанавливается в 0. После этого производятся следующие действия: -% TODO: оформить алгоритм -for i = 0 to 255 - j = (j + k_i + S_i) \pmod{256} - переставить $S_i$ и $S_j$. - +\begin{algorithm} + \For {$i = 0$ \to 255} { + $j = (j + k_i + S_i) \pmod{256}$\; + Переставить $S_i$ и $S_j$\; + } +\end{algorithm} \subsection{Методы анализа поточных шифров} @@ -121,8 +122,11 @@ for i = 0 to 255 \paragraph{Сеть Фейстеля.} Для построения алгоритмов часто используется \emph{Сеть Фейстеля} (см. рисунок). - -% TODO: Рисунок 1 (везде индексы i) +\begin{figure}[H] + \centering + \includegraphics[width=0.8\textwidth]{lecture15/feistel} + \caption{Сеть Фейстеля} +\end{figure} Преобразование, реализуемое сетью Фейстеля в $i$-м цикле шифрования имеет вид \begin{equation*} @@ -164,8 +168,11 @@ RC5. Обработка данных сводится в основном к заменам и перестановкам зависящим от ключа $k_i$ (см. рисунок). - -% TODO: Рисунок 2 +\begin{figure}[H] + \centering + \includegraphics[width=0.6\textwidth]{lecture15/sp} + \caption{SP-сеть} +\end{figure} SP-сети являются гораздо менее распространёнными, чем сети Фейстеля. На их базе, например, основаны алгоритмы шифрования Serpent, SAFER+. @@ -203,9 +210,21 @@ S-боксы делятся на линейные и нелинейные. В л В нелинейном S-боксе нельзя задать линейные соотношения для каждого выхода. -Пример S-бокса представлен на рисунке, где первый бит входа определяет строку, -два следующих бита входа определяют столбец. - -Два бита на выходе --- это значение на пересечении выбранных строки и столбца. - -% TODO: Рисунок 3 +Пример S-бокса представлен в таблице, где первый бит входа определяет строку, +два следующих бита входа определяют столбец. Два бита на выходе --- это значение +на пересечении выбранных строки и столбца. +\begin{table}[H] + \centering + \begin{tabular}{|c|c|c|c|c|} + \cline{2-5} + \multicolumn{1}{c|}{} & + \textbf{00} & \textbf{01} & \textbf{10} & \textbf{11} \\ \hline + \textbf{0} & 00 & 01 & 10 & 11 \\ \hline + \textbf{1} & 00 & 01 & 10 & 11 \\ \hline + \end{tabular} + \caption{Пример S-блока} +\end{table} + +\begin{example} + Вход --- 110; Выход --- 11. +\end{example} |