diff options
| -rw-r--r-- | buch/papers/mceliece/aufbau.tex | 56 | ||||
| -rw-r--r-- | buch/papers/mceliece/funktionsweise.tex | 86 |
2 files changed, 102 insertions, 40 deletions
diff --git a/buch/papers/mceliece/aufbau.tex b/buch/papers/mceliece/aufbau.tex index 0ee95fa..f8533d6 100644 --- a/buch/papers/mceliece/aufbau.tex +++ b/buch/papers/mceliece/aufbau.tex @@ -49,7 +49,7 @@ Beispielsweise \] \subsection{Linear-Code-Generatormatrix $G_{n,k}$ -\label{mceliece:subsection:g_m}} +\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, @@ -76,7 +76,7 @@ Beispiel \] \subsection{Permutations-Matrix $P_n$ -\label{mceliece:subsection:p_m}} +\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 @@ -106,12 +106,33 @@ Beispiel \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:p_m}} +\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 zu korrigieren vermag. +wie die Anzahl Fehler, die der Linearcode der Generatormatrix $G_{n,k}$ zu korrigieren vermag. Beispiel \[ @@ -127,23 +148,10 @@ Beispiel \end{pmatrix} \] -\subsection{Public-Key $K_{n,k}$ -\label{mceliece:subsection:k_m}} -Der öffentliche Schlüssel, welcher zum Verschlüsseln verwendet wird, -berechnet sich mit -\[ - 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} -\]
\ No newline at end of file +\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 diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 3dfc963..e412313 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -6,22 +6,76 @@ \section{Funktionsweise \label{mceliece:section:funktionsweise}} \rhead{Funktionsweise} -Um den Ablauf des Datenaustausches mittels M +Um den Ablauf des Datenaustausches mittels McEliece-Verschlüsselung zu erläutern, +wird ein Szenario verwendet, +bei dem Bob an Alice eine verschlüsselte Nachticht über ein öffentliches Netzwerk zukommen lässt. -\subsection{De finibus bonorum et malorum -\label{mceliece:subsection:bonorum}} -At vero eos et accusamus et iusto odio dignissimos ducimus qui -blanditiis praesentium voluptatum deleniti atque corrupti quos -dolores et quas molestias excepturi sint occaecati cupiditate non -provident, similique sunt in culpa qui officia deserunt mollitia -animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis -est et expedita distinctio. Nam libero tempore, cum soluta nobis -est eligendi optio cumque nihil impedit quo minus id quod maxime -placeat facere possimus, omnis voluptas assumenda est, omnis dolor -repellendus. Temporibus autem quibusdam et aut officiis debitis aut -rerum necessitatibus saepe eveniet ut et voluptates repudiandae -sint et molestiae non recusandae. Itaque earum rerum hic tenetur a -sapiente delectus, ut aut reiciendis voluptatibus maiores alias -consequatur aut perferendis doloribus asperiores repellat. +\subsection{Vorbereitung +\label{mceliece:section:vorbereitung}} +Damit der Nachrichtenaustausch stattfinden kann, muss Alice (Empfängerin) +zuerst ein Schlüsselpaar definieren. +Dazu erstellt sie die einzelnen Matrizen $S_k$, $G_{n,k}$ und $P_n$. +Diese drei einzelnen Matrizen bilden den privaten Schlüssel von Alice +und sollen geheim bleiben. +Der öffentliche Schlüssel $K_{n,k}$ hingegen berechnet sich +aus der Multiplikation der privaten Matrizen\ref{mceliece:subsection:k_nk} +und wird anschliessend Bob, zugestellt. +\subsection{Verschlüsselung +\label{mceliece:section:verschl}} +Bob berechnet nun die verschlüsselte Nachricht $c_n$, indem er seine Daten $d_k$ +mit dem öffentlichen Schlüssel $K_{n,k}$ von Alice multipliziert +und anschliessend durch eine Addition mit einem Fehlervektor $e_n$ einige Bitfehler hinzufügt. +\[ + c_n\,=\,K_{n,k}\cdot d_k + e_n\,. +\] +Dabei wird für jede Nachricht (oder für jedes Nachrichtenfragment) +einen neuen, zufälligen Fehlervektor generiert. +Die verschlüsselte Nachricht $c_n$ wird anschliessend Alice zugestellt. +\subsection{Entschlüsselung +\label{mceliece:section:entschl}} +Alice entschlüsselt die erhaltene Nachricht in mehreren einzelnen Schritten. +Um etwas Transparenz in diese Prozedur zu bringen, wird der öffentliche Schlüssel mit seinen Ursprungsmatrizen dargestellt. +\[ + \begin{align*} + c_n\,&=\,K_{n,k}\cdot d_k + e_n \\ + &= P_{n}\cdot G_{n,k}\cdot S_{k}\cdot d_k + e_n \\ + \end{align*} +\] +Zuerst wird der Effekt der Permutationsmatrix rückgängig gemacht, +indem das Codewort mit dessen Inversen $P_n^{-1}$ multipliziert wird. + +\[ + \begin{align*} + c_{n}''\,=\,P_n^{-1}\cdot \hat{c}_n\,&= P_n^{-1}\cdot P_{n}\cdot G_{n,k}\cdot S_{k}\cdot d_k + P_n^{-1}\cdot e_n \\ + &= G_{n,k}\cdot S_{k}\cdot d_k + P_n^{-1}\cdot e_n \\ + \end{align*} +\] + +Eine weitere Vereinfachung ist nun möglich, +weil $P_n^{-1}$ einerseits auch eine gewöhnliche Permutationsmatrix ist +und andererseits ein zufälliger Fehlerwektor $e_n$ multipliziert mit einer Permutationsmatrix +wiederum einen gleichwertigen, zufälligen Fehlerwektor $e_n'$ ergibt. +\[ + \begin{align*} + c_{n}''\,&=\,G_{n,k}\cdot S_{k}\cdot d_k + P_n^{-1}\cdot e_n \\ + &=\,G_{n,k}\cdot S_{k}\cdot d_k + e'_n\quad \quad \quad \quad | \, + e'_n\,=\,P_n^{-1}\cdot e_n + \end{align*} +\] + +Dank des Linearcodes können nun die Bitfehler, verursacht durch den Fehlervektor $e'_n$, +entfernt werden. +Da es sich bei diesem Schritt nicht um eine einfache Matrixmultiplikation handelt, +wird die Operation durch eine Funktion dargestellt. +Wie dieser Decoder genau aufgebaut ist ist, +hängt vom verwendeten Linearcode ab. + +\[ + \begin{align*} + c_{k}'\,&=\text{Linear-Code-Decoder($c''_n$)}\\ + &=\text{Linear-Code-Decoder($G_{n,k}\cdot S_{k}\cdot d_k + e'_n$)}\\ + &=S_{k}\cdot d_k + \end{align*} +\]
\ No newline at end of file |