\chapter[Das RSA-Verfahren] {Das RSA-Verfahren}
\thispagestyle{empty}
Das von Rivest, Shamir und Adlemann erfundene asymetrische
Ver\-schl"us\-selungs\-ver\-fahren ist eines der heute am besten
erforschten Public Key Cryptosysteme. Mit den heute bekannten
Algorithmen kann es mit vertretbaren Aufwand nicht entschl"usselt
werden. Wie bei jedem Public Key Cryptosystem kann der Schl"ussel,
der der Dechiffrierung dient, aus dem "offentlichen
Schl"ussel ermittelt werden. In der Praxis scheitert dies aber an
mangelnder Rechengeschwindigkeit und Speicherkapazit"at.\\
Weil das RSA-Verfahren eine sehr gro\3e Sicherheit bietet, hat diese
Verschl"usselungsmethode eine weite Verbreitung erlangt, und wird heute
schon in bestehenden Softwarepaketen zur Verf"ugung gestellt.
Nachfolgend m"ochte ich auf die mathematischen Grundlagen dieses
Verfahrens eingehen.

\section[Grundlagen des RSA Verfahrens] {Grundlagen des RSA Verfahrens}
Die grundlegende Idee eines Public Key Cryptosystems ist es, zwei
Funktionen $E$ {\it 'Encrypt'} und $D$ {\it 'Decrypt'} zu
erzeugen, wobei $E$ ver"offentlicht werden kann, ohne da\3 dadurch
die Funktion $D$ bekannt wird, bzw. in endlicher Zeit berechnet
werden kann.

