From 098cc6c392283476e84a47f3a193b8f5f79ec413 Mon Sep 17 00:00:00 2001
From: Reto Fritsche <reto.fritsche@ost.ch>
Date: Mon, 9 Aug 2021 11:47:16 +0200
Subject: searching latex error
---
buch/papers/mceliece/aufbau.tex | 56 ++++++++++++---------
buch/papers/mceliece/funktionsweise.tex | 86 +++++++++++++++++++++++++++------
2 files changed, 102 insertions(+), 40 deletions(-)
(limited to 'buch/papers')
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
--
cgit v1.2.1