From 032e1fa27ff9faa9a5d82624dbfc5fe8a48c339c Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sun, 11 Dec 2022 12:43:48 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=205=20=D0=BB=D0=B0=D0=B1=D0=BE=D1=80=D0=B0=D1=82=D0=BE=D1=80?=
 =?UTF-8?q?=D0=BD=D0=B0=D1=8F?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 reports/lab5/lab5.tex | 135 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 135 insertions(+)
 create mode 100644 reports/lab5/lab5.tex

(limited to 'reports/lab5/lab5.tex')

diff --git a/reports/lab5/lab5.tex b/reports/lab5/lab5.tex
new file mode 100644
index 0000000..5505297
--- /dev/null
+++ b/reports/lab5/lab5.tex
@@ -0,0 +1,135 @@
+\documentclass[a4paper,oneside]{article}
+
+\usepackage[utf8]{inputenc}
+\usepackage[T2A]{fontenc}
+\usepackage[english,russian]{babel}
+
+\usepackage{amsmath}
+\usepackage{mathtools}
+\usepackage{amsfonts}
+\usepackage{enumitem}
+\usepackage{amsthm}
+\usepackage{minted}
+\setminted{fontsize=\small, breaklines=true, style=emacs, linenos}
+\usepackage{graphicx}
+\graphicspath{ {./images/} }
+\usepackage{float}
+\usepackage{algorithm}
+\floatname{algorithm}{Алгоритм}
+
+\newcommand{\Z}{\mathbb{Z}}
+\DeclarePairedDelimiter\ceil{\lceil}{\rceil}
+\DeclarePairedDelimiter\floor{\lfloor}{\rfloor}
+
+\newtheorem{theorem}{Теорема}
+\newtheorem*{theorem*}{Теорема}
+
+% --- Определение --- %
+\theoremstyle{definition}
+\newtheorem{definition}{Определение}
+\newtheorem*{definition*}{Определение}
+% ------------------- %
+
+\theoremstyle{definition}
+\newtheorem*{example}{Пример}
+
+
+\title{{Криптографические методы защиты информации}\\{Лабораторная работа №5}}
+\author{Гущин Андрей, 431 группа, 1 подгруппа, 2 вариант}
+\date{\the\year{} г.}
+
+\begin{document}
+\maketitle
+
+\section{Схема}
+
+Рассмотрим следующее упрощение схемы Эль-Гамаля. Пусть $p$ --- простое число,
+$g$ --- порождающий элемент мультипликативной группы $Z^\cdot_p$. Эти данные
+открыты.
+
+Пользователь выбирает секретное число $1 \leq a \leq p - 1$ и открывает значение
+$y = g^a \pmod{p}$.
+
+К сообщению $m \in \{ 0, 1 \}^*$ применяется известная хэш-функция, дающая
+значение $h = h(m) \in Z_p$.
+
+Допустим, что $\gcd(h, p - 1) = 1$. Этого можно добиться, внеся необходимые
+коррективы в случае невыполнения.
+
+При генерации подписи пользователь вычисляет значение
+\begin{equation}
+  z = h^{-1} a \pmod{(p - 1)}
+  \label{eq:zpow}
+\end{equation}
+
+В качестве подписи под документом $m$ предлагается использовать $g^z$.
+
+Проверка правильности подписи элементарна:
+\begin{equation}
+  (g^z)^h = g^{h^{-1} h a} = g^a \pmod{p}
+  \label{eq:check}
+\end{equation}
+
+Подпись принимается, если полученное значение совпадает с $y$.
+
+Необходимо объяснить почему упомянутая схема неприемлема.
+
+
+\section{Неверность схемы}
+
+Заметим, что в выражении \ref{eq:check} подразумевается, что значения $z$
+и $h$ находятся в одном кольце и поэтому можно написать $z \cdot h =
+h^{-1} \cdot a \cdot h = h^{-1} \cdot h \cdot a = a$.
+
+Но, также можно заметить, что при вычислении $z$ в выражении \ref{eq:zpow}
+умножаемые значения берутся по модулю $(p - 1)$. То есть, значение $z$
+является элементом мультипликативной группы $Z^\cdot_{(p - 1)}$. При этом
+значение $h$ является элементом группы $Z^\cdot_p$ по условию.
+
+Таким образом, в общем случае мы можем сказать, что
+\begin{equation*}
+  z \cdot h 
+  = (h^{-1} \cdot a \pmod{(p - 1)}) \cdot h
+  \neq h^{-1} \cdot a \cdot h
+\end{equation*}
+
+Например, пусть $p = 31, a = 19, h = 11$. При этом $h^{-1} = 17$, где обратное
+берётся в группе $Z^\cdot_p$.
+
+\begin{align*}
+  z &= 17 \cdot 19 \pmod{30} = 23 \\
+  z \cdot h &= 23 \cdot 11 \pmod{31} = 5 \\
+  h^{-1} \cdot a \cdot h &= 17 \cdot 19 \cdot 11 \pmod{31} = 19
+\end{align*}
+
+Получаем
+\begin{equation*}
+  z \cdot h = 5 \neq 19 = h^{-1} \cdot a \cdot h
+\end{equation*}
+
+Таким образом, получаем, что сгенерированную подпись невозможно проверить и
+данная схема является неприменимой и неприемлемой.
+
+\section{Взлом схемы}
+
+Будем считать схему подписи \emph{неприемлемой}, если имеется возможность
+создать подпись для произвольного сообщения не имея при этом секретного ключа.
+
+Рассмотрим выражение \ref{eq:check}. Можно заметить, что $(g^z)^h = y$. Также
+можем получить 
+\begin{equation*}
+  \left( \left( g^z \right)^h \right)^{h^{-1}} = y^{h^{-1}}
+\end{equation*}
+
+То есть
+\begin{equation*}
+  g^z = y^{h^{-1}}
+\end{equation*}
+
+Но значение $y$ является частью открытого ключа, а $h^{-1}$ вычисляется из
+публично известной хэш-функции для произвольного сообщения.
+
+Таким образом, можно создать подпись для произвольного сообщения не имея при
+этом секретного ключа, а основываясь только на публичных данных.
+
+\end{document}
-- 
cgit v1.2.3