diff options
Diffstat (limited to 'buch/papers/mceliece')
| -rw-r--r-- | buch/papers/mceliece/aufbau.tex | 131 | ||||
| -rw-r--r-- | buch/papers/mceliece/einleitung.tex | 11 | ||||
| -rw-r--r-- | buch/papers/mceliece/example_code/mceliece_simple.py | 14 | ||||
| -rw-r--r-- | buch/papers/mceliece/fazit.tex | 80 | ||||
| -rw-r--r-- | buch/papers/mceliece/funktionsweise.tex | 411 |
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}% |