diff options
Diffstat (limited to 'cryptography')
| -rw-r--r-- | cryptography/cryptography.pdf | bin | 701003 -> 701428 bytes | |||
| -rw-r--r-- | cryptography/lectures/lecture4.tex | 8 | ||||
| -rw-r--r-- | cryptography/lectures/lecture5.tex | 11 | ||||
| -rw-r--r-- | cryptography/lectures/lecture6.tex | 45 | ||||
| -rw-r--r-- | cryptography/lectures/lecture7.tex | 12 | ||||
| -rw-r--r-- | cryptography/lectures/lecture8.tex | 8 |
6 files changed, 45 insertions, 39 deletions
diff --git a/cryptography/cryptography.pdf b/cryptography/cryptography.pdf Binary files differindex 8c0b130..9492ca8 100644 --- a/cryptography/cryptography.pdf +++ b/cryptography/cryptography.pdf diff --git a/cryptography/lectures/lecture4.tex b/cryptography/lectures/lecture4.tex index 0ccf2ac..3ee5f06 100644 --- a/cryptography/lectures/lecture4.tex +++ b/cryptography/lectures/lecture4.tex @@ -88,7 +88,7 @@ $k \in K$. D)$$ введённых множеств, для которых выполняются следующие свойства: \begin{enumerate} \item Для любых $x \in X$ и $k \in K$ выполняется равенство $D_k(E_k(x)) = x$; - \item $Y = \cup_{k \in K} E_k(X)$. + \item $Y = \bigcup_{k \in K} E_k(X)$. \end{enumerate} Неформально, шифр --- это совокупность множеств возможных открытых текстов (то, @@ -127,8 +127,8 @@ $E_k(x)$ для подходящих элементов $x \in X$ и $k \in K$. В большинстве случаев множества $X$ и $Y$ представляют собой объединения декартовых степеней некоторых множеств $A$ и $B$ соответственно, так что для -некоторых натуральных $L$ и $L_1$: $$X = \cup_{L = 1}^L A^l \, \land \, Y = -\cup_{L = 1}^{L_1} B^l$$ +некоторых натуральных $L$ и $L_1$: $$X = \bigcup_{l = 1}^L A^l \, \land \, Y = +\bigcup_{l = 1}^{L_1} B^l$$ Множества $A$ и $B$ называются соответственно \emph{алфавитом открытого текста} и \emph{алфавитом шифрованного текста}. @@ -160,7 +160,7 @@ $E_k(x)$ для подходящих элементов $x \in X$ и $k \in K$. быть полностью и надёжно скрыты в шифрованном тексте; \item длина шифрованного текста должна быть равной длине исходного текста; \item - не должно быть простых и легко устанавливаемых зависимостью между ключами, + не должно быть простых и легко устанавливаемых зависимостей между ключами, последовательно используемыми в процессе шифрования; \item любой ключ из множества возможных должен обеспечивать надёжную защиту diff --git a/cryptography/lectures/lecture5.tex b/cryptography/lectures/lecture5.tex index 1ceb48a..d0ddf14 100644 --- a/cryptography/lectures/lecture5.tex +++ b/cryptography/lectures/lecture5.tex @@ -17,13 +17,13 @@ $S(M)$ является коммутативной только в случае Перенумеровав элементы множества $M$ некоторым фиксированным образом $M = \{ x_1, x_2, \dots, x_n \}$ и отождествив элементы $x_i$ с их номерами $i$, вместо группы $S(M)$ можно рассматривать группу $S(\Omega)$, где $\Omega = \{ 1, 2, -\dots, n \}$. Обычно группа $S(\Omega)$ обозначают через $S_n$. +\dots, n \}$. Обычно группу $S(\Omega)$ обозначают через $S_n$. Любая подгруппа $G$ группы $S_n$ называется \emph{группой подстановок} степени $n$. Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого ключа $k$, открытого текста $x = (x_1, \dots, x_L)$ и шифрованного текста $y = (y_1, \dots, y_L)$ правила зашифрования и расшифрования \emph{шифра перестановки} -определяется формулами $$E_k(x) = (x_{k(1)}, \dots, x_{k(L)}), \, D_k(y) = +определяются формулами $$E_k(x) = (x_{k(1)}, \dots, x_{k(L)}), \, D_k(y) = (y_{k^{-1}(1)}, \dots, y_{k^{-1}(L)})$$ где $k^{-1}$ --- подстановка, обратная к $k$. @@ -31,7 +31,7 @@ $n$. Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого Широкое применение получили так называемые \emph{маршрутные перестановки}, основанные на некоторой геометрической фигуре. Отрезок открытого текста -записывается в такую фигуру на некоторой траектории. Шифрованным текстом +записывается в такую фигуру по некоторой траектории. Шифрованным текстом является последовательность, полученная при выписывании по другой траектории. \begin{example} @@ -87,6 +87,7 @@ $n$. Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого \paragraph{} Приведём основные идеи, используемые при вскрытии вертикальных перестановок. +% TODO: Заметим, что (это/если)? буквы... Заметим, что это буквы каждого столбца заполненного прямоугольника выписываются в криптограмму подряд, то есть криптограмма разбивается на отрезки, являющиеся столбцами таблицы. @@ -99,7 +100,7 @@ $n$. Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого которые можно составить из букв криптограммы. Если для первой пробы выбрано, например, сочетание НИ, то можно по очереди -приписывать к каждой букве Н криптограммы каждую букву и из неё. +приписывать к каждой букве Н криптограммы каждую букву И из неё. При этом несколько букв, стоящих до и после данной буквы Н, и несколько букв, стоящих до и после данной буквы И, соединяются в пары, то есть получаются два @@ -150,7 +151,7 @@ $n$. Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого \end{tabular} \end{table} \item - Ограничением можно послужить появление запретной биграммы + Ограничением может послужить появление запретной биграммы \begin{table}[H] \centering \begin{tabular}{cc} diff --git a/cryptography/lectures/lecture6.tex b/cryptography/lectures/lecture6.tex index 756db81..6154cc4 100644 --- a/cryptography/lectures/lecture6.tex +++ b/cryptography/lectures/lecture6.tex @@ -8,7 +8,7 @@ \end{tabular} \end{table} -Если предположить, что две конкретные буквы в одном из сообщений идут один +Если предположить, что две конкретные буквы в одном из сообщений идут одна за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом из остальных сообщений, соединяются подобным же образом. Значит, они могут служить проверкой правильности первого предположения. @@ -50,21 +50,21 @@ $V = (v_1, \dots, v_M)$ --- множество возможных шифробо в каждом такте шифрования замену соответствующей шифровеличине. Поскольку $M \geq N$, множество $V$ можно представить в виде объединения $V = -\cup_{i = 1}^{N} V^{(i)}$ непересекающихся непустых подмножеств $V^{(i)}$. +\bigcup_{i = 1}^{N} V^{(i)}$ непересекающихся непустых подмножеств $V^{(i)}$. Рассмотрим произвольное семейство, состоящее из $r$ таких разбиений множества -$V$: $$V = \cup_{i = 1}^{N} V^{(i)}_\alpha, \, \alpha = \overline{1, r}, \, -r \in N,$$ и соответствующее семейство биекций: $$\varphi_\alpha : U \to \{ -V^{(1)}_\alpha, \dots, V^{(N)}_\alpha \},$$ для которых $\varphi_\alpha (u_i) = +$V$: $$V = \bigcup_{i = 1}^{N} V^{(i)}_\alpha, \, \alpha = \overline{1, r}, \, +r \in N,$$ и соответствующее семейство биекций: $$\varphi_\alpha : U \to \set{ +V^{(1)}_\alpha, \dots, V^{(N)}_\alpha},$$ для которых $\varphi_\alpha (u_i) = V^{(i)}_\alpha, \, i = \overline{1, N}$. -Рассмотрим также произвольное отображение $\psi : K \times \mathbb{N} \to -\mathbb{N}^*_r$, где $\mathbb{N}_r = \{ 1, 2, \dots, r \}$, такое, что для любых -$k \in K, \, l \in \mathbb{N}$ $$\psi(k, l) = a^{(k)}_1 \dots a^{(k)}_l, \, -a^{(k)}_j \in \mathbb{N}_r, \, j = \overline{1, l}$$ +Рассмотрим также произвольное отображение $\psi : K \times \N \to \N^*_r$, +где $\N^*_r = \set{1, 2, \dots, r}$, такое, что для любых $k \in K, \, l \in +\N$ $$\psi(k, l) = a^{(k)}_1 \dots a^{(k)}_l, \, a^{(k)}_j \in \N^*_r, \, j = +\overline{1, l}$$ Последовательность $\psi(k, l)$ называется \emph{распределителем}, отвечающим -данным значениям $k \in K,\, l \in \mathbb{N}$. +данным значениям $k \in K,\, l \in \N$. Теперь можно определить правило зашифрования произвольного шифра замены. Пусть $$x \in X, x = x_1 \dots x_l, x_i \in U, i = \overline{1, l}, k \in K, \quad @@ -82,9 +82,14 @@ $\varphi_{\alpha^{(k)}}(x_j)$. Для однозначных шифров замены, у которых правило дешифрования $E_k(x)$ является однозначной функцией, например, шифр гаммирования, справедливо свойство -$$\forall \alpha, i : |V^{(i)}_\alpha| = 1$$ для многозначных шифров замены, -например, шифров пропорциональной замены: $$\exists \alpha, i : |V^{(i)}_\alpha| -> 1$$ +\begin{equation*} + \forall \alpha, i : |V^{(i)}_\alpha| = 1 +\end{equation*} + +Для многозначных шифров замены, например, шифров пропорциональной замены: +\begin{equation*} + \exists \alpha, i : |V^{(i)}_\alpha| > 1 +\end{equation*} Далее будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. @@ -94,7 +99,7 @@ M}$. % Ручная нумерация формулы Для шифра однозначной замены определение правила зашифрования можно -уточнить в формуле (1) включение следует заменить равенством $$y_j = +уточнить в формуле (1): включение следует заменить равенством $$y_j = \varphi_{\alpha_j^{(k)}} (x_j), j = \overline{1, l} \quad (1')$$ Если для некоторого числа $q \in \N$ выполняются включения $v_i \in B^q, i @@ -117,15 +122,15 @@ A^p$ для некоторого $p \in \mathbb{N}$. Введём шифр простой замены в алфавите $A$. -Пусть $X = Y = \cup_{i = 1}^L A^i, \, K \subseteq S(A)$, где $S(A)$ --- +Пусть $X = Y = \bigcup_{i = 1}^L A^i, \, K \subseteq S(A)$, где $S(A)$ --- симметрическая группа подстановок множества $A$. Для любого ключа $k \in K$, открытого текста $x = (x_1, \dots, x_l)$ и -шифрованного текста $y = (y_1, \dots, y_i)$ правила зашифрования и расшифрования +шифрованного текста $y = (y_1, \dots, y_l)$ правила зашифрования и расшифрования шифра простой замены в алфавите $A$ определяются формулами: \begin{align*} - E_k(x) &= (k(x_1), \dots, k(x_1)), \\ - D_k(x) &= (k^{-1}(y_1), \dots, k^{-1}(y_1)), + E_k(x) &= (k(x_1), \dots, k(x_l)), \\ + D_k(x) &= (k^{-1}(y_1), \dots, k^{-1}(y_l)), \end{align*} где $k^{-1}$ --- подстановка, обратная к $k$. @@ -139,7 +144,7 @@ A^p$ для некоторого $p \in \mathbb{N}$. буквы шифроалфавита, который совпадает с алфавитом открытых текстов. В первой строке шифровальной таблицы записывается алфавит языка открытых текстов. Во второй, начиная с некоторого места записывается лозунг (пароль). Затем -на оставшихся местах второй строки, начиная с места следующего за паролем, +на оставшихся местах второй строки, начиная с места, следующего за паролем, записывается полный алфавит с пропуском тех букв, которые встречаются в пароле. Закончив движение по строке, возвращаемся в её начало, процесс продолжается. @@ -177,7 +182,7 @@ A^p$ для некоторого $p \in \mathbb{N}$. \subsubsection{Анализ шифров простой замены} \paragraph{} -Методы вскрытия шифра простой однобуквенной замены основан на том, что с +Методы вскрытия шифра простой однобуквенной замены основаны на том, что с точностью до переобозначений частотные характеристики $m$-грамм криптограммы и открытого текста одинаковы. diff --git a/cryptography/lectures/lecture7.tex b/cryptography/lectures/lecture7.tex index c6b1712..2565f14 100644 --- a/cryptography/lectures/lecture7.tex +++ b/cryptography/lectures/lecture7.tex @@ -17,7 +17,7 @@ Восстановление истинных значений шифробозначений. - При этом учитывается, что каждая буква имеет предпочтительных связей, + При этом учитывается, что каждая буква имеет группу предпочтительных связей, которые составляют её наиболее характерную особенность. Как правило, такие гипотезы подтверждаются не полностью. @@ -158,10 +158,10 @@ n$ над кольцом $Z_m$ и вектор-строка $\vec{a}$ разме \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 & 1 & 1 \\ + 1 & 2 & 2 \\ + 1 & 2 & 3 + \end{pmatrix} + (1, 8, -12) = \\ &= (-1, -8, -20) + (1, 8, -12) = \\ &= (0, 0, 0) = \text{<<яяя>>} \end{align*} @@ -230,5 +230,5 @@ n$ над кольцом $Z_m$ и вектор-строка $\vec{a}$ разме Однако свойство линейности является их криптографической слабостью, например, задача нахождения ключа является не слишком трудоёмкой, если известны $n + 1$ -пар блоков открытого текста и соответствующих их блоков шифртекста, полученные +пар блоков открытого текста и соответствующих им блоков шифртекста, полученные на данном ключе. diff --git a/cryptography/lectures/lecture8.tex b/cryptography/lectures/lecture8.tex index 537f6e8..9bf6643 100644 --- a/cryptography/lectures/lecture8.tex +++ b/cryptography/lectures/lecture8.tex @@ -64,7 +64,7 @@ до 4444. Каждому кодовому обозначению соответствовала некоторая законченная - фраза. Когда такая фраза встречалась в открытом сообщении, на заменялась + фраза. Когда такая фраза встречалась в открытом сообщении, она заменялась соответствующим кодовым обозначением, а с помощью диска цифры зашифровывались как обычные знаки открытого текста, превращались в буквы. \end{enumerate} @@ -100,7 +100,7 @@ С <<Энигмой>> теснейшим образом связан ход многих событий периода второй мировой войны. С <<Энигмой>> связано также появление первой в истории вычислительной -машины, сконструированный в 1942 году для перебора ключевых элементов группой +машины, сконструированной в 1942 году для перебора ключевых элементов группой специалистов-криптографов под руководством А. Тьюрингом. В 1934 году Б. Хагелин создал свою очередную машину B-211, которую снабдил @@ -108,8 +108,8 @@ тот момент она была самой портативной печатающей шифрмашиной. В том же 1934 году французский генштаб заказал Б. Хагелину карманную печатающую -машину, которая могла бы обслуживать одним человеком. Через некоторое время -такая машина была изготовления. +машину, которая могла бы обслуживаться одним человеком. Через некоторое время +такая машина была изготовлена. Она реализовывала шифр гаммирования, причём для выработки гаммы была использована идея суммирующего устройства, состоящего из комбинационных линеек, |