diff options
Diffstat (limited to 'cryptography/cry.org')
| -rw-r--r-- | cryptography/cry.org | 880 |
1 files changed, 0 insertions, 880 deletions
diff --git a/cryptography/cry.org b/cryptography/cry.org deleted file mode 100644 index 4d3894e..0000000 --- a/cryptography/cry.org +++ /dev/null @@ -1,880 +0,0 @@ -#+TITLE: Криптографические методы защиты информации - -# Лекция 3 (19.09.22) -* ... - -** ... - -** Алгебраические структуры - -Множество R с двумя бинарными ассоциативными операциями сложения "+" и умножения -"*" называется *кольцом*, если выполнены следующие условия: -1. множество R с бинарной операцией сложения является пбелевой группой - (нейтральный элемент кольца называют /нулём/ кольца и обозначают через 0) -2. операция "*" удовлетворяет условию дистрибутивности относительно операции "+" - то есть $(a + b) * c = a * c + b * c$ и $a * (b + c) = a * b + a * c$ - -Если операция умножения коммутативна, то кольцо называется коммутативным. -Пример - множество $Z_n$, образующее полную систему вычетов целых чисел по модулю -$n$ с операциями сложения и умножения по модулю $n$, причём это кольцо является -коммутативным. - -Кольцо вычетов $Z_4$: - -_+4_| 0 1 2 3 -----+-------- -0 | 0 1 2 3 -1 | 1 2 3 0 -2 | 2 3 0 1 -3 | 3 0 1 2 - -_*4_| 0 1 2 3 -----+-------- -0 | 0 1 2 3 -1 | 1 2 3 0 -2 | 2 3 0 1 -3 | 3 0 1 2 - -x | 0 1 2 3 ----+-------- --x | 0 3 2 1 - - -Если в кольце существует элемент 1 такой, что $g \cdot 1 = 1 \cdot g = g$ (нейтральный -элемент относительно умножения), такое кольцо называется /кольцом с единицей/. - -/Полем/ называется коммутативное кольцо с единицей, отличной от нуля, в котором -любой ненулевой элемент обратим. - -Кольцо вычетов целых чисел по модулю $Z_n$ является полем в том и только том -случае, когда $n$ --- простое число. - -Поля вычетов являются конечными полями. Конечные поля называются /полями Галуа/. - - -** Открытые сообщения - -*** Характеристики - -- Открытый и шифрованные тексты представляют собой последовательности символов, - взятых из конечного набора, называемого /алфавитом/. -- Элемент алфавита называется /буквой/. -- Число символов алфавита называется /мощностью/ алфавита. - -Примеры --- Алфавиты: -1) $A_1$ --- алфавит прописных букв, $|A_1| = 33$ : А, Б, В, \dots, Э, Ю, Я -2) $A_2$ --- прописные и строчные буквы, целые числа, пробел и знаки препинания - (мощность алфавита примерно равна 84): А, Б, В, \dots, Э, Ю, Я, а, б, в, - \dots, э, ю, я, \dots, 0, 1, \dots, 9, пробел, запятая, точк, :, ;, ", ?, !. -3) $A_3$ --- элементы множества $\{0, 1\}$. - -В основном используются производные от $A_3$ алфавиты, совпадающие с множеством -$V_n$ двоичных n-мерных векторов. - -Мощность алфавитов равна $2^n$, и, как правило, $5 \leq n \leq 8$. - -Часто в процессе шифрования наз символами алфавита производятся вычислительные -действия, поэтому удобно их представлять в виде чисел или двоичных наборов. - -Рассмотрим в качестве алфавита $Z_m = \{ 0, 1, \dots, m - 1 \}$ - -Всякий текст, записанный в некотором алфавите имеет /длину/, равную числу букв в -соответствующей записи. - -Последовательность $k$ соседних букв текста, $k \geq 2$, называется $k$-граммой (при -$k = 2$ --- биграммой и т.д.). - -Помимо алфавита $Z_m$ могут рассматриваться производные от него алфавиты $Z_m(t)$ -представляющие собой набор всевозможных $t$-грамм исходного алфавита. - - -*** Детерминированные модели открытых текстов - -Каждый истоник открытых сообщений порождает тексты в соответствии с правилами -грамматики некоторого языка, что нахолит отражение и в статистических -характеристиках сообщений. - -Всякий язык и всякий источник открытых сообщений можно характеризовать -разбиением множества всех $k$-грамм, $k = 2, 3, \dots$, на /допустимые/ -(встречающиейся в каких-либо текстах) и /запрещённые/ (не -встречающиеся ни в каких текстах), что определяет /детерминированную -модель/ источника открытых сообщений. - -В такой модели открытый текст рассматривается как последовательность букв некоторого -алфавита, не содержащая запретных $k$-грамм. - -*** Вероятностные модели открытых текстов - -В вероятностных моделях источник открытых сообщений рассматривается как источник -случайных последовательностей. - -Пусть источник генерирует в алфавите $Z_m$ текст конечной или бесконечной длины, -в результате чего получается последовательность случайных переменных $x_1, x_2, -\dots, x_{n - 1}, \dots$, принимающих значения в $Z_m$. - -/Вероятность случайного сообщения/ $(a_0, a_1, \dots, a_{n - 1})$ определяется -как вероятность такой последовательности событий: -$$P(a_0, a_1, \dots, a_{n - 1}) = P(x_0 = a_0, x_1 = a_1, \dots, x_{n - 1} = a_{n - 1})$$ - -Множество случайных сообщений образует вероятностное пространство, если выполнены -условия: -1) $P(a_0, a_1, \dots, a_{n - 1}) \geq 0$ для любого случайного - сообщения $(a_0, a_1, \dots, a_{n - 1})$. -2) $\displaystyle\sum_{(a_0, a_1, \dots, a_{n - 1})} P(a_0, a_1, \dots, a_{n - - 1}) = 1$ -3) для любого случайного сообщения $(a_0, a_1, \dots, a_{n - 1})$, и - любого $s > n$ $P(a_0, a_1, \dots, a_{n - 1}) = \sum_(a_n, \dots, - a_{s - 1}) P(a_0, a_1, \dots, a_{s - 1})$, то есть вероятность - всякого случайного сообщения $n$ есть сумма вероятностей всех - продолжения этого сообщения до длины $s$. - -Текст, порождаемый таким источником, является вероятностным аналогом -языка. Он обладает одинаковыми с языком частотными характеристиками -$k$-грамм. Задавая определённое вероятностное распределение на -множестве открытых текстов, задаётся соответствующая модель источника -открытых сообщений. - -Например, в модели стационарного источника независимых символов -алфавита (/позначная модель открытых текстов/) предполагается, что -вероятности сообщений полностью определяются вероятностями -использования отдельных букв алфавита в случайном тексте - -$$P(a_0, a_1, \dots, a_{n - 1}) = \prod_{i = 0}^{n - 1} P(x_i = a_i)$$ - -где для всех $i \in {0, 1, \dots, n - 1}$ и любого $a \in Z_m P(x_i = a) > 0$; -$\sum_{a \in Z_m} P(x_i = a) = 1$. - -Открытый текст такого источника является реализацией -последовательности независимых испытаний в полиномиальной -вероятностной схеме с числом исходов, равным $m$. - -Множество исходов взаимнооднозначно соответствует множеству всех -символов алфавита. - -Частота букв в разных языках: -- /Русский язык/: О (11%), И (8.9%), Е, А, Н, Т -- /Английский язык/: E (12.86%), T (9.72%), A, I, N, R - -Эта модель эффективно используется для дешифрования текстов, -защищаемых шифром простой замены. - -Самые частые биграммы: -- /Русский язык/: СТ (1.74%), НО (1.29%), ЕН, ТО, НА - -Наиболее частые триграммы: -- /Русский язык/: СТО, ЕНО, НОВ, ТОВ, ОВО - -Информация, которую реально несёт каждая буква сообщения меньше, чем -её максимальная информация при случайном и равновероятном появлении. - -В связи с ним возник термин "избыточность языка". - -Поэтому часть букв открытого текста можно опустить без потери -содержания потерянная информация будет восстановлена другими буквам -сообщения вследствие закономерностей языка. - -** Критерий распознавания открытого текста - -(а) Открытый текст представляет собой реализацию независимых испытаний -случайной величины, значениями которой являются буквы алфавита $A = -{a_1, a_2, \dots, a_n}$, появляющиеся в соответствии с распеределнием -вероятностей $P(A) = (p(a_1), p(a_2), \dots, p(a_n))$. - -Требуется определить, является ли случайная последовательность $c_1 -c_2 \dots c_l$ букв алфавита $A$ открытым текстом или нет. - -# Лекция 4 (26.09.22) -Пусть $H_0$ --- гипотеза, состоящая в том, что данная -последовательность --- открытый текст, $H_1$ --- альтернативная -гипотеза. - -В простейшем случае при гипотезе $H_1$ последовательность $c_1 c_2 -\dots c_l$ можно рассматривать как случайную и равносильную, то есть -при расшифровании криптограммы с помощью ложного ключа получается -"бессмыссленная" последовательность знаков. - -В более общем случае можно считать, что при гипотезе $H_1$ -последовательность $c_1 c_2 \dots c_l$ представляет собой реализацию -независимых испытаний некоторой случайной величины, значениями которой -являются буквы алфавита $A = \{ a_1, \dots, a_n \}$, появляющиеся в -соответствии с распределением вероятностей $Q(A) = (q(a_1), \dots, -q(a_n))$. - -При таких договорённостях можно применить, например, /наиболее мощный -критерий/ различения двух простых гипотез, который даёт /лемма -Неймана-Пирсона/. - -В силу своего вероятностного характера такой критерий может совершать -ошибки двух родов: -1. критерий может принять открытый текст за случайный набор - знаков. Такая ошибка называется /ошибкой первого рода/, её - вероятность равна $\alpha = p(H_1/H_0)$. -2. Критерий может принять случайный набор знаков за открытый - текст. Такая ошибка называется /ошибкой второго рода/ и её - вероятность $\beta = p(H_0/H_1)$. - -Эти ошибки определяют качество работы критерия. В криптографических -исследованиях естественно минимизировать вероятность ошибки первого -рода, чтобы не "пропустить" открытый текст. - -Лемма Неймана-Пирсона при заданной вероятности первого рода -минимизирует также вероятность ошибки второго рода. - -(б) Критерии на открытый текст, использующие зпретные сочетания -знаков, например, k-граммы подряд идущих букв, называются /критериями -запретных k-грамм/. - -Отбирается некоторое число $s$ редких k-грамм, которые объявляются запретными. - -Теперь, просматривая последовательно k-грамму за k-граммой -анализируемой последовательности $c_1 c_2 \dots c_l$, она объявляется -случайной, как только в ней встретится одна из запретных k-грамм, и -открытым текстом в противном случае. - -Такие критерии также могут совершить ошибки в принятии решения. В -простейших случаях их можно рассчитать. Несмотря на свою простоту, -критерии запретных k-грамм являются весьма эффективными. - -** (1.4) Математические модели шифров - -*** (1) Алгебраическая модель шифра - -Введём алгебраическую модель шифра (шифрсистемы), предложенную К. Шенноном. - -Пусть $X, K, Y$ --- конечные множества возможных открытых текстов, -ключей и криптограмм соответственно; $E_k : X \to Y$ --- правило -зашифрования на ключе $k \in K$. - -Множество $\{ E_k : k \in K \}$ обозначим через $E$, а множество $\{ -E_k(x) : x \in X \}$ --- через $E_k(X)$. - -Пусть $D_k : E_k(X) \to X$ --- правило расшифрования на ключе $k \in K$, и -$D$ --- множество $\{ D_k : k \in K \}$. - -Если ключ $k \in K$ представляется в виде $k = (k_o, k_p)$, где $k_o$ --- ключ зашифрования, -а $k_p$ --- ключ расшифрования (причём $k_o \neq k_p$), то $E_k$ понимается как функция -$E_{k_p}$, а $D_k$ --- как функция $D_{k_p}$. - -/Шифром (шифрсистемой)/ называется совокупность -$$\sum_A = (X, K, Y, E, D)$$ -введённых множеств, для которых выполняются следующие свойства: -1) Для любых $x \in X$ и $k \in K$ выполняется равенство $D_k(E_k(x)) = x$; -2) $Y = \cup_{k \in K} E_k(X)$. - -Неформально, шифр --- это совокупность множеств возможных открытых -текстов (то, что шифруется), возможных ключей (то, с помощью чекго -шифруется), возможных шифртекстов (то, во что шифруется), правил -зашифрования и правил расшифрования. - -Условие (1) отвечает требованию однозначности расшифрования. -Из условия (1) следует свойство инъективности функции $E_k$: если -$x_1, x_2 \in X$, причём $x_1 \neq x_2$, то при любых $k \in K$ -выполняется неравенство $E_k(x_1) \neq E_k(x_2)$. - -Условие (2) означает, что любой элемент $y \in Y$ может быть представлен в виде -$E_k(x)$ для подходящих элементов $x \in X$ и $k \in K$. - -В общем случае утверждение "для любых $k \in K$ и $y \in E_k(X)$ выполняется -равенство $E_k(D_k(y)) = y$" является неверным. - -Реальный шифр отождествляется с его математической моделью $\sum_A$, которая -называется /алгебраической моделью шифра/. - -*** (2) Вероятностная модель шифра - -Следуя К. Шеннону, введём априорные распределения вероятностей $P(X)$ и $P(K)$ -на множестве $X$ и $K$ соответственно. - -Для любого $x \in X$ определена вероятность $p_X(x) \in P(X)$ и для -любого $k \in K$ --- вероятность $p_K(k) \in P(K)$, причём выполняются -равенства $$\sum_{x \in X} p_X(x) = 1 \text{ и } \sum_{k \in K} p_K(k) -= 1$$ - -В тех случаях, когда требуется знание распределений $P(X)$ и $P(K)$, -используется вероятностная модель $\Sigma_B$, состоящая из пяти -множеств, связанных условиями (1) и (2) определения шифра и двух -вероятностных распределений: - -$$\Sigma_B = (X, K, Y, E, D, P(X), P(K))$$ - -Вероятностные характеристики шифров используются только в криптоанализе. - -В большинстве случаев множества $X$ и $Y$ представляют собой объединения -декартовых степеней некоторых множеств $A$ и $B$ соответственно, так что -для некоторых натуральных $L$ и $L_1$ -$$X = \cup_{L = 1}^L A^l \text{ и } Y = \cup_{L = 1}^{L_1} B^l$$ - -Множества $A$ и $B$ называются соответственно /алфавитом открытого -текста/ и /алфавитом шифрованного текста/. - -*** (3) Основные требования к шифрам - -Для современны криптографических систем защиты информации -сформулированы следующие общепринятые требования: -1) зашифрованное сообщение должно поддаваться чтению только при - наличии ключа; -2) число операция, необходимых для определения использованного ключа - шифрования по фрагменту шифрованного сообщения и соответствующего - ему открытого текста, должно быть не меньше общего числа возможных - ключей; -3) число операция, необходимых для расшифровывания информации путём - перебора всевозможных ключей должно иметь строгую нижнюю оценку и - выходить за пределы возможностей современных компьтеров (с учётом - возможности использования сетевых вычислений); -4) знание алгоритма шифрования не должно влиять на надёжность защиты; -5) незначительное изменение ключа (сообщения?) должно приводить к - существенному изменению вида зашифрованного сообщения даже при - использовании одного и того же ключа; -6) структурные элементы алгоритма шифрования должны быть неизменными; -7) дополнительные биты \dots - - //ДОПИСАТЬ!!!// - -# Лекция (03.10.22) -** (1.5) Шифры перестановки - -*** (1) /Определение/ - -Шифр перестановки --- шифр, при котором буквы открытого текста при -шифровании меняются друг с другом. Ключи шифра является перестановка -номеров букв открытого текста. - -Множество всех подстановок на множестве $M$ называют любое биективное -отображение множества $M$ в себя. Множество всех подстановок на -множестве $M$ обозначают через $S(M)$. Множество $S(M)$ относительно -операции суперпозиции отображения образует группу. - -Если $M$ --- конечное множество мощности $n$, то говорят, что $S(M)$ ---- симметрическая группа подстановок степени $n$. - -Группа $S(M)$ является коммутативной только в случае $n \leq 2$. - -Перенумеровав элементы множества $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$. - -Любая подгруппа $G$ группы $S_n$ называется /группой подстановок/ степени $n$. - -Пусть $X = Y = A^L$ и пусть $K \subset S_L$. Для любого ключа $k$, открытого -текста $x = (x_1, \dots, x_L)$ и шифрованного текста $y = (y_1, \dots, y_L)$ -правила зашифрования и расшифрования /шифра перестановки/ определяется -формулами -$$ 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$. - -*** (2) Маршрутные перестановки - -Широкое применение получили так называемые /маршрутные перестановки/, -основанные на некоторой геометрической фигуре. - -Отрезок открытого текста записывается в такую фигуру на некоторой -траектории. - -Шифрованным текстом является последовательность, полученная при -выписывании по другой траектории. - -*Примеры* - -1) /В учении нельзя останавливаться/, 28 букв - - в у ч е н и - и н е л ь з - я о с т а н - а в л и в а - т ь с я - - - - - - - - - - - вуиянчееоатвслниьтльсиазнвяа - -2) Вертикальная перестановка. - В этой системе также используется прямоугольная таблица, в которую сообщение - записывается построкам слева направо. - - Выписывается сообщение по вертикали (сверху вниз), при этом столбцы - выбираются в порядке, определяемом числовым ключом (например, в - алфавитном порядке букв ключа). - - /Без примера ничему не выучишься/, 27 букв - - | б | е | з | п | р | и | - | м | е | р | а | н | и | - | ч | е | м | у | н | е | - | в | ы | у | ч | и | ш | - | ь | с | я | - | - | - | - |---+---+---+---+---+---| - | ж | ё | л | у | д | ь | - - рнниеееысбмчвьзрмуяпаучииеш - -Более сложные маршрутные перестановки могут использовать другие -геометрические фигуры и более "хитрые" маршруты, например, при -обходе шахматной доски "ходом коня", пути в некотором лабиринте -и тому подобное. - -*** (3) Элементы криптоанализа шифров перестановки - -(а) Приведём основные идеи, используемые при вскрытии вертикальных -перестановок. - -Заметим, что это буквы каждого столбца заполненного прямоугольника -выписываются в криптограмму подряд, то есть криптограмма разбивается -на отрезки, являющиеся столбцами таблицы. - -Поэтому при дешифровании следует попытаться соединить две группы -последовательных букв криптограммы так, чтобы они образовывали -читаемые комбинации. - -Для этого естественно использовать наиболее частые биграммы открытого -текста, которые можно составить из букв криптограммы. - -Если для первой пробы выбрано, например, сочетание НИ, то можно по -очереди приписывать к каждой букве Н криптограммы каждую букву и из -неё. - -При этом несколько букв, стоящих до и после данной буквы Н, и несколько -букв, стоящих до и после данной буквы И, соединяются в пары, то есть -получаются два стобца букв, записанные рядом: -| I | II | -| ... | ... | -| Н | И | -| ... | ... | - -Длина столбцов неизвестна, но используя положение конкретных букв, -можно получить на них некоторые ограниения: -1) Столбцы должны иметь одинаковые длины или первый столбец может быть - длиннее второго на одну букву, и тогда эта буква --- последняя буква - сообщения. - | ... | ... | - | Р | А | - | ... | ... | - | У | Ч | - | Я | - | -2) Если приписываемые друг к другу буквы разделены, например, только четырьмя буквами, - то можно составить в соседних столбцах не более пяти пар, и длина каждого столбца - не превышает пяти: - | б | е | /з/ | п | р | и | - | м | е | /р/ | а | н | и | - | ч | /е/ | /м/ | у | н | е | - | в | /ы/ | у | ч | и | ш | - | ь | /с/ | я | - | - | - | - |---+-----+-----+---+---+---| - | ж | ё | л | у | д | ь | -3) Ограничением можно послужить появление запретной биграммы - | ... | ... | - | Н | И | - | ... | ... | - | И | Ь | - -Для выбранного сочетания НИ получается по одной паре столбцов для -каждого конкретного выбора букв Н и И из криптограммы, и из них -целесообразно отобрать ту пару, которая содержит наиболее частые -биграммы. - -При автоматизации этого процесса можно приписать каждой биграмме вес, -равный частоте её появления в открытом тексте. - -Тогда отбираеися та пара столбцов, которая имеет наибольший вес. - -Появление одной биграммы с низкой частотой может указать на то, что -длину столбца надо ограничить. - -Выбрав пару столбцов аналогичным образом подбирается к ним третий -(справа или слева) и так далее. Описанная процедура значительно -упрощается при использовании вероятных слов, то есть слов, которые -могут встретиться в тексте с большой вероятностью. - - -(б) Рассмотрим метод, применимый к любым шифрам перестановки. - -Допустим, что к двум или более сообщениям (или отрезкам сообщений) -одинаковой длины применяется один и тот же шифр перестановки. - -Тогда очевидно, что буквы, которые находились на одинаковых местах -в открытых текстах, окажутся на одинаковых местах и в криптограммах. - -Выпишем криптограммы одну под другой так, что первые буквы всех сообщений -оказываются в первом столбце, вторых --- во втором и так далее. - -# Лекция (10.10.22) - -палец -> ЕПЦЛА -волна -> НВАЛО -Ключ: 41532 - -Если предположить, что две конкретные буквы в одном из сообщений идут один -за другой в открытом тексте, то буквы, стоящие на тех же местах в каждом -из остальных сообщений, соединяются подобным же образом. - -Значит, они могут служить проверкой правильности первого предположения. - -К каждому из указанных двухбуквенных сочетаний можно добавить третью букву -для образования триграммы и так далее. - -Если располагать не менее чем 4 сообщениями одинаковой длины, то можно с -уверенностью гарантировать их вскрытие подобным образом. - -Если ключ зашифрования совпадает с ключом расшифрования, то такие шифры называют -/симметричными/, иначе --- /асимметричными/. - -** (1.6) Шифры простой замены - -*** (1) /Шифр замены/ -/Шифр замены/ --- шифр, при котором фрагменты открытого текста -(отдельные буквы или группы букв) заменяются некоторыми их -эквивалентами в криптограмме. - -Определим модель $\Sigma_A = (X, K, Y, E, D)$ произвольного шифра замены. - -Будем считать, что открытые и шифрованные тексты являются словами в алфавитах A и B -соответственно. $X \subset A^*, \, Y \subset B^*, \, |A| = n, \, |B| = m$. - -Перед зашифрованием открытый текст предварительно представляется в виде последовательностей -подслов, называемых /шифровеличинами/ (слова из $A^*$). - -При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в шифртексте, которые -называются /шифробозначениями/ (слова из $B^*$). - -Пусть -$U = (u_1, \dots, u_N)$ --- множество возможных шифрвеличин. -$V = (v_1, \dots, v_N)$ --- множество возможных шифробозначений. -При этом $N \geq n, \, M \geq m, \, M \geq N$. - -Для определения правила зашфирования $E_k(x)$ в общем случае понадобится -ряд обозначений и понятие /распределителя/, который, по сути, и будет -выбирать в каждом такте шифрования замену соответствующей шифровеличине. - -Посколько $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 \in N,$$ -и соответствующее семейство биекций: -$$\varphi_\alpha : U \to \{ 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, l)$ называется /распределителем/, отвечающим данным значениям -$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) !!!$. - -В качестве $y_j$ можно выбрать любой элемент множества $\varphi_{\alpha^{(k)}}(x_j)$. - -Всякий раз при шифровании этот выбор можно производить случайно, например, -с помощью некоторого /рандомизатора/ типа игровой рулетки. - -Для однозначных шифров замены, у которых правило дешифрования $E_k(x)$ -является однозначной функцией, например, шифр гаммирования, справедливо -свойство -$$\forall \alpha, i : |V^{(i)}_\alpha| = 1$$ -для многозначных шифров замены, например, шифров пропорциональной замены: -$$\exists \alpha, i : |V^{(i)}_\alpha| > 1$$ - -Далее будем заниматься в основном изучением однозначных замен, -получивших наобольшее практическое применение. - -Итак, далее $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}$, -то соответствующий шифр замены называется /шифром равнозначной замены/, в противном случае --- -/шифром разнозначной замены/. - -В подавляющем большинстве случаев используются шифры замены, для которых -$U \in A^p$ для некоторого $p \in \mathbb{N}$. - -При $p = 1$ говорят о /поточных шифрах замены/, при $p > 1$ --- о /блочных шифрах замены/. - -В случае $r = 1$ шифр замены называют /одноалфавитным шифром замены/ -или /шифром простой замены/. В противном случае --- /многоалфавитным шифром замены/. - - -*** (2) Одноалфавитные однозначные замены называются /шифрами простой замены/. - -Введём шифр простой замены в алфавите $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$. - -Например, в рассказе Артура Конана Дойля "Пляшущие человечки", -бандит Аб Слени использовал шифр, где заменялист схематическими -человеческими фигурками в разных позах, при этом каждая поза этих -человечков является отдельной буквой. - -*** (3) Лозунговый шифр - -При этом методе осуществляется посимвольная замена букв открытого -текста на буквы шифроалфавита, который совпадает с алфавитом открытых -текстов. - -В первой строке шифровальной таблицы записывается алфавит языка открытых -текстов. - -Во второй, начиная с некоторого места записывается лозунг (пароль). - -Затем на оставшихся местах второй строки, начиная с места следующего -за паролем, записывается полный алфавит с пропуском тех букв, которые -встречаются в пароле. - -Закончив движение по строке, возвращаемся в её начало, процесс продолжается. - -/ПРИМЕР!!!/ - -*** (4) Шифр простой неравнозначной замены - -Пример --- шифр Марк. - -/ПРИМЕР!!!/ - -Буквы, стоящие во второй строке таблицы при шифровании заменяются -стоящими над ними, остальные буквы --- двузначными числами -"строка-столбец". - -*** (5) Анализ шифров простой замены - -**** (а) Методы вскрытия шифра простой однобуквенной замены - -(а) Методы вскрытия шифра простой однобуквенной замены основан на том, -что с точностью до переобозначений частотные характеристики $m$-грамм -криптограммы и открытого текста одинаковы. - -При этом используются частотные характеристики предполагаемого -открытого текста, полученные с учётом "характера переписки". - -Обычно выделяют следующие этапы алгоритма. - -# Лекция 7 (17.10.22) -1) Подсчёт частот шифрообозначений, а также некоторых их сочетаний - (например, биграмм). - - Если длина текста достаточно велика, то найденные частоты окажутся - близкими к значениям частот знаков открытого текста; - -2) Выявление шифрообозначений, заменяющих гласные и согласные буквы. - - Основано на характерных свойствах этих букв, например, удвоение - гласных в открытом тексте происходит реже, чем согласных. - -3) Выдвижение гипотез о значениях шифрообозначений и их проверка. - - Восстановление истинных значений шифрообозначений. - - При этом учитывается, что каждая буква имеет предпочтительных - связей, которые составляют её наиболее характерную особенность. - - Как правило, такие гипотезы подтверждаются не полностью. - - Хорошим критерием при этом является "читаемость" - восстанавливаемого открытого текста. - -Приведём описание эвристического алгоритма дешифрования, основанного -на идее Томаса Якобсена. -1) Построить начальный вариант ключа $k$ на основе сравнения частот - знаков криптограмм и открытого текста. -2) Положить $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}$ --- эталонная матрица биграмм открытого текста. -3) Положить $k' = k$. -4) Поменять местами в нижней строке подстановки $k'$ некоторую пару букв, - например, $\alpha$ и $\beta$. -5) Положить $v' = f(D_{k'}(y))$. -6) Если $v' < v$, то положить $k = k', \, v' = v$ и перейти к 4). -7) Перейти к шагу 3). - -Алгоритм заканчивается, когда условие $v' < v$ не выполняется в течение -некоторого числа итераций, например, 100. - -Если шифр простой замены не является однобуквенным, то при вскрытии -криптограммы необходимо попытаться восстановить множество шифрвеличин. - -Если задача решена, то дальнейшая работа аналогична. - -**** (б) Некоторые особенности вскрытия равнозначных шифров простой замены. - -1) Длины повторений фрагментов и расстояния между ними должны быть - кратны значности шифра (/значность шифра/ --- количество знаков - (цифр или букв), образующих одно шифрообозначение). -2) Находя НОД этих чисел с большей вероятностью получается искомая значность. -3) Подсчитать общее число шифрообозначения, если это число близко к - ожидаемому числу шифрообозначений (например, к числу букв - алфавита), и диаграмма их повторяемости близка к табличной, то, - скорее всего, значность определена верно. - -**** (в) Некоторые особенность вскрытия разнозначных шифров простой замены - -1) В этом случае числа, равные длинам повторений и расстояниям между ними, - скорее всего, взаимно просты в совокупности. - - Для определения множества шифрообозначений помогает естественное - ограничение, которым обычно пользуются при составлении таблицы - шифрообозначений. - - Оно связано с требованием однозначности расшифрования и заключается в - том, чтобы ни одно из шифрообозначений не являлось началом никакого - другого шифрообозначения (в теории кодирования в подобной ситуации - говорит о /префиксном коде/); - -2) Если значность шифрообозначений колеблется в незначительных пределах, - то перебор сравнительно небольшого числа вариантов приводит (с учётом - ограничения) к правильному определению большинства шифробобзначений. - - Некоторые затруднения могут возникать лишь при определении значности - шифрообозначений, редко встречающихся в тексте. - - Как правило, эти проблемы решаются вместе с попытками прочтения тех - участков криптограммы, для которых восстановленная значность - шифрообозначений не вызывает сомнений. - -Увеличение значности шифрообозначений делает шифр неэкономным, поэтому -получили распространение шифры, использующие одно- и двузначные -шифрообозначения. - -Для таких шифров наибольшую повторяемость в шифртексте имеют цифры, -с которых начинаются двузначные шифрообозначения. - -Выдвигая гипотезы о таких цифрах и отмечая в шифртексте соответствующие -двузначные шифрообозначения, можно восстановить и однозначные шифрообозначения, -оказавшиеся в шифртексте между некоторыми двузначными шифрообозначениями. - -*** (6) Блочные шифры простой замены. - -**** Пример --- Шифр хилла. - -Шифр Хилла --- полиграммный шифр подстановки, основанный на линейной -алгебре и модульной арифметике. - -Изобретён американским математиком Л. Хиллом в 1929 году. - -Пусть мощность алфавита равна $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}$. - -/Пример/: Еду = $(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$ предложен следующий практический -способ: -1) Нужно взять произвольную нижнюю треугольную матрицу над $Z_m$ с определителем, - равным 1 (для этого достаточно положить равными 1 все элементы главной диагонали). -2) Далее берётся верхняя треугольная метрица над $Z_m$ с определителем, равным 1. -3) Перемножив эти матрица, получаем обратимую матрицу над кольцом $Z_m$. - -Пример: -$$\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$ -является /инволютивной/, то есть $A^{-1} = A$. Тогда $\vec{x} = (\vec{y} - \vec{a}) A$. - -Как построить ниволютивную матрицу? - -1) Пусть для заданных $m$ и $n$ имеется пара взаимообратных матриц - $A$ и $A^{-1}$. Возьмём любую диагональную инволютивную матриу $I$ - (можно просто вбрать элементы главной диагонали равными 1 и -1). -2) Тогда $A I A^{-1}$ --- инволютивная матрица. - -\begin{remark} - К настоящему времени не найдена простая формула для подсчёта - количества инволютвных матриц над $Z_m$. -\end{remark} - -Увеличение значности шифрвеличин резко усложняет попытки вскрытия -открытого текста по известному тексту криптограмм. - -Однако свойство линейности является их криптографической слабостью, -например, задача нахождения ключа является не слишком трудоёмкой, если -известны $n + 1$ пар блоков открытого текста и соответствующих их -блоков шифртекста, полученные на данном ключе. - -# Лекция (24.10.22) -* Шифры многоалфавитной замены - -Напомним, что правило зашифрования многоалфавитного шифра однозначной замены -определяется следующим образом. - -Пусть $x = (x_1, \dots, x_l)$ --- открытый текст, представленный последовательностью шифрвеличин -$x_l$ |