diff options
Diffstat (limited to 'buch/papers/mceliece/aufbau.tex')
| -rw-r--r-- | buch/papers/mceliece/aufbau.tex | 160 |
1 files changed, 160 insertions, 0 deletions
diff --git a/buch/papers/mceliece/aufbau.tex b/buch/papers/mceliece/aufbau.tex new file mode 100644 index 0000000..521488d --- /dev/null +++ b/buch/papers/mceliece/aufbau.tex @@ -0,0 +1,160 @@ +% +% einleitung.tex -- Beispiel-File für die Einleitung +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\section{Aufbau\label{mceliece:section:Aufbau}} +\rhead{Aufbau} +Das McEliece-Kryptosystem besteht aus folgenden Elementen: + +\subsection{Datenvektor $d_k$ +\label{mceliece:subsection:d_k}} +In diesem Vektor der Länge $k$ sind die zu verschlüsselnden Daten enthalten. +Beispielsweise +\[d_4= +\begin{pmatrix} + 1\\ + 1\\ + 1\\ + 0 +\end{pmatrix} +\] + +\subsection{Binäre Zufallsmatrix $S_k$ +\label{mceliece:subsection:s_k}} +$S_k$ ist eine Binäre Zufallsmatrix der Grösse $k \times k$. +Auch muss diese Matrix in $\mathbb{F}_2$ invertierbar sein. +Für kleine Matrizen kann durchaus jedes Matrizenelement zufällig generiert werden, +wobei danach mithilfe des Gauss-Algorythmusses deren Inverse bestimmt werden kann. +Da eine solche Matrix möglicherweise singulär ist, muss in diesem Fall eine neue Zufallsmatrix erzeugt werden. +Für grössere Matrizen existieren bessere Methoden, auf welche hier nicht weiter eingegangen wird \cite{mceliece:GenerationRandMatrix}. + +Beispiel: +\[S_4= + \begin{pmatrix} + 0 & 0 & 1 & 1\\ + 0 & 0 & 0 & 1\\ + 0 & 1 & 0 & 1\\ + 1 & 0 & 0 & 1 + \end{pmatrix} +\] + +\[ + S_4^{-1}= + \begin{pmatrix} + 0 & 1 & 0 & 1\\ + 0 & 1 & 1 & 0\\ + 1 & 1 & 0 & 0\\ + 0 & 1 & 0 & 0\\ + \end{pmatrix} +\] + +\subsection{Linear-Code-Generatormatrix $G_{n,k}$ +\label{mceliece:subsection:g_nk}} +Das wichtigste Element des McEliece-Systems ist ein fehlerkorrigierender Code, +der in der Lage ist, $t$ Fehler zu korrigieren. +Im Zusammenhang mit McEliece werden dabei meist Goppa-Codes verwendet, +es können prinzipiell auch andere Codes wie beispielsweise Reed-Solomin verwendet werden, +jedoch besitzen einige Codes Schwachstellen \cite{mceliece:lorenz}. +Das Codieren mit diesem linearen Code kann mithilfe dessen Generatormatrix $G_{n,k}$ erfolgen. +Da es sich um einen fehlerkorrigierenden Code handelt, +wird das Codewort länger als das Datenwort, +es wird also Redundanz hinzugefügt, +um die Fehlerkorrektur möglich zu machen. + +Beispiel +\[ + G_{7,4}= + \begin{pmatrix} + 1 & 0 & 0 & 0\\ + 1 & 1 & 0 & 0\\ + 0 & 1 & 1 & 0\\ + 1 & 0 & 1 & 1\\ + 0 & 1 & 0 & 1\\ + 0 & 0 & 1 & 0\\ + 0 & 0 & 0 & 1 + \end{pmatrix} +\] + +\subsection{Permutations-Matrix $P_n$ +\label{mceliece:subsection:p_n}} +Mit der zufällig generierten Permutationsmatrix $P_n$ wird die Reihenfolge der Bits geändert. +Mit der Inversen $P_n^{-1}$ kann die Bitvertauschung rückgängig gemacht werden. + +Beispiel +\[ + P_7= + \begin{pmatrix} + 0 & 1 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 0 & 1\\ + 0 & 0 & 0 & 0 & 0 & 1 & 0\\ + 0 & 0 & 1 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 1 & 0 & 0 & 0\\ + 1 & 0 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 1 & 0 & 0 + \end{pmatrix} +\] +, +\[ + P_7^{-1}=P_7^t= + \begin{pmatrix} + 0 & 0 & 0 & 0 & 0 & 1 & 0\\ + 1 & 0 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 1 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 1 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 0 & 1\\ + 0 & 0 & 1 & 0 & 0 & 0 & 0\\ + 0 & 1 & 0 & 0 & 0 & 0 & 0 + \end{pmatrix} +\] + +\subsection{Public-Key $K_{n,k}$ +\label{mceliece:subsection:k_nk}} +Der öffentliche Schlüssel, welcher zum Verschlüsseln verwendet wird, +berechnet sich aus den bereits bekannten Matrizen wiefolgt: +\[ + K_{n,k}=P_{n}\cdot G_{n,k}\cdot S_{k}\,. +\] + +Beispiel +\[ + K_{7,4}= + \begin{pmatrix} + 0 & 0 & 1 & 0\\ + 1 & 0 & 0 & 1\\ + 0 & 0 & 1 & 1\\ + 1 & 1 & 1 & 1\\ + 0 & 1 & 0 & 1\\ + 0 & 1 & 0 & 0\\ + 1 & 0 & 0 & 0 + \end{pmatrix} +\] + +\subsection{Fehler-Vektor $e_n$ +\label{mceliece:subsection:e_n}} +Dieser Vektor der Länge $n$ besteht aus $t$ Einsen, welche zufällig innerhalb des Vektors angeordnet sind, +alle anderen Einträge sind Null. +Dieser Fehlervektor besitzt also gleich viele Einer, +wie die Anzahl Fehler, die der Linearcode der Generatormatrix $G_{n,k}$ zu korrigieren vermag. + +Beispiel +\[ + E_7= + \begin{pmatrix} + 0\\ + 0\\ + 1\\ + 0\\ + 0\\ + 0\\ + 0 + \end{pmatrix} +\] + +\subsection{Daten-Vektor $d_k$ +\label{mceliece:subsection:d_k}} +In diesem Vektor der länge $k$ ist die Nachricht (oder einen Teil davon) enthalten. + +\subsection{Code-Vektor $c_n$ +\label{mceliece:subsection:c_n}} +In diesem Vektor der länge $n$ ist die verschlüsselte Nachricht (oder einen Teil davon) enthalten.
\ No newline at end of file |