diff options
21 files changed, 2362 insertions, 0 deletions
diff --git a/crypto-algebra/crypto-algebra.pdf b/crypto-algebra/crypto-algebra.pdf Binary files differindex a8f0f3f..2412a6f 100644 --- a/crypto-algebra/crypto-algebra.pdf +++ b/crypto-algebra/crypto-algebra.pdf diff --git a/crypto-algebra/crypto-algebra.tex b/crypto-algebra/crypto-algebra.tex index bc2c47a..992621b 100644 --- a/crypto-algebra/crypto-algebra.tex +++ b/crypto-algebra/crypto-algebra.tex @@ -18,5 +18,16 @@ % Семестр 1 \input{lectures/lecture1.tex} \input{lectures/lecture2.tex} +\input{lectures/lecture3.tex} +\input{lectures/lecture4.tex} +\input{lectures/lecture5.tex} +% \input{lectures/lecture6.tex} +\input{lectures/lecture7.tex} +\input{lectures/lecture8.tex} +\input{lectures/lecture9.tex} +\input{lectures/lecture10.tex} +\input{lectures/lecture11.tex} +% \input{lectures/lecture12.tex} +\input{lectures/lecture13.tex} \end{document} diff --git a/crypto-algebra/lectures/lecture10.tex b/crypto-algebra/lectures/lecture10.tex new file mode 100644 index 0000000..c9da50d --- /dev/null +++ b/crypto-algebra/lectures/lecture10.tex @@ -0,0 +1,224 @@ +% Лекция 10 (13.11.23) +%% TODO: проверить рендеринг потому что maker не завёлся + +%% NOTE: 7 +\paragraph{Расширения конечных полей} + +%% NOTE: 39 +\begin{theorem}[Количество точек эллиптической кривой над конечным полем, + свойство эндоморфизма Фробениуса] + Пусть $E / \F_q$ --- эллиптическая кривая, + \begin{equation*} + \varphi : E \to E,\, (x, y) \to (x^q, y^q), --- + \end{equation*} + эндоморфизм Фробениуса степени $q$ и + \begin{equation*} + t = q + 1 - #E(\F_q). + \end{equation*} + \begin{enumerate} + \item + Пусть $\alpha, \beta \in \C$ --- корни полинома $T^2 - tT + q$. Тогда + $\alpha$ и $\beta$ --- комплексно-сопряжённые, удовлетворяющие условиям + $|\alpha| = |\beta| = \sqrt{q}$, и для любого $r \geq 1$ + \begin{equation*} + #E(\F_q^r) = q^r + 1 - \alpha^r - \beta^r. + \end{equation*} + \item + Эндоморфизм Фробениуса удовлетворяет условию + \begin{equation*} + \varphi^2 - t \varphi + q = 0 \text{в кольце эндоморфизмов } \fn{End}(E). + \end{equation*} + \end{enumerate} + \label{thm:39} +\end{theorem} + +\begin{theorem}[Теорема Вейля для эллиптических кривых, А. Вейль, 1949 г.] + Пусть $E / \F_q$ --- эллиптическая кривая. Тогда существует $t \in \Z$ такое, + что дзета-функция эллиптической кривой является рациональной функцией от $T$: + \begin{equation*} + Z(E/\F_q; T) = \frac{1 - tT + qT^2}{(1 - T)(1 - qT)}. + \end{equation*} + + Более того $1 - tT + qT^2 = (1 - \alpha T)(1 - \beta T)$ с $|\alpha| = |\beta| + = \sqrt{q}$. +\end{theorem} +\begin{proof} + Логарифмируем равенство + %% TODO: переписать + \begin{equation*} + \ln Z(E/\F_q; T) \bydef \sum_{r = 1}^\infty \frac{#E(\F_q^r) T^r}{r} + =%_теорема 39 пункт а) + \sum_{r = 1}^\infty \frac{(1 - \alpha^r - \beta^r + q^r) T^r}{r} = + \sum_{r = 1}^\infty \frac{T^r}{r} - \sum_{r = 1}^\infty \frac{(\alpha T)^r}{r} - +\sum_{r = 1}^\infty \frac{(\beta T)^r}{r} +\sum_{r = 1}^\infty \frac{(q T)^r}{r} +=_* +используя тождество +ln(1 - x) = ln(1 + (-x)) = \sum_{r = 1}^\infty \frac{(-1)^{r + 1} (-x)^r}{r} = - \sum_{r = 1}^\infty \frac{x^r}{r}, +получаем +=_* -ln(1 - T) + ln(1 - \alpha T) + ln(1 - \beta T) - ln(1 - qT) = ln \left( \frac{1 - \alpha T) (1 - \beta T)}{(1 - T) (1 - qT)} \right). + \end{equation*} + следовательно, + \begin{equation*} + Z(E/\F_q; T) = \frac{1 - \alpha T) (1 - \beta T)}{(1 - T) (1 - qT)} + \end{equation*} + + По теореме \ref{thm:39}, пункт а) \alpha и \beta являются комплексно-сопряжёнными корнями полинома $T^2 - tT + q$, удовлетворяющие условиям + $|\alpha| = |\beta| = \sqrt{q}$, тогда по теореме Виета + \begin{equation*} + \alpha + \beta = t \land \alpha \beta = q. + \end{equation*} + + Имеем + \begin{equation*} + (1 - \alpha T)(1 - \beta T) = 1 - \beta T - \alpha T + \alpha \beta T^2 = 1 - (\alpha + \beta) T + (\alpha \beta) T^2 = 1 - tT + qT^2 + \end{equation*} + + Получаем + \begin{equation*} + Z(E/\F_q; T) = \frac{1 - tT + qT^2}{(1 - T)(1 - qT)} + \end{equation*} + + Также + \begin{equation*} + t = \alpha + \beta = q + 1 - #E(\F_q) \in \Z. + \end{equation*} +\end{proof} + +Пусть $E/\F_q$ --- эллиптическая кривая. Величина +\begin{equation*} + t = q+ 1 - #E(\F_q) +\end{equation*} +называется \emph{следом Фробениуса}. + + +Примечание --- К теореме Хассе. Из рассуждений имеем +\begin{equation*} + |#E(\F_q) - (q + 1)| = |-t| = |t| = |\alpha + \beta| \leq |\alpha| + |\beta| \leq 2\sqrt{q} +\end{equation*} + +Так как $\alpha$ и $\beta$ вместе с $t$ определяют значение $#E(\F_q)$, то число +точек над $\F_q$ однозначно определяет число точек над любым его расширением. + +Таким образом, теорему Вейля для эллиптических кривых можно использовать, в +частности, для нахождения числа точек над расширениями высокой степени. + +\begin{example} + Вычислим число точек эллиптической кривой $y^2 + y = x^3$. Здесь есть три + $\F_2$-рациональные точки: $(0; 0)$, $(0; 1$, $\mathcal{O}$ --- и дзета-функция + данной эллиптической кривой над полем $\F_2$ вычисляется следующим образом: + %% TODO: часть 1, 2, 3, 4 +\end{example} + +%% NOTE: 9 +\paragraph{Скручивание эллиптических кривых} + +Скручивание $E/F$ --- это гладкая кривая $E'/F$, изоморфная $E$ над $\overline{F}$. +Два скручивания эквивалентны, если они изоморфны над $F$. + +%% TODO: \ref{8} +Пусть $E$ --- эллиптическая кривая, заданная уравнением (8) над конечным полем +$\F_q,\, v \in \F_q$ --- некоторый квадратичный невычет. + +Эллиптическая кривая $E'$: +\begin{equation*} + y^2 = x^3 + a'x + b'. +\end{equation*} +где $a' = v^2 a,\, b = v^3 b$, является скручиванием $E$ над полем $\F_q$. + +%% NOTE: 41 +\begin{theorem}[О порядках эллиптической кривой и её скручивания] + Пусть $E$ --- эллиптическая кривая над $\F_q$, $E'$ --- скручивание эллиптической + кривой $E$ над $\F_q$. Тогда + \begin{equation*} + #E(\F_q) + #E'(\F_q) = 2q + 2. + \end{equation*} +\end{theorem} +\begin{proof} + Пусть + \begin{equation*} + g(x) = x^3 + ax + b. + \end{equation*} + + Тогда кривая $E$ задаётся уравнением + \begin{equation*} + y^2 = g(x), + \end{equation*} + для кривой $E'$ получаем + \begin{equation*} + y^2 = x^3 + a'x + b' = x^3 + v^2 ax + v^3 b = v^3 \left( \left(\frac{x}{v}\right)^3 + a \frac{x}{v} + b \right) = + v^3 g \left( \frac{x}{v} \right), + \end{equation*} + то есть кривая $E'$ задаётся уравнением + \begin{equation*} + y^2 = v^3 g \left( \frac{x}{v} \right). + \end{equation*} + + Когда $x$ пробегает все значения из $\F_q$, $\frac{x}{v}$ также пробегает все + значения из $\F_q$. Таким образом, каждому корню полинома $g$ соответствует + одна точка на каждой из эллиптических кривых $E$ и $E'$. + + Каждому значению $g$, которое является квадратичным вычетом, соответствуют две + точки на $E$ и ни одной на $E'$, так как $v^3 g$ будет квадратичным невычетом. + + Обратно, каждому значению $g$, которое является квадратичным невычетом + соотвествует две точки на $E'$ и ни одной на $E$, так как $v^3 g$ будет + квадратичным вычетом. + + Поэтому каждое значение $g$ в сумме даёт две точки на кривых $E$ и $E'$. + Поскольку всего имеется $a$ значений $g$ (с учётом кратности), то получаем + аффинные $2q$ точки на кривых $E$ и $E'$. + + Так как каждая из этих кривых содержит $\mathcal{O}$, то общее количество + элементов на $E$ и $E'$ равно $2q + 2$. +\end{proof} + +Благодаря этому факту после того, как найден порядок кривой, порядок её скручивания +находится без вычисления. + +\begin{example} + Пусть $E: y^2 = x^3 + 9$ --- эллиптическая кривая над $\F_{29}$. Возьмём, + например, $2 \in \F_{29}$ --- квадратичный невычет, так как сравнение $x^2 - 2 + \equiv 0 \pmod{29}$ не имеет решений. + + То есть скручивание $E'$: + \begin{equation*} + y^2 = x^3 + v^3 b = x^3 + 2^3 \cdot 9 = x^3 + 72 + \end{equation*} + + Тогда + \begin{equation*} + #E(\F_{29}) + #E'(\F_{29}) = 2 \cdot 29 + 2 = 60. + \end{equation*} +\end{example} + + +%% NOTE: 9 +\paragraph{Строение группы точек эллиптической кривой.} + +%% NOTE: 42 +\begin{theorem}[Строение группы точек эллиптической кривой, определённой над + конечным полем]. + Пусть $E/\F_q$ --- эллиптическая кривая, заданная над конечным полем $\F_q$. + Тогда $E(\F_q)$ либо является циклической группой, либо изоморфна произведению + двух циклических групп: + \begin{equation*} + E(\F_q) \cong \Z_{d_1} \times \Z_{d_2}, + \end{equation*} + где $d_1 | d_2$ и $d_1 | (q - 1)$. +\end{theorem} + +Пусть $N = #E(\F_q)$. Разлагая каждую из циклических групп в произведение групп +порядков $p^n$ для разных простых, можно представить группу точек произвольной +эллиптической кривой единственным образом в виде произведения групп вида +\begin{equation*} + \Z_{p^\alpha} \times \Z_{p^\beta}, +\end{equation*} +где произведение берётся по всем простым делителям $N$ (здесь $\alpha \geq 1,\, +\beta \geq 0$). + +Под \emph{типом} абелевой группы $\F_q$-рациональных точек на $E$ понимается +список $(\dots, p^\alpha, p^\beta, \dots)_{p|N}$ порядков циклических +$p$-примерных сомножителей в указанном представлении в виде произведения +(если $\beta = 0$, $p^\beta$ опускаем). + diff --git a/crypto-algebra/lectures/lecture11.tex b/crypto-algebra/lectures/lecture11.tex new file mode 100644 index 0000000..fbf6e72 --- /dev/null +++ b/crypto-algebra/lectures/lecture11.tex @@ -0,0 +1,13 @@ +% Лекция 11 (20.11.23) + +Тип определяет группу с точностью до изоморфизма. Найти тип не всегда легко. + +\begin{example} + Найдём тип абелевой группы эллиптической кривой $y^2 = x^3 - x$, определённой + над $\F_{71}$. Найдём сначала число точек $N$. + + Заметим, что в сумме (\ref{eq:18}) члены для $x$ и для $-x$ сокращаются друг + с другом (то есть функция нечётная): + + %% TODO: дописать пример 1, 2, 3, 4 +\end{example} diff --git a/crypto-algebra/lectures/lecture13.tex b/crypto-algebra/lectures/lecture13.tex new file mode 100644 index 0000000..7b6414f --- /dev/null +++ b/crypto-algebra/lectures/lecture13.tex @@ -0,0 +1,183 @@ +% Лекция 13 (04.12.23) + +Соответствие $x \\ x'$ является взаимно однозначным и легко вычислимым. + +\begin{example} + Встроим открытый текст в координату точки эллиптической кривой, определённой + над конечным полем $\FF_{32} = \FF_{2^5}$. Пусть эллиптическая кривая $E(\FF_{32})$ + задана уравнением + \begin{equation*} + y^2 + xy = x^3 + t; + \end{equation*} + поле $\FF_{32}$ задано полиномом + \begin{equation*} + t^5 + t^2 + 1, + \end{equation*} + таким образом, $\FF_{32} = \FF_2 / (t^5 + t^2 + 1)$. + + Кривая имеет 16 точек. Открытый текст $t^3 + 1$ не является $x$-координатой + точки кривой. Вычисляем + \begin{align*} + \sqrt{t} &= t^{2^{5 - 1}} = t^{16} = * \\ + t^5 &= -t^2 - 1 = t^2 + 1; \\ + t^6 &= tt^5 = t(t^2 + 1) = t^3 + t; \\ + t^7 &= t^4 + t^2; \\ + t^8 &= t^5 + t^3 = t^3 + t^2 + 1; \\ + t^{16} &= (t^8)^2 = t^6 + 2t^5 + t^4 + 2t^3 + 2t^3 + 2t^2 + 1 + = t^4 + t^3 + t + 1. \\ + * &= t^4 + t^3 + t + 1. + \end{align*} + + Заменяем элемент $t^3 + 1$ на элемент, заданный уравнением + \begin{equation*} + \frac{1}{x} = \frac{1}{t^4 + t^3 + t + 1} + \frac{1}{t^3 + 1}. + \end{equation*} + + Получаем необходимую $x$-координату точки кривой: + \begin{align*} + \frac{1}{x} &= \frac{t^4 + t^3 + t + 1 + t^3 + 1}{(t^4 + t^3 + t + 1)(t^3 + 1)} = \\ + &= \frac{t(t^3 + 1)}{(t^4 + t^3 + t + 1)(t^3 + 1)} = \\ + &= \frac{t}{t^4 + t^3 + t + 1}; \\ + x &= t^3 + t^2 + \frac{1}{t} + 1 = \\ + &= t^3 + t^2 + (t^4 + t) + 1 = \\ + &= t^4 + t^3 + t^2 + t + 1. + \end{align*} +\end{example} + +%% NOTE: 3.3.2 +\subsubsection{Установление сеансового ключа} + +Рассмотрим аналог ключевого обмена Диффи--Хеллмана. Предположим, что Алиса и Боб +хотят договориться о ключе, которым будут впоследствии пользоваться в некоторой +классической криптосистеме. + +Ключом может служить <<случайная>> точка на эллиптической кривой $E$, так как +Алиса и Боб могут заранее договориться о способе преобразования её в целое число +(например, взять образ её координаты $x$ при некотором установленном в системе +простом отображении из $\FF_q$ в натуральные числа). + +Итак, предположим, что $E$ --- эллиптическая кривая над $\FF_q$, а $Q$ --- +согласованная (и общеизвестная) точка на кривой. Желательно, чтобы точка $Q$ +имела весьма большой порядок (равный либо $\#E(\FF_q)$, либо большому делителю +$\#E(\FF_q)$). + +Здесь точка $Q$ играет ту же роль, что и образующий элемент $g$ в системе +Диффи--Хеллмана для конечных полей. + +Договорённость может быть предварительной, или эллиптическая кривая может +создаваться непосредственно в ходе сеанса связи. + +Для установления сеансового ключа Алиса и Боб выполняют следующий протокол: +\begin{enumerate} + \item + Алиса случайным образом выбирает целое число $k_A$, которое держит в секрете. + \item + Алиса вычисляет точку $k_A Q \in E$ и посылает её Бобу (возможно открыто). + \item + Боб случайным образом выбирает целое число $k_B$, которое держит в секрете. + \item + Боб вычисляет точку $k_B Q \in E$ и посылает её Алисе (возможно открыто). + \item + Алиса умножает точку, которую она получила от Боба, на свой секретный ключ + $k_A$. Боб умножает точку, которую он получил от Алисы, на свой секретный + ключ $k_B$, тем самым получая общий ключ + \begin{equation*} + P = k_A k_B Q \in E + \end{equation*} +\end{enumerate} + +Ева, которая бы хотела шпионить за Алисой и Бобом, должна была бы определить $P += k_A k_B Q$, зная $Q$, $k_A Q$ и $k_B Q$, но не зная $k_A$ или $k_B$. + +Задача подслушивателя называется <<задачей Диффи--Хеллмана для эллиптических +кривых>>. + +Систему Диффи--Хеллмана можно взломать, если решить <<проблему дискретного +логарифма>> в группе точек эллиптической кривой $E$. + +\subsubsection{Шифрование} + +Протокол Диффи--Хеллмана модифицируется для передачи сообщений, используя +идею Эль-Гамаля. Пусть $E$ --- эллиптическая кривая над $\FF_q$, а $Q$ --- +согласованная (и общеизвестная) точка на кривой. + +Предположим, что набор единиц сообщения был встроен в $E$ некоторым +согласованным образом, и Боб хочет послать Алисе сообщение $M \in E$. + +\begin{enumerate} + \item + Алиса случайным образом выбирает целое число $k_A$, которое держит в секрете. + \item + Алиса вычисляет точку $k_A Q \in E$ и посылает её Бобу (возможно открыто). + \item + Боб случайным образом выбирает целое число $k_B$, которое держит в секрете. + \item + Боб вычисляет точку $k_B Q \in E$ и посылает её Алисе (возможно открыто). + \item + Боб выбирает другое секретное случайное целое число $l$. + \item + Боб отправляет Алисе пару точек + \begin{equation*} + (lQ, M + l(k_A q)). + \end{equation*} + \item + Чтобы расшифровать сообщение, Алиса умножает первую точку в паре на своё + секретное $k_A$, а затем вычитает результат из второй точки в паре: + \begin{equation*} + (M + l(k_A Q)) - k_A(lQ) = M. + \end{equation*} +\end{enumerate} + +Данную систему также можно будет взломать, если решить <<проблему дискретного +логарифма>> в группе точек эллиптической кривой $E$. + + +\subsubsection{Цифровая подпись} + +\paragraph{Протокол цифровой подписи Эль-Гамаля.} + +В протоколе цифровой подписи Эль-Гамаля открытый ключ проверки подписи сожержит +уравнение эллиптической кривой $E(F)$, образующую $Q$ простого порядка $r$ и +точку $P = lQ$. + +Секретным ключом формирования подписи является показатель $l$. Кроме того, в +протоколе подписи используется хэш-функция $h$ и функция $f$. В качестве +функции $f(R)$ могут использоваться функции от координат: $x_R$, $y_R$, +$x_R + y_R$ и т. п. + +Для получения цифровой подписи под сообщением $M$ необходимо выполнять +следующие действия (шаги) по алгоритму: +\begin{enumerate} + \item вычислить хэш-код сообщения $M: h(m)$; + \item + сгенерировать случайное (псевдослучайное) целое число $k$, удовлетворяющее + неравенству + \begin{equation*} + 0 < k < r; + \end{equation*} + \item + вычислить точку эллиптической кривой $R = kQ$, $R = (x_R, y_R)$; + \item + вычислить значение $s$ из решения сравнения + \begin{equation} + h(m) \equiv lf(R) + ks \pmod{r} + \label{eq:23} + \end{equation} +\end{enumerate} + +При этом необходимо, чтобы выполнялось неравенство $f(R) \neq 0 \pmod{r}$, в +противном случае вернуться к шагу 2. Если $f(R) \equiv 0 \pmod{r}$, то подпись +не зависит от персонального ключа. + +Исходными данными этого процесса являются ключ подписи $l$ и подписываемое +сообщение $M$, а входным результатом --- цифровая подпись $(R, s)$. + +При этом можно сократить объём подписи, задав вместо $R$ только координату +$x_R$ и знак координаты $y_R$ (0, если $y_R < \frac{p}{2}$, и 1, если $y_R +> \frac{p}{2}$), тогда при проверке подписи необходимо будет восстановить +координату $y_R$ решением квадратного уравнения в поле $F$. + +Для проверки цифровой подписи $(R, s)$ под полученным сообщением $M$ необходимо +выполнять следующие действия (шаги) по алгоритму: + +%% TODO: дописать diff --git a/crypto-algebra/lectures/lecture3.tex b/crypto-algebra/lectures/lecture3.tex new file mode 100644 index 0000000..826342c --- /dev/null +++ b/crypto-algebra/lectures/lecture3.tex @@ -0,0 +1,176 @@ +% Лекция 3 (18.09.23) + +Пусть $R$ --- некоторое кольцо. Подмножество $I \subseteq R, I \neq +\varnothing$, называется \emph{правым идеалом}, если +\begin{enumerate} + \item + $I$ является подгруппой аддитивной группы $R$ (то есть для любых $a, b \in + I$ выполняется $a + b \in I$); + \item + Для любых $x \in R$ и $a \in I$ выполняется $ax \in I$, то есть $Ix + \subseteq I$. +\end{enumerate} + +Аналогично определяется \emph{левый идеал}. Если идеал является одновременно +правым и левым, то его называют \emph{двусторонним идеалом} или просто +\emph{идеалом}. В коммутативных кольцах все идеалы двусторонние. + +\begin{example} + Если $r$ --- какой-то элемент из коммутативного кольца $R$, то множество $rR$ + всегда является идеалом в $R$. Говорят, что $rR$ --- \emph{главный идеал}, + порождённый элементом $r \in R$. +\end{example} + +\paragraph{Векторные пространства} %% NOTE: 6 + +\emph{Векторным пространством} $V$ над полем $F$ называется абелева группа +$(V, +)$ вместе с операцией умножения $\cdot : F \times V \to V$ (обычно +обозначаемой сопоставлением) такой, что для всех $a, b \in F$ и $v, w \in V$ +выполняются следующие аксиомы: +\begin{enumerate} + \item $a (v + w) = av + aw$; + \item $v (a + b) = av + bv$; + \item $(ab)v = a(bv)$; + \item $1v = v$. +\end{enumerate} + +Элементы $V$ называются \emph{векторами}, а элементы $F$ называются +\emph{скалярами}. Групповая операция $+$ называется \emph{векторным сложением}, +а операция умножения --- \emph{скалярным умножением}. + +Пусть $S = \set{v_1, v_2, \dots, v_n}$ --- конечное подмножество векторного +пространства $V$ над полем $F$. + +Линейная комбинация $S$ --- это выражение вида +\begin{equation*} + a_1 v_1 + a_2 v_2 + \dots + a_n v_n, +\end{equation*} +где каждое $a_i \in F$. + +Множество $S$ \emph{линейно зависимо} над $F$, если существуют скаляры $a_1, +a_2,$ $\dots, a_n$, не все нули, такие, что +\begin{equation*} + a_1 v_1 + a_2 v_2 + \dots + a_n v_n = 0 +\end{equation*} + +Если таких скаляров не существует, то $S$ \emph{линейно независимо} над $F$. + +Пусть $V$ --- векторное пространство над полем $F$. Его (конечным) +\emph{базисом} называется такое множество $n$ векторов $v_1, \dots, v_n$, что +любой $w \in V$ однозначно представим в виде линейной комбинации +\begin{equation*} + w = a_1 v_1 + \dots + a_n v_n, +\end{equation*} +где $a_i \in F$. + +\begin{theorem}[О базисе] %% NOTE: 12 + Пусть $V$ --- векторное пространство. Если существует один конечный базис $V$ + над $F$, то любой другой базис имеет то же число элементов. +\end{theorem} + +Если векторное пространство $V$ имеет базис, то количество элементов в базисе +называется \emph{размерностью} $V$ и обозначается $\dim V$. + +Если пространство не имеет конечного базиса, оно называется +\emph{бесконечномерным}. + +\begin{example} + Полиномы степени $\leq n$ над любым полем $F$ образуют $(n + 1)$-мерное + векторное пространство над $F$ с базисом $1, x, x^2, \dots, x^n$ (базис + не определяется однозначно, например, $1, 1 + x, 1 + x^2, \dots, 1 + + x^n$ --- тоже базис). Коммутативное кольцо все полиномов $F[x]$ является + бесконечномерным векторным пространством над полем $F$. +\end{example} + +Пусть $K$ --- расширение поля $F$. Тогда $K$ можно рассматривать как векторное +пространство над подполем $F$, где векторное сложение и скалярное умножение --- +это операции сложения и умножения в поле $K$. + +Это означает, что $(K, +)$ --- абелева группа и что определено умножение её +элементов на элементы $F$ (скаляры), подчиняющиеся тождествам +\begin{enumerate} + \item $a (bv) = (ab) v$; + \item $(a + b) v = av + bv$; + \item $a (v + w) = av + aw$; + \item $1v = v$. +\end{enumerate} +для всех $a, b \in F$ и $v, w \in K$. + +Размерность этого векторного пространства называется \emph{степенью} $K$ над +$F$ и обозначается $[K: F]$. Если эта степень конечна, то $K$ называется +\emph{конечным расширением} F. + +\begin{theorem}[О конечном расширении] + Пусть $F, K, L$ --- поля. Если $L$ --- конечное расширение $K$ и $K$ --- + конечное расширение $F$, то $L$ также является конечным расширением $F$ и + \[ [L: F] = [L: K] [K: F] \] +\end{theorem} + + +\paragraph{Расширения полей.} + +Пусть $F$ и $K$ --- два поля, причём $F \subset K (K / F)$. Поле $K$ называется +\emph{простым расширением} поля $F$, если существует такой элемент $a \in K$, +что $K = F(a)$ --- наименьшее подполе $K$, содержащее $F$ и $a$. Элемент $a$ +называется \emph{примитивным элементом} расширения. Подполе поля $K$, отличное +от $K$, называется \emph{собственным полем}. \emph{Простым} называется поле, не +содержащее собственных полей. + +Элемент $a \in K$ называется \emph{алгебраическим} над полем $F$, если он +удовлетворяет алгебраическому уравнению +\begin{equation*} + f(a) = \sum_{k = 0}^n c_k a^k = 0, +\end{equation*} +где $c_0, \dots, c_n \in F$. + +Полином $f(x)$ называется \emph{аннулирующим полиномом элемента $a$}. + +Среди всех аннулирующих полиномов можно выбрать полином наименьшей степени +со старшим коэффициентом, равным единице. Такой полином называется +\emph{минимальным полиномом} элемента $a$ (минимальный полином неприводим, то +есть не разлагается в произведение полиномов меньшей степени). + +Алгебраичность элемента измеряется размерностью подполя, которое он порождает. + +Расширение полей $F \subset K$ называется \emph{алгебраическим}, если любой +элемент $a \in K$ алгебраичен над $F$. Коротко говорят, что расширение $K$ +конечно (алгебраично) над $F$. + +Итак, поле $F(a)$ содержит кольцо $R$ полиномов от переменной $a$ с +коэффициентами из $F$, $R = \set{\sum c_k a^k}$, $c_k \in F$. + +Имеет место изоморфизм $R \cong F[x] / f(x)$, более того +\begin{equation*} + F(a) = R \cong F[x] / f(x), +\end{equation*} +где $F[x]$ --- кольцо полиномов от одной переменной $x$, $x$ --- формальная +переменная, не имеющая отношения к полю $F(a)$, $a$ --- элемент поля $F(a)$, +$f(x)$ --- неприводимый над $F$ полином такой, что $f(a) = 0$. + +Элемент $a$ удовлетворяет уравнению $f(a) = 0$, которое называется +\emph{уравнением, определяющим поле $F(a)$.} + +Таким образом, любой элемент поля $F(a)$ в этом случае является полиномом. С +такими полиномами можно обращаться как с классами вычетов по модулю $f(x)$, то +есть степень каждого из них меньше степени полинома $f(x)$. Для некоторого +полинома $f(a) \in F[a]$ равенство $f(a) = 0$ эквивалентно сравнению $f(a) +\equiv 0 \pmod{f(a)}$. + +\begin{example} + Пусть $F = \set{0, 1}$. Построим алгебраическое расширение $F(t)$ степени 4. + Выберем неприводимый полином вида $f(x) = x^4 + x + 1$. Обозначим корень + этого полинома через $t$. Тогда $F(t) = F[t] / f(t)$. +\end{example} + +Поле $K$ называется \emph{алгебраически замкнутым}, если любой полином из +$K[x]$ степени, большей нуля, имеет в $K$ корень, то есть любое алгебраическое +над полем $K$ число принадлежит этому полю (то есть любой полином из $K[x]$ +раскладывается на линейные множители). + +Поле $K \supset F$ называется \emph{алгебраическим замыканием} поля $F$, если +$K$ алгебраично над $F$ и алгебраически замкнуто. + +\begin{theorem}[Об алгебраичности расширения конечной степени] + Всякое расширение $F \subset K$ конечной степени алгебраично, то есть все + элементы поля $K$ алгебраичны над полем $F$. +\end{theorem} diff --git a/crypto-algebra/lectures/lecture4.tex b/crypto-algebra/lectures/lecture4.tex new file mode 100644 index 0000000..88feafe --- /dev/null +++ b/crypto-algebra/lectures/lecture4.tex @@ -0,0 +1,92 @@ +% Лекция 4 (18.09.23) + +\paragraph{Модель решётки.} + +Пусть $X$ --- конечное множество. Бинарное отношение <<$\leq$>> на множестве $X$ +называется \emph{отношением частичного порядка}, когда для любых $a, b, c \in X$ +выполняются три свойства: +\begin{enumerate} + \item рефлексивность: $a \leq a$; + \item транзитивность: $(a \leq b, b \leq c) \implies (a \leq c)$; + \item антисимметричность: $(a \leq b, b \leq a) \implies (a = b)$. +\end{enumerate} + +Множество $X$ с заданной на нём частичной упорядоченностью называется +\emph{частично упорядоченным}. + +Если $a, b \in X$ и $a \leq b$, то, в зависимости от обстоятельств, говорят, +что $a$ \emph{меньше или равно} $b$, $a$ \emph{содержится в} $b$, $a$ +\emph{предшествует} $b$. + +Для $a, b \in X$ элемент $c = a \oplus b \in X$ называется \emph{наименьшей +верхней гранью}, когда выполняются условия: +\begin{enumerate} + \item $a \leq c, b \leq c$; + \item для $d \in X$ истинно $(a \leq d, b \leq d) \implies (c \leq d)$. +\end{enumerate} + +Для $a, b \in X$ элемент $c = a \otimes b \in X$ называется \emph{наибольшей +нижней гранью}, когда выполняются условия: +\begin{enumerate} + \item $c \leq a, c \leq b$; + \item для $d \in X$ истинно $(d \leq a, d \leq b) \implies (d \leq c)$. +\end{enumerate} + +Для пары элементов частично упорядоченного множества $X$ не обязательно +существует наименьшая верхняя (наибольшая нижняя) грань, но, если она +существует, то из антисимметричности следует её единственность. + +Эти элементы называют также \emph{точными} (\emph{верхней} и \emph{нижней} +соответственно) \emph{гранями} подмножества $X^* \subseteq X$. + +Пусть $X$ --- частично упорядоченное множество. $(X, \leq)$ называется +\emph{решёткой}, если каждое его конечное подмножество имеет точную нижнюю и +точную верхнюю грани, то есть, когда $\forall a, b \in X$ существуют +$a \otimes b \in X$ и $a \oplus b \in X$. + +\begin{lemma} %% TODO: пронумеровать (лемма 1) + Для любого набора $S = \set{a_1, a_2, \dots, a_n}$ элементов решётки $(X, + \leq)$ существуют единственные элементы: + \begin{itemize} + \item + $\oplus S = a_1 \oplus a_2 \oplus \dots \oplus a_n$ --- наименьшая + верхняя грань $S$; + \item + $\otimes S = a_1 \otimes a_2 \otimes \dots \otimes a_n$ --- наибольшая + нижняя грань $S$. + \end{itemize} +\end{lemma} + +Для решётки $(X, \leq)$ существует максимальный элемент $high = \oplus X$ и +минимальный элемент $low = \otimes X$. + +\emph{Линейная решётка (линейная шкала)} из $n$ элементов --- это линейное +упорядоченное множество; можно всегда считать $X = \set{0, 1, \dots, n}$. + +Как правило, решётки представляют с помощью ориентированных графов. При этом +вершинами графа являются элементы множества $X$, и если для $a_1, a_2 \in X$ +справедливо неравенство $a_1 \leq a_2$, то в графе существует путь из $a_1$ в +$a_2$. + +Частным важным случаем решёток является \emph{решётка подмножеств некоторого +конечного множества $U$}. Пусть $U$ --- конечное множество, $X = 2^{U}$ --- +множество всех подмножеств множества $U$. Определим решётку $(X, \leq)$ с +бинарным отношением частичного порядка <<$\leq$>>, где для $a, b \subseteq U$, +$a, b \in X$ выполняется условие: $a \leq b \iff a \subseteq b$. При этом $a +\oplus b = a \cup b,\, a \otimes b = a \cap b$. + +Пусть $(L, \leq)$ --- линейная решётка, $(X, \leq)$ --- решётка подмножеств $U$. +Определим \emph{решётку многоуровневой безопасности} $(X \times L, \leq)$ с +бинарным отношением частичного порядка <<$\leq$>>, где для $(a, \alpha), +(b, \beta) \in X \times L$ выполняется условие: $(a, \alpha) \leq (b, \beta) +\iff a \subseteq b, a \leq b$. + +При этом +\begin{align*} + (a, \alpha) \oplus (b, \beta) &= (a \cup b, \max\set{\alpha, \beta}) \\ + (a, \alpha) \otimes (b, \beta) &= (a \cap b, \min\set{\alpha, \beta}) \\ +\end{align*} + +На практике при использовании решёток многоуровневой безопасности решётка +$(L, \leq)$ является линейной шкалой уровней конфиденциальности, а $(X, \leq)$ +--- решёткой подмножеств множества неирархических категорий информации. diff --git a/crypto-algebra/lectures/lecture5.tex b/crypto-algebra/lectures/lecture5.tex new file mode 100644 index 0000000..dda14e3 --- /dev/null +++ b/crypto-algebra/lectures/lecture5.tex @@ -0,0 +1,164 @@ +% Лекция 5 (25.09.23) + +%% NOTE: 8 +\paragraph{Конечное поле} --- это поле $F$, содержащее конечное число элементов. + +\begin{theorem}[Существование и единственность конечных полей] + \begin{enumerate} + \item + Если $F$ --- конечное поле, то $F$ содержит $p^m$ элементов для некоторого + простого числа $p$ и целого числа $m \geq 1$. + \item + Для каждого простого числа $p$ и целого числа $m \geq 1$ существует + единственное (с точностью до изоморфизма) конечное поле порядка $p^m$. + \end{enumerate} +\end{theorem} + +Конечное поле порядка $p^m$ обозначается $\FF_{p^m}$ или $GF(p^m)$ и +называется \emph{полем Галуа}. Заметим, что если $p$ --- простое число, то +$\Z_p$ --- поле, а значит, каждое поле порядка $p$ изоморфно $\Z_p$. + +\begin{theorem}[О свойствах поля $\mathbb{F}_q$] + Если $\FF_q$ --- конечное поле порядка $q = p^m$, $p$ --- простое число, + то характеристикой $\FF_q$ является $p$. Более того, $\FF_q$ содержит в + качестве подполя простое поле $\FF_p = \Z_p$. Следовательно, $\FF_q$ можно + рассматривать как расширение поля $\Z_p$ степени $m$. +\end{theorem} + +Группа ненулевых элементов $\FF_q$ обозначается $\FF^*_q$. +\emph{Образующий элемент $g$} конечного поля $\FF_q$ есть элемент порядка $q - +1$. + +\begin{theorem}[О циклической группе $\FF_q$] + Каждое конечное поле имеет образующий элемент. Если $g$ --- образующий элемент + $\FF^*_q$, то $g^j$ также является образующим элементом $\iff \gcd(j, q - 1) = + 1$. Таким образом, всего имеется $\varphi(q - 1)$ различных образующих + элементов $\FF^*_q$, где $\varphi$ --- функция Эйлера. +\end{theorem} + +\begin{theorem}[Единственность конечного поля порядка $q = p^f$] + Если $\FF_q$ --- поле из $q = p^f$ элементов, то каждый элемент удовлетворяет + уравнению $x^q - x = 0$, а $\FF_q$ --- это в точности множество корней этого + уравнения. + + Обратно, для каждой степени простого числа $q = p^f$ поле разложения над + $\FF_p$ многочлена $x^q - x$ является полем из $q$ элементов. +\end{theorem} + +Пусть $K$ --- расширение степени $n$ конечного поля $F = \FF_p$. \emph{След +элемента $x \in K$} в поле $F$ определяется как сумма +\begin{equation*} + Tr(x) = x + x^p + \dots + x^{p^{n - 1}} +\end{equation*} + +\begin{theorem}[След элемента] + След $Tr$ является гомоморфизмом аддитивных групп $K \to F$. +\end{theorem} + +%% NOTE: 9 +\paragraph{Логарифмирование.} + +Наличие в конечном поле примитивного элемента $a$ позволяет ввести понятие +логарифма для ненулевых элементов этого поля. Пусть $G$ --- конечная +мультипликативная группа. \emph{Задача дискретного логарифмирования} состоит в +решении при заданных $a, b \in G$ уравнения \[a^x = b\] относительно целого $x$, +$0 \leq x < n = \text{ord } a$. + +Решение $x$ называется \emph{дискретным логарифмом}, или \emph{индексом}, $b$ +по основанию $a$ и обозначается $\text{ind}_a b$. + +\emph{Примечание} --- Когда групповая операция в $G$ записывается аддитивно, то +рассматривается уравнение $xa = b$. + +По сути, \emph{эллиптическая кривая над конечным полем} --- это конечная абелева +группа, в которой можно ставить задачу о вычислении дискретных логарифмов. + +\subsection{Введение в эллиптические кривые} + +\paragraph{Аффинные алгебраические многообразия, проективная плоскость.} + +Пусть $F$ --- поле, $F^*$ --- множество обратимых элементов поля $F$. + +\emph{Аффинным $n$-мерным пространством $A^n(F)$} над $F$ называется множество +точек \[\set{P = (x_1, \dots, x_n)} \in F^n\] значения $x_1, \dots, x_n$ +называются \emph{аффинными координатами}. + +\emph{Аффинное алгебраическое многообразие (множество) $V$} --- это подмножество +аффинного пространства, на котором обращаются в нуль полиномы $f_1, \dots, f_k +\in F[x_1, \dots, x_n]$: +\begin{equation*} + V = \set{P \in F^n | f_1(P) = 0, \dots, f_k(P) = 0} +\end{equation*} + +В случае $n = 2$ аффинное пространство называется \emph{аффинной плоскостью}, а +алгебраическое многообразие, идеал которого образован одиночным полиномом, --- +(плоской) \emph{алгебраической кривой}. + +Степень полинома, задающего кривую, называется \emph{степенью кривой}. + +\emph{Неприводимая алгебраическая кривая} задаётся неприводимым (над алгебраическим +замыканием $\overline{F}$ поля $F$) полиномом из кольца $F[x, y]$. + +\begin{example} + Алгебраическая кривая, заданная полиномом + \begin{equation*} + f(x, y) = (xy + 1)(x^2 + y^2 + 1) + \end{equation*} + + Полином $f(x, y)$ раскладывается на множители, поэтому алгебраическая кривая + является объединением кривых + \begin{equation*} + xy + 1 = 0 \land x^2 + y^2 + 1 = 0 + \end{equation*} + + Вместо этой кривой можно рассмотреть две более простых алгебраических кривых, + задаваемых неразложимыми делителями левой части уравнения. Таким образом, + изучение алгебраической кривой сводится к изучению её подмножеств, задаваемых + нулями неприводимых полиномов. +\end{example} + +Алгебраическую кривую $E$, заданную уравнением с коэффициентами из поля $F$, +будем обозначать $E/F$; алгебраическую кривую, точки которой лежат в $F^2$, +будем обозначать $E(F)$. + +Даже если уравнение $f(x, y) = 0$, задающее кривую $E$, имеет коэффициенты +из простого поля $F$, множество решений этого уравнения (и, соответственно, +множество точек кривой) может рассматриваться над расширением поля $F$, +например, над его алгебраическим замыканием. + +\emph{Аффинная прямая $A^1(F)$} над полем $F$ представляет собой поле $F$. + +\emph{Проективной прямой $P^1(F)$} над полем $F$ называется множество пар +\begin{equation*} + \set{X, Y} \in F^2 \backslash (0, 0) +\end{equation*} +с эквивалентностью $(X, Y) \equiv (aX, aY)$, если $a \in F^*$. + +Если $Y \neq 0$, то каждая точка $(X, Y) \in P^1(F)$ эквивалентна точке $(x, +1)$ аффинной прямой: просто полагаем $x = X / Y$. Но на проективной прямой есть +точка вида $(X, 0)$, соответствующая аффинной точке. + +Эта точка $P_\infty$ называется \emph{бесконечно удалённой}. Поэтому +\begin{equation*} + P^1(F) = A^1(F) \cup \set{P_\infty} +\end{equation*} + +\emph{Проективной плоскостью} $P^2(F)$ над полем $F$ называется множеством троек +\begin{equation*} + \set{X, Y, Z} \in F^3 \backslash (0, 0, 0) +\end{equation*} +с эквивалентностью $(X, Y, Z) \equiv (aX, aY, aZ)$, если $a \in F^*$. Здесь +$X, Y, Z$ --- проективные координаты. + +Свяжем аффинную плоскость с проективной. Полагая +\begin{equation*} + x = \frac{X}{Z}, y = \frac{Y}{Z}, Z \neq 0, +\end{equation*} +получаем биекцию между множеством точек $(x, y)$ аффинной плоскости и +подмножеством точек $(x, y, 1)$ проективной плоскости. + +Однако на проективной плоскости есть точки с нулевой $Z$-координатой, которые не +соответствуют никаким точкам аффинной плоскости. + +Тем самым проективную плоскость можно представить как объединение всех точек +$(x, y)$ обычной (<<аффинной>>) плоскости с точками, для которых $Z = 0$. diff --git a/crypto-algebra/lectures/lecture7.tex b/crypto-algebra/lectures/lecture7.tex new file mode 100644 index 0000000..a618f56 --- /dev/null +++ b/crypto-algebra/lectures/lecture7.tex @@ -0,0 +1,186 @@ +% Лекция 7 (09.10.23) + +\paragraph{Нормальные формы эллиптической кривой, дискриминант и $j$-инвариант.} + +\emph{Эллиптическая кривая} --- это пара $(E, P_\infty)$, где $E$ --- гладкая +кубическая кривая и $P_\infty \in E$. Существуют наиболее употребительные +(нормальные) формы уравнения эллиптической кривой, получаемые линейной заменой +переменных. Большинство из них являются частными случаями \emph{обобщённой +формы Вейерштрасса}, содержащей единственную бесконечно удалённую точку, которая +является точной перегиба, а бесконечно удалённая прямая является касательной в +этой точке. + +\emph{Эллиптическая кривая} $E$ записывается \emph{уравнением Вейерштрасса} вида +\begin{equation} + y^2 + a_1 x y + a_3 y = x^3 + a_2 x^2 + a_4 x + a_6 + \label{eq:weierstrass} +\end{equation} + +Если $a_1, a_2, a_3, a_4, a_6 \in F$, то говорят, что $E$ определена над $F$. + +%% TODO: Примечание +Заметим, что в уравнении (\ref{eq:weierstrass}) нет коэффициента $a_5$. Это +объясняется тем, что индексы коэффициентов имеют следующий смысл. Видим, что +$y = x^\frac{3}{2} + o(x)$. Сделав замену +\begin{equation*} + \begin{cases} + x = t^2 + o(t) \\ + y = t^2 + o(t) + \end{cases} +\end{equation*} +можно переписать (\ref{eq:weierstrass}) в виде +\begin{equation*} + t^6 + a_1 t^5 + a_3 t^3 = t^6 + a_2 t^4 + a_4 t^2 + a_6 +\end{equation*} +%% END + +Для обозначения эллиптической кривой используют запись $E$ или $E/F$, чтобы +подчеркнуть, что кривая определена над $F$. + +Точки, лежащие на эллиптической кривой, являются решениями $(x, y) \in F^2$ +уравнения (\ref{eq:weierstrass}) (это так называемые \emph{аффинные точки}); +единственную, лежащую на $E$ (в проективной плоскости), точку на бесконечности, +в дальнейшем будем обозначать $\mathcal{O}$. + +Если $K$ --- некоторое расширение поля $F$, то $E(K)$ обозначает множество +точек $(x, y) \in K^2$, которые удовлетворяют (\ref{eq:weierstrass}), их +называют $K$-рациональными вместе с точкой $\mathcal{O}$ + +Для того, чтобы кривая (\ref{eq:weierstrass}) была эллиптической, она +должна быть гладкой. Это означает, что не существует подходящих $(x, y) +\in E(\overline{F})$, где $\overline{F}$ --- алгебраической замыкание $F$, +удовлетворяющих двум уравнениям +\begin{align*} + a_1 y &= 3x^2 + 2a_2 x + a_4, \\ + 2y + a_1 x + a_3 &= 0. +\end{align*} + +\emph{Дискриминантом} уравнения Вейерштрасса является величина +\begin{equation*} + \Delta = -b_2^2 b_8 - 8 b_4^3 - 27 b_6^2 + 9 b_2 b_4 b_6, +\end{equation*} +где +\begin{align*} + b_2 &= a_1^2 + 4 a_2, \\ + b_4 &= 2 a_4 + a_1 a_3, \\ + b_6 &= a_3^2 + 4 a_6, \\ + b_8 &= a_1^2 a_6 + 4 a_2 a_6 - a_1 a_3 a_4 + a_2 a_3^2 - a_4^2. \\ +\end{align*} + +В случае $\Delta \neq 0$ $j$-инвариантом эллиптической кривой $F$ называется +величина +\begin{equation*} + j(E) = \frac{c_4^3}{\Delta}, +\end{equation*} +где $c_4 = b_2^2 - 24 b_4$. + +%% TODO: теорема 20 +\begin{theorem}[Критерий гладкости кривой, заданной уравнением Вейерштрасса] + Кривая $E$, заданная уравнением Вейерштрасса (\ref{eq:weierstrass}), гладкая + $\iff \Delta(E) \neq 0$. +\end{theorem} + +Будем рассматривать только гладкие кубические кривые. Две эллиптические кривые +$E$ и $\widetilde{E}$ над полем $F$, заданные уравнениями +%% TODO: дописать + +Эллиптические кривые, заданные над полем $F$, могут быть не изоморфными над +этим полем, но могут стать изоморфными над расширением. + +\begin{theorem}[Критерий изоморфности эллиптических кривых] %% NOTE: 21 + Две эллиптические кривые $E_1$ и $E_2$ изоморфны над $\overline{F} \iff + j(E_1) j(E_2)$. +\end{theorem} + +%% TODO: ссылка на уравнение (3) +Замена переменных (3) в уравнении (\ref{eq:weierstrass}) называется +\emph{допустимой}. Это преобразование обратимо и обратное преобразование также +допустимо. Кроме того, допустима тождественная замена переменных, поэтому +всякая эллиптическая кривая изоморфна сама себе. + +Композиция допустимых преобразований также является допустимой. Таким образом, +изоморфизм эллиптических кривых является отношением эквивалентности, и +множество эллиптических кривых разбивается на классы эквивалентных, причём +каждый класс эллиптических кривых, изоморфных над алгебраическим данного поля, +однозначно определяется величиной $j$-инварианта. + +\begin{theorem}[Об изоморфных эллиптических кривых над полем характеристики 2] + Всякая эллиптическая кривая над полем характеристики 2 изоморфны некоторой + эллиптической кривой одного из следующих видов: + \begin{equation} + y^2 + xy = x^3 + b_2 x^2 + b_6 + \label{eq:char2_1} + \end{equation} + или + \begin{equation} + y^2 + b_3 y = x^3 + b_4 x + b_6 + \label{eq:char2_2} + \end{equation} +\end{theorem} +\begin{proof} + Пусть $F$ --- поле характеристики 2, $E$ --- эллиптическая кривая, заданная + уравнением (\ref{eq:weierstrass}). + + Если $a_1 \neq 0$, то произведём в (\ref{eq:weierstrass}) замену переменных + \begin{equation*} + (x, y) \mapsto (a_1^2 x + a_1^{-1} a_3, a_1^3 y), + \end{equation*} + получим + \begin{align*} %% TODO: сделать красиво + &(a_1^3 y)^2 + a_1 (a_1^2 x + a_1^{-1} a_3) a_1^3 y + a_3 a_1^3 y = \\ + &= (a_1^2 x + a_1^{-1} a_3)^3 + a_2 (a_1^2 x + a_1^{-1} a_3)^2 + a_4 (a_1^2 x + + a_1^{-1} a_3) + a_6, \\ + &a_1^6 y^2 + a_1^6 xy + a_1^3 a_3 y + a_1^3 a_3 y = \\ + &= (a_1^4 x^2 + 2 a_1^2 x a_1^{-1} a_3 + a_1^{-2} a_3^2)(a_1^2 x + a_1^{-1} + a_3 + a_2) + a_1^2 a_4 x + a_1^{-1} a_4 a_3 + a_6,\\ + &a_1^6 y^2 + a_1^6 xy = \\ + &= a_1^6 x^3 + a_1^3 a_3 x^2 + a_1^4 a_2 x^2 + a_3^2 x + + a_1^{-3} a_3^3 + a_1^{-2} a_2 a_3^2 + a_1^2 a_4 x + a_1^{-1} a_4 a_3 + a_6,\\ + &a_1^6 y^2 + a_1^6 xy =\\ + &= a_1^6 x^3 + (a_1^3 a_3 + a_1^4 a_2) x^2 + (a_3^2 + a_1^2 a_4) x + + a_1^{-3} a_3^3 + a_1^{-2} a_2 a_3^2 + a_1^{-1} a_4 a_3 + a_6. + \end{align*} + + Получим, что данная замена переводит $E$ в кривую + \begin{equation} + y^2 + xy = x^3 + \widetilde{a}_2 x^2 + \widetilde{a}_4 x + \widetilde{a}_6 + \label{eq:char2_tmp1} + \end{equation} + + Произведём в (\ref{eq:char2_tmp1}) замену переменных $(x, y) \mapsto (x, y + + \widetilde{a}_4)$: + \begin{align*} + y^2 + \widetilde{a}_4^2 + xy &= x^3 + \widetilde{a}_2 x^2 + \widetilde{a}_6, \\ + y^2 + xy &= x^3 + \widetilde{a}_2 x^2 + (\widetilde{a}_6 - \widetilde{a}_4^2). + \end{align*} + + Получим, что данная замена переводит кривую (\ref{eq:char2_tmp1}) в кривую + (\ref{eq:char2_1}). + + Если $a_1 = 0$, то замена переменных $(x, y) \mapsto (x + a_2, y)$ переводит + $E$ в кривую вида (\ref{eq:char2_2}). +\end{proof} + +%% TODO: 23 +\begin{theorem}[Об изоморфных эллиптических кривых над полем характеристики $\neq 2$] + Всякая эллиптическая кривая над полем характеристики $\neq 2$ изоморфна + некоторой эллиптической кривой вида + \begin{equation} + y_2 = x^3 + b_2 x^2 + b_4 x + b_6. + \label{eq:isom_neq2} + \end{equation} +\end{theorem} +\begin{proof} + Пусть $F$ --- поле характеристики $\neq 2$, $E$ --- эллиптическая кривая, + заданная уравнением (\ref{eq:weierstrass}). + + Сделаем замену переменных + \begin{equation*} + (x, y) \mapsto (x, y - \frac{a_1}{2} x - \frac{a_3}{2}), + \end{equation*} + получим + %% TODO: дописать eq1 + + Таким образом, получили, что данная замена переводит кривую $E$ в кривую + (\ref{eq:isom_neq2}). +\end{proof} diff --git a/crypto-algebra/lectures/lecture8.tex b/crypto-algebra/lectures/lecture8.tex new file mode 100644 index 0000000..c7f1d0d --- /dev/null +++ b/crypto-algebra/lectures/lecture8.tex @@ -0,0 +1,191 @@ +% Лекция 8 (16.10.23) + +%% NOTE: 24? +\begin{theorem}[Об изоморфных эллиптических кривых над полем характеристики $> 3$] + Всякая эллиптическая кривая над полем характеристики $> 3$ изоморфна + эллиптической кривой вида + \begin{equation*} %% NOTE: 8 + y^2 = x^3 + ax + b + \end{equation*} +\end{theorem} +\begin{proof} + Пусть $F$ --- поле характеристики $> 3$, $E$ --- эллиптическая кривая, + заданная уравнением (2). Согласно теореме 23 данная кривая изоморфна кривой + (7). Тогда сделаем в (7) замену переменных + \begin{equation*} + (x, y) \mapsto (x - \frac{b_2}{3}, y), + \end{equation*} + получим + %% TODO: дописать eq1 + \begin{align*} + y^2 &= \left(x - \frac{b_2}{3}\right)^3 + b_2 \left(x - \frac{b_2}{3}\right)^2 + + b_4 \left(x - \frac{b_2}{3}\right) + b_6, \\ + y^2 &= x^3 - b_2 x^2 + \frac{b_2^2}{3}x - \frac{b_2^3}{27} + b_2 + \left(x^2 - \frac{2b_2}{3}x + \frac{b_2^2}{9}\right) + b_4 x - \frac{b_2 b_4}{3} + b_6, \\ + \dots + \end{align*} + + Таким образом, данная замена переводит кривую (7) в (8). +\end{proof} + +Для эллиптической кривой, заданной уравнением (8), формулы для дискриминанта и +$j$-инварианта принимают вид +\begin{align*} + \Delta &= -16 (4a^3 + 27b^2), \\ + j(E) &= -1728 \frac{64a^3}{\Delta} = 1728 \frac{4a^3}{4a^3 + 27b^2} +\end{align*} + +В уравнении левая сторона ($y^2$) имеет степень 2, в то время как правая сторона +имеет степень 3 ($x^3$). Это означает, что горизонтальная линия может пересекать +кривую в трёх точках, если все корни вещественные. Однако вертикальная линия +может пересечь кривую самое большее в двух точках. + +\begin{example} + На рисунке 14 показаны две эллиптические кривые с уравнениями + \begin{equation*} + y^2 = x^3 - 9x \land y^2 = x^3 - 1 \; (y^2 = (x - 1)(x^2 + x + 1)) + \end{equation*} + %% TODO: рисунок 1 (14) + + Таким образом, обе кривые гладкие. Однако первое имеет три вещественных корня + ($x = \pm 3, x = 0$), второе --- только один вещественные корень ($x = 1$) и + два мнимых ($x = \pm \frac{\sqrt{3} i - 1}{2}$; удовлетворяют уравнению + $x^2 + x + 1 = 0$). +\end{example} + +%% NOTE: 4 +\paragraph{Сложение точек эллиптической кривой.} + +Существует ряд эквивалентных способов для описания группового закона сложения +точек эллиптической кривой. Геометрически этот закон можно сформулировать +следующим образом: \emph{три коллинеарные точки на эллиптической кривой дают +нулевую сумму}. Операция сложения точек на эллиптической кривой, введённая по +данному правилу, превращает эллиптическую кривую в коммутативную группу. + +Далее будут рассмотрены формулы сложения точек эллиптической кривой, которые +вытекают из данного правила. В качестве нулевого элемента выбирается точка +$\mathcal{O}$ на бесконечности. Таким образом, для любой точки $P \in E$ +имеют место равенства +\begin{equation*} + P + \mathcal{O} = \mathcal{O} + P = P. +\end{equation*} + +Секущая, проходящая через бесконечно удалённую точку $\mathcal{O}$ и данную +точку кривой $P$, является вертикальной прямой. + +Пусть $P \ne \mathcal{O}$ --- точка эллиптической кривой $E$ и $l$ --- +вертикальная прямая, проходящая через точку $P = (x_1, y_1)$. Эта прямая +пересекает $E$ ещё в точке $Q$ (с учётом кратности). Таким образом, $-P = Q$. + +Пусть $Q = (x_2, y_2)$. Так как она лежит на вертикальной прямой $l$, то +$x_1 = x_2$. Тогда $y_2$ является решением уравнения +\begin{equation} %% NOTE: 9 + y^2 + f_1(x_1) y - f_3(x_1) = 0, + \label{eq:9} +\end{equation} +где $f_1(x) = a_1 x + a_3$, $f_3(x) = x^3 + a_2 x^2 + a_4 x + a_6$. + +Уравнение (\ref{eq:9}) имеет два корня $y_1$ и $y_2$. По теореме Виета +\begin{equation*} + y_1 + y_2 = -f_1(x_1), +\end{equation*} +откуда получаем +\begin{equation*} + y_2 = -y_1 - f_1(x_1). +\end{equation*} + +Итак, +\begin{equation} + -(x_1, y_1) = (x_1, -y_1 - a_1 x_1 - a_3). + \label{eq:10} +\end{equation} + +Может оказаться, что $y_2 = y_1$ и, соответственно, $-P = P$. Это возможно, если +вертикальная прямая, проходящая через $P$, касается кривой $E$ в точке $P$. + +Рассмотрим, как вычисляется сумма двух различных точек $P_1 = (x_1, y_1)$ и +$P_2 = (x_2, y_2)$ на эллиптической кривой. Предположим, что $P_1, P_2 \neq +\mathcal{O}$ и $P_1 \neq \pm P_2$. Тогда $x_1 \neq x_2$. Пусть $l$ --- прямая, +проходящая через точки $P_1$ и $P_2$. Уравнение $l$ имеет вид +\begin{equation} + y = \alpha x + \beta. + \label{eq:11} +\end{equation} + +Коэффициенты $\alpha$ и $\beta$ --- решения системы. +\begin{equation*} + \begin{cases} + y_1 = \alpha x_1 + \beta, \\ + y_2 = \alpha x_2 + \beta. + \end{cases} +\end{equation*} + +Тогда +\begin{align*} + \alpha &= \frac{y_1 - y_2}{x_1 - x_2}, \\ + \beta &= y_1 - \alpha x_1 = y_2 - \alpha x_2. +\end{align*} + +Прямая $l$ пересекает эллиптическую кривую $E$ в некоторой третьей точке +$Q = -(P_1 + P_2) = (\widetilde{x_3}, \widetilde{y_3})$. + +Подставляя (\ref{eq:11}) в уравнение Вейерштрасса, получаем +\begin{equation*} + (\alpha x + \beta)^2 + (\alpha x + \beta) (a_1 x + a_3) - (x^3 + a_2 x^2 + + a_4 x + a_6) = 0. +\end{equation*} + +Кубическое уравнение +\begin{equation*} + -x^3 + (\alpha^2 + a_1 \alpha - a_2) x^2 + (2 \alpha \beta + a_3 \alpha + a_1 + \beta - a_4) x + (\beta^2 + a_3 \beta - a_6) = 0 +\end{equation*} +имеет три корня: $x_1, x_2, \widetilde{x_3}$. + +По теореме Виета +\begin{equation*} + x_1 + x_2 + \widetilde{x_3} = \alpha^2 + a_1 \alpha - a_2. +\end{equation*} + +Таким образом, +\begin{equation*} + \begin{cases} + \widetilde{x_3} = -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2, \\ + \widetilde{y_3} = \alpha \widetilde{x_3} + \beta = (y_1 - \alpha x_1) + + \alpha \widetilde{x_3} = y_1 - \alpha(x_1 - \widetilde{x_3}) + \end{cases} +\end{equation*} + +Получаем, $P_1 + P_2 = -Q = -(\widetilde{x_3}, \widetilde{y_3})$, используя +(\ref{eq:10}), находим +\begin{equation*} + P_1 + P_2 = (x_3, y_3), +\end{equation*} +где +\begin{equation} + \begin{cases} + x_3 = -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2, \\ + y_3 = -y_1 + \alpha (x_1 - x_3) - a_1 x_3 - a_3. + \end{cases} +\end{equation} + +\begin{example} + На рисунке 15 представлен типичный случай сложения точек $P_1$ и $P_2$. Чтобы + найти $P_1 + P_2$, проводим прямую $\overline{P_1 P_2}$ и в качестве $P_1 + P_2$ + берём точку, симметричную относительно оси $x$ третьей точке, определяемой + пересечением прямой $\overline{P_1 P_2}$ и кривой. + + %% TODO: рис 2 (15) +\end{example} + +Найдём правило вычисления удвоенной точки $P + P$. Будем предполагать, что +$P \neq -P$. Чтобы найти $P + P$, проведём касательную через точку $P$. Эта +прямая задаётся уравнением (\ref{eq:11}). + +Для нахождения углового коэффициента касательной $\alpha$ нужно найти полнй +дифференциал от полинома $f(x, y)$, задающего кривую в форме Вейерштрасса +(2). Получим +\begin{equation} %% TODO: другое \delta + df(x, y) = \frac{\partial f}{\partial x} dx + \frac{\partial f}{\partial y} dy. +\end{equation} + diff --git a/crypto-algebra/lectures/lecture9.tex b/crypto-algebra/lectures/lecture9.tex new file mode 100644 index 0000000..1077224 --- /dev/null +++ b/crypto-algebra/lectures/lecture9.tex @@ -0,0 +1,204 @@ +% Лекция 9 (23.10.23) + +Угловой коэффициент касательной равен +\begin{equation*} + \alpha = \frac{dy}{dx} +\end{equation*} + +Имеем $f'_x dx = -f'_y dy,\, \frac{dy}{dx} = -\frac{f'_x}{f'_y}$. + +Поэтому угловой коэффициент касательной равен +\begin{equation} + \alpha = \frac{3 x_1^2 + 2 a_2 x_1 + a_4 - a_1 y_1}{2 y_1 + a_1 x_1 + a_3} + \label{eq:13} +\end{equation} + +Таким образом, удвоенная точка также вычисляется по формулам (\ref{eq:12}), +но с $\alpha$, найденным по (\ref{eq:13}). + +\begin{example} + Рассмотрим эллиптическую кривую $y^2 = x^3 - 12x$. + + Пусть $x_1 = x_2 = 6$, тогда $y_1 = y_2 = 12$. + + \begin{align*} + \alpha &= \frac{3 x_1^2 + 2 a_2 x_1 + a_4 - a_1 y_1}{2 y_1 + a_1 x_1 + a_3} + = \frac{3 \cdot 6^2 - 12}{2 \cdot 12} = 4 \\ + \beta &= y_1 - \alpha x_1 = 12 - 4 \cdot 6 = -12 + \end{align*} + + Таким образом, касательная, проходящая через точку $P_1 = P_2 = (6, 12)$ + имеет вид $y = 4x - 12$. + + В результате $P_1 + P_2 = 2 P_1 = P_3 = (x_3, y_3)$, где + \begin{align*} + x_3 &= -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2 = -6 - 6 + 4^2 = 4 \\ + y_3 &= -y_1 + \alpha (x_1 - x_3) - a_1 x_3 - a_3 = -12 + 4 (6 - 4) = -4 + \end{align*} + + %% TODO: рис 1 +\end{example} + +%% TODO: рис 2 + +\begin{theorem}[Группа точек эллиптической кривой] + Пусть $F$ --- поле, $E/F$ --- эллиптическая кривая. Тогда для любого + расширения $K$ поля $F$ относительно введённой выше операции <<$+$>> множество + $E(K)$ образует абелеву группу. Операция сложения задаётся по следующим + правилам: + \begin{enumerate} + \item + для любой точки $P \in E$ верно $P + \mathcal{O} = \mathcal{O} + P = P$; + \item + для любой точки $P = (x, y) \neq \mathcal{O}$ точка $-P$ находится по + формуле \[ -P = (x, -y - a_1 x - a_3); \] + \item + для любых точек $P_1 = (x_1, y_1) \neq \mathcal{O}$, $P_2 = (x_2, y_2) + \neq \mathcal{O}$ сумма точек $P_1 + P_2 = P_3 = (x_3, y_3)$ задаётся + следующими формулами: + \begin{enumerate} + \item если $P_2 = -P_1$, то $P_3 = \mathcal{O}$; + \item если $P_2 \neq -P_1$, то + \begin{equation} + \begin{cases} + \alpha = \begin{cases} + \frac{3x_1^2 + 2a_2 x_1 + a_4 - a_1 y_1}{2y_1 + a_1 x_1 + a_3}, + &\text{если } x_1 = x_2, \\ + \frac{y_1 - y_2}{x_1 - x_2}, &\text{если } x_1 \neq x_2, + \end{cases} \\ + x_3 = -x_1 - x_2 + \alpha^2 + a_1 \alpha - a_2, \\ + y_3 = -y_1 + \alpha (x_1 - x_3) - a_1 x_3 - a_3. + \end{cases} + \label{eq:14} + \end{equation} + \end{enumerate} + \end{enumerate} +\end{theorem} + +\begin{corollary}[Об операции сложения в группе точек эллиптической кривой над + полем характеристики $> 3$] + Для кривой, заданной уравнением (\ref{eq:8}), формулы (\ref{eq:14}) принимают + упрощённый вид: + \begin{equation} + \begin{cases} + \alpha = \begin{cases} + \frac{3 x_1^2 + a}{2y_1}, &\text{если } x_1 = x_2, \\ + \frac{y_1 - y_2}{x_1 - x_2}, &\text{если } x_1 \neq x_2, + \end{cases} \\ + x_3 = -x_1 - x_2 + \alpha^2, \\ + y_3 = -y_1 + \alpha (x_1 - x_3). + \end{cases} + \label{eq:15} + \end{equation} + Кроме того, противоположная к $P = (x, y)$ точка равна $-P = (x, -y)$. + + Порядком точки $P$ на эллиптической кривой называется такое наименьшее + натуральное число $N$, что $NP = \mathcal{O}$. +\end{corollary} + +Такого конечного $N$ может не существовать. Часто требуется найти точки +конечного порядка на эллиптической кривой. + +\begin{example} + Найти порядок точки $P = (0, -3)$ на эллиптической кривой $y^2 = x^3 + 9$. + + Применяя (\ref{eq:15}), находим, что $2P = (0, 3)$, получаем $2P = -P$, откуда + $3P - \mathcal{O}$. Итак, $P$ имеет порядок 3. +\end{example} + +\emph{Гиперэллиптической кривой} над полем $F$ называется аффинная кривая, +задаваемая уравнением $y^2 + h(x) y = f(x)$ и не имеющая особых точек +на аффинной плоскости над $\overline{F}$, где $h$, $f$ --- полиномы с +коэффициентами из $F$, $\deg(f) = 2g + 1$, $\deg(h) \leq g$. + +Натуральное число $g$ называется \emph{родом кривой}. Эллиптическую кривую +можно рассматривать как гиперэллиптическую кривую рода 1. + +Алгебраическая формула (\ref{eq:14}) для сложения точек на эллиптической +кривой имеет смысл над любым полем. + +\paragraph{Изогении.} + +Пусть $E_1$ и $E_2$ --- эллиптические кривые. \emph{Изогенией} из $E_1$ в +$E_2$ называется морфизм $\varphi : E_1 \to E_2$, удовлетворяющий условию +$\varphi(\mathcal{O}) = \mathcal{O}$. Две эллиптические кривые $E_1$ и $E_2$ +\emph{изогенны}, если существует изогения из $E_1$ до $E_2$ с $\varphi(E_1) \neq +\set{\mathcal{O}}$. + +Изогения эллиптических кривых является отношением эквивалентности. + +Эллиптические кривые являются абелевыми группами, поэтому отображения между +ними образуют группы. Обозначим множество изогений из $E_1$ в $E_2$ через +\begin{equation*} + \fn{Hom}(E_1, E_2) = \set{\text{изогении } E_1 \to E_2} +\end{equation*} + +Сумма двух изогений определяется формулой +\begin{equation*} + (\varphi + \psi)(P) = \varphi(P) + \psi(P), +\end{equation*} +также $\varphi + \psi$ --- морфизм, поэтому это изогения. + +Следовательно, $\fn{Hom}(E_1, E_2)$ --- группа. Если $E_1 = E_2$, то можно также +составить изогении. Таким образом, если $E$ --- эллиптическая кривая, то +\begin{equation*} + \fn{End}(E) = \fn{Hom}(E, E) +\end{equation*} +является кольцом, закот сложения которого указан выше, а умножение --- это +композиция +\begin{equation*} + (\varphi \psi)(P) \equiv \varphi(\psi(P)). +\end{equation*} + +Также имеет место дистрибутивный закон. Кольцо $\fn{End}(E)$ называется +\emph{кольцом эндоморфизмов} эллиптической кривой $E$. + +Обратимые элементы кольца $\fn{End}(E)$ образуют группу автоморфизмов $E$ +которая обозначается $\fn{Aut}(E)$. + +\begin{example} + Для каждого $m \in \Z$, изогения умножения на $m$ обозначается + \begin{align*} + [m] &: E \to E \\ + [m]P &= \underbrace{P + P + \dots + P}_m + \end{align*} + при $m < 0$ полагают $[m]P = [-m](-P)$ и $[0]P = \mathcal{O}$. + + $[m]$ --- морфизм, а значит, изогения, поскольку он явно переводит + $\mathcal{O}$ в $\mathcal{O}$. + + Пусть $E$ --- эллиптическая кривая, $m \in \Z, m \geq 1$. \emph{Подгруппа} + $m$-кручения $E$, обозначаемая $E[m]$, --- это множество точек $E$ порядка + $m$: + \begin{equation*} + E[m] = \set{P \in E : [m]P = \mathcal{O}}. + \end{equation*} + \emph{Подгруппа кручения $E$}, обозначаемая $E_{tors}$, представляет собой + множество точек конечного порядка: + \begin{equation*} + E_{tors} = \bigcup_{m = 1}^\infty E[m]. + \end{equation*} +\end{example} + +Если $E$ определено над $F$, то $E_{tors}(F)$ обозначает точки конечного порядка +в $E(F)$. Пусть $F$ --- поле характеристики $p > 0$, $q = p^r$ и $E/F$ --- +эллиптическая кривая, заданная уравнением Вейерштрасса (\ref{eq:2}). + +Кривая $E^{(q)}/f$ определяется возведением коэффициентов уравнения для $E$ в +степень $q$, морфизм Фробениуса $\varphi_q$ определяется как +\begin{equation*} + \varphi_q : E \to E^{(q)}, (x, y) \to (x^q, y^q) +\end{equation*} + +$E^{(q)}$ является гладкой эллиптической кривой, $\Delta(E^{(q)}) = \Delta(E)^q$ +и $j(E^{(q)}) = j(E)^q$. + +Так как $F$ --- конечное поле с $q$ элементами, тогда отображение $q$-й степени +на $F$ является тождественным, поэтому $E^{(q)} = E$ и $\varphi_q$ является +эндоморфизмом $E$, называемым \emph{эндоморфизмом Фробениуса}. + +Множество точек, зафиксированных $\varphi_q$, (точки с координатами из поля $F$ +остаются неподвижными) есть в точности конечная группа $E(\mathbb{F}_q)$. + +Этот факт лежит в основе доказательства теоремы Хассе об оценке количества +$\mathbb{F}_q$-рациональных точек эллиптической кривой $E$. diff --git a/security-models/lectures/lecture10.tex b/security-models/lectures/lecture10.tex new file mode 100644 index 0000000..3a0a0d7 --- /dev/null +++ b/security-models/lectures/lecture10.tex @@ -0,0 +1,131 @@ +% Лекция 10 (24.11.23) + +%% NOTE: 2.3 + +Устовия применения де-факто правил в исходном состоянии $G = (S, O, E \cup F)$ +и результаты их применения в результирующем состоянии $G' = (S, O, E \cup F')$ +приведены в таблице. + +%% TODO: таблица 1 - Де-факто правила расширенной модели Take-Grant + +\begin{table}[H] + \smallsize + \centering + \caption{} + \begin{tabular}{|c|p{6cm}|p{6cm}|} + \hline + Правило & + Исходное состояние $G = (S, O, E \cup F)$ & + Результирующее состояние $G' = (S, O, E \cup F')$ \\ \hline + + Первое правило & + $x \in S; y \in O; (x, y, r) \in E \cup F$ & + $F' = F \cup \set{(y, x, w), (x, y, r)}$ \\ \hline + + Второе правило & + $x \in S; y \in O; (x, y, w) \in E \cup F$ & + $F' = F \cup \set{(y, x, r), (x, y, w)}$ \\ \hline + + $\fn{spy}(x, y, z)$ & + $x, y \in S; x \neq z; \set{(x, y, r), (y, z, r)} \subset E \cup F$ & + $F' = F \cup \set{(x, z, r), (z, x, w)}$ \\ \hline + + $\fn{find}(x, y, z)$ & + $x, y \in S; z \in O; x \neq z; \set{(x, y, w), (y, z, w)} \subset E \cup F$ & + $F' = F \cup \set{(x, z, w), (z, x, r)}$ \\ \hline + + $\fn{post}(x, y, z)$ & + $x, z \in S; y \in O; x \neq z; \set{(x, y, r), (z, y, w)} \subset E \cup F$ & + $F' = F \cup \set{(x, z, r), (z, x, w)}$ \\ \hline + + $\fn{pass}(x, y, z)$ & + $y \in S; x, z \in O; x \neq z; \set{(y, x, w), (y, z, r)} \subset E \cup F$ & + $F' = F \cup \set{(x, z, r), (z, x, w)}$ \\ \hline + \end{tabular} +\end{table} + +Из определения де-факто правил следует, что для анализа информационных потоков +достаточно рассматривать потоки одного вида: либо на чтение, либо на запись. + +Будем рассматривать только информационные потоки на запись. Будем предполагать, +что при возникновении информационного потока не накладывается ограничений на +кооперацию субъектов системы, участвующих в этом процессе. + +Пусть $x, y \in O_0$, $x \neq y$, --- различные объекты графа доступов и +информационных потоков $G_0 = (S_0, O_0, E_0 \cup F_0)$. Определим предикат +$\fn{can_write}(x, y, G_0)$, который будет истинным $\iff$ $\exists$ графы $G_1 += (S_1, O_1, E_1 \cup F_1), \dots, G_N = (S_N, O_N, E_N \cup F_N)$ и де-юре +или де-факто правила $op_1, \dots, op_N$, где $N \geq 0$, такие, что $G_0 +\vdash_{op_1} G_1 \vdash_{op_2} \dots \vdash_{op_N} G_N$ и $(x, y, w) \subset +F_N$. + +%% NOTE: 2.8 +\begin{theorem} + Пусть $G_0 = (S_0, O_0, E_0 \cup F_0)$ --- граф доступов и информационных + потоков, $x, y \in O_0$, $x \neq y$. Тогда предикат $\fn{can_write}(x, y, G_0)$ + истинен $\iff$ существуют объекты $o_1, \dots, o_m \in O_0$, где $o_1 = x, + o_m = y$, такие, что или $m = 2$ и $(x, y, w) \in F_0$, или для $i = 1, \dots, + m - 1$ выполняется одно из трёх условий: + \begin{enumerate} + \item + $o_i \in S_0$ и или истинен предикат $\fn{can_share}(\set{w}, o_i, o_{i + + 1}, G_0)$, или $(o_i, o_{i + 1}, w) \in E_0 \cup F_0$; + \item + $o_{i + 1} \in S_0$ и или истинен предикат $\fn{can_share}(\set{r}, o_{i + + 1}, o_i, G_0)$, или $(o_{i + 1}, o_i, r) \in E_0 \cup F_0$; + \item + $o_i, o_{i + 1} \in S_0$ и или истинен предикат $\fn{can_share}(\alpha, + o_i, o_{i + 1}, G_0)$, или истинен предикат $\fn{cna_share}(\alpha, o_{i + + 1}, o_i, G_0)$, где $\alpha \in \set{t, g}$, или существует объект + $o_i' \in O_0$ такой, что либо истинны предикаты $\fn{can_share}(\set{t}, + o_i, o_i', G_0)$, $\fn{can_share}(\set{g}, o_{i + 1}, o_i', G_0)$, + либо истинны предикаты $\fn{can_share}(\set{g}, o_i, o_i', G_0)$, + $\fn{can_share}(\set{t}, o_{i + 1}, o_i', G_0)$. + \end{enumerate} + + \label{thm:2.8} +\end{theorem} + +\paragraph{Алгоритм построения замыкания графа доступов и информационных потоков.} + +Для проверки истинности предиката $\fn{can_share}(\alpha, x, y, G_0)$ или +$\fn{can_write}(x, y, G_0)$ для многих пар вершин неэффективно использовать +алгоритмы проверки условий теорем \ref{thm:2.6}, \ref{thm:2.8}. + +Эффективнее применять алгоритмы, позволяющие осуществлять проверку истинности +данных предикатов сразу для всех пар вершин. Такие алгоритмы реализуют +преобразование графа доступов и информационных потоков в его замыкание. + +Пусть $G = (S, O, E \cup F)$ --- граф доступов и информационных потоков такой, +что для каждого субъекта $s \in S$ существует объект $o \in O$ такой, что +выполняется условие $(s, o, \set{t, g, r, w}) \in E$. + +\emph{Замыканием} (или \emph{де-факто замыканием}) графа $G$ называется граф +доступов и информационных потоков $G^* = (S, O, E^* \cup F^*)$, полученный из +$G$ применением последовательности правил take, grant и де-факто правил. При +этом применение к графу $G^*$ указанных правил не приводит к появлению в нём +новых дуг. + +$tg$-замыканием графа $G$ называется граф доступов и информационных +потоков $G^{tg} = (S, O, E^{tg} \cup F)$, полученный из $G$ применением +последовательности правил take или grant. + +При этом каждое ребро $(o_1, o_2, \alpha) \in E^{tg} - E$ имеет вид $(o_1, o_2, +t)$ или $(o_1, o_2, g)$, и применение к графу $G^{tg}$ правил take или grant не +приводит к появлению в нём новых дуг указанного вида. + +\emph{Де-юре замыканием} графа $G$ называется граф доступов и информационных +потоков $G^\text{де-юре} = (S, O, E^\text{де-юре} \cup F)$, полученный из $G$ +применением последовательности правил take или grant. При этом применение в +графу $G^\text{де-юре}$ правил take или grant не приводит к появлению в нём +новых дуг. + +Алгоритм построения замыкания графа доступов состоит из трёх этапов: +\begin{enumerate} + \item построение $tg$-замыкания; + \item построение де-юре-замыкания; + \item построение замыкания. +\end{enumerate} + +Алгоритм построения $tg$-замыкания графа доступов и информационных потоков +$G = (S, O, E \cup F)$. diff --git a/security-models/lectures/lecture12.tex b/security-models/lectures/lecture12.tex new file mode 100644 index 0000000..8aad472 --- /dev/null +++ b/security-models/lectures/lecture12.tex @@ -0,0 +1,218 @@ +% Лекция 12 (04/08.12.23) + +%% NOTE: 3.1 +% \subsection{Модель Белла-ЛаПадулы} + +$M = \set{m_{|S| \times |O|}}$ --- множество возможных матриц доступов, где +$m_{|S| \times |O|}$ --- матрица доступов, $m[s, o] \subseteq R$ --- права +доступа субъекта $s$ к объекту $o$; + +$(f_s, f_o, f_c) \in F = L^S \times L^O \times L^S$ --- тройка функций +%% TODO: дописать + +\begin{itemize} + \item $V = B \times M \times F$ --- множество состояний системы; + \item $Q$ --- множество запросов системе; + \item + $D$ --- множество ответов по запросам, например, $D = \set{yes, no, error}$; + \item + $W \subseteq Q \times D \times V \times V$ --- множество действий системы, + где $(q, d, v^*, v) \in W$, означает, что системы по запросу $q$ с ответом + $d$ перешла из состояния $v$ в состояние $v^*$; + \item + $\NN_0 = \set{0, 1, 2, \dots}$ --- множество значений времени; + \item + $X$ --- множество функций $x : \NN_0 \to Q$, задающих все возможные + последовательности запросов к системе; + \item + $Y$ --- множество функций $y : \NN_0 \to D$, задающих все возможные + последовательности ответов системы по запросам; + \item + $Z$ --- множество функций $z : \NN_0 \to V$, задающих все возможные + последовательности состояний системы. +\end{itemize} + +$\Sigma (Q, D, W, z_0) \subseteq X \times Y \times Z$ называется \emph{системой}, +когда для каждого $(x, y, z) \in \Sigma (Q, D, W, z_0)$ выполняется условие: +для $t \in \NN_0 \; (x_t, y_t, z_{t + 1}, z_t) \in W$, где $z_0$ --- начальное +состояние системы. + +При этом каждый набор $(x, y, z) \in \Sigma (Q, D, W, z_0)$ называется +\emph{реализацией} системы, а $(x_t, y_t, z_{t + 1}, z_t) \in W$ --- +\emph{действием} системы в момент времени $t \in \NN_0$. + +В классической модели Белла-ЛаПадулы рассматриваются следующие запросы, входящие +в множество $Q$: +\begin{enumerate} + \item запросы изменения множества текущих доступов $b$; + \item запросы изменения функций $f$; + \item запросы изменения прав доступа в матрице $m$. +\end{enumerate} + +Следующий список описывает изменения каждого элемента состояния системы. +Конкретное решение по запросу включает возможность производить следующие +изменения в состоянии системы. +\begin{enumerate} + \item + Изменение текущих доступов: + \begin{enumerate} + \item + получить доступ (добавить тройку (субъект, объект, вид доступа) в + текущее множество доступов $b$); + \item + отменить доступ (удалить аналогично). + \end{enumerate} + \item + Изменение значений функций уровней конфиденциальности и доступа: + \begin{enumerate} + \item изменить уровень конфиденциальности объекта; + \item изменить уровень доступа субъекта. + \end{enumerate} + \item + Изменение прав доступа: + \begin{enumerate} + \item + дать разрешение на доступ (добавить право доступа в соответствующий + элемент матрицы доступов $m$); + \item + отменить разрешение на доступ (удалить аналогично). + \end{enumerate} +\end{enumerate} + +Безопасность системы определяется с помощью трёх свойств: +\begin{itemize} + \item + ss --- свойства простой безопасности (simple security, безопасность по + чтению); + \item + * --- свойства <<звезда>> (безопасность по записи); + \item + ds --- свойства дискреционной безопасности (discretionary security, + безопасность (разрешённость) по матрице доступа). +\end{itemize} + +Доступ $(s, o, r) \in S \times O \times R$ обладает ss-свойством относительно +$f = (f_s, f_o, f_c) \in F$, когда выполняется одно из условий: +\begin{enumerate} + \item $r \in \set{execute, append}$; + \item $r \in {read, write} \land f_s(s) \geq f_o(o)$. +\end{enumerate} + +Состояние системы $(b, m, f) \in V$ обладает ss-свойством, когда каждый элемент +$(s, o, r) \in b$ обладает ss-свойством относительно $f$. + +Доступ $(s, o, r) \in S \times O \times R$ обладает *-свойством относительно +$f = (f_s, f_o, f_c) \in F$, когда выполняется одно из условий: +\begin{enumerate} + \item $r = execute$; + \item $r = append \land f_o(o) \geq f_c(s)$; + \item $r = read \land f_c(s) \geq f_o(o)$; + \item $r = write \land f_c(s) = f_o(o)$. +\end{enumerate} + +Состояние системы $(b, m, f) \in V$ обладает *-свойством, когда каждый элемент +$(s, o, r) \in b$ обладает *-свойством относительно $f$. + +Состояние системы $(b, m, f) \in V$ обладает *-свойством относительно +подмножества $S' \subseteq S$, когда каждый элемент $(s, o, r) \in b$, где +$s \in S'$, обладает *-свойством относительно $f$. + +При этом $S \backslash S'$ называется \emph{множеством доверенных субъектов}, +то есть субъектов, имеющих право нарушать требования *-свойства. + +Состояние системы $(b, m, f) \in V$ обладает ds-свойством, когда для каждого +доступа $(s, o, r) \in b$ выполняется условие $r \in m[s, o]$. + +Состояние системы $(b, m, f)$ называется \emph{безопасным}, когда оно обладает +*-свойством относительно $S'$, ss-свойством и ds-свойством. + +Реализация системы $(x, y, z) \in \Sigma (Q, D, W, z_0)$ обладает ss-свойством +(*-свойством, ds-свойством), когда в последовательности $(z_0, z_1, \dots)$ +каждое состояние обладает ss-свойством (*-свойством, ds-свойством). + +Система $\Sigma (Q, D, W, z_0)$ обладает ss-свойством (*-свойством, ds-свойством), +когда каждая её реализация обладает ss-свойством (*-свойством, ds-свойством). + +Система $\Sigma (Q, D, W, z_0)$ нащывается \emph{безопасной}, когда она обладает +ss-свойством, *-свойством, ds-свойством одновременно. + +Описанные свойства можно пояснить следующим образом: +\begin{enumerate} + \item + из обладания доступом *-свойством относительно $f$ следует обладание этим + доступом ss-свойством относительно $f$; + \item + из обладания ss-свойством следует, что в модели Белла-ЛаПадулы выполняется + запрет на чтение вверх, требуемый мандатной политикой безопасности. + + Кроме того, ss-свойство не допускает модификацию с использованием доступа + write, когда $f_s(s) < f_o(o)$. + + Таким образом, функция $f_s(s)$ задаёт для субъекта $s$ верхний уровень + конфиденциальности объектов, к которым он потенциально может получить доступ + read или write; + \item + если субъект $s$ может понизить свой текущий уровень доступа до $f_c(s) = + f_o(o)$, то он может получить доступ write к объекту $o$, но не доступ + read к объектам $o'$, чей уровень $f_o(o') > f_c(s)$. + + Хотя при этом, возможно, справедливо неравенство $f_s(s) \geq f_o(o')$, и + в каких-то других состояниях системы субъект $s$ может получить доступ + read к объекту $o'$. + + Таким образом, *-свойство исключает появление в системе запрещённого + информационного потока <<сверху вниз>> и соответствует требованиям мандатной + политики безопасности (см. рис. 3.1). + + %% TODO: рис 1 (3.1): Иллюстрация *-свойства +\end{enumerate} + +%% NOTE: 3.1 +\begin{theorem} + Система $\Sigma(Q, D, W, z_0)$ обладает ss-свойством для любого начального + состояния $z_0$, обладающего ss-свойством $\iff$ для каждого действия + $(q, d, (b^*, m^*, f^*), (b, m, f)) \in W$ выполняется два условия: + \begin{enumerate} + \item + каждый доступ $(s, o, r) \in b^* \backshash b$ обладает ss-свойством + относительно $f^*$; + \item + если $(s, o, r) \in b$ и не обладает ss-свойством относительно $f^*$, + то $(s, o, r) \not\in b^*$. + \end{enumerate} +\end{theorem} + +\begin{theorem} + Система $\Sigma(Q, D, W, z_0)$ обладает *-свойством относительно $S' \subseteq S$ + для любого начального состояния $z_0$, обладающего *-свойством относительно + $S'$ $\iff$ для каждого действия $(q, d, (b^*, m^*, f^*), (b, m, f)) \in W$ + выполняются два условия: + \begin{enumerate} + \item + для $s \in S'$ доступ $(s, o, r) \in b^* \backslash b$ обладает *-свойством + относительно $f^*$; + \item + для $s \in S'$, если $(s, o, r) \in b$ и не обладает *-свойством + относительно $f^*$, то $(s, o, r) \not\in b^*$. + \end{enumerate} +\end{theorem} + +\begin{theorem} + Система $\Sigma(Q, D, W, z_0)$ обладает ds-свойством для любого начального + состояния $z_0$, обладающего ds-свойством $\iff$ для каждого действия + $(q, d, (b^*, m^*, f^*), (b, m, f)) \in W$ выполняется два условия: + \begin{enumerate} + \item + для каждого $(s, o, r) \in b^* \backslash b$ выполняется условие + $r \in m^*[s, o]$; + \item + если доступ $(s, o, r) \in b \land r \not\in m^*[s, o] \implies (s, o, r) + \not\in b^*$. + \end{enumerate} +\end{theorem} + +%% NOTE: 3.4 +\begin{theorem}[Базовая теорема безопасности] + Система $\Sigma(Q, D, W, z_0)$ безопасна для безопасного $z_0$ $\iff$ + множество действий системы $W$ удовлетворяет условиям теорем 3.1 -- 3.3. +\end{theorem} diff --git a/security-models/lectures/lecture4.tex b/security-models/lectures/lecture4.tex new file mode 100644 index 0000000..aefcb56 --- /dev/null +++ b/security-models/lectures/lecture4.tex @@ -0,0 +1,159 @@ +% Лекция 4 (13.10.23) + +\subsection{Модель типизированной матрицы доступов} + +Дискреционная модель, получившая название <<типизированная матрица доступов>> +(ТМД), представляет собой развитие модели ХРУ, дополненной концепцией типов, +что позволяет несколько смягчить те условия, для которых возможно доказательство +безопасности системы. + +Формальное описание модели включает в себя следующие элементы: +\begin{itemize} + \item $O$ --- множество объектов системы; + \item $S$ --- множество субъектов системы ($S \subseteq O$); + \item $R$ --- множество прав доступа субъектов к объектам; + \item $M$ --- матрица доступов; + \item $C$ --- множество команд; + \item $T$ --- множество типов объектов; + \item $t: O \to T$ --- функция, ставящая в соответствие каждому объекту его тип; + \item $q = (S, O, t, M)$ --- состояние системы; + \item $Q$ --- множество состояний системы. +\end{itemize} + +Состояния системы изменяются в результате применения к ним команд множества $C$. + +\begin{align*} + comm&and c(x_1 : t_1, \dots, x_k : t_k) \\ + &if (r_1 \in M[x_{s_1}, x_{o_1} and \dots and r_m \in M[x_{s_m}, x_{o_m}]) then \\ + & a_1; \\ + & \dots \\ + & a_n; \\ + &endif \\ + & end. +\end{align*} + +Перед выполнением команды происходит проверка типов фактических параметров, и, +если они не совпадают с указанными в определении команды, то команда не +выполняется. + +В модели ТМД используются 6 видов примитивных операторов, отличающихся от +аналогичных операторов модели ХРУ только использованием типизированных +параметров. + +%% TODO: таблица +Примитивный оператор / Исходное состояние $q = (S, O, t, M)$ / Результирующее состояние $q' = (S', O', t', M')$ +<<внести>> право $r$ в $M[s, o]$ / $s \in S, o \in O, r \in R$ / $S' = S, O' = O, t' = t, M'[s, o] = M[s, o] \cup \set{r}$, если $(s', o') \neq (s, o)$, то $M'[s', o'] = M[s', o']$. +<<удалить>> право $r$ из $M[s, o]$ / $s \in S, o \in O, r \in R$ / $S' = S, O' = O, t' = t, M'[s, o] = M[s, o] - \set{r}$, если $(s', o') \neq (s, o)$, то $M'[s', o'] = M[s', o']$. +<<создать>> субъект $s'$ с типом $t_s$ / $s' \not\in O$ / $S' = S \cup \set{s'}, O' = O \cup \set{s'}$, если $o \in O$, то $t'(o) = t(o), t'(s') = t_s$, если $(s, o) \in S \times O$, то $M'[s, o] = M[s, o]$, если $o \in O'$, то $M'[s', o] = \varempty$, если $s \in S'$, то $M'[s, s'] = \varempty$. +<<создать>> объект $o'$ с типом $t_o$ / $o' \not\in O$ / $S' = S, O' = O \cup \set{o'}$, если $o \in O$, то $t'(o) = t(o), t'(o') = t_o$, если $(s, o) \in S \times O$, то $M'[s, o] = M[s, o]$, если $s \in S'$, то $M'[s, o'] = \varempty$. +<<уничтожить>> субъект $s'$ / $s' \in O$ / $S' = S - \set{s'}, O' = O - \set{s'}$, если $o \in O$, то $t'(o) = t(o)$, если $(s, o) \in S' \times O'$, то $M'[s, o] = M[s, o]$. +<<уничтожить>> объект $o'$ / $o' \in O, o' \in S$ / $S' = S, O' = O - \set{o'}$, если $o \in O'$, то $t'(o) = t(o)$, если $(s, o) \in S' \times O'$, то $M'[s, o] = M[s, o]$. + +Таким образом, ТМД является обобщением модели ХРУ, которую можно рассматривать +как частный случай ТМД с одним единственным типом для всех субъектов и объектов. + +С другой стороны, любую ТМД можно выразить через систему ХРУ, введя для +обозначения типов специальные права доступа, а проверку типов в командах +заменив проверкой наличия соответствующих прав доступа. + +Пусть $c(x_1 : t_1, \dots, x_k : t_k)$ --- некоторая команда системы ТМД. Будем +говорить, что $x_i$ является \emph{дочерним параметром}, а $t_i$ является +\emph{дочерним типом} в $c(x_1 : t_1, \dots, x_k : t_k)$, где $1 \leq i \leq k$, +в случае, когда в ней имеется один из следующих примитивных операторов: +\begin{itemize} + \item <<создать>> субъект $x_i$ с типом $t_i$; + \item <<создать>> объект $x_i$ с типом $t_i$. +\end{itemize} + +В противном случае будем говорить, что $x_i$ является \emph{родительским +параметром}, а $t_i$ является \emph{родительским типом} в команде +$c(x_1 : t_1, \dots, x_k : t_k)$. + +Заметим, что в одной команде тип может быть одновременно и родительским и +дочерним. + +Например, +\begin{align*} + &command foo(s_1: u, s_2: u, s_3: v, o_1: w, o_2: b) \\ + & \text{<<создать>> субъект } s_2 \text{с типом } u; \\ + & \text{<<создать>> объект } s_3 \text{с типом } v; \\ + &end. +\end{align*} + +Здесь $u$ является + + +\emph{Система монотонной ТМД} (МТМД) --- система ТМД, в командах которой +отсутствуют немонотонные примитивные операторы вида <<удалить>> и +<<уничтожить>>. + +\emph{Каноническая форма системы МТМД} (КФМТМД) --- система МТМД, в которой +команды, содержащие примитивные операторы вида <<создать>>, не содержат +условий и примитивных операторов вида <<внести>>. + +\begin{theorem} %% NOTE: 2.3 + Для каждой системы МТМД существует эквивалентная ей система КФМТМД. +\end{theorem} +\begin{proof} + Пусть задана система МТМД, в которой определены множества $R, T, Q, C$. + Построим эквивалентную ей систему КФМТМД, определив множества $R^*, T^*, + Q^*, C^*$. + + Зададим множества + \begin{align*} + R^* &= R \cup \set{active}; \\ + T^* &= T \cup \set{t_{active}}. + \end{align*} + + В каждом состоянии $q^* = (S^*, O^*, t^*, M^*)$, соответствующем состоянию + $q = (S, O, t, M)$, справедливы равенства: + \begin{align*} + S^* &= S \cup \set{s_{active}}; \\ + O^* &= O \cup \set{s_{active}}. + \end{align*} + + Пусть также для каждого $o \in O$ справедливо равенство $t^*(o) = t(o)$ и + $s_{active}$ --- единственный объект такой, что $t^*(s_{active}) = t_{active}$. + + Кроме того, для $s \in S, o \in O$ справедливо равенство $M^*[s, o] = M[s, o]$, + и в начальном состоянии $q_0^* = (S_0^*, O_0^*, t_0^*, M_0^*)$ системы КФМТМД + для $o \in O_0$ справедливо равенство $M_0^*[s_{active}, o] = \set{active}$. + + Таким образом, право доступа $active$ обозначает активизированные субъекты и объекты + КФМТМД. + + Каждую команду $c(x_1: t_1, \dots, x_k: t_k) \in C$ системы МТМД, не содержащую + примитивные операторы <<создать>>, представим командой $c(x_1: t_1, \dots, x_k: + t_k, x: active)$ системы КФМТМД, полученной из исходной команды добавлением + условий проверки $active \in M[x, x_i], i = 1, \dots, k$. + + Каждую команду $c(x_1: t_1, \dots, x_k: t_k)$ системы МТМД, содержащую + примитивные операторы <<создать>>, представим монотонными командами КФМТМД: + \begin{itemize} + \item + $c'_{x_i}(x_{j_1}: t_{j_1}, \dots x_{j_m}: t_{j_m})$ --- команды без + проверки условий, каждая из которых соответствуют одному дочернему + параметру $x_i$ команды $c(x_1: t_1, \dots, x_k: t_k)$, содержит все её + родительские параметры и параметр $x_i$ и содержит соответствующий + примитивный оператор вида <<создать>>; + \item + $c''(x_1: t_1, \dots, t_k: t_k, x: t_{active})$ --- команда, содержащая + условия и примитивные операторы <<внести>> команды $c(x_1: t_1, \dots, + x_k: t_k)$, условия проверки $active \in M[x, x_i]$, для всех + родительских параметров $x_i$, примитивные операторы <<внести>> право + $active$ в $M[x, x_i]$ для всех дочерних параметров $x_i$. + \end{itemize} + + Таким образом, только <<активизированные>> объекты (в том числе и субъекты) + системы КФМТМД соответствуют объектам системы МТМД, а все преобразования над + ними в системе КФМТМД, соответствуют преобразованиям системы МТМД. +\end{proof} + +\emph{Граф создания системы МТМД} --- ориентированный граф с множеством вершин +$T$, в котором дуга от вершина $u$ к вершине $v$ существует $\iff$ в системе +имеется команда, в которой $u$ является родительским типом, а $v$ --- дочерним +типом. + +Система МТМД (КФ МТМД) называется \emph{ациклической} (АМТМД или, соответственно, +АКФМТМД) $\iff$ её граф создания не содержит циклов; в противном случае система +является \emph{циклической}. diff --git a/security-models/lectures/lecture5.tex b/security-models/lectures/lecture5.tex new file mode 100644 index 0000000..72ba78b --- /dev/null +++ b/security-models/lectures/lecture5.tex @@ -0,0 +1,2 @@ +% Лекция 5 (20.10.23) + diff --git a/security-models/lectures/lecture6.tex b/security-models/lectures/lecture6.tex new file mode 100644 index 0000000..856d7f7 --- /dev/null +++ b/security-models/lectures/lecture6.tex @@ -0,0 +1,182 @@ +% Лекция 6 (27.10.23) + +Третий шаг алгоритма всегда будет иметь конечную сложность. Так как множество +объектов не изменяется, то необходимо перебрать все последовательности различных +команд, а их конечное число. + +Наибольшую трудоёмкость в общем случае представляет разработка алгоритма +построения <<развёрнутого>> состояния. + +Однако для АМТМД или АКФМТМД такой алгоритм существует. + +Пусть $\alpha$ и $\beta$ --- две различные команды системы МТМД, содержащие +примитивные операторы <<создать>>, \dots. Будем считать, что $\alpha < \beta \iff$ +для некоторого дочернего типа команды $\alpha$ в графе создания найдётся путь +в некоторый родительский тип команды $\beta$. + +В системе АМТМД отношение <<$<$>> на множестве команд, содержащих примитивные +операторы <<создать>>, \dots, является отношением строгого порядка + +%% TODO +\textbf{Алгоритм 2.2} \emph{Алгоритм построения <<развёрнутого>> состояния для +системы АКФМТМД.} +\begin{enumerate} + \item + Упорядочить в списке все команды, содержащие примитивные операторы вида + <<создать>>, \dots (команда $\alpha$ следует в списке перед командой $\beta + \iff \alpha < \beta \; \lor$ $\alpha$ и $\beta$ не сравнимы). + \item + Начиная с начального состояния, применять команды в соответствии с созданным + на шаге 1 списком, при этом каждая команда применяется со всеми возможными + для неё наборами родительских объектов. +\end{enumerate} + +%% NOTE: 2.4 +\begin{theorem} + Существует алгоритм проверки безопасности систем АМТМД. +\end{theorem} +%% NOTE: 2.2 +\begin{corollary} + Алгоритм проверки безопасности систем АМТМД имеет экспоненциальную сложность. +\end{corollary} + +Для АМТМД, в которых каждая команда имеет не более трёх параметров, доказано, +что алгоритм проверки их безопасности имеет полиномиальную сложность. + +%% NOTE: 2.3 +\subsection{Модель распространения прав доступа Take-Grant} + +\subsubsection{} + +Классическая модель Take-Grant ориентирована на анализ путей распространения +прав доступа в системе дискреционного управления доступом. + +Основными элементами модели Take-Grant являются: +\begin{itemize} + \item $O$ --- множество объектов; + \item $S \subseteq O$ --- множество субъектов; + \item + $R = \set{r_1, r_2, \dots, r_m} \cup \set{t, g}$ --- множество видов прав + доступа, где $t$ (take) --- право брать права доступа, $g$ (grant) --- право + давать права доступа; + \item + $G = (S, O, E)$ --- конечный помеченный ориентированный без петель граф + доступов, описывающий состояние системы. +\end{itemize} + +Элементы множеств $S$ и $O$ являются вершинами графа, которые обозначаются +$\otimes$ --- объекты (элементы множества $O - S$) и $\cdot$ --- субъекты +соответственно. + +Элементы множества $E \subseteq O \times O \times R$ являются дугами графа. +Каждая дуга помечена непустым подмножеством множества видов прав доступа $R$. +Состояние системы описывается соответствующим ему графом доступов. + +В отличие от подели ХРУ в модели Take-Grant возможно наличие прав доступов не +только у субъектов к объектам, но и у объектов к объектам. + +Основная цель классической модели Take-Grant --- определение и обоснование +алгоритмически проверяемых условий проверки возможности утечки права доступа по +исходному графу доступов, соответствующего некоторому состоянию системы. + +Порядок перехода системы модели Take-Grant из состояния в состояние определяется +правилами преобразования графа доступов, которые в классической модели носят +название де-юре правил. + +Преобразование графа $G$ в граф $G'$ в результате выполнения правила $op$ +обозначается через $G \vdash_{op} G'$. + +В классической модели Take-Grant рассматриваются следующие четыре де-юре +правила преобразования графа, выполнение каждого из которых может быть +инициировано только субъектом, являющимся активной компонентой системы: +\begin{enumerate} + \item + $take$ --- брать права доступа (см. рис 2.1): субъект $x$ берёт у объекта + $y$ права $\alpha$ на объект $z$; + %% TODO: рис. 1 + \item + $grant$ --- давать права доступа (см. рис. 2.2): субъект $x$ даёт объекту + $y$ права $\alpha$ на объект $z$; + %% TODO: рис. 2 + \item + $create$ --- создать новый объект или субъект, при этом субъект создатель + может взять на созданный субъект любые права доступа (по умолчанию + предполагается, что создаётся объект, создание субъекта оговаривается особо) + (см. рис. 2.3); + %% TODO: рис. 3 + \item + $remove$ --- удалять права доступа (см. рис. 4): субъект $x$ удаляет из + своих прав доступа на объект $y$ набор прав $\alpha$. + %% TODO: рис. 4 +\end{enumerate} + +%% TODO: нумерация +В таблице 2.3 приведены условия применения де-юре правил в исходном состоянии +$G = (S, O, E)$ и результаты их применения в результирующем состоянии +$G' = (S', O', E')$. + +%% TODO: таблица 2.3 --- Де-юре правила классической модели Take-Grant +Правила | Исходное состояние $G = (S, O, E)$ | Результирующее состояние $G' = (S', O', E')$ +$take(\alpha, x, y, z)$ | $x \in S, \; y, z \in O, \; (x, y, \set{t}) \subset E, \; (y, z, \beta) \subset E, \; x \neq z, \; \alpha \subseteq \beta$ | $S' = S, O' = O, E'= E \cup \set{(x, z, \alpha)}$ + +\begin{itemize} + \item $grant(\alpha, x, y, z)$ + \item + $x \in S, \; y, z \in O, \; (x, y, \set{g}) \subset E, \; (x, z, \beta) + \subset E, \; y \neq z, \; \alpha \subseteq \beta$ + \item $S' = S, O' = O, E'= E \cup \set{(y, z, \alpha)}$ +\end{itemize} +\begin{itemize} + \item $create(\beta, x, y)$ + \item $x \in S, \; y \not\in O, \beta \neq \varnothing$ + \item $O' = O \cup \set{y}$, если $y$ субъект, то $S' = S \cup \set{y}$, + иначе $S' = S, \; E' = E \cup \set{(x, y, \beta)}$ +\end{itemize} +\begin{itemize} + \item $remove(\alpha, x, y)$ + \item $x \in S, \; y \in O, \; (x, y, \beta) \subset E, \; \alpha \subseteq \beta$ + \item $S' = S, \; O' = O, \; E' = E - \set{(x, y, \alpha)}$ +\end{itemize} + +Рассмотрим условия, при которых в системе возможно распространение прав доступа. + +Пусть дан граф доступов $G_0 = (S_0, O_0, E_0), \; x, y \in O_0, \; x \neq y, \; +\alpha \subseteq R$. Определим предикат $\fn{can_share}(\alpha, x, y, G_0)$, +который будет истинным $\iff \exists G_1 = (S_1, O_1, E_1), \dots, G_N = (S_N, +O_N, E_N)$ и правила $op_1, \dots, op_N, \; N \geq 0 : G_0 \vdash_{op_1} G_1 +\vdash_{op_2} \dots \vdash_{op_N} G_N \land (x, y, \alpha \subset E_N$. + +Определение истинности предиката $\fn{can_share}(\alpha, x, y, G_0)$ +непосредственно по определению является в общем случае алгоритмически +неразрешимой задачей, так как требует проверки всех траекторий функционирования +системы. + +По этой причине для проверки истинности предиката $\fn{can_share}(\alpha, x, y, +G_0)$ следует определить необходимые и достаточные условия, проверка которых +возможна. Решение этой задачи будет выполнено в два этапа: +\begin{enumerate} + \item %% TODO: дописать + \item Определены и обоснованы условия истинности предиката для произвольных + графов. +\end{enumerate} + +Пусть $G = (S, S, E)$ --- граф доступов, все вершины которого являются субъектами. +Говорят, что вершины графа доступов являются $tg$-связными или что они соединены +$tg$-путём, когда, без учёта направления рёбер, в графе между ними существует +путь такой, что каждое ребро этого пути помечено $t$ или $g$. + +\begin{theorem} + Пусть $G_0 = (S_0, O_0, E_0)$ --- граф доступов, содержащий только вершины + субъекты, $x, y \in S_0, \; x \neq y$. + + Тогда предикат $\fn{can_share}(\alpha, x, y, G_0)$ истинен $\iff$ выполняются + следующие два условия: + \begin{enumerate} + \item + существуют субъекты $s_1, \dots, s_m \subset S_0 : (s_i, y, \gamma_i) + \subset E_0$, где $i = 1, \dots, m$ и $\alpha = \gamma_1 \cup \dots \cup + \gamma_m$; + \end{enumerate} +\end{theorem} + +%% TODO: дописать diff --git a/security-models/lectures/lecture7.tex b/security-models/lectures/lecture7.tex new file mode 100644 index 0000000..9134d9e --- /dev/null +++ b/security-models/lectures/lecture7.tex @@ -0,0 +1,65 @@ +% Лекция 7 (03.11.23) + +% 2.4 (9) Постройте графы создания для систем МТМД со следующими наборами команд. +% +% а) +% command a1(x: $\alpha$, y: $\beta$, z: $\beta$) +% <<создать>> субъект x с типом $\alpha$; +% end; +% command a2(x: $\alpha$, y: $\gamma$, z: $\beta$, s: $\delta$) +% <<создать>> субъект y с типом $\gamma$; +% <<создать>> субъект s с типом $\delta$; +% end; +% command a3(x: $\varepsilon$, y: $\delta$, z: $\beta$, s: $\gamma$, o: $\delta$) +% <<создать>> субъект o с типом $\delta$; +% <<создать>> субъект x с типом $\varepsilon$; +% end; + +\emph{Начальным пролётом моста} в графе доступов $G_0$ называется $tg$-путь, +началом которого является вершина субъект, концом --- объект, проходящий +через вершины объекты, словарная запись которого имеет вид $\vec{t}^* \vec{g}$. + +\emph{Конечным пролётом моста} в графе доступов $G_0$ называется $tg$-путь, +началом которого является вершина субъект, концом --- объект, проходящий через +вершины объекты, словарная запись которого имеет вид $\vec{t}^*$. + +%% NOTE: 2.6 +\begin{theorem} + Пусть $G_0 = (S_0, O_0, E_0)$ --- произвольный граф доступов, $x, y \in O_0, + x \neq y$. Предикат $\fn{can_share}(\alpha, x, y, G_0)$ истинен $\iff$ или + $(x, y, \alpha) \subset E_0$, или выполняются следующие три условия: + \begin{enumerate} + \item + существуют объекты $s_1, \dots, s_m \in O_0: (s_i, y, \gamma_i) \subset + E_0$ для $i = 1, \dots, m$ и $\alpha = \gamma_1 \cup \dots \cup \gamma_m$; + \item + существуют субъекты $x_1', \dots, x_m', s_1', \dots, s_m' \in S_0$ : + \begin{enumerate} + \item + $x = x_i'$ или $x_i'$ соединён с $s_i$ конечным пролётом моста в графе + $G_0$, где $i = 1, \dots, m$; + \item + $s_i = s_i'$ или $s_i'$ соединён с $s_i$ конечным пролётом моста в + $графе G_0$, где $i = 1, \dots, m$; + \end{enumerate} + \item + в графе $G_0$ для каждой пары $(x_i', s_i')$, $i = 1, \dots, m$, + существуют острова $I_{i,1}, \dots, I_{i,u_i}$, где $u_i \geq 1$, такие, + что $x_i' \in I_{i,1}, s_i' \in I_{i,u_i}$, и существуют мосты между + островами $I_{i,j}$ и $I_{i,j + 1}$, $j = 1, \dots, u_i - 1$. + \end{enumerate} +\end{theorem} + +Смысл теоремы состоит в том, что если в системе разграничения доступа в +начальном состоянии между двумя какими-либо объектами имеется $tg$-путь, +включающий, в том числе, мосты между островами, то найдётся такая +последовательность команд вида <<take>>, <<grant>>, <<create>>, в результате +которой первый объект получит необходимые права доступа над другим объектом. +Существенным при этом является отсутствие каких-либо ограничений на кооперацию +субъектов и объектов доступа, в частности, отсутствие запретов на передачу прав +доступа к объекту субъектами, изначально обладающими необходимыми правами на +объект, представляющий интерес для других субъектов. Говоря иначе, подобный +порядок вещей характеризует идеальное сотрудничество и доверие между субъектами +доступа. + + diff --git a/security-models/lectures/lecture8.tex b/security-models/lectures/lecture8.tex new file mode 100644 index 0000000..afc6c39 --- /dev/null +++ b/security-models/lectures/lecture8.tex @@ -0,0 +1,148 @@ +% Лекция 8 (10.11.23) + +Похищение прав доступа является примером случая, когда передача прав доступа +к объекту осуществляется без содействия субъекта, изначально обладавшего +передаваемыми правами, таким образом, не все субъекты системы кооперируют друг с +другом. + +Пусть $x, y \in O_0, \, x \neq y$ --- различные объекты графа доступов $G_0 = +(S_0, O_0, E_0),\, \alpha \subseteq R$. Определим предикат $\fn{can_steal}( +\alpha, x, y, G_0)$, который будет истинным $\iff (x, y, \alpha) \cap E_0 = +\varnothing$, существуют графы $G_1 = (S_1, O_1, E_1)$, $\dots$, $G_N = (S_N, +O_N, E_N)$ и правила $op_1, \dots, op_N$, где $N \geq 1$, такие, что $G_0 +\vdash_{op_1} G_1 \vdash_{op_2} \dots \vdash_{op_N} G_N$ и $(x, y, \alpha) +\subset E_N$, при этом, если существует $(s, y, \gamma) \subset E_0$, где +$\gamma \subseteq \alpha$, то справедливо неравенство $op_k \neq \fn{grant}( +\gamma, s, z, y)$, где $z \in O_{K - 1}, K = 1, \dots, N$. + +Говоря иначе, согласно определению похищением прав является процесс получения +прав доступа на какой-либо объект без представления прав третьим субъектам со +стороны субъекта, обладающего в начальном состоянии требуемыми правами на +объект <<интересе>>. + +%% NOTE: 2.7 +\begin{theorem} + Пусть $G_0 = (S_0, O_0, E_0)$ --- произвольный граф доступов, $x, y \in O_0$, + $x \neq y$. Предикат $\fn{can_steal}(\alpha, x, y, G_0)$ истинен $\iff$ + выполняются следующие четыре условия: + \begin{enumerate} + \item $(x, y, \alpha) \cap E_0 = \varnothing$; + \item существуют объекты $s_1, \dots, s_m \in O_0$ такие, что $(s_i, y, + \gamma_i) \subset E_0$ для $i = 1, \dots, m$ и $\alpha = \gamma_1 \cup + \dots \cup \gamma_m$; + \item являются истинными предикаты $\fn{can_share}(\set{t}, x, s_i, G_0)$, + где $i = 1, \dots, m$; + \item + для $i = 1, \dots, m$ граф доступов $G_0$ не является графом вида, + приведённого на рисунке 2.7 + %% TODO: рис 1 (2.7) + %% TODO: Условие 4 теоремы 2.5 + \end{enumerate} +\end{theorem} + +Данная теорема означает, что если политика разграничения доступа в компьютерной +системе запрещает субъектам, имеющим в исходном состоянии права доступа к +определённым объектам, непосредственно предоставлять эти права другим субъектам +(то есть такие потоки, для которых в графе доступов $G_0$ нет дуг <<$g$>> от +этих субъектов), которые изначально такими правами не обладают, то тем не менее, +такие первоначально <<обделённые>> субъекты могут получить данные права при +наличии в графе доступов возможностей получения доступа с правом $t$ к первым +субъектам. + +Таким образом, модель \emph{take-grant} играет важную методологическую роль, +предоставляя теоретико-графовый инструмент анализа систем разграничения доступа +с точки зрения санкционированного и несанкционированного со стороны определённых +субъектов распространения прав доступа в рамках дискреционной политики. + +Правила де-юре контролируют только передачу полномочий, они ничего не говорят о +передач информации, поэтому на основе классической модели \emph{Take-Grant} +были разработаны её расширения, которые предлагают новые механизмы анализа, в +большей степени применимые к современным системам защиты информации. + +Рассмотрим некоторые расширения модели. + +%% NOTE: 1 +\paragraph{Де-факто правила, предназначенные для поиска и анализа информационных +потоков.} + +Вместо прав доступа take и grant в расширенной модели в первую очередь +рассматриваются права read и write, наличие которых у субъектов системы является +причиной возникновения информационных потоков. + +Основные элементы (дополнения): +\begin{itemize} + \item + $R = \set{r_1, r_2, \dots, r_m} \cup \set{t, g} \cup \set{r, w}$ --- + множество видов прав доступа информационных потоков, где r (read) --- право + на чтение или информационный поток на чтение, w (write) --- право на запись + или информационный поток на запись; + \item + $G = (S, O, E \cup F)$ --- граф доступов и информационных потоков; + \item + Элементы множества $E \subseteq O \times O \times R$ являются <<реальными>> + дугами графа, соответствующими правам доступа, и в графе доступов + обозначается сплошными линиями; + \item + Элементы множества $F \subseteq O \times O \times \set{r, w}$ являются + <<мнимыми>> дугами, соответствующими информационным потокам, и в графе + доступов обозначаются пунктирными линиями. + \item + Каждая <<реальная>> дуга помечена непустым подмножеством множества всех видов + прав доступа $R$, каждая <<мнимая>> дуга помечена непустым подмножеством + множества $\set{r, w}$; + \item + Порядок перехода системы расширенной модели \emph{Take-Grant} из состояния + в состояние определяется де-юре и де-факто правилами преобразования графов + доступов и информационных потоков; + \item + Преобразование графа $G$ в граф $G'$ в результате выполнения правила $op$ + обозначается $G \vdash_{op} G'$. +\end{itemize} + +Определение де-юре правил take, grant, create, remove совпадает с определением +этих правил в классической модели Take-Grant. + +Де-юре правила применяются только к <<реальным>> дугам (элементам множества +$E$). Де-факто правила применяются к <<реальным>> или <<мнимым>> дугам +(элементам множества $E \cup F$), помеченным $r$ или $w$. + +Результатом применения де-факто правил является добавление новых <<мнимых>> дуг +в множество $F$. Рассматриваются шесть де-факто правил: два вспомогательных и +четыре основных + +\begin{itemize} + \item + См. рисунок 2.8: субъект $x$ получает возможность записи (в себя) информации, + осуществляя доступ $r$ к объекту $y$. + %% TODO: рис. 2 (2.8) + %% TODO: Применение первого де-факто правила + \item + См. рисунок 2.8: субъект $x$ получает возможность чтения информации, + осуществляя доступ $w$ к объекту $y$. + %% TODO: рис. 3 (2.9) + %% TODO: Применение второго де-факто правила + \item + \emph{Spy} (шпион) (см. рисунок 2.10): субъект $x$ получает возможность + чтения информации из объекта $z$, осуществляя доступ $r$ к субъекту $y$, + который, в свою очередь, осуществляет доступ $r$ к объекту $z$, при этом + также у субъекта $x$ возникает возможность записи к себе информации из + объекта $z$. + + Получается, $x$ шпионит за $z$, используя $y$, другими словами, $x$ <<смотрит + через плечо>> $y$, чтобы следить за $z$. + %% TODO: рис. 4 (2.10) + %% TODO: Применение правила spy(x, y, z) + \item + \emph{Find} (находить) (см. рисунок 2.11): субъект $x$ получает возможность + чтения информации из объекта $z$, осуществляя доступ $w$ к субъекту $y$, + который, в свою очередь, осуществляет доступ $w$ к объекту $z$, при этом + также у субъекта $x$ возникает возможность записи к себе информации из + объекта $z$. + %% TODO: рис. 5 (2.11) + %% TODO: Применение правила spy(x, y, z) + \item + \emph{Post} (почта) (см. рисунок 2.12): субъект $x$ получает возможность чтения + информации от (из) другого субъекта $z$, осуществляя доступ $r$ к объекту + $y$, к которому субъект $z$ осуществляет доступ $w$, а субъект $z$, в + свою очередь. +\end{itemize} diff --git a/security-models/lectures/lecture9.tex b/security-models/lectures/lecture9.tex new file mode 100644 index 0000000..357dc2c --- /dev/null +++ b/security-models/lectures/lecture9.tex @@ -0,0 +1,2 @@ +% Лекция 9 (17.11.23) + diff --git a/security-models/security-models.pdf b/security-models/security-models.pdf Binary files differindex 91b4dc6..9a85d02 100644 --- a/security-models/security-models.pdf +++ b/security-models/security-models.pdf diff --git a/security-models/security-models.tex b/security-models/security-models.tex index 7d25199..571d40c 100644 --- a/security-models/security-models.tex +++ b/security-models/security-models.tex @@ -16,6 +16,17 @@ \newpage % Семестр 1 +% 1 \input{lectures/lecture2.tex} +% 3 +\input{lectures/lecture4.tex} +% \input{lectures/lecture5.tex} +\input{lectures/lecture6.tex} +\input{lectures/lecture7.tex} +\input{lectures/lecture8.tex} +% \input{lectures/lecture9.tex} +\input{lectures/lecture10.tex} +% 11 +\input{lectures/lecture12.tex} \end{document} |