\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\usepackage{polski}
\usepackage{float}
\usepackage[T1]{fontenc}
\title{Właściwości algorytmu Gaussa}
\author{Damian Krata}
\date{10 Kwietnia 2019}
\usepackage[pscoord]{eso-pic}% The zero point of the coordinate systemis the lower left corner of the page (the default).

\newcommand{\placetextbox}[3]{% \placetextbox{<horizontal pos>}{<vertical pos>}{<stuff>}
  \setbox0=\hbox{#3}% Put <stuff> in a box
  \AddToShipoutPictureFG*{% Add <stuff> to current page foreground
    \put(\LenToUnit{#1\paperwidth},\LenToUnit{#2\paperheight}){\vtop{{\null}\makebox[0pt][c]{#3}}}%
  }%
}%
\begin{document}

\begin{titlepage}
	\begin{center}
	\fontsize{28pt}{34pt}\selectfont
	WOJSKOWA AKADEMIA TECHNICZNA \\
	\fontseries{b}\fontsize{14pt}{20pt}\selectfont
	im. Jarosława Dąbrowskiego
	\vspace*{1.0\baselineskip}

	\fontseries{b}\fontsize{24pt}{20pt}\selectfont
	Wydział Cybernetyki

	\begin{figure}[!ht]
	    \centering
	    \includegraphics{logo_wat.png}
	\end{figure}


	%\vspace*{1\baselineskip}
	\fontseries{m}\fontsize{32pt}{20pt}\selectfont
	Krzywe hipereliptyczne w~kryptologii\\
	\fontseries{m}\fontsize{20pt}{20pt}\selectfont
	\vspace*{1.15\baselineskip}
	%\fontsize{20pt}{15pt}\selectfont
	%sierż. pchor. Damian Krata\\
	%\vspace*{1.15\baselineskip}
	\fontseries{b}\fontsize{15pt}{18pt}\selectfont
	ECMQV \\
	\end{center}

	\vspace*{2\baselineskip}
	\placetextbox{0.25}{0.25}{Autorzy}
	\placetextbox{0.25}{0.23}{inż. Tomasz Czechowski}
	\placetextbox{0.25}{0.21}{sierż. pchor. Damian Krata}

	\placetextbox{0.75}{0.25}{Prowadzący}
	\placetextbox{0.75}{0.23}{mjr Tomasz Kijko}


	\placetextbox{0.5}{0.15}{Warszawa 2019}
\end{titlepage}
\section{Opis protokołu}

\hspace*{5mm}\textit{\textbf{Eliptic Curve Menezes–Qu–Vanstone (Eliptic Curve MQV)}} jest protokołem uzgadniania klucza oparty na schemacie Diffie'go-Hellman'a, działający w grupie krzywej eliptycznej. Pierwotnie został zaproponowany w 1995 roku.\\

Alicja posiada parę kluczy $(A, a)$ z $A$ jej kluczem publicznym i $a$ jej kluczem prywatnym, takimi że $A = aP$, gdzie $P$ jest punktem na krzywej eliptycznej. Analogicznie, Bob posiada parę kluczy $(B, b)$ z $B$ jego kluczem publicznym i $b$ jego kluczem prywatnym.\\

Niech $R = (x, y)$ będzie punktem na krzywej eliptycznej. Wtedy $\overline{R} = (x \bmod 2^L) + 2^L$, gdzie $L = \lceil \frac{\lfloor log_2{n} \rfloor + 1}{2} \rceil$ i $n$ jest rzędem punktu $P$. Czyli $\overline{R}$ to pierwsze $L$ bitów pierwszej współrzędnej punktu $R$.\\

\begin{enumerate}
\item Alicja generuje parę kluczy $(X, x)$ generując losowo $x$ i obliczając $X = xP$, gdzie $P$ jest punktem na krzywej eliptycznej.
\item Bob generuje parę kluczy $(Y, y)$ w ten sam sposób jak Alicja.
\item Alicja oblicza $S_a = x + \overline{X}a$ modulo $n$ i wysyła $X$ do Boba.
\item Bob oblicza $S_b = y + \overline{Y}b$ modulo $n$ i wysyła $Y$ do Alicji.
\item Alicja oblicza $K = h \cdot S_a(Y + \overline{Y}B)$, a Bob oblicza $K = h \cdot S_b(X + \overline{X}A)$, gdzie $h$ jest kofaktorem krzywej eliptycznej.
\item Komunikacja sekretu $K$ zakończyła się powodzeniem. Klucz dla algorytmu symetrycznego można uzyskać z $K$.
\end{enumerate}

\section{Dowód poprawności}
\begin{itemize}
\item Bob oblicza: \\ $K = h \cdot S_b(X + \overline{X}A) = h \cdot S_b(xP + \overline{X}aP) = h \cdot S_b(x + \overline{X}a)P = h \cdot S_bS_aP$
\item Alicja oblicza: \\ $K = h \cdot S_a(Y + \overline{Y}B) = h \cdot S_a(yP + \overline{Y}bP) = h \cdot S_a(y + \overline{Y}b)P = h \cdot S_bS_aP$
\item Stąd sekrety $K$ Alicji i Boba są takie same z $K = h \cdot S_bS_aP$.
\end{itemize}

\section{Uwagi dotyczące bezpieczeństwa}
\begin{itemize}
\item Pary kluczy długoterminowych $(A, a)$ oraz $(B, b)$ mają na celu zabezpieczyć przed atakiem \textit{\textbf{Man in the middle}}.
\item Pary kluczy $(X, x)$ oraz $(Y, y)$ mają na celu zapewnić unikalność sesji uzgadniania sekretu.
\end{itemize}

\section{Parametry krzywej eliptycznej}
\begin{itemize}
\item $y^2 = x^3 + ax + b$, $a = 0$ i $b = 7$ (Secp256k1, Bitcoin)
\item $p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFF\\FFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F_{hex}$
\item punkt $P=(79BE667EF9DCBBAC55A06295CE870B07029BFC\\DB2DCE28D959F2815B16F81798_{hex},483ADA7726A3C4655DA\\4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8_{hex})$
\item rząd $n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAA\\EDCE6AF48A03BBFD25E8CD0364141_{hex}$ punktu $P$
\item kofaktor $h = 1$
\end{itemize}

\section{Opis implementacji}
Implementacja została wykonana w języku C++ z wykorzystaniem oprogramowania \textit{\textbf{Qt Creator}} oraz biblioteki dużych liczb \textit{\textbf{GMP}}. Komunikacja pomiędzy Alicją, a Bobem odbywa się za pomocą socketów oraz protokołui UDP. Wybór protokołu został podyktowany wykorzystaniem jednej jednostki obliczeniowej, przez co straty wynikające z transmisji można było pominąć.

W celu realizacji potoku obliczeń powstała arytmetyka na krzywej:
\begin{enumerate}
    \item funkcja curve\_init - za pomocą tej funkcji, na początku działania programu, następuje wczytanie parametrów krzywej i klucza prywatnego osoby wywołującej program. Ponadto następuje wpisanie trwałego klucza publicznego osoby z którą się komunikujemy, poprzez odczytanie tych danych z innego pliku. Pliki wejściowe do funkcji podawane są w momencie uruchamiania programu.
    \item funkcja add - reprezentuje ona dodawanie punktów na krzywej eliptycznej. Warto w tym miejscu zauważyć, że dodawanie to może się odbywać na krzywej o współczynniku przy x równym zero.
    \item funkcja quick\_add - realizuje szybkie liczenie krotności punktu. Działa podobnie do algorytmu szybkiego potęgowania.
    \item funkcja generate\_key - tworzy klucze tymczasowe użytkowników, które następnie wysyłane są za pośrednictwem sieci.
    \item funkcja R\_hat - zwraca wartość oznaczoną w protokole jako R z daszkiem.
    \item funkcja S i K - realizują kroki algorytmu zgodnie z przedstawionymi powyżej wzorami.
    \item funkcja wait - wprowadza element dydaktyczny do implementacji, nakazując wciśnięcie klawisza ENTER w celu dalszego obliczania protokołu. Dzięki tej funkcji, wszystkie kroki algorytmu wykonywane są zgodnie z wiedzą użytkownika.
\end{enumerate}
\subsection{Uruchomienie programu}
\begin{figure}[H]
\begin{center}
    \includegraphics[width=\textwidth]{1.png}
    \caption{Pliki niezbędne do uruchomienia programu.}
    \label{fig:uruchomienie}
\end{center}
\end{figure}
\hspace*{5mm}W celu uruchomienia programu, w folderze zawierającym plik wykonywalny muszą znajdować się dwa dodatkowe pliki tekstowe. Jeden odpowiedzialny za przechowywanie klucza tajnego użytkownika wraz z parametrami krzywej oraz drugi przechowujący klucz publiczny osoby, z którą chcemy nawiązać kontakt, również wraz z parametrami krzywej. Parametry krzywej są zapisane heksadecymalnie, natomiast klucze decymalnie.

Plik z kluczem prywatnym w kolejnych liniach składa się z:
\begin{enumerate}
\item liczba pierwsza $p$.
\item współczynnik $a$ krzywej.
\item współczynnik $b$ krzywej.
\item współrzędna $P_x$ punktu $P$.
\item współrzędna $P_y$ punktu $P$.
\item rząd $n$ punktu $P$.
\item kofaktor $h$ krzywej.
\item klucz prywatny.
\end{enumerate}

Plik z kluczem publicznym w kolejnych liniach składa się z:
\begin{enumerate}
\item liczba pierwsza $p$.
\item współczynnik $a$ krzywej.
\item współczynnik $b$ krzywej.
\item współrzędna $P_x$ punktu $P$.
\item współrzędna $P_y$ punktu $P$.
\item rząd $n$ punktu $P$.
\item kofaktor $h$ krzywej.
\item klucz publiczny $A_x$.
\item klucz publiczny $A_y$.
\end{enumerate}

Uruchomienie wymaga wpisania w linię komend:\\
$./nazwa\_programu$  $klucz\_prywatny.txt$  $klucz\_publiczny.txt$, gdzie\\ $klucz\_prywatny.txt$ jest plikiem zawierającym klucz prywatny użytkownika, a $klucz\_publiczny.txt$ plikiem zawierającym klucz publiczny osoby, z którą chcemy nawiązać kontakt. Przykładowe uruchomienie:

\begin{figure}[H]
\begin{center}
    \includegraphics[width=\textwidth]{2.png}
    \caption{Uruchomienie programów z wiersza poleceń.}
    \label{fig:uruchomienie_2}
\end{center}
\end{figure}
Jak widzimy na rysunku nr \ref{fig:uruchomienie_2}, w celu uruchomienia np. programu realizującego potok obliczeniowy dla Alice, należy jako parametry podać pliki alice.txt oraz bob.txt.
\subsection{Etapy działania programu}
Kolejne etapy działania programu realizowane są następująco:
\begin{figure}[H]
\begin{center}
    \includegraphics[width=\textwidth]{3.png}
    \caption{Wprowadzenie i wypisanie na ekran parametrów krzywej.}
    \label{fig:uruchomienie_3}
\end{center}
\end{figure}
\begin{figure}[H]
\begin{center}
    \includegraphics[width=\textwidth]{4.png}
    \caption{Przykładowy potok dla Alice.}
    \label{fig:uruchomienie_4}
\end{center}
\end{figure}
\begin{figure}[H]
\begin{center}
    \includegraphics[width=\textwidth]{5.png}
    \caption{Przykładowy potok dla Boba.}
    \label{fig:uruchomienie_5}
\end{center}
\end{figure}
\begin{figure}[H]
\begin{center}
    \includegraphics[width=\textwidth]{6.png}
    \caption{Zakończenie pracy dla Alice.}
    \label{fig:uruchomienie_6}
\end{center}
\end{figure}

Zgodnie z rysunkiem nr \ref{fig:uruchomienie_5} oraz \ref{fig:uruchomienie_6} widzimy, że uzgodnione przez Alicję i Boba klucze są takie same. Mogą one stanowić podstawę dla funkcji uzgadniania kluczy (ang. \textit{Key Derivation Function}) i stanowić początek dla szyfrowania za pomocą np. algorytmu blokowego.






\begin{thebibliography}{9}
\bibitem{fips}
Phillip Rogaway, Mihir Bellara, Dan Boneh
Evaluation of Security Level of Cryptography
ECMQVS (from SEC 1)
\textit{https://www.ipa.go.jp/security/enc/CRYPTREC/fy15/doc/1069\_ks\-ecmqv.pdf}. 2019.

\end{thebibliography}










\end{document}