diff options
Diffstat (limited to 'buch/papers/mceliece')
| -rw-r--r-- | buch/papers/mceliece/aufbau.tex | 9 | ||||
| -rw-r--r-- | buch/papers/mceliece/fazit.tex | 52 | ||||
| -rw-r--r-- | buch/papers/mceliece/funktionsweise.tex | 41 |
3 files changed, 61 insertions, 41 deletions
diff --git a/buch/papers/mceliece/aufbau.tex b/buch/papers/mceliece/aufbau.tex index 0849fc1..ef45bc1 100644 --- a/buch/papers/mceliece/aufbau.tex +++ b/buch/papers/mceliece/aufbau.tex @@ -6,6 +6,9 @@ \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. \subsection{Datenvektor $d_k$ \label{mceliece:subsection:d_k}} @@ -27,7 +30,7 @@ der in der Lage ist, $t$ Fehler zu korrigieren. 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, 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, @@ -41,7 +44,7 @@ Mit der Inversen $P_n^{-1}$ kann die Bitvertauschung rückgängig gemacht werden \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: +berechnet sich aus den bereits bekannten Matrizen wie folgt: \[ K_{n,k}=P_{n}\cdot G_{n,k}\cdot S_{k}\,. \] @@ -50,7 +53,7 @@ berechnet sich aus den bereits bekannten Matrizen wiefolgt: \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. \subsection{Daten-Vektor $d_k$ diff --git a/buch/papers/mceliece/fazit.tex b/buch/papers/mceliece/fazit.tex index eb96288..aab1f54 100644 --- a/buch/papers/mceliece/fazit.tex +++ b/buch/papers/mceliece/fazit.tex @@ -15,20 +15,26 @@ Damit diese mit dem Linearcode-Decoder wieder entfernt werden können, wird Redundanz benötigt, weshalb dessen Kanalefizienz (Nutzbits/Übertragungsbits) sinkt. 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}. +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. +Eine Übersicht zu diesem Thema bietet Tabelle \ref{mceliece:tab:comparison_effort}. + Beim Rechenaufwand sei noch erwähnt, dass asymmetrische Verschlüsselungen meist nur dazu verwendet werden, um einen Schlüssel für eine symmetrische Verschlüsselung auszutauschen. -\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: &1025 &40555 \\ - Entschlüsselungsaufwand: &2311 &6557176, 5 -\end{tabular} -\end{center} +\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: &1025* &40555* \\ + Entschlüsselungsaufwand: &2311* &6557176,5* \\ + \end{tabular} + \end{center} + \caption{\label{mceliece:tab:comparison_effort}Vergleich zwischen RSA und McEliece bezüglich Effizienz. (*Aufwand in binären Operationen pro Informationsbit\cite{mceliece:CodeBasedCrypto})} +\end{table} \subsection{Sicherheit} Grosse Unterschiede zwischen den beiden Kryptosystemen gibt es jedoch bei der Sicherheit. @@ -38,19 +44,25 @@ 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, 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, welche nennenswerte Vorteile gegenüber dem Durchprobieren (brute-force) bringen, auch nicht mithilfe eines Quantencomputers. -\begin{center} -\begin{tabular}{l|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, diff --git a/buch/papers/mceliece/funktionsweise.tex b/buch/papers/mceliece/funktionsweise.tex index 8288e7f..76b4b70 100644 --- a/buch/papers/mceliece/funktionsweise.tex +++ b/buch/papers/mceliece/funktionsweise.tex @@ -8,7 +8,7 @@ \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}} @@ -33,7 +33,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) $d_k$ -einen neuen, zufälligen Fehlervektor generiert. +ein neuer, zufälliger Fehlervektor generiert. Die verschlüsselte Nachricht $c_n$ wird anschliessend Alice zugestellt. \subsection{Entschlüsselung @@ -45,7 +45,7 @@ Um etwas Transparenz in diese Prozedur zu bringen, wird der öffentliche Schlüs &= 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\,. \\ @@ -71,18 +71,18 @@ hängt vom verwendeten Linearcode ab: &=\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, +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*} 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. +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 einem numerischen Beispiel demonstriert werden. +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 @@ -162,6 +162,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \end{pmatrix} + \,. \] \end{itemize} \item Öffentlicher Schlüssel: @@ -205,6 +206,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1 \end{pmatrix} + \,. \end{align*} \end{itemize} \item Verschlüsselung: @@ -248,6 +250,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 0\\ 0 \end{pmatrix} + \,. \end{align*} \end{itemize} \item Entschlüsselung (Permutation rückgängig machen): @@ -284,6 +287,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 1\\ 1 \end{pmatrix} + \,. \end{align*} \end{itemize} \item Entschlüsselung (Bitfehlerkorrektur mit Linearcode): @@ -308,6 +312,7 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 1 \end{pmatrix} \text{)} + \,. \end{align*} \end{itemize} \item Entschlüsselung (Umkehrung des $S_4$-Matrix-Effekts): @@ -335,15 +340,15 @@ Der verwendete Linear-Code wird im Abschnitt \ref{mceliece:subsection:seven_four 1\\ 1 \end{pmatrix} + \,. \end{align*} \end{itemize} \end{itemize} - -\subsubsection{7/4-Code +\subsection{7/4-Code \label{mceliece:subsection:seven_four}} Beim 7/4-Code handelt es sich um einen linearen Code, -der ein Bitfehler korrigieren kann. +der einen 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 (Codiervorgang): @@ -352,8 +357,8 @@ Somit lässt sich das Code-Polynom $P_c$ berechnen, indem das Daten-Polynom $P_d \] 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\,. + 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 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, @@ -362,13 +367,13 @@ sodass die Polynommultiplikation mit $d_4$ mittels Matrixmultiplikation realisie \[ 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} + \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\\ |