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 From 9ef53904ccf44f3c04bda08610cccb30fee47e50 Mon Sep 17 00:00:00 2001 From: Reto Fritsche Date: Tue, 31 Aug 2021 22:49:58 +0200 Subject: some corrections --- buch/papers/mceliece/funktionsweise.tex | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'buch/papers/mceliece/funktionsweise.tex') diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index b4f00f0..5aceb24 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -71,10 +71,12 @@ hängt vom verwendeten Linearcode ab: 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: \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\,. \end{align*} +Möchte ein Angreifer die verschlüsselte Nachricht knacken, muss dieser die drei privaten Matrizen $S_k$, $G_{n,k}$ und $P_n$ kennen. +Aus dem Öffentlichen Schlüssel lassen sich diese nicht rekonstruieren +und eine systematische Analyse der Codeworte wird durch das Hinzufügen von zufälligen Bitfehlern zusätzlich erschwert. \subsection{Beispiel} Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden. @@ -303,7 +305,7 @@ Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden \end{pmatrix} \end{align*} \end{itemize} - \item Entschlüsselung (Umkehrung des $S_k$-Matrix-Effekts): + \item Entschlüsselung (Umkehrung des $S_4$-Matrix-Effekts): \begin{itemize} \item[] \begin{align*} -- cgit v1.2.1 From 0d5fb702bb57294fbd9dda7aab4b76efebed6c22 Mon Sep 17 00:00:00 2001 From: Reto Date: Tue, 31 Aug 2021 23:41:43 +0200 Subject: added syndrome table --- buch/papers/mceliece/funktionsweise.tex | 41 ++++++++++++++++++++++++--------- 1 file changed, 30 insertions(+), 11 deletions(-) (limited to 'buch/papers/mceliece/funktionsweise.tex') diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 5aceb24..58337c8 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -75,7 +75,7 @@ womit der Inhalt der ursprünglichen Nachricht nun wiederhergestellt wurde: &=d_k\,. \end{align*} Möchte ein Angreifer die verschlüsselte Nachricht knacken, muss dieser die drei privaten Matrizen $S_k$, $G_{n,k}$ und $P_n$ kennen. -Aus dem Öffentlichen Schlüssel lassen sich diese nicht rekonstruieren +Aus dem öffentlichen Schlüssel lassen sich diese nicht rekonstruieren und eine systematische Analyse der Codeworte wird durch das Hinzufügen von zufälligen Bitfehlern zusätzlich erschwert. \subsection{Beispiel} @@ -336,21 +336,21 @@ Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden \subsubsection{7/4-Code} -Bem 7/4-Code handelt es sich um einen linearen Code, +Beim 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: +Somit lässt sich das Code-Polynom $P_c$ berechnen, indem das Daten-Polynom $P_d$ mit dem Generatorpolynom $P_g$ multipliziert wird (Codiervorgang): \[ P_c=P_g \cdot P_d\,. \] -Damit diese Multiplikation mit Matrizen ausgeführt weredn kann, werden die Polynome in Vektoren abgefüllt: +Damit diese Multiplikation mit Matrizen ausgeführt werden kann, werden die Polynome in mit Vektoren dargestellt: \[ 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, +Auch das Daten-Polynom 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}$ gepackt, sodass die Polynommultiplikation mit $d_4$ mittels Matrixmultiplikation realisiert werden kann: \[ @@ -381,12 +381,31 @@ sodass die Polynommultiplikation mit $d_4$ mittels Matrixmultiplikation realisie 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$ +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. +dass vom einen gültigen Codewort zu einem anderen gültigen Codewort drei Bitfehler auftreten 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. +Jeder der möglichen acht Bitfehler führt bei der Division 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 (Tabelle \ref{mceliece:tab:syndrome}) hinterlegt werden. +\begin{table} + \begin{center} + \begin{tabular}{l|c} + \hline + Syndrom (Divisionsrest) &korrespondierender Bitfehler\\ + \hline + 1 ($[1,0,0]$) &$[1,0,0,0,0,0,0]$\\ + 2 ($[0,1,0]$) &$[0,1,0,0,0,0,0]$\\ + 3 ($[1,1,0]$) &$[0,0,0,1,0,0,0]$\\ + 4 ($[0,0,1]$) &$[0,0,1,0,0,0,0]$\\ + 5 ($[1,0,1]$) &$[0,0,0,0,0,0,1]$\\ + 6 ($[0,1,1]$) &$[0,0,0,0,1,0,0]$\\ + 7 ($[1,1,1]$) &$[0,0,0,0,0,1,0]$\\ + \hline + + \end{tabular} + \end{center} + \caption{\label{mceliece:tab:syndrome}Syndrom-Tabelle 7/4-Code} +\end{table} -- cgit v1.2.1 From 283986431bbf1e343666e6ea243afff3dc28ccfb Mon Sep 17 00:00:00 2001 From: Reto Date: Wed, 1 Sep 2021 00:02:03 +0200 Subject: typos & co --- buch/papers/mceliece/funktionsweise.tex | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'buch/papers/mceliece/funktionsweise.tex') diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 58337c8..03601b3 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -293,7 +293,7 @@ Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden 1\\ 1 \end{pmatrix} - &=\text{Linear-Code-Decoder} + &=\text{Linear-Code-Decoder(} \begin{pmatrix} 0\\ 1\\ @@ -303,6 +303,7 @@ Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden 1\\ 1 \end{pmatrix} + \text{)} \end{align*} \end{itemize} \item Entschlüsselung (Umkehrung des $S_4$-Matrix-Effekts): @@ -344,7 +345,7 @@ Somit lässt sich das Code-Polynom $P_c$ berechnen, indem das Daten-Polynom $P_d \[ P_c=P_g \cdot P_d\,. \] -Damit diese Multiplikation mit Matrizen ausgeführt werden kann, werden die Polynome in mit Vektoren dargestellt: +Damit diese Multiplikation mit Matrizen ausgeführt werden kann, werden die Polynome in mit Vektoren dargestellt (Kapitel \ref{buch:section:polynome:vektoren}): \[ 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\,. @@ -392,7 +393,7 @@ womit das dazugehörige Bit identifiziert und korrigiert werden kann, indem beispielsweise die Bitfehler mit dem dazugehörigen Rest in der sogenannten Syndrom-Tabelle (Tabelle \ref{mceliece:tab:syndrome}) hinterlegt werden. \begin{table} \begin{center} - \begin{tabular}{l|c} + \begin{tabular}{|l|l|} \hline Syndrom (Divisionsrest) &korrespondierender Bitfehler\\ \hline -- cgit v1.2.1 From 362e2db0b3272a304adc9523788b9e0cdc81536f Mon Sep 17 00:00:00 2001 From: Reto Date: Wed, 1 Sep 2021 09:18:29 +0200 Subject: typos & co --- buch/papers/mceliece/funktionsweise.tex | 15 ++++++++++----- 1 file changed, 10 insertions(+), 5 deletions(-) (limited to 'buch/papers/mceliece/funktionsweise.tex') diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 03601b3..8288e7f 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -12,8 +12,11 @@ bei dem Bob an Alice eine verschlüsselte Nachticht über ein öffentliches Netz \subsection{Vorbereitung \label{mceliece:section:vorbereitung}} -Damit der Nachrichtenaustausch stattfinden kann, muss Alice (Empfängerin) -zuerst ein Schlüsselpaar definieren. +Bevor einen Datenaustausch zwischen Sender und Empfänger stattfinden kann, +muss abgemacht werden, welche Länge $n$ das Code-Wort und welche Länge $k$ das Datenwort hat +und wie viele Bitfehler $t$ (angewendet mit Fehlervektor $e_n$) +für das Rauschen des Code-Wortes $c_n$ verwendet werden. +Danach generiert Alice (Empfängerin) ein Schlüsselpaar. 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. @@ -29,7 +32,7 @@ und anschliessend durch eine Addition mit einem Fehlervektor $e_n$ einige Bitfeh \[ c_n\,=\,K_{n,k}\cdot d_k + e_n\,. \] -Dabei wird für jede Nachricht (oder für jedes Nachrichtenfragment) +Dabei wird für jede Nachricht (oder für jedes Nachrichtenfragment) $d_k$ einen neuen, zufälligen Fehlervektor generiert. Die verschlüsselte Nachricht $c_n$ wird anschliessend Alice zugestellt. @@ -79,7 +82,8 @@ Aus dem öffentlichen Schlüssel lassen sich diese nicht rekonstruieren und eine systematische Analyse der Codeworte wird durch das Hinzufügen von zufälligen Bitfehlern zusätzlich erschwert. \subsection{Beispiel} -Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden. +Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden. +Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four} beschrieben. \begin{itemize} \item Daten- und Fehlervektor \begin{itemize} @@ -336,7 +340,8 @@ Die Verschlüsselung soll mittels einem numerischen Beispiel demonstriert werden \end{itemize} -\subsubsection{7/4-Code} +\subsubsection{7/4-Code +\label{mceliece:subsection:seven_four}} Beim 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, -- cgit v1.2.1