From 4894a2a01fb072dc0ebf5133993832fbcfe5244c Mon Sep 17 00:00:00 2001 From: Reto Fritsche Date: Sun, 29 Aug 2021 23:57:01 +0200 Subject: created example, made some succested correction/improvements --- buch/papers/mceliece/funktionsweise.tex | 337 ++++++++++++++++++++++++++++++-- 1 file changed, 322 insertions(+), 15 deletions(-) (limited to 'buch/papers/mceliece/funktionsweise.tex') diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 7c69b13..b4f00f0 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -25,7 +25,7 @@ und wird anschliessend Bob zugestellt. \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. +und anschliessend durch eine Addition mit einem Fehlervektor $e_n$ einige Bitfehler hinzufügt: \[ c_n\,=\,K_{n,k}\cdot d_k + e_n\,. \] @@ -36,25 +36,25 @@ 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 $K_{n,k}$ mit seinen Ursprungsmatrizen dargestellt. +Um etwas Transparenz in diese Prozedur zu bringen, wird der öffentliche Schlüssel $K_{n,k}$ 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 + &= 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. +indem das Codewort mit dessen Inversen $P_n^{-1}$ multipliziert wird: \begin{align*} c_{n}''\,=\,P_n^{-1}\cdot 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 \\ + &= 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 Fehlervektor $e_n$ multipliziert mit einer Permutationsmatrix -wiederum einen gleichwertigen, zufälligen Fehlervektor $e_n'$ ergibt. +wiederum einen zufälligen Fehlervektor gleicher Länge und mit der gleichen Anzahl Fehlern $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 | \, - e'_n\,=\,P_n^{-1}\cdot e_n + &=\,G_{n,k}\cdot S_{k}\cdot d_k + e'_n \quad \text{mit} \quad + e'_n\,=\,P_n^{-1}\cdot e_n\,. \end{align*} Dank des fehlerkorrigierenden Codes, der durch die implizite Multiplikation mittels $G_{n,k}$ auf die Daten angewendet wurde, können nun die Bitfehler, verursacht durch den Fehlervektor $e'_n$, @@ -62,22 +62,329 @@ 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, -hängt vom verwendeten Linearcode ab. +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 + &=S_{k}\cdot d_k\,. \end{align*} Zum Schluss wird das inzwischen fast entschlüsselte Codewort $c'_k$ mit der inversen der zufälligen Binärmatrix $S^{-1}$ multipliziert, -womit der Inhalt der ursprünglichen Nachricht nun wiederhergestellt wurde. +womit der Inhalt der ursprünglichen Nachricht nun wiederhergestellt wurde: \begin{align*} c_{k}'\,&=S_{k}\cdot d_k \quad | \cdot S_k^{-1}\\ d'_{k}\,=\,S_{k}^{-1} \cdot c'_k&=S_{k}^{-1} \cdot S_{k}\cdot d_k\\ - &=d_k + &=d_k\,. \end{align*} \subsection{Beispiel} +Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden. +\begin{itemize} + \item Daten- und Fehlervektor + \begin{itemize} + \item[] + \[d_4= + \begin{pmatrix} + 1\\ + 1\\ + 1\\ + 0 + \end{pmatrix} + ,\, + e_7= + \begin{pmatrix} + 0\\ + 0\\ + 1\\ + 0\\ + 0\\ + 0\\ + 0 + \end{pmatrix} + \] + \end{itemize} + \item Private Matrizen: + \begin{itemize} + \item[] + \[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}, + \] + \item[] + \[ + 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},\, + \] + \item[] + \[ + P_7= + \begin{pmatrix} + 0 & 1 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 0 & 1\\ + 1 & 0 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 1 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 1 & 0\\ + 0 & 0 & 1 & 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} + \] + \end{itemize} + \item Öffentlicher Schlüssel: + \begin{itemize} + \item[] + \begin{align*} + K_{7,4}&=P_{7}\cdot G_{7,4}\cdot S_{4}=\\ + \begin{pmatrix} %k + 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} + &= + \begin{pmatrix} %p + 0 & 1 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 0 & 1\\ + 1 & 0 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 1 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 1 & 0\\ + 0 & 0 & 1 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 1 & 0 & 0 + \end{pmatrix} + \cdot + \begin{pmatrix} %g + 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} + \cdot + \begin{pmatrix} %s + 0 & 0 & 1 & 1\\ + 0 & 0 & 0 & 1\\ + 0 & 1 & 0 & 1\\ + 1 & 0 & 0 & 1 + \end{pmatrix} + \end{align*} + \end{itemize} + \item Verschlüsselung: + \begin{itemize} + \item[] + \begin{align*} + c_7&=K_{7,4}\cdot d_4 + e_7=\\ + \begin{pmatrix} %c + 1\\ + 1\\ + 0\\ + 1\\ + 1\\ + 1\\ + 1 + \end{pmatrix} + &= + \begin{pmatrix} %k + 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} + \cdot + \begin{pmatrix} %d + 1\\ + 1\\ + 1\\ + 0 + \end{pmatrix} + + + \begin{pmatrix} %e + 0\\ + 0\\ + 1\\ + 0\\ + 0\\ + 0\\ + 0 + \end{pmatrix} + \end{align*} + \end{itemize} + \item Entschlüsselung (Permutation rückgängig machen): + \begin{itemize} + \item[] + \begin{align*} + c_{7}''&=P_7^{-1}\cdot c_7=\\ + \begin{pmatrix} %c'' + 0\\ + 1\\ + 1\\ + 1\\ + 1\\ + 1\\ + 1 + \end{pmatrix} + &= + \begin{pmatrix} %p^-1 + 0 & 0 & 1 & 0 & 0 & 0 & 0\\ + 1 & 0 & 0 & 0 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 1 & 0\\ + 0 & 0 & 0 & 1 & 0 & 0 & 0\\ + 0 & 0 & 0 & 0 & 0 & 0 & 1\\ + 0 & 0 & 0 & 0 & 1 & 0 & 0\\ + 0 & 1 & 0 & 0 & 0 & 0 & 0 + \end{pmatrix} + \cdot + \begin{pmatrix} %c + 1\\ + 1\\ + 0\\ + 1\\ + 1\\ + 1\\ + 1 + \end{pmatrix} + \end{align*} + \end{itemize} + \item Entschlüsselung (Bitfehlerkorrektur mit Linearcode): + \begin{itemize} + \item[] + \begin{align*} + c_{7}'\,&=\text{Linear-Code-Decoder($c''_7$)}=\\ + \begin{pmatrix} %c' + 1\\ + 0\\ + 1\\ + 1 + \end{pmatrix} + &=\text{Linear-Code-Decoder} + \begin{pmatrix} + 0\\ + 1\\ + 1\\ + 1\\ + 1\\ + 1\\ + 1 + \end{pmatrix} + \end{align*} + \end{itemize} + \item Entschlüsselung (Umkehrung des $S_k$-Matrix-Effekts): + \begin{itemize} + \item[] + \begin{align*} + d'_{4}&=S_{4}^{-1} \cdot c'_4 \,(= d_4)\\ + \begin{pmatrix} + 1\\ + 1\\ + 1\\ + 0 + \end{pmatrix} + &= + \begin{pmatrix} %s^-1 + 0 & 1 & 0 & 1\\ + 0 & 1 & 1 & 0\\ + 1 & 1 & 0 & 0\\ + 0 & 1 & 0 & 0\\ + \end{pmatrix} + \cdot + \begin{pmatrix} %c' + 1\\ + 0\\ + 1\\ + 1 + \end{pmatrix} + \end{align*} + \end{itemize} +\end{itemize} -TODO: --alle Beispielmatrizen- und Vektoren hierhin zügeln, numerisches Beispiel kreieren\\ --erläutern des 7/4-codes (ja/nein)? \ No newline at end of file + +\subsubsection{7/4-Code} +Bem 7/4-Code handelt es sich um einen linearen Code, +der ein Bitfehler korrigieren kann. +Es gibt unterschiedliche Varianten zum Erzeugen eines 7/4-Codes, +wobei der hier verwendete Code mithilfe des irreduziblen Generator-Polynoms $P_g = x^3 +x + 1$ generiert wird. +Somit lässt sich das Code-Polynom $P_c$ berechnen, indem das Daten-Polynom $P_d$ mit dem Generatorpolynom $P_g$ multipliziert wird: +\[ + P_c=P_g \cdot P_d\,. +\] +Damit diese Multiplikation mit Matrizen ausgeführt weredn kann, werden die Polynome in Vektoren abgefüllt: +\[ + P_g = \textcolor{red}{1}\cdot x^0 + \textcolor{blue}{1}\cdot x^1 + \textcolor{green}{0}\cdot x^2 + \textcolor{orange}{1}\cdot x^3 \implies + [\textcolor{red}{1}, \textcolor{blue}{1} ,\textcolor{green}{0}, \textcolor{orange}{1}] = g_4\,. +\] +Auch das Datenpolynom wird mit einem Vektor dargestellt: $P_d = d_0 \cdot x^0 + d_1 \cdot x^1 + d_2 \cdot x^2 + d_3 \cdot x^3 \implies [d_0, d_1, d_2, d_3] = d_4$\,. +Der Vektor $g_4$ wird nun in die sogenannte Generatormatrix $G_{7,4}$ gepakt, +sodass die Polynommultiplikation mit $d_4$ mittels Matrixmultiplikation realisiert werden kann: + +\[ + c_7=G_{7,4} \cdot d_4= + \begin{pmatrix} + \textcolor{red}{1} & 0 & 0 & 0 \\ + \textcolor{blue}{1} & \textcolor{red}{1} & 0 & 0 \\ + \textcolor{green}{0} & \textcolor{blue}{1} & \textcolor{red}{1} & 0 \\ + \textcolor{orange}{1} & \textcolor{green}{0} & \textcolor{blue}{1} & \textcolor{red}{1} \\ + 0 & \textcolor{orange}{1} & \textcolor{green}{0} & \textcolor{blue}{1} \\ + 0 & 0 & \textcolor{orange}{1} & \textcolor{green}{0} \\ + 0 & 0 & 0 & \textcolor{orange}{1} + \end{pmatrix} + \begin{pmatrix} + d_0\\ + d_1\\ + d_2\\ + d_3 + \end{pmatrix} + = + \begin{pmatrix} + c_0\\ + c_1\\ + c_2\\ + c_3\\ + c_4\\ + c_5\\ + c_6\\ + \end{pmatrix}\,. +\] +Beim nun entstandenen Code-Vektor $c_7=[c_0, ..., c_6]$ entsprechen die Koeffizienten dem dazugehörigen Code-Polynom $P_c=c_0\cdot x^0+...+c_6\cdot x^6$ +Aufgrund der Multiplikation mit dem Generatorpolynom $P_g$ lässt sich das Codewort auch wieder restlos durch $P_g$ dividieren. +Wird dem Codewort nun einen Bitfehler hinzugefügt, entsteht bei der Division durch $P_g$ einen Rest. +Beim gewählten Polynom beträgt die sogenannte Hamming-Distanz drei, das bedeutet, +dass vom einen gültigen Codewort zu einem anderen gültigen Codewort drei Bitfehler vorkommen müssen. +Somit ist es möglich, auf das ursprüngliche Bitmuster zu schliessen, solange maximal ein Bitfehler vorhanden ist. +Jeder der möglichen acht Bitfehler führt bei der Divison zu einem anderen Rest, +womit das Dazugehörige Bit identifiziert und korrigiert werden kann, +indem beispielsweise die Bitfehler mit dem Dazugehörigen Rest in der sogenannten Syndrom-Tabelle hinterlegt werden. -- cgit v1.2.1