diff options
Diffstat (limited to 'buch/papers/mceliece/fazit.tex')
| -rw-r--r-- | buch/papers/mceliece/fazit.tex | 80 |
1 files changed, 51 insertions, 29 deletions
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. |