diff options
Diffstat (limited to 'report/coursework.tex')
| -rw-r--r-- | report/coursework.tex | 498 |
1 files changed, 498 insertions, 0 deletions
diff --git a/report/coursework.tex b/report/coursework.tex new file mode 100644 index 0000000..3821166 --- /dev/null +++ b/report/coursework.tex @@ -0,0 +1,498 @@ +\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} |