\documentclass[spec, och, coursework]{SCWorks}
\usepackage{preamble}


\begin{document}
\include{titlepage.tex}
\tableofcontents


\intro
Для безопасного ведения корреспонденции в Интернете необходимы способы 
подтверждения авторства того или иного пользователя для каждого сообщения.
Методы, используемые для реализации таких систем взаимодействия зачастую
намного более надёжные, чем системы общения с помощью физических бумажных
носителей. Такая надёжность достигается с помощью использования современных
криптографических протоколов, взлом которых является крайне неэффективной
задачей.

Основной схемой подтверждения авторства какого-либо сообщения является
\textit{Электронная цифровая подпись}. При подписи сообщения по такой схеме
используется сразу несколько криптографических протоколов, обеспечивающих
надёжность подписи.

Для реализации алгоритмов цифровой подписи обычно используется два
криптографических алгоритма:
\begin{itemize}
    \item 
        Хэш-функции --- односторонние функции, которые однозначно преобразуют
        сообщение произвольной длины в сообщение фиксированной длины;
    \item
        Системы с открытым ключом --- системы ассиметричного шифрования,
        которые позволяют надёжно защитить электронную подпись от подделки.
\end{itemize}

Системы, в которых используется какой-либо вид цифровой подписи способны
распознать любые попытки компрометации сообщений любого своего пользователя.


\section{Хэширование}
В основе алгоритмов цифровой подписи обычно используется какая-либо 
односторонняя хэш-фунцкция в том или ином виде.

Хэш-функция определена для сообщений любой длины, при этом в результате 
получается хэш некоторой фиксированной длины. То есть $h = H(M)$, где 
$H$ -- некоторая хэш-функция, $M$ -- некоторое сообщение, а $h$ -- хэш 
сообщения, полученный с помощью функции $H$. При этом хэш-функции обладают 
дополнительными свойствами, которые обеспечивают полезность таких функций 
в крипографии:

\begin{itemize}
    \item Для данного $M$ легко вычислить $h$;
    \item Для данного $h$ сложно вычислить такое $M$, что $H(M) = h$;
    \item Для данного $M$ сложно найти другое такое $M'$, что $H(M) = H(M')$.
\end{itemize}

На практике, для реализации односторонних хэш-функций используется идея функции
сжатия. В результате применения такой функции получается значение длины $n$, 
меньшее длины $m$ исходного сообщения. В качестве параметров односторонняя
функция сжатия принимает часть сообщения и хэш-значение всех предыдущих блоков,
полученных по данному алгоритму. Таким образом хэш текущей части сообщения $M_i$
вычисляется по формуле \[ h_i = f(M_i, h_{i - 1}) \].

Это значение становится одним из параметров для вычисления хэша для следующего
блока сообщения. Хэшем всего сообщения является хэш последнего блока. 
\cite{scheiner-applied}

Наиболее известными алгоритмами хэширования являются MD5 и SHA, разработанные
в 1991 и 1995 году соответственно. На данный момент оба алгоритма считаются
небезопасными для определённых целей, но на их примере можно рассмотреть 
практическую реализацию и применение односторонних хэш-функций.


\subsection{MD5}
Алгоритм MD5 основан является улучшенной версией предшествующего алгоритма MD4.
Они cхожи по дизайну, хотя MD5 является несколько более сложным. Эти алгоритмы 
обрабатывают данное сообщение блоким по 512 бит, которые в свою очередь
разбиты на 16 32-битных подблоков. В результате их исполнения в обоих случаях 
получается хэш длины 128 бит, который получается конкатенацией четырёх
32-битных блоков.

Перед применением непосредственно алгоритма хэширования MD5 предварительно 
обрабатывает сообщение. Суть обработки состоит в том, что сообщение дополняется
так, что его длина была на 64 бита меньше числа, кратного 512. Дополнение
состоит из одного единичного бита, за которым следует необходимое количество 
нулей. После этого в конце добавляется 64-битное представление длины сообщения
(до дополнения). Таким образом, в резултате получается сообщение, длина которого
кратна 512 битам.