\subsection[Der grunds"atzliche Ver- und Entschl"usselungsvorgang]
{Der grunds"atzliche Ver- und Entschl"usselungsvorgang}
Ist ${\cal N}$ die Menge der Nachrichten, $N \in {\cal N}$ die zu
verschl"usselnde Nachricht, $E(N)=N'$ die verschl"usselte und $D(N')=N$
die entschl"usselte Nachricht, so versteht man unter der Verschl"usselung
die Abbildung
$$
E: {\cal N} \longmapsto {\cal N}
$$
und unter der Entschl"usselung die Abbildung
$$
D: {\cal N} \longmapsto {\cal N}
$$
Weiterhin mu\ss\  die Reihenfolge der Ausf"uhrung dieses Verfahrens
unbedeutend sein. Dies ist besonders f"ur digitale Unterschriften eine
wichtige Eigenschaft. $${D(E(N))=N=E(D(N))}$$ Betrachtet man diese
Eigenschaft n"aher, so kann man leicht erkennen, da\3 D die inverse
Funktion von E darstellt. Auf diesen Zusammenhang komme ich sp"ater noch zu
sprechen.

\subsection[Austausch von Nachrichten] {Austausch von Nachrichten}
Teilnehmer A m"ochte eine Nachricht N verschl"usseln und an den Teilnehmer B
verschicken, um so ein ''Mith"oren`` Dritter zu vermeiden. Dazu ist
folgendes Vorgehen notwendig:\\
Der Teilnehmer A ermittelt aus dem "offentlichen
Schl"usselverzeichnis, das mit einem Telefonbuch vergleichbar ist,
den "offentlichen Schl"ussel $E_B$ von B und verschl"usselt damit seine Nachricht.
$$
{N \longmapsto N'=E_B(N)}
$$
Diese verschl"usselte Nachricht wird dann im
Rechnernetz "ubertragen. Weil die Umkehrung der Verschl"usselung nur dem
Empf"anger bekannt ist, kann ein ''Lauscher`` den Inhalt der Nachricht
nicht bestimmen oder verf"alschen.\\
Der Empf"anger bekommt dann die Nachricht
und verwendet seinen geheimen Schl"ussel $D_B$ um die urspr"ungliche
Nachricht zu erhalten:
$${D_B(E_B(N))=D_B(N')=N}$$

\subsection[Die digitale Unterschrift] {Die digitale Unterschrift}
Die Verwendung eines Public Key Cryptosystems erlaubt auch
sogenannte {\it digitale Unterschriften}. Diese Methode erlaubt die
zweifelsfreie Autorisierung des Senders einer Nachricht. Diese M"oglichkeit
stellt einen der wichtigsten Vorteile gegen"uber den symmetrischen
Verschl"usselungsverfahren dar, weil sie auch verbindliche Unterschriften
erlaubt.\\
Bei diesem Verfahren kann\footnote{Die tats"achliche Methode wird von Herrn
J"urgen Weinelt in einem sp"ateren Kapitel erl"autert}
folgende Vorgehensweise verwendet werden:\\
Der Teilnehmer A verschl"usselt seine Nachricht mit dem "offentlichen
Schl"ussel von B, den er aus dem Schl"usselverzeichnis erhalten hat, und die
gleiche Nachricht mit seinem geheimen
Schl"ussel. Dieses Nachrichtenpaar wird dann verschickt. $$ (E_B(N),
D_A(N))=(N_1,N_2)$$
Der Empf"anger bekommt dieses Datenpaar und wertet den Teil
$E_B(N)$ mit seiner geheimen Funktion $D_B$ aus. Dieser Teil der
Nachricht ist noch nicht ausreichend f"ur eine Identifizierung des
Senders, weil der "offentliche Schl"ussel $E_B$ f"ur alle Teilnehmer in
der Schl"usselverteilzentrale, bzw. im Schl"usselverzeichnis
erh"altlich ist. Da in dieser Nachricht N
der Name des Senders enthalten sein mu\3, kann nun der
"offentliche Schl"ussel des Senders aus dem Schl"usselverzeichnis
ermittelt werden. Sodann verschl"usselt der Empf"anger mit der erhaltenen
Funktion $E_A$ den empfangenen Datenblock $D_A(N)=N_2$. Ist das Ergebnis
dieser Berechnung das gleiche wie bei der ersten Berechnung, ist die
Identit"at des Senders zweifelsfrei best"atigt.
Denn $D_A$ hat die Eigenschaft, da"s  $\forall \ N \in {\cal N}$
$E_A(D_A(N))=N$ ist. Dazu mu"s nat"urlich durch die Schl"usselverteilzentrale
gew"ahrleistet sein, da"s verschiedene Teilnehmer nicht denselben
Schl"ussel bekommen. Dabei bleibt das ''Restrisiko``, da"s d"ur ein
gewisses $N \in {\cal N}$ trotzdem $E_A(D_{A'}(N))=N, A \not= A'.$
%
\section[Die Schl"usselgenerierung] {Die Schl"usselgenerierung}
Das RSA-Verfahren arbeitet in Restklassenringen ${\cal Z}_n$
bzw. ${\cal Z}_{\varphi(n)}$. Deshalb gilt f"ur alle verwendeten
Zahlen $0\le x <n$.
%
\subsection{Restklassenringe}
Unter einer Restklasse versteht man eine Menge von
nat"urlichen Zahlen, die bei der Division durch eine andere
nat"urliche Zahl den gleichen Rest lassen. Diese Zahlen werden dann
einer Restklasse zugeordnet.\\
Beispiel:\\
Die Zahlen $\{1,6,11,16,21,26,31,36,\ldots \}$ lassen bez"uglich der
Teilung durch 5 alle den gleichen Rest, d.h sie bilden eine
Restklasse. Die Menge aller Restklassen mod m bezeichnet man kurz mit
${\cal Z}_m$.
Definiert man zwei Verkn"upfungen $+$ und $*$, die den normalen bekannten
Operationen $+$ und $*$ entsprechen, so entsteht ein kommutativer Ring mit
Einselement. Deshalb gelten in einem solchen Restkassenring alle bekannten
Rechenregeln, wie das Distributiv- und Assoziativgesetz. Die Ausnahme
bildet die Division ${a \over b} = a*b^{-1}$, weil in einem Ring nicht
alle Elemente bzgl. $*$ invertierbar sein m"ussen. D.h. es existiert
nicht f"ur alle $x \in {\cal Z}_m$ ein inverses Element $x^{-1}$.\\
Zur Berechnung in diesen Ringen ist es noch wichtig zu wissen, da\3 man wie
mit nat"urlichen Zahlen rechnet und erst dann das Ergebnis einer
Restklasse zuordnet. Dabei soll $\overline{a}$ die Zuordnung von $a$ zu einer
Restklasse bedeuten.\\
Beispiel:
\begin{displaymath}
\overline{x}+\overline{y}=\overline{x+y} \quad
\overline{x}*\overline{y}=\overline{x*y} \quad x,y \in {\cal N}
\end{displaymath}
D.h. im Restklassenring mod 5 lautet das Ergebnis der
Addition $4+3=7=2$. Weil die Zahlen 7 und 2 der gleichen
Restklasse angeh"oren.
Da ${\cal Z}_n$ ein endlicher Ring ist, k"onnen die
Verkn"upfungen $+$ und $*$ auch durch Gruppentafeln definiert
werden.

\begin{center}
 \begin{tabular} {cc}
  \multicolumn{2}{c}{Beispiel f"ur einen Restklassenring mod 5}\\

  \begin{tabular}[t] {|r|r|r|r|r|r|} \hline
   + & 0 & 1 & 2 & 3 & 4 \\ \hline
   0 & 0 & 1 & 2 & 3 & 4 \\ \hline
   1 & 1 & 2 & 3 & 4 & 0 \\ \hline
   2 & 2 & 3 & 4 & 0 & 1 \\ \hline
   3 & 3 & 4 & 0 & 1 & 2 \\ \hline
   4 & 4 & 0 & 1 & 2 & 3 \\ \hline
  \end{tabular}

  \hspace{0.7cm}

  \begin{tabular}[t] {|r|r|r|r|r|r|} \hline
   * & 0 & 1 & 2 & 3 & 4 \\ \hline
   0 & 0 & 0 & 0 & 0 & 0 \\ \hline
   1 & 0 & 1 & 2 & 3 & 4 \\ \hline
   2 & 0 & 2 & 4 & 1 & 3 \\ \hline
   3 & 0 & 3 & 1 & 4 & 2 \\ \hline
   4 & 0 & 4 & 3 & 2 & 1 \\ \hline
  \end{tabular}

 \end{tabular}
\end{center}

\subsection [Die Einheitengruppen] {Die Einheitengruppen}
F"ur die Einheitengruppe ${\cal R}^*$ gilt:
$${
{\cal R}^* = \{ x \in {\cal R} | x\ ist\ invertierbar \}
\mbox{ also } x \in {\cal R}^* \Rightarrow \exists\ y:xy=yx=1
}$$
Es zeigt sich, da\3 x dann zur Einheitengruppe ${\cal R}^*$
geh\"ort, wenn x teilerfremd zu n ist, d.h wenn x in ${\cal R}$
invertierbar ist.
$${
{\cal Z}^*_n=\{x \in {\cal Z}_n | ggT(x,n)=1 \}
}$$
Beweis:\\
In jedem euklidischen Ring existiert eine lineare Darstellung des ggT
$$ggT(x,n)=1 \Leftrightarrow ax+bn=1$$
Es gilt:
\begin{displaymath}
\begin{array}{rrrrl}

&{ax+\underbrace{bn}_{=0}}&=&1&mod\ n\\
\Rightarrow&ax&=&1&mod\ n\\
\Rightarrow&a&=&x^{-1}&mod\ n\\
\end{array}
\end{displaymath}
{\noindent Deshalb ist x genau dann invertierbar, wenn ggT(x,n)=1 ist.}

\subsection[Die Eulersche ${\cal \varphi}$-Funktion]
{Die Eulersche ${\cal \varphi}$-Funktion}
Unter der Eulerschen ${\cal \varphi}$-Funktion versteht man die Abbildung
${\cal \varphi}:{\cal N} \longmapsto {\cal N}$ mit:
$${{\cal \varphi}(n)}=n*\prod(1-{1 \over p}),\ wobei\ p\ \in\ {\cal P}\
\wedge\ p|n$$
${\cal \varphi}(n)$ ist die Anzahl der invertierbaren Elemente in
${\cal Z}_n$, d.h. die Anzahl der Elemente in der dazugeh"origen
Einheitengruppe ${\cal Z}^*_n$.\\
Beispiel:\\
In ${\cal Z}_{15}$ sind 8 Zahlen invertierbar:
\begin{displaymath}
{\cal Z}^*_{15}:=\{1,2,4,7,8,11,13,14\}
\end{displaymath}
Was durch einfaches Ausprobieren leicht nachgepr"uft werden kann.\\
Die Zahl 15 hat die Primfaktorisierung $15=3*5$. Deshalb berechnet sich
$${\cal \varphi}(15)=15*(1-{1\over3})*(1-{1\over5})=8.$$
Sollte sich, wie beim RSA-Verfahren, n nur aus zwei Primfaktoren $p \not= q$
zusammensetzen, so kann ${\cal \varphi}(n)$ auch durch
$${\cal \varphi}(n)={\cal\varphi}(pq)=p*q*(1-{1 \over p})*(1-{1 \over q})=
(p-1)*(q-1),\ wobei\ p,q \in {\cal P}$$
errechnet werden. Diese vereinfachte Berechnung der Eulerschen
${\cal \varphi}$-Funktion ist besonders f"ur die Schl"usselerzeugung von
besonderer Bedeutung, weil dort die ${\cal \varphi}$-Funktion von Zahlen
dieses Typs ermittelt werden mu\3.
%
\subsection[Die Schl"usselgenerierung] {Die Schl"usselgenerierung}
Die eigentliche Schl"usselgenerierung ist dann einfach.
\begin{itemize}
\item W"ahle zwei gro\3e Primzahlen p und q und berechne $n=p*q$\\
Um eine ausreichende Sicherheit zu gew"ahrleisten sollten die Zahlen
p und q ca. 100 Stellen lang sein und sich in ihrer L"ange um einige
Dezimalstellen unterscheiden.\footnote{In dieser Studienarbeit konnte
aufgrund von Rechenzeitproblemen nur mit erheblich kleineren Primzahlen
gearbeitet werden.}\\
Wird dies nicht beachtet oder werden die Primzahlen zu klein gew"ahlt, so
kann das Verfahren durch die Primfaktorisierung der Zahl n ''geknackt``
werden. Der schnellste hierzu bekannte Algorithmus hat einen Aufwand von
$$ Aufwand=ln(n)^{\sqrt{ln(n) \over
{ln(ln(n))}}}\ Operationen$$
Bei einer 200-stelligen Zahl w"urde die Faktorisierung
$\approx 1.2*10^{23}$ Operationen ben"otigen. Sollte dazu ein normaler
1 MIPS-Rechner verwendet werden, w"urde dies
$\approx 4*10^9$ Jahre Rechenzeit ben"otigen.
Dabei ist zu beachten, da\3 eine Implementation auf Softwarebasis weitaus
mehr Operationen f"ur einen Rechenschritt durchf"uhren mu\3, weil z.B.
eine 200-stellige Addition auf einem gew"ohnlichen Rechner weitaus
mehr Teiloperationen zur Abarbeitung braucht.
Deshalb ist der reale Aufwand im Wirklichkeit um einige Gr"o\3enordnungen
h"oher.\\
Die Forderung, da\3 sich die Primzahlen p und q um einige
Dezimalstellen unterscheiden sollen, hat folgende Begr"undung:\\
Sollten die Primzahlen zu nahe beieinander liegen, so existiert ein
effizienter Algorithmus zur Bestimmung der Primfaktoren:\\
{\absatz {Ansatz:\hfill}
$n=(a+b)(a-b)=a^2-b^2$, d.h suche ein a f"ur das $a^2-n$ eine
Quadratzahl.\\
Wenn $b^2$ keine Quadratzahl ist, dann inkrementiere a und f"uhre das Verfahren noch einmal
durch.\\
Beispiel: n=2773 $\rightarrow \lceil \sqrt{n} \thinspace \rceil = 53
=a$\\
$a^2-n = 36 \Rightarrow b=6$\\
$n=(53+6)(53-6)=59*47$.
}\\
Weil die zu erzeugenden Primzahlen sehr gro\3 sein m"ussen, versagen
klassische Verfahren wie das ``Sieb des Erathostenes'' aufgrund von
Speicherproblemen und mangelnder Rechenzeit. Deshalb mu\3te der
Miller-Rabin-Test ($\longrightarrow{}\ref{Miller}$) verwendet werden.
\item Berechne die Eulersche ${\cal \varphi}$-Funktion von n mit ${\cal
\varphi}(n)=(p-1)(q-1)$
\item W"ahle ein e $ \in {\cal Z}_{{\cal \varphi}(n)}$, soda\3
$ggT(e,{\cal \varphi}(n))=1$.\\
Da p,q $\in {\cal P} \wedge p,q>2$ sind beide Zahlen ungerade. Deshalb
sind die Zahlen $p-1$ und $q-1$ gerade.
\begin{displaymath}
\begin{array}{rrrl}
\Rightarrow&p-1&=&2p'\\
\Rightarrow&q-1&=&2q'\\
\Rightarrow&{\cal \varphi}(n)&=&4p'q' \Rightarrow 4|{\cal \varphi}(n)\\
\end{array}
\end{displaymath}
Aus diesem Grund darf e nie durch 2 oder 4 teilbar sein.\\
W"ahlt man einfach eine Zufallszahl, so ist die Wahrscheinlichkeit
das e und ${\cal \varphi}(n)$ teilerfremd sind $\frac{6}{\pi^2}
\approx 0.6079$. Auf einen Beweis wird hier verzichtet, weil er keinen Nutzen
zur Auffindung von $e$ beitr"agt.\\
Der Einfachkeit halber w"ahlt man deshalb $e \in {\cal P} \mbox{mit }
e \not\hspace{2pt}\mid {\cal \varphi}(n)$, weil dann die
Bedingung $ggT(e,{\cal \varphi}(n))=1$ immer erf"ullt ist.
Man erh"alt den Dechiffrierungsschl"ussel d mit $ed \equiv 1\ mod\ {\cal
\varphi}(n)$, der sich aus der Lineardarstellung des ggT
$$
ex+{\cal \varphi}(n)y=1\ (Euklid-Berlekamp)
$$
als $d:=x\ MOD\ {\cal \varphi}(n)$ ergibt. Jetzt m"ussen die Zahlen p,q und
${\cal \varphi}(n)$ gel"oscht werden, weil sonst ein Angreifer, der
d ermitteln m"ochte, den Schl"ussel aus p und q bzw. ${\cal \varphi}(n)$
berechnen k"onnte.
\end{itemize}

\section[Die Ver- bzw. Entschl"usselung] {Die Ver- bzw. Entschl"usselung}
Beim RSA-Verfahren mu\3 die zu verschl"usselnde Nachricht N eine
ganze Zahl $(0\le N <n)$ sein, d.h $N \in {\cal Z}_n$. Dies
erzeugt einige Schwierigkeiten, wie sp"ater noch erw"ahnt wird. Die
Ver- bzw. Entschl"usselung geschieht dann folgenderma"sen:
$$E(N)=N^e\ mod\ n$$
\centerline{und}
$$D(N)=N^d\ mod\ n$$
Um eine solche Verschl"usselung r"uckg"angig machen zu k"onnen,
ist es notwendig, da\3 E(N) und D(N) folgende Eigenschaften
besitzen:
$$D(E(N))=N=E(D(N))$$
Deshalb ist zu zeigen: $$N^{ed} \equiv N\ (mod\ n)$$
Satz: $$a \equiv b\ mod\ p\ \wedge\ a \equiv b\ mod\ q \Rightarrow a
\equiv b\ mod\ pq$$

{\absatz\noindent{Beweis:\hfill}
{\obeylines
$a \equiv b\ mod\ p \Rightarrow p|(a-b) \Rightarrow a-b=rp$
$a \equiv b\ mod\ q \Rightarrow q|(a-b) \Rightarrow a-b=sq$
$\Rightarrow rp=sq \Leftrightarrow r={sq \over p} \Rightarrow p|sq$
}
Weil p $\ne$ q (Bedingung beim RSA-Verfahren)\par
$\Rightarrow sq=s_1*s_2*s_3*....*s_j*p$ (Primfaktorzerlegung von
$sq$)\par
Deshalb gilt: $p|s \Rightarrow r={s \over p}q$\par
$\Rightarrow tp=s$\par
$\Rightarrow a-b=sq=tpq$\par
$\Rightarrow pq|(a-b) \Rightarrow a \equiv b\ mod\ pq$\par
}
{\noindent Deshalb kann der Beweis $E(D(N))=N=D(E(N))$ in zwei Teilbeweise
aufgeteilt werden.}\\
$N^{ed} \equiv N\ mod\ n $ mit $n=pq$\\
wird in
$$N^{ed} \equiv N\ mod\ p$$ \centerline{und} $$N^{ed} \equiv N\ mod\ q$$
aufgeteilt.\\
Beweis:
\begin{enumerate}
\item[1. Fall] $p|N \Rightarrow N \equiv 0$ mod p,
weil $p|(N-0)$ deshalb $N^{ed} \equiv N \equiv 0$ mod p
%
\item[2. Fall] $p \not\hspace{2pt}\mid N$ (Dies ist der h"aufigste Fall bei
der Anwendung des RSA-Verfahrens)\\
Lineardarstellung des ggT: $ggT(e,{\cal \varphi}(n))=1\\$
$\Rightarrow ed-a{\cal \varphi}(n)=1 \Rightarrow ed=1+a{\cal \varphi}(n)$
\begin{displaymath}
\begin{array}{rrrrrl}

&N^{ed}&\equiv&N&mod&p\\
\Leftrightarrow&N^{1+a{\cal \varphi}(n)}&\equiv&N&mod&p\\
\Leftrightarrow&N*N^{a{\cal \varphi}(n)}&\equiv&N&mod&p\\
\Leftrightarrow&N*N^{{\cal \varphi}(n)^a}&\equiv&N&mod&p\\
\Leftrightarrow&N*\underbrace{N^{p-1^{{q-1}^{a}}}}_{=1}&\equiv&N&mod&p\\
\Leftrightarrow&N&\equiv&N&mod&p\\
\end{array}
\end{displaymath}

\end{enumerate}
F"ur $N^{ed} \equiv N$ mod q wird der Beweis analog gef"uhrt.\\
Die Beziehung $N^{p-1^{q-1{a}}}=1$ ergibt sich aus dem ''Satz von Euler``:
$$
A^{p-1}\ mod\ p=1
$$
Aufgrund der Kommutativit"at der Multiplikation $(ed=de)$ ist auch
gew"ahrleistet, da\3 die Beziehung D(E(N))=N=E(D(N)) gilt.