diff options
Diffstat (limited to 'cryptography/lectures')
| -rw-r--r-- | cryptography/lectures/lecture6.tex | 131 |
1 files changed, 65 insertions, 66 deletions
diff --git a/cryptography/lectures/lecture6.tex b/cryptography/lectures/lecture6.tex index 54d51b8..4d706e1 100644 --- a/cryptography/lectures/lecture6.tex +++ b/cryptography/lectures/lecture6.tex @@ -1,84 +1,85 @@ % Лекция 6 (10.10.22) -палец -> ЕПЦЛА -волна -> НВАЛО -Ключ: 41532 +\begin{tabular}{l} + палец $\to$ ЕПЦЛА \\ + волна $\to$ НВАЛО \\ + Ключ: 41532 \\ +\end{tabular} Если предположить, что две конкретные буквы в одном из сообщений идут один за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом из -остальных сообщений, соединяются подобным же образом. +остальных сообщений, соединяются подобным же образом. Значит, они могут служить +проверкой правильности первого предположения. -Значит, они могут служить проверкой правильности первого предположения. - -К каждому из указанных двубуквенных сочетаний можно добавить третью букву -для образования триграммы и так далее. - -Если располагать не менее чем 4 сообщениями одинаковой длины, то можно с -уверенностью гарантировать их вскрытие подобным образом. +К каждому из указанных двухбуквенных сочетаний можно добавить третью букву для +образования триграммы и так далее. Если располагать не менее чем 4 сообщениями +одинаковой длины, то можно с уверенностью гарантировать их вскрытие подобным +образом. Если ключ зашифрования совпадает с ключом расшифрования, то такие шифры называют \emph{симметричными}, иначе --- \emph{асимметричными}. \subsection{(1.6) Шифры простой замены} -\subsubsection{(1) \emph{Шифр замены}} +\subsubsection{(1) Шифр замены} \emph{Шифр замены} --- шифр, при котором фрагменты открытого текста (отдельные буквы или группы букв) заменяются некоторыми их эквивалентами в криптограмме. -Определим модель \(\Sigma_A = (X, K, Y, E, D)\) произвольного шифра замены. +Определим модель $\Sigma_A = (X, K, Y, E, D)$ произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах A -и B соответственно. \(X \subset A^*, \, Y \subset B^*, \, |A| = n, \, |B| = m\). +и B соответственно. $X \subset A^*, \, Y \subset B^*, \, |A| = n, \, |B| = m$. Перед зашифрованием открытый текст предварительно представляется в виде последовательностей подслов, называемых \emph{шифровеличинами} (слова из -\(A^*\)). +$A^*$). При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в -шифртексте, которые называются \emph{шифробозначениями} (слова из \(B^*\)). +шифртексте, которые называются \emph{шифробозначениями} (слова из $B^*$). Пусть -\(U = (u_1, \dots, u_N)\) --- множество возможных шифрвеличин. -\(V = (v_1, \dots, v_N)\) --- множество возможных шифробозначений. -При этом \(N \geq n, \, M \geq m, \, M \geq N\). +$U = (u_1, \dots, u_N)$ --- множество возможных шифрвеличин. +$V = (v_1, \dots, v_N)$ --- множество возможных шифробозначений. +При этом $N \geq n, \, M \geq m, \, M \geq N$. -Для определения правила зашифрования \(E_k(x)\) в общем случае понадобится ряд +Для определения правила зашифрования $E_k(x)$ в общем случае понадобится ряд обозначений и понятие \emph{распределителя}, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифровеличине. -Поскольку \(M \geq N\), множество \(V\) можно представить в виде объединения \(V -= \cup_{i = 1}^{N} V^{(i)}\) непересекающихся непустых подмножеств \(V^{(i)}\). +Поскольку $M \geq N$, множество $V$ можно представить в виде объединения $V = +\cup_{i = 1}^{N} V^{(i)}$ непересекающихся непустых подмножеств $V^{(i)}$. -Рассмотрим произвольное семейство, состоящее из \(r\) таких разбиений множества -\(V\): $$V = \cup_{i = 1}^{N} V^{(i)}_\alpha, \, \alpha = \overline{1, r}, \, +Рассмотрим произвольное семейство, состоящее из $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^{(i)}_\alpha, \, i = \overline{1, N}\). +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 \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, l)\) называется \emph{распределителем}, отвечающим -данным значениям \(k \in K,\, l \in \mathbb{N}\). +Последовательность $\psi(k, l)$ называется \emph{распределителем}, отвечающим +данным значениям $k \in K,\, l \in \mathbb{N}$. Теперь можно определить правило зашифрования произвольного шифра замены. Пусть $$x \in X, x = x_1 \dots x_l, x_i \in U, i = \overline{1, l}, k \in K, \quad \psi(k, l) = a^{(k)}_1 \dots a^{(k)}_l$$ -Тогда \(E_k(x) = y\), где \(y = y_1 \dots y_l, y_j \in -\varphi_{\alpha^{(k)}}(x_j), j = \overline{1, l} \quad (1) !!!\). +% Ручная нумерация формулы +Тогда $E_k(x) = y$, где $y = y_1 \dots y_l, y_j \in \varphi_{\alpha^{(k)}}(x_j), +j = \overline{1, l} \quad (1)$. -В качестве \(y_j\) можно выбрать любой элемент множества -\(\varphi_{\alpha^{(k)}}(x_j)\). +В качестве $y_j$ можно выбрать любой элемент множества +$\varphi_{\alpha^{(k)}}(x_j)$. Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого \emph{рандомизатора} типа игровой рулетки. -Для однозначных шифров замены, у которых правило дешифрования \(E_k(x)\) -является однозначной функцией, например, шифр гаммирования, справедливо свойство +Для однозначных шифров замены, у которых правило дешифрования $E_k(x)$ является +однозначной функцией, например, шифр гаммирования, справедливо свойство $$\forall \alpha, i : |V^{(i)}_\alpha| = 1$$ для многозначных шифров замены, например, шифров пропорциональной замены: $$\exists \alpha, i : |V^{(i)}_\alpha| > 1$$ @@ -86,42 +87,45 @@ $$\forall \alpha, i : |V^{(i)}_\alpha| = 1$$ для многозначных ш Далее будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. -Итак, далее \(M = N\) и \(\varphi_\alpha(u_i) = v^{(i)}_\alpha, i = \overline{1, -M}\). +Итак, далее $M = N$ и $\varphi_\alpha(u_i) = v^{(i)}_\alpha, i = \overline{1, +M}$. +% Ручная нумерация формулы Для шифра однозначной замены определение правила зашифрования можно уточнить в формуле (1) включение следует заменить равенством $$y_j = \varphi_{\alpha_j^{(k)}} (x_j), j = \overline{1, l} \quad (1')$$ -Если для некоторого числа \(q \in N\) выполняются включения \(v_i \in B^q, i -= \overline{1, N}\), то соответствующий шифр замены называется \emph{шифром +Если для некоторого числа $q \in N$ выполняются включения $v_i \in B^q, i += \overline{1, N}$, то соответствующий шифр замены называется \emph{шифром равнозначной замены}, в противном случае --- \emph{шифром разнозначной замены}. -В подавляющем большинстве случаев используются шифры замены, для которых \(U \in -A^p\) для некоторого \(p \in \mathbb{N}\). +В подавляющем большинстве случаев используются шифры замены, для которых $U \in +A^p$ для некоторого $p \in \mathbb{N}$. -При \(p = 1\) говорят о \emph{поточных шифрах замены}, при \(p > 1\) --- о +При $p = 1$ говорят о \emph{поточных шифрах замены}, при $p > 1$ --- о \emph{блочных шифрах замены}. -В случае \(r = 1\) шифр замены называют \emph{одноалфавитным шифром замены} -или \emph{шифром простой замены}. В противном случае --- \emph{многоалфавитным +В случае $r = 1$ шифр замены называют \emph{одноалфавитным шифром замены} или +\emph{шифром простой замены}. В противном случае --- \emph{многоалфавитным шифром замены}. -\subsubsection{(2) Одноалфавитные однозначные замены называются \emph{шифрами простой замены}.} +\subsubsection{(2) Шифры простой замены} -Введём шифр простой замены в алфавите \(A\). +Одноалфавитные однозначные замены называются \emph{шифрами простой замены}. -Пусть \(X = Y = \cup_{i = 1}^L A^i, \, K \subseteq S(A)\), где \(S(A)\) --- -симметрическая группа подстановок множества \(A\). +Введём шифр простой замены в алфавите $A$. -Для любого ключа \(k \in K\), открытого текста \(x = (x_1, \dots, x_l)\) -и шифрованного текста \(y = (y_1, \dots, y_i)\) правила зашифрования и -расшифрования шифра простой замены в алфавите \(A\) определяются формулами: +Пусть $X = Y = \cup_{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)$ правила зашифрования и расшифрования +шифра простой замены в алфавите $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)), \end{align*} -где \(k^{-1}\) --- подстановка, обратная к \(k\). +где $k^{-1}$ --- подстановка, обратная к $k$. Например, в рассказе Артура Конана Дойля "Пляшущие человечки", бандит Аб Слени использовал шифр, где заменялись схематическими человеческими фигурками в разных @@ -130,16 +134,11 @@ A^p\) для некоторого \(p \in \mathbb{N}\). \subsubsection{(3) Лозунговый шифр} При этом методе осуществляется посимвольная замена букв открытого текста на -буквы шифроалфавита, который совпадает с алфавитом открытых текстов. - -В первой строке шифровальной таблицы записывается алфавит языка открытых -текстов. - -Во второй, начиная с некоторого места записывается лозунг (пароль). - -Затем на оставшихся местах второй строки, начиная с места следующего за паролем, +буквы шифроалфавита, который совпадает с алфавитом открытых текстов. В первой +строке шифровальной таблицы записывается алфавит языка открытых текстов. +Во второй, начиная с некоторого места записывается лозунг (пароль). Затем +на оставшихся местах второй строки, начиная с места следующего за паролем, записывается полный алфавит с пропуском тех букв, которые встречаются в пароле. - Закончив движение по строке, возвращаемся в её начало, процесс продолжается. \emph{ПРИМЕР!!!} @@ -151,7 +150,7 @@ A^p\) для некоторого \(p \in \mathbb{N}\). \emph{ПРИМЕР!!!} Буквы, стоящие во второй строке таблицы при шифровании заменяются стоящими над -ними, остальные буквы --- двузначными числами "строка-столбец". +ними, остальные буквы --- двузначными числами <<строка-столбец>>. \subsubsection{(5) Анализ шифров простой замены} @@ -162,4 +161,4 @@ A^p\) для некоторого \(p \in \mathbb{N}\). открытого текста одинаковы. При этом используются частотные характеристики предполагаемого открытого текста, -полученные с учётом "характера переписки". +полученные с учётом <<характера переписки>>. |