Следующим шагом будет установка начальных значений четырёх \textit{цепных 
переменных}. Они получают следующие значения:
\begin{align*}
    A &= \texttt{01234567}_{16} \\
    B &= \texttt{89abcdef}_{16} \\
    C &= \texttt{fedcba98}_{16} \\
    D &= \texttt{76542210}_{16}
\end{align*}

Эти значения копируются в новые временные переменные $a = A$, $b = B$, $c = C$, 
$d = D$.

Алгоритм обрабатывает изначальное сообщения по циклам, при этом в каждом цикле
обрабатывается свой 512-битный блок. Каждый цикл разделён на 4 раунда, в каждом
из который используется своя нелинейная функция
\begin{align*}
    F(x, y, z) &= (x \land y) \lor (\neg x \land z) \\
    G(x, y, z) &= (x \land z) \lor (\neg z \land y) \\
    H(x, y, z) &= x \oplus y \oplus z \\
    I(x, y, z) &= y \oplus (x \lor \neg z)
\end{align*}

Для обработки $j$-го 32-битного подблока $M_j$ вводятся ещё четыре операции для
каждого из четырёх раундов:
\begin{align*}
    FF(a, b, c, d, M_j, s, t_i) &= (a = b + ((a + F(b, c, d) + M_j + t_i) <<< s)) \\
    GG(a, b, c, d, M_j, s, t_i) &= (a = b + ((a + G(b, c, d) + M_j + t_i) <<< s)) \\
    HH(a, b, c, d, M_j, s, t_i) &= (a = b + ((a + H(b, c, d) + M_j + t_i) <<< s)) \\
    II(a, b, c, d, M_j, s, t_i) &= (a = b + ((a + I(b, c, d) + M_j + t_i) <<< s))
\end{align*}

Каждая итерация состоит из 64 шагов по 16 шагов на раунд. Для шагов 
$i = \overline{1,64}$ константа $t_i = \left[2^{32} \cdot |\sin(i)|\right]$. 
После выполнения всех шагов алгоритма, изменённые значения $a$, $b$, $c$, $d$ 
прибавляются к $A$, $B$, $C$, $D$ и алгоритм повторяется для следующего блока 
сообщения. Результат получается после выполнения алгоритма на последнем блоке и
конкатенации $A$, $B$, $C$ и $D$.

Операции каждого раунда MD5 можно посмотреть в приложении $?$.
\cite{scheiner-applied}


\subsection{Secure Hash Algorithm}
Алгоритм хэширования SHA (или SHA-1) в общих чертах схож с алгоритмом MD4,
но в нём присутствуют дополнительные изменения, которые делают его более
криптостойким.
\begin{enumerate}
    \item 
        Более длинная 160-битная длина хэша из-за использования пяти цепных
        переменных вместо четырёх;
    \item
        В SHA используется 4 раунда, как и в MD5, но при этом в четвёртом
        раунде используется такая же функция, как и во втором;
    \item Количество шагов алгоритма увеличено с 64 до 80;
    \item 
        Количество числовых констант уменьшено до четырёх, каждая из которых
        является общей для одного из раундов алгоритма, вместо уникальной
        константы для каждого шага алгоритма;
    \item Изменён набор нелинейных функций.
\end{enumerate}

Как и в MD5 первым шагом является установка начальных значений цепных 
переменных:
\[ A = \texttt{67452301}_{16} \]
\[ B = \texttt{efcdab89}_{16} \]
\[ C = \texttt{98badcfe}_{16} \]
\[ D = \texttt{10325476}_{16} \]
\[ E = \texttt{c3d2e1f0}_{16} \]

На каждой итерации алгоритма обрабатывается очередной блок исходного сообщения.
Значения цепных переменных копируются в новые переменные $a = A$, $b = B$,
$c = C$, $d = D$, $e = E$.

