diff options
| -rw-r--r-- | cryptography/cryptography.pdf | bin | 251291 -> 221209 bytes | |||
| -rw-r--r-- | cryptography/lectures/lecture7.tex | 210 |
2 files changed, 108 insertions, 102 deletions
diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf Binary files differindex fbd522e..ba3c1ff 100644 --- a/cryptography/cryptography.pdf +++ b/cryptography/cryptography.pdf diff --git a/cryptography/lectures/lecture7.tex b/cryptography/lectures/lecture7.tex index bd17ef1..fda95b9 100644 --- a/cryptography/lectures/lecture7.tex +++ b/cryptography/lectures/lecture7.tex @@ -10,44 +10,43 @@ \item Выявление шифробозначений, заменяющих гласные и согласные буквы. - Основано на характерных свойствах этих букв, например, удвоение - гласных в открытом тексте происходит реже, чем согласных. - + Основано на характерных свойствах этих букв, например, удвоение гласных в + открытом тексте происходит реже, чем согласных. \item Выдвижение гипотез о значениях шифробозначений и их проверка. Восстановление истинных значений шифробозначений. - При этом учитывается, что каждая буква имеет предпочтительных - связей, которые составляют её наиболее характерную особенность. + При этом учитывается, что каждая буква имеет предпочтительных связей, + которые составляют её наиболее характерную особенность. Как правило, такие гипотезы подтверждаются не полностью. - Хорошим критерием при этом является "читаемость" - восстанавливаемого открытого текста. + Хорошим критерием при этом является <<читаемость>> восстанавливаемого + открытого текста. \end{enumerate} Приведём описание эвристического алгоритма дешифрования, основанного на идее Томаса Якобсена. \begin{enumerate} \item - Построить начальный вариант ключа \(k\) на основе сравнения частот - знаков криптограмм и открытого текста. + Построить начальный вариант ключа $k$ на основе сравнения частот знаков + криптограмм и открытого текста. \item - Положить $v = f(D_k(y))$, где \(f(t) = \sum_{i,j}|\Delta_{ij}(t) - b_{ij}|\) - --- "целевая функция", \(\Delta(t) = (\Delta_{ij}(t))_{n \times m}\) --- - матрица биграмм данного текста \(t\), \(n\) --- число букв алфавита. \(B = - (b_{ij})_{n \times m}\) --- эталонная матрица биграмм открытого текста. - \item Положить \(k' = k\). + Положить $v = f(D_k(y))$, где $f(t) = \sum_{i,j}|\Delta_{ij}(t) - b_{ij}|$ + --- <<целевая функция>>, $\Delta(t) = (\Delta_{ij}(t))_{n \times m}$ --- + матрица биграмм данного текста $t$, $n$ --- число букв алфавита. $B = + (b_{ij})_{n \times m}$ --- эталонная матрица биграмм открытого текста. + \item Положить $k' = k$. \item - Поменять местами в нижней строке подстановки \(k'\) некоторую пару букв, - например, \(\alpha\) и \(\beta\). - \item Положить \(v' = f(D_{k'}(y))\). - \item Если \(v' < v\), то положить \(k = k', \, v' = v\) и перейти к 4). + Поменять местами в нижней строке подстановки $k'$ некоторую пару букв, + например, $\alpha$ и $\beta$. + \item Положить $v' = f(D_{k'}(y))$. + \item Если $v' < v$, то положить $k = k', \, v' = v$ и перейти к 4). \item Перейти к шагу 3). \end{enumerate} -Алгоритм заканчивается, когда условие \(v' < v\) не выполняется в течение +Алгоритм заканчивается, когда условие $v' < v$ не выполняется в течение некоторого числа итераций, например, 100. Если шифр простой замены не является однобуквенным, то при вскрытии криптограммы @@ -59,9 +58,9 @@ \begin{enumerate} \item - Длины повторений фрагментов и расстояния между ними должны быть - кратны значности шифра (\emph{значность шифра} --- количество знаков - (цифр или букв), образующих одно шифробозначений). + Длины повторений фрагментов и расстояния между ними должны быть кратны + значности шифра (\emph{значность шифра} --- количество знаков (цифр или + букв), образующих одно шифробозначений). \item Находя НОД этих чисел с большей вероятностью получается искомая значность. \item @@ -118,100 +117,107 @@ Изобретён американским математиком Л. Хиллом в 1929 году. -Пусть мощность алфавита равна \(m\). - -Каждой букве присваивается число, равное порядковому номеру алфавита, последней -букве --- 0 (полная система вычетов по модулю \(m\)). +Пусть мощность алфавита равна $m$. Каждой букве присваивается число, равное +порядковому номеру алфавита, последней букве --- 0 (полная система вычетов по +модулю $m$). / !!!ТАБЛИЦА С БУКВАМИ И ИХ НОМЕРАМИ / -Пусть открытый текст разбивается на блоки длины \(n\). Шифрование осуществляется -поблочно. Пусть \(\vec{x}\) --- вектор-строка длины \(n\) (над кольцом вычетов -\(Z_m\)). - -Сообщение преобразуется из открытого текста заменой букв соответствующими -числами. - -Рассмотрим кольцо \(Z_m\). - -Выбирается обратимая матрица \(A\) размерности \(n \times n\) над кольцом -\(Z_m\) и вектор-строка \(\vec{a}\) размерности \(n\) над \(Z_m\). - -Шифрование осуществляется по формуле \(\vec{y} = \vec{x} A + \vec{a}\) (все -действия осуществляются по модулю \(m\), то есть в кольце \(Z_m\)). - -Ключом шифра является пара \((A, \vec{a})\). - -Тогда дешифрование \(\vec{x} = (\vec{y} - \vec{a}) A^{-1}\). - -\emph{Пример}: Еду = \((6, 5, 20) = \vec{x}, m = 32, \vec{x} = (6, 5, -12)\) - -Матрица \(A = \begin{pmatrix} - 1 & 1 & 1 \\ - 1 & 2 & 2 \\ - 1 & 2 & 3 -\end{pmatrix}\) - -Матрица \(A^{-1} = \begin{pmatrix} - 2 & -1 & 0 \\ - -1 & 2 & -1 \\ - 0 & -1 & 1 -\end{pmatrix}\) - -\(\vec{a} = (1, 8, -12)\) - -$$\vec{y} = \vec{x} A + \vec{a} = (6, 5, -12) \begin{pmatrix} - 2 & -1 & 0 \\ - -1 & 2 & -1 \\ - 0 & -1 & 1 -\end{pmatrix} + (1, 8, -12) = (-1, -8, -20) + (1, 8, -12) = (0, 0, 0) = \text{яяя}$$ - -$$\vec{x} = (\vec{y} - \vec{a}) A^{-1} = (-1, -8, 12) \begin{pmatrix} - 2 & -1 & 0 \\ - -1 & 2 & -1 \\ - 0 & -1 & 1 -\end{pmatrix} = (6, 5, 20) = \text{еду}$$ - -Для нахождения обратимых матриц над кольцом \(Z_m\) предложен следующий +Пусть открытый текст разбивается на блоки длины $n$. Шифрование осуществляется +поблочно. Пусть $\vec{x}$ --- вектор-строка длины $n$ (над кольцом +вычетов $Z_m$). Сообщение преобразуется из открытого текста заменой букв +соответствующими числами. + +Рассмотрим кольцо $Z_m$. Выбирается обратимая матрица $A$ размерности $n \times +n$ над кольцом $Z_m$ и вектор-строка $\vec{a}$ размерности $n$ над $Z_m$. +Шифрование осуществляется по формуле $\vec{y} = \vec{x} A + \vec{a}$ (все +действия осуществляются по модулю $m$, то есть в кольце $Z_m$). + +Ключом шифра является пара $(A, \vec{a})$. Тогда дешифрование $\vec{x} = +(\vec{y} - \vec{a}) A^{-1}$. + +\begin{example} + <<еду>> = $(6, 5, 20) = \vec{x}, m = 32, \vec{x} = (6, 5, -12)$ + + Матрица $A = \begin{pmatrix} + 1 & 1 & 1 \\ + 1 & 2 & 2 \\ + 1 & 2 & 3 + \end{pmatrix}$ + + Матрица $A^{-1} = \begin{pmatrix} + 2 & -1 & 0 \\ + -1 & 2 & -1 \\ + 0 & -1 & 1 + \end{pmatrix}$ + + \begin{equation*} + \vec{a} = (1, 8, -12) + \end{equation*} + + \begin{align*} + \vec{y} &= \vec{x} A + \vec{a} = \\ + &= (6, 5, -12) \begin{pmatrix} + 2 & -1 & 0 \\ + -1 & 2 & -1 \\ + 0 & -1 & 1 + \end{pmatrix} + (1, 8, -12) = \\ + &= (-1, -8, -20) + (1, 8, -12) = \\ + &= (0, 0, 0) = \text{<<яяя>>} + \end{align*} + + \begin{equation*} + \vec{x} = (\vec{y} - \vec{a}) A^{-1} = (-1, -8, 12) \begin{pmatrix} + 2 & -1 & 0 \\ + -1 & 2 & -1 \\ + 0 & -1 & 1 + \end{pmatrix} = (6, 5, 20) = \text{<<еду>>} + \end{equation*} +\end{example} + + +Для нахождения обратимых матриц над кольцом $Z_m$ предложен следующий практический способ: \begin{enumerate} \item - Нужно взять произвольную нижнюю треугольную матрицу над \(Z_m\) с + Нужно взять произвольную нижнюю треугольную матрицу над $Z_m$ с определителем, равным 1 (для этого достаточно положить равными 1 все элементы главной диагонали). - \item Далее берётся верхняя треугольная матрица над \(Z_m\) с определителем, равным 1. - \item Перемножив эти матрица, получаем обратимую матрицу над кольцом \(Z_m\). + \item Далее берётся верхняя треугольная матрица над $Z_m$ с определителем, равным 1. + \item Перемножив эти матрица, получаем обратимую матрицу над кольцом $Z_m$. \end{enumerate} -Пример: -$$\begin{pmatrix} - 1 & 0 & 0 \\ - 1 & 1 & 0 \\ - 1 & 1 & 1 -\end{pmatrix} \cdot -\begin{pmatrix} - 1 & 1 & 1 \\ - 0 & 1 & 1 \\ - 0 & 0 & 1 -\end{pmatrix} = -\begin{pmatrix} - 1 & 1 & 1 \\ - 1 & 2 & 2 \\ - 1 & 2 & 3 -\end{pmatrix}$$ - -Особенно удобно для практического применения шифра Хилла, когда матрица \(A\) -является \emph{инволютивной}, то есть \(A^{-1} = A\). Тогда \(\vec{x} = (\vec{y} -- \vec{a}) A\). +\begin{example} + \begin{equation*} + \begin{pmatrix} + 1 & 0 & 0 \\ + 1 & 1 & 0 \\ + 1 & 1 & 1 + \end{pmatrix} \cdot + \begin{pmatrix} + 1 & 1 & 1 \\ + 0 & 1 & 1 \\ + 0 & 0 & 1 + \end{pmatrix} = + \begin{pmatrix} + 1 & 1 & 1 \\ + 1 & 2 & 2 \\ + 1 & 2 & 3 + \end{pmatrix} + \end{equation*} +\end{example} + +Особенно удобно для практического применения шифра Хилла, когда матрица $A$ +является \emph{инволютивной}, то есть $A^{-1} = A$. Тогда $\vec{x} = (\vec{y} +- \vec{a}) A$. Как построить инволютивную матрицу? - \begin{enumerate} \item - Пусть для заданных \(m\) и \(n\) имеется пара взаимнообратных матриц \(A\) - и \(A^{-1}\). Возьмём любую диагональную инволютивную матрицу \(I\) (можно + Пусть для заданных $m$ и $n$ имеется пара взаимнообратных матриц $A$ + и $A^{-1}$. Возьмём любую диагональную инволютивную матрицу $I$ (можно просто выбрать элементы главной диагонали равными 1 и -1). - \item Тогда \(A I A^{-1}\) --- инволютивная матрица. + \item Тогда $A I A^{-1}$ --- инволютивная матрица. \end{enumerate} \begin{remark} @@ -223,6 +229,6 @@ $$\begin{pmatrix} текста по известному тексту криптограмм. Однако свойство линейности является их криптографической слабостью, например, -задача нахождения ключа является не слишком трудоёмкой, если известны \(n + 1\) +задача нахождения ключа является не слишком трудоёмкой, если известны $n + 1$ пар блоков открытого текста и соответствующих их блоков шифртекста, полученные на данном ключе. |