aboutsummaryrefslogtreecommitdiffstats
path: root/buch/papers/mceliece
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--buch/papers/mceliece/aufbau.tex131
-rw-r--r--buch/papers/mceliece/einleitung.tex11
-rw-r--r--buch/papers/mceliece/example_code/mceliece_simple.py14
-rw-r--r--buch/papers/mceliece/fazit.tex80
-rw-r--r--buch/papers/mceliece/funktionsweise.tex411
5 files changed, 466 insertions, 181 deletions
diff --git a/buch/papers/mceliece/aufbau.tex b/buch/papers/mceliece/aufbau.tex
index 200cb7b..64c0cb3 100644
--- a/buch/papers/mceliece/aufbau.tex
+++ b/buch/papers/mceliece/aufbau.tex
@@ -6,156 +6,71 @@
\section{Aufbau\label{mceliece:section:Aufbau}}
\rhead{Aufbau}
Das McEliece-Kryptosystem besteht aus folgenden Elementen:
+Nachfolgend sind alle Bestandteile für das McEliece-Kryptosystem aufgelistet,
+wobei alle Vektoren und Matrizen sowie die Rechenoperationen damit
+im binären Raum $\mathbb{F}_2$ stattfinden.
+\index{F2@$\mathbb{F}_2$}%
\subsection{Datenvektor $d_k$
\label{mceliece:subsection:d_k}}
In diesem Vektor der Länge $k$ sind die zu verschlüsselnden Daten enthalten.
-Beispiel:
-\[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$.
+$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-Algorithmus deren Inverse bestimmt werden kann.
+\index{Gauss-Algorithmus}%
+\index{inverse Matrix}%
Da eine solche Matrix möglicherweise singulär ist, muss in diesem Fall eine neue Zufallsmatrix erzeugt werden.
+\index{Zufallsmatrix}%
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}}
+\index{Generator-Matrix}%
+\index{Linear-Code}%
Das wichtigste Element des McEliece-Systems ist ein fehlerkorrigierender Code,
der in der Lage ist, $t$ Fehler zu korrigieren.
+\index{fehlerkorrigierender Code}%
Im Zusammenhang mit McEliece werden dabei meist binäre Goppa-Codes \cite{mceliece:goppa} verwendet,
-es können prinzipiell auch andere Codes wie beispielsweise Reed-Solomon verwendet werden,
+\index{Goppa-Code}%
+es können prinzipiell auch andere Codes wie beispielsweise Reed-Solomon (Kapitel~\ref{chapter:reedsolomon}) verwendet werden,
+\index{Reed-Solomon-Code}%
jedoch besitzen einige (unter anderem auch Reed-Solomon) Codes Schwachstellen \cite{mceliece:lorenz}.
-Das Codieren mit diesem linearen Code kann mithilfe dessen Generatormatrix $G_{n,k}$ erfolgen.
+Das Codieren mit diesem linearen Code kann mithilfe seiner 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,
+\index{Redundanz}%
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 zufällig generierten Permutationsmatrix $P_n$ (Abschnitt~\ref{buch:section:permutationsmatrizen}) wird die Reihenfolge der Bits geändert.
+\index{Permutationsmatrix}
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
+berechnet sich aus den bereits bekannten Matrizen wie folgt:
\[
- 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}
+ K_{n,k}=P_{n}\cdot G_{n,k}\cdot S_{k}.
\]
\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,
+Dieser Fehlervektor besitzt also gleich viele Einsen
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.
+In diesem Vektor der Länge $k$ ist die Nachricht oder ein 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
+In diesem Vektor der Länge $n$ ist die verschlüsselte Nachricht oder ein Teil davon enthalten.
diff --git a/buch/papers/mceliece/einleitung.tex b/buch/papers/mceliece/einleitung.tex
index cebb8ed..f289512 100644
--- a/buch/papers/mceliece/einleitung.tex
+++ b/buch/papers/mceliece/einleitung.tex
@@ -6,11 +6,16 @@
\section{Einleitung
\label{mceliece:section:einleitung}}
\rhead{Einleitung}
-Beim McEliece-Kryptosystem handelt es sich um ein asymetrisches Verschlüsselungsverfahren, welches erlaubt,
+Beim McEliece-Kryptosystem handelt es sich um ein asymmetrisches Verschlüsselungsverfahren, welches erlaubt,
+\index{McEliece-Kryptosystem}%
+\index{Kryptosystem}%
+\index{Verschlüsselungsverfahren, asymmetrisch}%
+\index{asymmetrische Verschlüsselung}%
Daten verschlüsselt über ein Netzwerk zu übermitteln, ohne dass vorab ein gemeinsamer,
geheimer Schlüssel unter den Teilnehmern ausgetauscht werden müsste.
-Eine andere, bereits erläuterte Variante einer asymetrischen Verschlüsselung ist das Diffie-Hellman-Verfahren \ref{buch:subsection:diffie-hellman}.
-Im Gegensatz zu Diffie-Hellman gilt das McEliece-System als Quantencomputerresistent
+Eine andere, bereits erläuterte Variante einer asymmetrischen Verschlüsselung ist das Diffie-Hellman-Verfahren (Abschnitt~\ref{buch:subsection:diffie-hellman}).
+Im Gegensatz zu Diffie-Hellman gilt das McEliece-System als quantencomputerresistent
+\index{quantencomputerresistent}%
und das Verschlüsseln/Entschlüsseln von Nachrichten wird hauptsächlich mit Matrizenoperationen durchgeführt.
diff --git a/buch/papers/mceliece/example_code/mceliece_simple.py b/buch/papers/mceliece/example_code/mceliece_simple.py
index bac3b42..c8d5e9d 100644
--- a/buch/papers/mceliece/example_code/mceliece_simple.py
+++ b/buch/papers/mceliece/example_code/mceliece_simple.py
@@ -187,14 +187,10 @@ def decode_linear_code(c, g, syndrome_table):
q, r=divmod(Poly(c), g)
q=np.r_[q.coef%2, np.zeros(len(c)-len(q)-len(g)+1)]
r=np.r_[r.coef%2, np.zeros(len(g)-len(r))]
- syndrome_index=np.sum([int(a*2**i) for i, a in enumerate(r)])
- while syndrome_index > 0:
- c=c ^ syndrome_table[syndrome_index]
- q, r=divmod(Poly(c), g)
- q=np.r_[q.coef%2, np.zeros(len(c)-len(q)-len(g)+1)]
- r=np.r_[r.coef%2, np.zeros(len(g)-len(r))]
- syndrome_index=np.sum([int(a*2**i) for i, a in enumerate(r)])
- return np.array(q, dtype=int)
+ syndrome_index=np.sum([int(a*2**i) for i, a in enumerate(r)]) #binary to decimal
+ q_corr, r_corr=divmod(Poly(syndrome_table[syndrome_index]), g)
+ q_corr=np.r_[q_corr.coef%2, np.zeros(len(c)-len(q_corr)-len(g)+1)]
+ return q.astype(int) ^ q_corr.astype(int)
def encode_linear_code(d, G):
'''
@@ -324,4 +320,4 @@ if __name__ == '__main__':
print(f'msg_rx: {msg_rx}')
- \ No newline at end of file
+
diff --git a/buch/papers/mceliece/fazit.tex b/buch/papers/mceliece/fazit.tex
index 186708b..b53328f 100644
--- a/buch/papers/mceliece/fazit.tex
+++ b/buch/papers/mceliece/fazit.tex
@@ -10,48 +10,70 @@ Ein kurzer Vergleich des McEliece-Systems
mit dem oft verwendeten RSA-System soll zeigen, wo dessen Vor- und Nachteile liegen.
\subsection{Resourcen}
-Eine Eigenheit des McEliece-Systems ist das hinzufügen von Rauschen (mit Fehlervektor $e_n$).
-Damit diese mit dem Lienarcode-Decoder wieder entfernt werden können,
+Eine Eigenheit des McEliece-Systems ist das Hinzufügen von Rauschen in Form des Fehlervektors $e_n$.
+Damit dieses mit dem Linearcode-Decoder wieder entfernt werden können,
wird Redundanz benötigt,
weshalb dessen Kanalefizienz (Nutzbits/Übertragungsbits) sinkt.
+\index{Kanaleffizienz}%
+
Die Schlüsselgrösse des McEliece-Systems ist deshalb so riesig, weil es sich um eine zweidimensionale Matrix handelt, währenddem RSA mit nur zwei Skalaren auskommt.
-Das McEliece-System benötigt dafür weniger Rechenaufwand beim Verschlüsseln/Entschlüsseln, da die meisten Operationen mit Matrixmultiplikationen ausgeführt werden können (Aufwand ist in binären Operationen pro Informationsbit)\cite{mceliece:CodeBasedCrypto}.
+\index{Schlüsselgrösse}%
+Das McEliece-System benötigt dafür weniger Rechenaufwand beim Verschlüsseln/Entschlüsseln,
+da die meisten Operationen mit Matrixmultiplikationen ausgeführt werden können.
+\index{Matrixmultiplikation}%
+Eine Übersicht zu diesem Thema bietet Tabelle \ref{mceliece:tab:comparison_effort}.
Beim Rechenaufwand sei noch erwähnt,
-dass asymetrische Verschlüsselungen meist nur dazu verwendet werden,
-um einen Schlüssel für eine symetrische Verschlüsselung auszutauschen.
-\begin{center}
-\begin{tabular}{c|c|c}
- &McEliece (n=2048, k=1718, t = 30) &RSA (2048, e = 216 + 1)\\
- \hline
- Schlüssegrösse: (Public) &429.5 KByte &0.5 KByte \\
- Kanaleffizienz: &83.9 \% &100 \% \\
- Verschlüsselungsaufwand: &1025 &40555 \\
- Entschlüsselungsaufwand: &2311 &6557176, 5
-\end{tabular}
-\end{center}
+\index{Rechenaufwand}%
+dass asymmetrische Verschlüsselungen meist nur dazu verwendet werden,
+um einen Schlüssel für eine symmetrische Verschlüsselung auszutauschen.
+\begin{table}
+ \begin{center}
+ \begin{tabular}{l|c|c}
+ &McEliece ($n=2048$, $k=1718$, $t = 30$) &RSA ($2048$, $e = 216 + 1$)\\
+ \hline
+ Schlüssegrösse (Public) &429.5 KByte &0.5 KByte \\
+ Kanaleffizienz &83.9 \% &100 \% \\
+ Verschlüsselungsaufwand\textsuperscript{$\dagger$} &1025 bitop &40555 bitop \\
+ Entschlüsselungsaufwand\textsuperscript{$\dagger$} &2311 bitop &6557176.5 bitop \\
+ \end{tabular}
+ \end{center}
+ \caption{\label{mceliece:tab:comparison_effort}Vergleich zwischen RSA und McEliece bezüglich Resourcen \cite{mceliece:CodeBasedCrypto}.% (*Aufwand in binären Operationen pro Informationsbit)}
+ \quad\small\textsuperscript{$\dagger$}Aufwand in binären Operationen pro Informationsbit.}
+\end{table}
\subsection{Sicherheit}
-Grosse unterschiede zwischen den beiden Kryptosystemen gibt es jedoch bei der Sicherheit.
+Grosse Unterschiede zwischen den beiden Kryptosystemen gibt es jedoch bei der Sicherheit.
+\index{Sicherheit}%
Der Kern der RSA-Verschlüsselung beruht auf dem Problem, eine grosse Zahl in ihre beiden Primfaktoren zu zerlegen.
+\index{Primfaktoren}%
Bei genügend grossen Zahlen ist diese Zerlegung auch mit den heute besten verfügbaren Computern kaum innerhalb vernünftiger Zeit zu lösen.
Weiter ist aber bekannt,
dass mithilfe des sogenannten Shor-Algorithmus \cite{mceliece:shor} und einem Quantencomputer auch diese Zerlegung zügig realisiert werden könnte,
+\index{Shor-Algorithmus}%
+\index{Algorithmus von Shor}%
+\index{Quantencomputer}%
was zur Folge hätte, dass die Verschlüsselung von RSA unwirksam würde.
-Zurzeit sind die Quantencomputer jedoch noch bei weitem nicht in der Lage, grosse Zahlen mithilfe dieses Algorithmuses zu zerlegen.
-Das McEliece-System hingegen beruht auf dem Problem des ``Syndrome decoding'' (Korrektur von Bitfehlern eines Codewortes, das mit einem entsprechenden Linearcode codiert wurde).
-Für das ``Syndrome decoding'' sind bis heute keine Methoden bekannt,
+Zurzeit sind die Quantencomputer jedoch noch bei weitem nicht in der Lage, grosse Zahlen mithilfe dieses Algorithmus zu zerlegen.
+
+Das McEliece-System hingegen beruht auf dem Problem des {\em Syndrome decoding}, also der Korrektur von Bitfehlern eines Codewortes, das mit einem entsprechenden Linearcode codiert wurde.
+Für das {\em Syndrome decoding} sind bis heute keine Methoden bekannt,
welche nennenswerte Vorteile gegenüber dem Durchprobieren (brute-force) bringen,
auch nicht mithilfe eines Quantencomputers.
-\begin{center}
-\begin{tabular}{c|c|c}
- &McEliece &RSA \\
-\hline
- Grundlage Verschlüsselung &Syndrome decoding &Integer factoring\\
- Aufwand (gewöhnliche CPU) &exponential &< exponential \\
- Aufwand (Quantencomputer) &> polynomial &$\mathcal{O}(\log(N)^3)$
-\end{tabular}
-\end{center}
+Eine Übersicht betreffend des Rechenaufwandes zum Knacken der Verschlüsselung ist in Tabelle \ref{mceliece:tab:comparison_security} gegeben und bezieht sich auf die Schlüsselgrösse $N$.
+\begin{table}
+ \begin{center}
+ \begin{tabular}{l|c|c}
+ &McEliece &RSA \\
+ \hline
+ Grundlage Verschlüsselung &Syndrome decoding &Integer factoring\\
+ Aufwand (gewöhnliche CPU) &exponentiell &< exponentiell \\
+ Aufwand (Quantencomputer) &> polynominell &$\mathcal{O}(\log(N)^3)$
+ \end{tabular}
+ \end{center}
+ \caption{\label{mceliece:tab:comparison_security}Vergleich zwischen RSA und McEliece bezüglich Sicherheit}
+\end{table}
+
Die Verbreitung des McEliece-Kryptosystems ist zurzeit äusserst gering.
Das liegt einerseits an der immensen Grösse des öffentlichen Schlüssels,
andererseits wird aber auch in naher Zukunft nicht mit einem genügend starken Quantencomputer gerechnet,
-welcher andere asymetrische Verschlüsselungen gefährden würde.
+welcher andere asymmetrische Verschlüsselungen gefährden würde.
diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex
index 7c69b13..4d6c18d 100644
--- a/buch/papers/mceliece/funktionsweise.tex
+++ b/buch/papers/mceliece/funktionsweise.tex
@@ -8,14 +8,17 @@
\rhead{Funktionsweise}
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.
+bei dem Bob an Alice eine verschlüsselte Nachricht über ein öffentliches Netzwerk zukommen lässt.
\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
+Diese drei 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 (Abschnitt \ref{mceliece:subsection:k_nk})
@@ -25,36 +28,36 @@ 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\,.
+ 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.
+Dabei wird für jede Nachricht (oder für jedes Nachrichtenfragment) $d_k$
+ein neuer, zufälliger 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 $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
+ 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.
+indem das Codewort mit der 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 \\
+ 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.
\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
+ 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 \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 +65,366 @@ 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
-\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.
-\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
+ 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*}
+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{equation*}
+ d'_{k}=S_{k}^{-1} \cdot c'_k=S_{k}^{-1} \cdot S_{k}\cdot d_k
+ =d_k.
+\end{equation*}
+Möchte ein Angreifer die verschlüsselte Nachricht knacken, muss er 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 eines numerischen Beispiels demonstriert werden.
+Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four} beschrieben.
+\begin{itemize}
+ \item Daten- und Fehlervektor
+ \begin{itemize}
+ \item[]
+ \[d_4=
+ \begin{pmatrix}
+ 1\\
+ 1\\
+ 1\\
+ 0
+ \end{pmatrix}
+ ,\quad
+ 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},\quad
+ 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},
+ \quad
+ 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:
+\index{Schlüssel, öffentlicher}%
+\index{ö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}
+ \text{)}
+ .
+ \end{align*}
+ \end{itemize}
+ \item Entschlüsselung (Umkehrung des $S_4$-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}
+
+\subsection{7/4-Code
+\label{mceliece:subsection:seven_four}}
+Beim 7/4-Code handelt es sich um einen linearen Code,
+der einen Bitfehler korrigieren kann.
+\index{7/4-Code}%
+\index{linearer Code}%
+\index{Code, linear}%
+Es gibt unterschiedliche Varianten zum Erzeugen eines 7/4-Codes,
+wobei der hier verwendete Code mithilfe des irreduziblen Generatorpolynoms $P_g = x^3 +x + 1$ generiert wird.
+\index{Generatorpolynom}%
+Somit lässt sich das Codepolynom $P_c$ berechnen, indem das Datenpolynom $P_d$ mit dem Generatorpolynom $P_g$ multipliziert wird (Codiervorgang):
+\[
+ P_c=P_g \cdot P_d.
+\]
+Damit diese Multiplikation mit Matrizen ausgeführt werden kann, werden die Polynome als Vektoren dargestellt (Kapitel \ref{buch:section:polynome:vektoren}):
+\[
+ P_g = \textcolor{red}{1}\cdot x^0 + \textcolor{blue}{1}\cdot x^1 + \textcolor{darkgreen}{0}\cdot x^2 + \textcolor{orange}{1}\cdot x^3 \implies
+ [\textcolor{red}{1}, \textcolor{blue}{1} ,\textcolor{darkgreen}{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}$ gepackt,
+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{darkgreen}{0} & \textcolor{blue}{1} & \textcolor{red}{1} & 0 \\
+ \textcolor{orange}{1} & \textcolor{darkgreen}{0} & \textcolor{blue}{1} & \textcolor{red}{1} \\
+ 0 & \textcolor{orange}{1} & \textcolor{darkgreen}{0} & \textcolor{blue}{1} \\
+ 0 & 0 & \textcolor{orange}{1} & \textcolor{darkgreen}{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 Codevektor $c_7=[c_0, ..., c_6]$ entsprechen die Koeffizienten dem dazugehörigen Codepolynom $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,
+\index{Hamming-Distanz}%
+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 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 Syndromtabelle (Tabelle \ref{mceliece:tab:syndrome}) hinterlegt werden.
+\index{Syndromtabelle}%
+\begin{table}
+ \begin{center}
+ \begin{tabular}{|l|l|}
+ \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
-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
+ \end{tabular}
+ \end{center}
+ \caption{\label{mceliece:tab:syndrome}Syndromtabelle 7/4-Code}
+\end{table}
+\index{Syndrom}%