Набор нелинейных функций у SHA следующий:
\begin{align*}
    f_t(x, y, z) &= (x \land y) \lor (\neg x \land z), \, \text{для } t = \overline{0, 19} \\
    f_t(x, y, z) &= x \oplus y \oplus z, \, \text{для } t = \overline{20, 39} \\
    f_t(x, y, z) &= (x \land y) \lor (x \land z) \lor (y \land z), \, \text{для } t = \overline{40, 59} \\
    f_t(x, y, z) &= x \oplus y \oplus z, \, \text{для } t = \overline{60, 79}
\end{align*}

Обрабатываемый блок сообщения преобразуется из 16 32-битных слов ($M_i, \,
i = \overline{0, 15}$) в 80 32-битных слов ($W_i, \, i = \overline{0, 79}$)
по следующему алгоритму:
\begin{align*}
    W_t &= M_t, \, \text{для } t = \overline{0, 15} \\
    W_t &= (W_{t - 3} \oplus W_{t - 8} \oplus W_{t - 14} \oplus W_{t - 16}) <<< 1, \, \text{для } t = \overline{16, 79} 
\end{align*}

Для четырёх раундов используются следующие числовые константы:
\begin{align*}
    K_t &= \left[\frac{\sqrt{2}}{4}  \cdot 2^{32}\right] = \texttt{5a827999}_{16}, \, \text{для } t = \overline{0, 19} \\
    K_t &= \left[\frac{\sqrt{3}}{4}  \cdot 2^{32}\right] = \texttt{6ed9eba1}_{16}, \, \text{для } t = \overline{20, 39} \\
    K_t &= \left[\frac{\sqrt{5}}{4}  \cdot 2^{32}\right] = \texttt{8f1bbcdc}_{16}, \, \text{для } t = \overline{40, 59} \\
    K_t &= \left[\frac{\sqrt{10}}{4} \cdot 2^{32}\right] = \texttt{ca62c1d6}_{16}, \, \text{для } t = \overline{60, 79} \\
\end{align*}

Основной цикл алгоритма:
\begin{minted}{basic}
    for t = 0 to 79
        tmp = (a <<< 5) + f_t(b, c, d) + e + W_t + K_t
        e = d
        d = c
        c = b <<< 30
        b = a
        a = tmp
\end{minted}

Далее переменные $a$, $b$, $c$, $d$ и $e$ прибавляются к $A$, $B$, $C$, $D$ 
и $E$ соответственно. Результатом всего алгоритма является конкатенация
$A$, $B$, $C$, $D$ и $E$ после выполнения его для всех блоков исходного 
сообщения.

\section{Ассиметричное шифрование}
В системах шифрования с открытым ключом (ассиметричных системах шифрования)
каждый из пользователей обладает некоторым ключом $k$, состоящим из
открытого ключа $k_o$, который определяет правило шифрования $E_k$, 
и закрытого ключа $k_p$, который определяет правило расшифрования $D_k$. 
Эти правила связаны соотношением
\[ E_k(M) = C, \, D_k(C) = M \]
где $M$ --- любой открытый текст, $C$ --- шифротекст. \cite{alferov}

Для отправки конфиденциального сообщения от пользователя B пользователю A,
следует использовать следующий алгоритм:
\begin{enumerate}
    \item Пользователь B запрашивает у пользователя A копию открытого ключа $k_o$;
    \item Пользователь B вычисляет шифротекст $C = E_k(M)$ для своего сообщения $M$;
    \item 
        Пользователь A получает шифротекст $C$ и расшифровывает его с помощью
        своего закрытого ключа $k_p$, чтобы получить зашифрованное сообщение
        $M = D_k(C)$.
\end{enumerate}

Системы шифрования с открытым ключом осуществляют блочное шифрование, поэтому
текст исходного сообщения перед началом алгоритма шифрования разбивается на
блоки необходимого размера, которые затем последовательно преобразуются.
Ассиметричные системы обычно обеспечивают значительно меньшие скорости 
шифрования, чем симметричные системы из-за чего из зачастую используют только
для передачи ключей пользователей, которые затем используются в симметричных
системах шифрования.

