1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
|
%
% teil3.tex -- Beispiel-File für Teil 3
%
% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
%
\section{Fazit
\label{mceliece:section:fazit}}
\rhead{Fazit}
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 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.
\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,
\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.
\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 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.
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 asymmetrische Verschlüsselungen gefährden würde.
|
