\chapter[Spezialroutinen] {Spezialroutinen} \thispagestyle{empty} In diesem Kapitel m"ochte ich auf einige Algorithmen eingehen, die in der allt"aglichen Programmierpraxis normalerweise nicht ben"otigt werden, aber bei der Implementierung des RSA-Verfahrens unverzichtbar sind. % \section[Primzahltests] {Primzahltests} \subsection[Klassische Verfahren] {Klassische Verfahren} Bei der Verschl"usselung von Daten mit Hilfe des RSA-Verfahrens werden zur Erzeugung des "offentlichen bzw. des geheimen Schl"ussels sehr gro\3e Primzahlen ben"otigt. Die "ublichen Methoden wie ''Sieb des Erathostenes`` versagen hier. Um dies zu veranschaulichen, m"ochte ich folgendes Beispiel geben:\\ Um 20-stellige Primzahlen mit dem ''Sieb des Erathostenes`` zu berechnen br"auchte man mindestens einen Speicherplatz von $10^{20}*1\ Bit \approx 2*10^{13}\ MB$, wenn man jeder Zahl ein 1 Bit zuordnet. Dabei wird jede Zahl durch ihren Index repr"asentiert und die Zust"ande ''gestrichen`` bzw. ''nichtgestrichen`` durch das Setzen oder L"oschen dieses Bits.\\ Weiterhin w"are die Speicherausnutzung nicht besonders hoch. F"ur gro\3e n l"a\3t sich die Anzahl der Primzahlen, die kleiner n sind, n"aherungsweise durch folgende Beziehung wiedergeben: $$A_p(n)={n \over {ln(n)}}$$ Deshalb ergibt sich eine durchschnittliche Primzahldichte von: $$D(n)=\frac{A_p(n)}{n}=\frac{1}{ln(n)}$$ Bei einer Suche bis zu 20-stelligen Primzahlen w"urde sich eine Speicherausnutzung von $2\%$ ergeben. Bei 100stelligen Primzahlen sogar nur von $0.4\%$. Selbst wenn eine Primzahl nur 2 Bytes belegen w"urde, w"are ein Speicherbedarf von $\frac{2*10^{20}}{20*ln(10)} \approx 5*10^{12}\ MB$ notwendig, um alle Primzahlen zu speichern. Dies verdeutlicht, da\3 es unsinnig w"are alle Primzahlen $< 10^{20}$ zu speichern, um so gro\3e Primzahlen zu berechnen.\\ Aber neben diesem Speicherproblem g"abe es auch noch das Rechenzeitproblem zu l"osen, wenn das ``Sieb des Erathostenes'' verwendet werden w"urde. Eine grobe Absch"atzung dieses Problems ergibt sich durch folgende "Uberlegung:\\ Im ersten Schritt sind $\frac{n}{2}$ Zahlen zu streichen. Im zweiten sind dann $\frac{n}{3}$ zu streichen. Bei j Durchl"aufen sind genau $$S=n*\sum_{i=1}^j{\frac{1}{p_i}},\ p_i \in {\cal P} \wedge p_i \le \sqrt{n}$$ Streichungen zu machen. Die oben angegebene Summe ist divergent. D.h der Aufwand der Streichungen erreicht nie eine Obergrenze.\\ Um dies zu zeigen, beginnen wir mit der Zetafunktion\footnote{$\zeta$-Funktion nach B. Riemann} $\zeta(s)$. Sie ist definiert als \begin{displaymath} \zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s} \end{displaymath} Wie man leicht erkennen kann, liegt bei $\zeta(1)$ ein Pol vor, weil die so entstehende harmonische Reihe divergent ist.\\ Desweiteren wird hier die {\it Eulersche Produktdarstellung der $\zeta$-Funktion} verwendet, die durch Reihenentwicklung der einzelnen Faktoren in die oben angegebene Form der $\zeta$-Funktion "ubergeht. \begin{displaymath} \zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s}=\prod_p \frac{1}{1-\frac{1}{p^s}},\ p \in {\cal P} \end{displaymath} Denn ein Faktor der {\it Eulersche Produktdarstellung der $\zeta$-Funktion} kann in eine geometrische Reihe entwickelt werden: \begin{displaymath} \frac{1}{1-(\frac{1}{p})^s}=1+\frac{1}{p^s}+\frac{1}{p^{2s}}+\frac{1}{p^{3s}}+\ldots \end{displaymath} deshalb kann das Produkt wie folgt geschrieben werden: \begin{displaymath} \begin{array}{rrl} \prod\limits_p\frac{1}{1-(\frac{1}{p})^s}&=&\phantom{*}(1+\frac{1}{2^s}+\frac{1}{2^{2s}}+\frac{1}{2^{3s}}+\ldots)\\ &&*(1+\frac{1}{3^s}+\frac{1}{3^{2s}}+\frac{1}{3^{3s}}+\ldots)\\ &&*(1+\frac{1}{5^s}+\frac{1}{5^{2s}}+\frac{1}{5^{3s}}+\ldots)\\ &&\vdots\\ &&*(1+\frac{1}{p_i^s}+\frac{1}{p_i^{2s}}+\frac{1}{p_i^{3s}}+\ldots)\\ \end{array} \end{displaymath} Weil jede nat"urliche Zahl eindeutig in Primfaktoren zerlegt werden kann, erzeugt der oben angegebene Ausdruck genau die Definitionsgleichung der $\zeta$-Funktion.\\ Da $\lim_{s \to 1} \zeta(s) = \infty$ ist auch $\lim_{s \to 1} ln(\zeta(s)) = \infty$.\\ Deshalb gilt: \begin{displaymath} ln(\zeta(s))=ln(\prod_p \frac{1}{1-\frac{1}{p^s}})=\sum_p ln( \frac{1}{1-\frac{1}{p^s}}) \end{displaymath} Der Ausdruck $ln(\frac{1}{1-p^{-s}})$ kann in eine logarithmische Reihe entwickelt werden: \begin{displaymath} ln(\zeta(s))=\sum_p {\sum_{n=1}^\infty \frac{p^{-n*s}}{n}} \end{displaymath} die Abspaltung des ersten Glieds ergibt: \begin{displaymath} ln(\zeta(s))=\sum_p p^{-s}+\sum_p \sum_{n=2}^\infty \frac{p^{-n*s}}{n} \end{displaymath} F"ur den Logarithmus der $\zeta$-Funktion gilt: $\lim_{s \to 1} ln(\zeta(s))=\infty$. Kann gezeigt werden, da"s $\lim_{s \to 1} \sum_p \sum_{n=2}^\infty \frac{p^{-ns}}{n}$ konvergiert, mu"s $\lim_{s \to 1} \sum_p p^{-s}$ divergieren.\\ Folgende Absch"atzung zeigt, da\3 $\lim_{s \to 1} \sum_p \sum_{n=2}^\infty \frac{p^{-ns}}{n}$ konvergiert. \begin{displaymath} \begin{array}{rlrl} % &\sum\limits_p\sum\limits_{n=2}^\infty \frac{1}{n*p^{n*s}}&<&\sum\limits_p \sum\limits_{n=2}^\infty \frac{1}{p^{n*s}}\\ \Rightarrow&\sum\limits_p (\frac{1}{(1-p^{-s}) p^{2s}})\\ \Rightarrow&\sum\limits_p \frac{1}{p^s(p^s-1)}&<&\sum\limits_p \frac{1}{p(p-1)}\\ \Rightarrow&\sum\limits_p \frac{1}{p(p-1)}&<&\sum\limits_{n=2}^\infty \frac{1}{n(n-1)} \le 1\\ \end{array} \end{displaymath} Deshalb mu\3 die Reihe $\sum\limits \frac{1}{p}=\lim\limits_{s \to 1} \sum\limits_p p^{-s}$ divergieren.\\ Bei einem Rechnerexperiment mit 10000 Primzahlen erreichte diese Summe den Wert von $\approx 2$. Nehmen wir bei unserer Absch"atzung diesen Wert als Obergrenze der Summe an, so erh"alt man als Untergrenze einen Aufwand von $2*10^{20}$ Streichungen. Hier sieht man deutlich, da\3 dies nicht in endlicher Zeit zu l"osen w"are.\\ Aus diesen Gr"unden mu\3 ein Verfahren gefunden werden, da\3 hinreichend schnell gro\3e Primzahlen finden kann. Dabei darf sich der Algorithmus nicht auf alle kleineren Primzahlen st"utzen, weil sonst wieder das oben beschriebene Speicherproblem auftreten w"urde. % \subsection[Miller-Rabin-Test] {Miller-Rabin-Test} \label{Miller} % \subsubsection[Allgemein]{Allgemein} % Ein Primzahltest liefert normalerweise eine Aussage der Form ''n ist prim`` oder ''n ist nicht prim``. Ein ''probabilistischer Test`` oder ''Monte-Carlo Test'' hingegen sagt aus: ''n ist mit hoher Wahrscheinlichkeit eine Primzahl``.\\ Die Wahrscheinlichkeit w, da"s n doch zusammengesetzt ist, kann als "au"serst klein betrachtet werden. Der folgende Test basiert auf der Methode von Gary Miller, mit "Anderungen von Michael Oser Rabin. % \subsubsection[Grundlage]{Grundlage} % Es gelte $n-1 = 2^k * u$, u ungerade. Wenn f"ur m zuf"allig gew"ahlte Werte $a < n$ die Bedingung $a^u\ mod\ n = 1$ oder $a^{2j*u}\ mod\ n = n-1$ f"ur ein j mit $0 \le j < k$ erf"ullt sind, kann man mit einer Wahrscheinlichkeit von bis zu $4^{-m}$ die Zahl n als Primzahl ansehen. % \subsubsection[Durchf"uhrung]{Durchf"uhrung} % Zun"achst bringt man $n-1$ in die Form $2^k * u$ und bildet eine gewisse Anzahl von Zufallszahlen a. F"ur jede ist der oben angegebene Test durchzuf"uhren. Zwei Bedingungen sind gegeben, nur eine davon mu"s erf"ullt sein. \begin{enumerate} % \item {Gilt $a^u\ mod\ n = 1$ dann hat das aktuelle a den Test erf"ullt und die Primwahrscheinlichkeit w"achst.} % \item {Gilt $a^u\ mod\ n = 1$ nicht, dann ist zun"achst zu pr"ufen, ob $a^u\ mod\ n = n-1$. Ist das nicht der Fall, wird mit $a^{2*u}\ mod\ n = n-1$ oder $a^{2^{2*u}} mod\ n = n-1$ usw. gepr"uft.} % \end{enumerate} % Ist nur eine dieser Gleichungen wahr, ist der Test positiv abgeschlossen, andernfalls folgt eindeutig, da"s n nicht prim sein kann.\\ Der Test beruht darauf, da"s mindestens eine der Bedingungen f"ur jede Primzahl gilt, f"ur eine zusammengesetzte Zahl jedoch nur mit einer Wahrscheinlichkeit von 25\% (1/4). F"uhrt man den Test einmal mit Erfolg durch, bedeutet das eine Wahrscheinlichkeit von 75\% (3/4), da"s n prim ist. Nach dem n"achsten erfolgreichen Durchlauf erh"oht sich die Fehlerwahrscheinlichkeit auf 1/16, dann weiter auf 1/64 usw. Hat eine Zahl alle Durchl"aufe (z.B. 30) bestanden, dann ist sie mit einer Fehlerwahrscheinlichkeit von $4*10^{-30} = 8.67*10^{-19}$ keine Primzahl. Diese Wahrscheinlichkeit liegt unter der Fehlerwahrscheinlichkeit von Computersystemen. % \subsubsection[Optimierung des Verfahrens]{Optimierung des Verfahrens} % Zeiteinsparung l"a"st sich erreichen, wenn die Rechenroutine alte Ergebnisse ausnutzt. Zun"achst wird der Variablen $w$ der Wert $a^u\ mod\ n$ zugewiesen und bei $w \not = 1$ auf $w^2$ gesetzt. Die Zufallsfolge hat als Startwert $a = 2$ und berechnet sich bei jedem Schleifendurchlauf mit $a^2 - 1\ mod\ n$. % \subsubsection[Schlu"sbemerkung zum Miller-Rabin Verfahren] {Schlu"sbemerkung zum Miller-Rabin Verfahren} % Besonders Zahlentheoretiker begegnen Monte-Carlo Tests mit Skepsis, da S"atze die sich aus dieser Primeigenschaft einer Zahl ergeben mit einer Fehlerwahrscheinlichkeit versehen werden m"u"sten. F"ur praktische Belange wie z.B. RSA-Verfahren gen"ugt dies v"ollig. % \section [Der Berlekamp-Algorithmus] {Der Berlekampalgorithmus} Soll der ggT\footnote{gr"o\3ter gemeinsamer Teiler} zweier Zahlen berechnet werden, so verwendet man den euklidischen Algorithmus\footnote{nach Euklid um 300 v. Chr.}. Dieser bekannte Algorithmus liefert den ggT zweier nat"urlichen Zahlen. Da aber eine Lineardarstellung des ggT zur Bestimmung des geheimen Schl"ussels d gebraucht wird, mu\3 der Berlekampalgorithmus verwendet werden. Dieser Algorithmus stellt eine leichte Abwandlung des euklidischen Algorithmus dar, der als Nebenprodukt noch die in jedem euklidischen Ring existierende lineare Darstellung des ggT liefert. Der Algorithmus l"a\3t sich durch folgenden Pseudocode beschreiben: {\obeylines \noindent hole die Zahl a; hole die Zahl b; IF $(a