\subsection{RSA}
Для обеспечения шифрования в алгоритме RSA используется факт того, что
имея два достаточно больших простых числа можно легко найти их произведение, 
но имея произведение двух простых чисел нет простого способа найти его 
разложение на множители \cite{encyclopedia}. Пусть $n = p \cdot q$ --- целое 
число, представимое в виде произведения
двух больших простых числел $p$ и $q$. Выберем два числа $e$ и $d$ из условия
\[ e \cdot d \equiv 1 (\text{mod } \varphi(n)) \]
где $\varphi(n) = (p - 1) \cdot (q - 1)$ --- значение функции Эйлера от числа
$n$.

Пусть $k = (n, p, q, e, d)$ --- некоторый выбранный ключ, который состоит из
открытого ключа $k_o = (n, e)$ и закрытого ключа $k_p = (n, p, q, d)$.
Тогда правила шифрования и расшифрования для некоторого сообщения $M$ и
шифротекста $C$ определяются следующими формулами:
\[ C = E_k(M) = M^e (\text{mod } n), \, D_k(C) = C^d (\text{mod } n) = M\]

Нетрудно продемонстрировать, что сложность нахождения секретного ключа RSA
определяется сложностью факторизации числа $n$. Поэтому для создания ключа
следует использовать достаочно длинные простые числа, на которые также
можно наложить дополнительные требования для усложнения задачи:
\begin{enumerate}
    \item 
        Числа $p$ и $q$ должны не слишком сильно отличаться друг от друга, но
        и не быть слишком близкими друг к другу;
    \item
        Следует подобрать такие два таких числа, что наибольший общий делитель
        чисел $p - 1$ и $q - 1$ был небольшим (желательно, равным 2);
    \item
        $p$ и $q$ должны быть сильно простыми числами, т. е. следующее 
        число имеет большой простой делитель и предыдущее число тоже имеет
        такой большой простой делитель $s$, что $s - 1$ также обладает
        достаточно большим простым делителем.
\end{enumerate}

\section{Электронная цифровая подпись}
Цифровая подпись является некоторым числом, которое зависит от исходного 
сообщения и некоторого закрытого ключа. С помощью цифровой подписи можно
решить три важных задачи при обмене сообщениями:
\begin{itemize}
    \item аутентификация источника сообщения;
    \item установление целостности сообщения;
    \item обеспечение невозможности отказа от факта подписи конкретного сообщения.
\end{itemize}

Надёжность схемы цифровой подписи определяется сложностью выполнения следующих
задач:
\begin{itemize}
    \item 
        Подделка подписи (нахождение значения подписи под заданным
        сообщением лицом, не являющимся владельцем секретного ключа);
    \item 
        Создание подписанного сообщения (нахождения хотя бы одного сообщения
        с правильным значением подписи);
    \item Подмена сообщения (подбор двух различных сообщений с одинаковой подписью).
\end{itemize}

Для создания цифровой подписи можно использовать алгоритмы шифрования с открытым
ключом, так как они обеспечивают невозможность подделки сообщения. Предположим, 
что имеется некоторая пара преобразований $(E_k, D_k)$, где $E_k$
зависит от открытого ключа $k_o$, а $D_k$ --- от закрытого $k_p$. Цифровую
подпись $S$ сообщения $M$ можно вычислить с помощью преобразования $D_k(M) = S$.
Таким образом, полученную подпись любой другой пользователь сможет проверить
с помощью известного ему преобразования $E_k(S) = M$ и получить исходное
сообщение.

Проблема такого подхода заключается в том, что для такой системы подписи не
выполняется требование невозможности создания подписанного сообщения,
так как для любого $S_1$ любой пользователь может вычислить $M_1 = E_k(S_1)$
и получить подписанное сообщение. 

Для решения этой проблемы зачастую в систему подписи также включается некоторая
хэш-функция $h$, которая перед подписью применяется к сообщению. 
Но так как по хэшу сообщения невозможно восстановить само сообщение, подпись 
должна отправляться вместе с сообщением. Создание подписи по такой схеме 
удовлетворяет всем трём требованиям для надёжности цифровой подписи. 
\cite{alferov}

