diff options
Diffstat (limited to 'cryptography/cry.org')
| -rw-r--r-- | cryptography/cry.org | 880 |
1 files changed, 880 insertions, 0 deletions
diff --git a/cryptography/cry.org b/cryptography/cry.org new file mode 100644 index 0000000..4d3894e --- /dev/null +++ b/cryptography/cry.org @@ -0,0 +1,880 @@ +#+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$ |