\subsection{Правовая сторона применения ЭЦП в России}
В российском Федеральном Законе \textnumero 63 электронные цифровые подписи
подразделяются на три вида:
\begin{enumerate}
    \item 
        Простая электронная подпись --- подпись, которая с помощью определённых
        криптографических протоколов позволяет подтвердить факт формирования
        подписи определённым лицом;
    \item 
        Неквалифицированная электронная подпись --- подпись, которая получена
        в результате криптографического преобразования информации с
        использованием ключа электронной подписи, позволяет определить лицо,
        подписавшее электронный документ, позволяет обнаружить факт внесения
        изменений в документ после его подписи;
    \item 
        Квалифицированная электронная подпись --- подпись, которая соответствует
        всем техническим признакам неквалифицированной электронной подписи, но
        при этом также имеет ключ проверки электронной подписи в 
        квалифицированном сертификате, а также создана при помощи средств
        электронной подписи, получивших подтверждение соответствия требованиям,
        установленных в \textnumero 63-ФЗ.
\end{enumerate}

Электронные документы считаются равнозначными документам на бумажном носителе, 
подписанном собственноручной подписью, если они подписаны квалифицированной 
электронной подписью и соответствуют остальным требованиям \textnumero 63-ФЗ.

Таким образом, электронные цифровые подписи, применяемые в разнообразных
веб-приложениях для защиты от компрометации канала связи обычно не имеют 
правовой силы на территории Российской Федерации.


\section{Разработка системы с применением ЭЦП}
В качестве системы, в которой необходимо применение электронной цифровой подписи
мною была выбрана система мгновенного обмена сообщениями (чат). Для разработки
данной системы я выбрал язык программирования Go, в стандартной библиотеке
которого присутствуют все криптографические функции, необходимые для реализации
данной системы. Для упрощения работы с чатом также были использованы две
сторонние библиотеки:
\begin{itemize}
    \item 
        \textbf{fyne.io}, для создания пользовательского интерфейса клиентской
        части системы;
    \item Реализация драйвера базы данных \textbf{sqlite3} для языка Go.
\end{itemize}

\subsection{Используемый алгоритм цифровой подписи}
В качестве алгоритма шифрования с открытым ключом используется RSA, в качестве
хэш-функции $h$ --- SHA-256, а также в процессе подписи к сообщению применяется
алгоритм Base64.

Алгоритм подписи:
\begin{enumerate}
    \item Генерируются открытый и закрытый ключи шифрования RSA;
    \item Сообщение $M$ преобразуется с помощью алгоритма Base64 в $B_M$; 
    \item Вычисляется хэш $H_M = h(B_M)$;
    \item Хэш зашифровывется с помощью ключа $k_o$: $C_M = E_k(H_M)$;
    \item 
        Полученный шифротекст $C_M$ преобразуется в подпись $S_M$ с помощью
        алгоритма Base64.
\end{enumerate}

Для отправки сообщения $M$ на сервер к нему дополнительно приставляется
его подпись. Данные, отправляемые на сервер состоят из трёх частей,
конкатенируемых перед отправкой:
\begin{itemize}
    \item Преобразованное с помощью алгоритма Base64 сообщение $M$;
    \item Знак точки;
    \item Цифровая подпись $S_M$.
\end{itemize}

При получении сообщения от клиента, сервер проверяет его подпись. Алгоритм
проверки подписи:
\begin{enumerate}
    \item Полученное сообщение разделяется на $B_M$ и $S_M$;
    \item $S_M$ декодируются с помощью алгоритма Base64 в шифротекст $C_M$;
    \item Вычисляется хэш $H_M = h(B_M)$;
    \item Шифротекст $C_M$ расшифровывается с помощью ключа $h_p$ в сообщение $H_S$;
    \item Подпись считается валидной в случае, если $H_S = H_M$.
\end{enumerate}

\subsection{Реализация сервера приложения}
Сервер приложения принимает сетевые запросы по прикладному протоколу $HTTP$.
В сервере реализованы следующие точки входа:
\begin{itemize}
    \item 
        \texttt{/api/register}: с помощью данной точки пользователь может внести
        свой ключ проверки подписи в систему;
    \item 
        \texttt{/api/sendMessage}: все сообщения, которые сервер должен сохранить
        в своей базе данных и передать другим пользователям системы отправляются
        на эту точку входа;
    \item
        \texttt{/api/pollMessages}: с помощью данной точки входа пользователь
        способен запросить все сообщения, которые пришли на сервер после
        некоторого момента времени (который пользователь указывает в запросе);
    \item
        \texttt{/api/getUserKey}: для проверки подписи пришедшего сообщения 
        на стороне клиента, пользователь может запросить ключ другого 
        пользователя, сохранённый на сервере;
    \item
        \texttt{/api/tryAuth}: данная точка входа не выполняет никаких действий,
        и реализована для удобства проверки возможности аутентификации 
        пользователя на сервере (при удачной аутентификации данная точка
        вернёт ответ со статусом HTTP 200, иначе, при провале аутентификации по
        каким-либо причинам, статус будет не равен 200 и клиент может вывести
        предупреждение пользователю).
\end{itemize}

\subsection{Работа с клиентом приложения}
Для начала обмена сообщения с другими ползователями, подключенными к системе
необходимо в неё войти, либо зарегистрироваться. Вход возможен только при
наличии сгенерированного ключа для подписи, поэтому при первом запуске
следует нажать на кнопку <<Зарегистрироваться>> (рис. \ref{fig:start}).
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{screenshots/start.png}
    \caption{Экран при запуске приложения}
    \label{fig:start}
\end{figure}

При регистрации (и входе) необходимо ввести URL сервера, к которому должен
присоединиться клиент и своё имя (рис. \ref{fig:register}). После этого 
необходимо нажать на кнопку <<Сгенерировать ключи подписи>>.
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{screenshots/register.png}
    \caption{Окно регистрации}
    \label{fig:register}
\end{figure}

Далее можно сохранить ключ в любом удобном месте с любым именем (рис. \ref{fig:key}).
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{screenshots/key.png}
    \caption{Выбор места для сохранения ключа}
    \label{fig:key}
\end{figure}

После выбора места сохранения ключа необходимо нажать на кнопку 
<<Зарегистрироваться>>, после чего клиент проверит возможность совершить
это действие с указанными данными. Если клиент не может соединиться с сервером,
либо на сервере уже зарегистрирован пользователь с таким именем, то клиент
выведет окно с ошибкой (рис. \ref{fig:error}).
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{screenshots/error.png}
    \caption{Ошибка при регистрации}
    \label{fig:error}
\end{figure}

Если клиенту удалось соединиться с сервером и успешно пройти все проверки, то
для пользователя откроется окно чата, в котором можно написать своё сообщение
в поле снизу. Для отправки сообщения необходимо нажать на кнопку <<Отправить>>
(рис. \ref{fig:input}).
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{screenshots/input.png}
    \caption{Ввод сообщения}
    \label{fig:input}
\end{figure}

Все сообщения, которые клиент смог получить от сервера отображаются в этом
окне чата (рис. \ref{fig:chat}).
\begin{figure}[H]
    \centering
    \includegraphics[width=0.7\textwidth]{screenshots/chat.png}
    \caption{Окно чата с сообщением}
    \label{fig:chat}
\end{figure}


\conclusion
Для реализации систем электронных цифровых подписей обычно используются
наиболее проверенные криптографически стойкие алгоритмы, которые способны
обеспечить защищённость от компрометации канала связи между пользователями.

Благодаря таким алгоритмам имеется возможность установления безопасного
канала связи даже через Интернет, между людьми, которым сложно физически 
обменяться ключами для проверки подписей.

Но с увеличением мощности вычислительных компьютерных систем и разработкой
квантовых компьютеров некоторые криптографические протоколы находятся
под угрозой потери надёжности и безопасности. Поэтому можно ожидать появления
новых алгоритмов шифрования, хэширования и электронной цифровой подписи,
учитывающих новые разработки в сфере квантовых вычислений.


\printbibliography

\end{document}