Seminar zur Zahlentheorie (Osnabrück 2008/09)/Public-Key-Kryptographie

Einführung

Motivation

Schon seit dem Altertum bestehen Wunsch und Notwendigkeit, Nachrichten vor dem Zugriff unbefugter Dritter zu schützen. Schon die Spartaner und später auch Cäsar sollen bei ihren Feldzügen Mitteilungen mit einfachen Chiffren vor dem Feind verborgen haben.
Lag das Hauptanwendungsgebiet kryptographischer Algorithmen noch vor 60 Jahren in der Hauptsache beim Militär und vielleicht vereinzeilt bei heimlichen Liebespaaren, ist eine sichere Datenübertragung nicht zuletzt mit der Verbreitung des Internets auch im täglichen Leben ein entscheidender Faktor geworden. Vom Einkauf bis zum Bankgeschäft werden heute viele Dinge online erledigt, ohne dass man sich Gedanken darüber macht, wer Zugriff auf die versendeten Daten hat. Dabei steigt mit wachsender Internetnutzung und der damit verbundenen, vermehrten Übertragung sensibler Daten die Gefahr, dass Kriminelle private Kommunikation abhören und gesammelte Informationen für ihre Zwecke missbrauchen. Mit Hilfe kryptographischer Verfahren verschlüsselte Kommunikation ist daher im Bereich sicherheitskritischen Informationsaustausches unerlässlich.

Kryptosysteme

Das Prinzip kryptographischer Verfahren ist denkbar einfach: Person A möchte eine wichtige Nachricht an Person B schicken, ohne dass eine andere Person an den Inhalt gelangen kann. Dazu verschlüsselt Person A den Text mit einem Schlüssel und sendet den Geheimtext an Person B, die als einzige in der Lage ist, den Text mit dem passenden Schlüssel wieder zu entschlüsseln.
Solche Verfahren zur sicheren Datenübertragung lassen sich auf verschiedenste Arten umsetzen. Um diese näher beschreiben zu können, werden einige Definitionen benötigt:

Definition (Schlüssel)

Ein Schlüsselpaar $K=(K_{E},K_{D})$ besteht aus dem Chiffrierungsschlüssel
$K_{E}\in {\mathcal {K_{E}}}$ und dem Dechiffrierungsschlüssel $K_{D}\in {\mathcal {K_{D}}}$, wobei ${\mathcal {K_{D}}}$ die Menge aller De-, ${\mathcal {K_{E}}}$ die Menge aller Chiffrierungsschlüssel beschreibt. Die Mächtigkeit des Schlüsselraums ${\mathcal {K}}$ ist ein wichtiges Indiz für die Sicherheit eines Verfahrens. Die Menge der Schlüssel muss notwendigerweise so groß, sein, dass ein Angreifer nicht durch einfaches Ausprobieren den Klartext zurückgewinnen kann.

Definition (Verschlüsselungsfunktion)

Eine Verschlüsselungsfunktion $E:{\mathcal {P}}\times {\mathcal {K_{E}}}{\xrightarrow {}}{\mathcal {C}}$ beschreibt die Abbildung aus der Menge ${\mathcal {P}}$ der Klartexte in die Menge ${\mathcal {C}}$ der Chiffren, die Entschlüsselungsfunktion $D:{\mathcal {C}}\times {\mathcal {K_{D}}}{\xrightarrow {}}{\mathcal {P}}$ die Abbildung der Geheimtexte auf die Klartexte.
Für ein gegebenes Schlüsselpaar $K$ gilt $P=D(E(P,K_{E}),K_{D})$.

Definition (Kryptosystem)

Ein Kryptosystem ist ein 5-Tupel $({\mathcal {P}},{\mathcal {C}},{\mathcal {K}},E,D)$ bestehend aus den Mengen aller Klar- und Geheimtexte, dem Schlüsselraum, sowie der Verschlüsselungs- und der Entschlüsselungsfunktion.
Im Allgemeinen lassen sich die kryptographischen Verfahren in zwei Gruppen einteilen: Die so genannten symmetrischen Verfahren , bei denen sowohl für die Ver- als auch die Entschlüsselung der gleiche, geheim zu haltende Schlüssel genutzt wird, und die asymmetrischen Verfahren , die zur Dechiffrierung einen anderen Schlüssel nutzen als bei der Chiffrierung.

Definition (symmetrisches Verfahren)

Ein Kryptoverfahren heißt symmetrisch , wenn $K_{E}=K_{D}$ gilt. Man spricht dann kurz vom Schlüssel $K$ und identifiziert $K$ mit $K_{E}$.

Beispiel (Caesar-Chiffre)

Das einfachste symmetrische Verschlüsselungsverfahren ist die so genannte Caesar-Chiffre, die auf monoalphabetischer Substitution beruht. Die Klartexte $P$ bestehen aus einer endlichen Folge $(p_{i})_{i\geq 1},p_{i}\in [0,\ldots ,n-1]$. Für den Schlüssel $K$ wählt man $K_{E}=K_{D}\in [1,\ldots ,n-1]$. $n$ ist hierbei die Mächtigkeit des verwendeten Alphabets. Es gilt $c_{i}=E(p_{i},K)=p_{i}+K\mod n$ und $p_{i}=D(c_{i},K)=c_{i}-K\mod n$, womit das Verfahren vollständig beschrieben ist.

Dass das Caesar-Verfahren sehr unsicher ist, springt sofort ins Auge. Die Größe des Alphabets übersteigt selten 100 Buchstaben, so dass sogar ein ungeübter Taschenrechner schnell alle möglichen Schlüssel testen und den Geheimtext so entschlüsseln kann. Das ist natürlich nur der Einfachheit des Beispiels geschuldet und kein generelles Problem der symmetrischen Verfahren.

Symmetrische Verfahren haben bei der Kommunikation über das Internet dennoch entscheidende Nachteile:

• Beide Kommunikationspartner müssen den geheimen Schlüssel kennen, der für die Verschlüsselung genutzt wird. Will also zum Beispiel eine Person eine sichere Bestellung bei einem Internet-Händler aufgeben, muss der Händler zunächst den Schlüssel sicher zum Kunden übertragen, ein sich selbst bedingendes Vorhaben.
• Zudem muss der Empfänger für jeden Kommunikationspartner einen eigenen Schlüssel generieren, da ansonsten jede andere Person (insbesondere ein Angreifer) die Nachrichten anderer Teilnehmer mitlesen könnte.
  
  

Um diese Probleme zu umgehen, werden die so genannten asymmetrischen Verfahren genutzt. Sie verwenden für Ver- und Entschlüsselung jeweils eigene Schlüssel $K_{E}$ und $K_{D}$. Der Chiffrierungs-Schlüssel $K_{E}$ soll hierbei sogar öffentlich bekannt gegeben werden, damit er von allen Beteiligten, die dem Schlüsseleigner eine Nachricht senden wollen, zur Chiffrierung verwendet werden kann. Diese Verfahren werden aus diesem Grund auch Public-Key-Verfahren genannt. Um Sicherheit und Anwendbarkeit gewährleisten zu können, werden einige Forderungen an die Verfahren gestellt:

• Die Funktionen $D$ und $E$ müssen effizient berechenbar sein.
• $K_{E}$ und $K_{D}$ müssen mit angemessenem Aufwand erzeugbar sein.
• Aus einem gegebenen Geheimtext und dem Schlüssel $K_{E}$ darf sich nicht der ursprüngliche Klartext ermitteln lassen.
• Die Bestimmung von $K_{D}$ aus $K_{E}$ darf bei gegebenem, frei gewählten Klartext nicht möglich sein.

Die Funktionen für Ver- und Entschlüsselung sind bei den asymmetrischen Verfahren so genannte Einwegfunktionen mit Falltür . Darunter versteht man injektive Funktionen $f:X{\xrightarrow {}}Y$, für die $y=f(x)$ leicht zu bestimmen ist, $x=f^{-1}(y)$ jedoch schwer, solange keine weiteren Parameter bekannt sind.

Das RSA-Verfahren

Eines der ersten Public-Key-Verfahren ist RSA , dessen Algortihmus 1977 von Ron Rivest, Adi Shamir und Leonard Adleman vorgestellt und zum Patent angemeldet wurde. RSA verwendet als Verschlüsselungsfunktion das Potenzieren in Restklassen. Seine Sicherheit bezieht das Verfahren dabei aus der Tatsache, dass derzeit kein Verfahren existiert, mit dem man die Primfaktorzerlegung einer Zahl mit geringem Aufwand bestimmen kann.
Im Folgenden soll nun zunächst ein Blick darauf geworfen werden, wie das RSA-Verfahren funktioniert und wie RSA-Schlüssel erzeugt werden. Anschließend wird das eigentliche Verfahren der Chiffrierung und Dechiffrierung betrachtet und zum Schluss noch einmal auf die Sicherheit des Verfahrens eingangen.

Bestandteile des Kryptosystems

Alphabet und Schlüssel

Für die Beschreibung des Kryptosystems RSA wird zuallererst eine natürliche Zahl $n=pq$ benötigt, deren einzige aus Sicherheitsgründen verschiedenen Primfaktoren $p$ und $q$ sind. Sie legt alle wichtigen Eigenschaften von RSA fest.

$n$ bestimmt die Mächtigkeit des Alphabets, aus dem die Klar- und Geheimtexte bestehen. Es gilt wie schon bei der Caesar-Chiffre gesehen, dass die Klartexte $P$ aus einer endlichen Folge bestehen, wobei

$(p_{i})_{i=1}^{k},p_{i}\in \mathbb {Z} /(n)$

gilt. Speziell könnte man noch 0 und 1 aus dem Definitionsbereich ausschließen, da diese identisch abgebildet werden. Die Wahrscheinlichkeit, dass sie auftreten, ist in der Praxis jedoch so gering, dass darauf auch verzichtet werden kann.
Die Geheimtexte $C$ sind ebenfalls endliche Folgen über dem gleichen Alphabet, es gilt also

$(c_{i})_{i=1}^{k},c_{i}\in \mathbb {Z} /(n)$

.

Zur Verschlüsselung wird die Funktion $E:P\times K_{E}\rightarrow C$ mit

$c_{i}=(p_{i})^{e}\mod n$

verwendet.
Die Entschlüsselungsfunktion $D:C\times K_{D}\rightarrow P$ bildet wie folgt ab:

$p_{i}=(c_{i})^{d}\mod n$

Der Schlüssel für die Chiffrierung muss also offensichtlich aus zwei Bestandteilen bestehen, nämlich $e$ und $n$. Für $D$ benötigt man neben dem Geheimtext die Bestandteile $d$ und $n$. Zusammenfassend lässt sich also sagen:

$K=(K_{E},K_{D})=((e,n),(d,n))$

Korrektheit des Verfahrens

Bevor die Korrektheit von RSA nachgewiesen werden kann, seien noch einmal einige grundlegende Begriffe für den kommutativen Ring $\mathbb {Z} /(n)$ wiederholt:

Satz (Einheit in $\mathbb {Z} /(n)$)

Eine Zahl $a$ ist genau dann Einheit in $\mathbb {Z} /(n)$, wenn $a$ und $n$ teilerfremd sind.

Beweis

Der Beweis folgt direkt aus dem Lemma von Bézout . Sind $a$ und $n$ teilerfremd, so gibt es eine Darstellung $xa+yn=1$ und damit $xa\equiv 1\mod n$ und $a$ Einheit. Ist $a$ umgekehrt Einheit, so existiert ein $g\in \mathbb {Z} /(n)$ mit $ga\equiv 1\mod n$ und somit wiederum eine Vielfachendarstellung $ga+hn=1$.$\square$

Definition (Einheitengruppe)

Die Einheiten von $\mathbb {Z} /(n)$ bilden die Einheitengruppe $\mathbb {Z} /(n)^{\times }$. Die Anzahl der Elemente in $\mathbb {Z} /(n)^{\times }$ wird gegeben durch die Eulersche $\varphi$-Funktion: $\varphi (n)=|\mathbb {Z} /(n)^{\times }|$. Es gilt im Falle von RSA

$\varphi (n)=\varphi (p\cdot {q})=\varphi (p)\cdot \varphi (q)=(p-1)\cdot (q-1)$,

da $\varphi$ als zahlentheoretische Funktion multiplikativ ist und $p$ und $q$ als Primzahlen zweifelsohne teilerfremd sind.

Damit $D$ und $E$ wirklich kryptographische Funktionen sind, also $P=D(E(P,K_{E}),K_{D})$ gilt, ist die Wahl von $e$ und $d$ nicht frei. Folgende Forderungen werden an die beiden Exponenten gestellt:

• Wähle $e$, $1<e<\varphi (n)=(p-1)(q-1)$ teilerfremd zu $\varphi (n)$
• Bestimme $d$ so, dass $ed\equiv 1\mod \varphi (n)$
  
  

Der wichtigste Bestandteil im Beweis, dass RSA auf die so definierte Weise korrekt arbeitet, ist der

Satz von Euler

Sei $n$ eine natürliche Zahl. Dann gilt für jede zu $n$ teilerfremde Zahl $a$ die Beziehung

$a^{\varphi (n)}\equiv 1\mod n$.

Beweis

Die zu $n$ teilerfremden Zahlen bilden die Einheitengruppe von $\mathbb {Z} /(n)$. Der Satz von Lagrange sagt nun gerade aus, dass die Ordnung jedes Elements ein Teiler der Gruppenordnung ist. Diese ist $m=\operatorname {ord} (\mathbb {Z} /(n)^{\times })=|\mathbb {Z} /(n)^{\times }|=\varphi (n)$, also gilt für alle Elemente $a:a^{m}=1$. $\square$

Die Anforderung an $d$ und $e$ war nun gerade, dass $ed\equiv 1\mod \varphi (n)$ ist, oder anders ausgedrückt $ed=k\varphi (n)+1$, wobei $k$ eindeutig bestimmt ist. Setzt man diese Formel ein, so ergibt sich ohne Umschweife

$a\equiv 1\cdot a\equiv a^{k\varphi (n)}\cdot a\equiv a^{k\varphi (n)+1}\equiv a^{ed}\equiv {(a^{e})}^{d}\mod n$.

Nun gilt der Satz von Euler nur bei zu $n$ teilerfremden Zahlen. Zusätzlich müssen also auch noch die Nullteiler betrachtet werden. O.B.d.A gelte $p\mid a\neq 0\mod n$, denn der Fall, dass $a$ von $q$ geteilt wird, läuft vollkommen analog ab.

Die multiplikative Eigenschaft der eulerschen $\varphi$-Funktion liefert schnell folgende

Bemerkung

Gilt $ed\equiv 1\mod \varphi (pq)$ für zwei Primzahlen $p$ und $q$, so folgt

$ed\equiv 1\mod (p-1)$ und $ed\equiv 1\mod (q-1)$.

Bemerkung

Auf $a$ kann nun wiederum der Satz von Euler angewandt werden. Es ergeben sich die folgenden beiden Kongruenzen:

• $a\equiv a^{u(q-1)+1}\equiv a^{ed}\mod q$ für ein $u\in \mathbb {Z}$
• $a\equiv a^{p}\equiv a^{ed}\mod p$

Beweis

Die erste Kongruenz gilt offensichtlich, da $a\neq 0$ teilerfremd zu $q$ ist und die Voraussetzungen des Satzes von Euler erfüllt sind. Ebenso trivial ist auch 2., weil $a$ ein Vielfaches von $p$ ist. Es ergibt sich $a=zp\equiv 0\equiv 0^{p}\equiv (zp)^{p}\equiv a^{p}\mod p$.$\square$

Um von hier aus zum Ziel zu kommen, wird der chinesische Restsatz benötigt, der die Beziehung zwischen $\mathbb {Z} /(n)$, $\mathbb {Z} /(p)$ und $\mathbb {Z} /(q)$ herstellt.
Die folgende Version des chinesischen Restsatzes ist in allgemeiner Version bereits bekannt:

Chinesischer Restsatz

Seien $p,q\in \mathbb {P}$ verschiedene Primzahlen und $n=pq$. Dann induzieren die kanonischen Ringhomomorphismen ${\mathbb {Z} }/(n)\rightarrow {\mathbb {Z} }/({p})$ und ${\mathbb {Z} }/(n)\rightarrow {\mathbb {Z} }/({q})$ einen Isomorphismus ${\mathbb {Z} }/(n)\cong {\mathbb {Z} }/({p})\times {\mathbb {Z} }/({q})$ .
Insbesondere gibt es zu gegebenen ganzen Zahlen $a_{p},a_{q}$ also genau eine natürliche Zahl $a<n$, die die simultanen Kongruenzen $a=a_{p}\mod p,a=a_{q}\mod q$ löst.

Beweis

Da die endlichen Ringe ${\mathbb {Z} }/(n)$ und ${\mathbb {Z} }/({p})\times {\mathbb {Z} }/({q})$ die gleiche Anzahl von Elementen haben, nämlich $n$, genügt es, die Injektivität der induzierten Abbildung zu zeigen. Sei $x$ eine natürliche Zahl, die in ${\mathbb {Z} }/({p})\times {\mathbb {Z} }/({q})$ zu null wird, also modulo $pq$ den Rest null hat. Dann ist $x$ ein Vielfaches von $pq$, d.h., in der Primfaktorzerlegung von $x$ muss $p$ und $q$ vorkommen. Also muss $x$ nach Teilbarkeitskriterium ein Vielfaches des Produktes sein, also ein Vielfaches von $n$. Damit ist $x\equiv 0\in {\mathbb {Z} }/(n)$ und die Abbildung ist injektiv. $\square$

Auf Grundlage der ersten Bemerkung gilt

$(a_{1},a_{2})^{ed}\equiv (a_{1},a_{2})$ für alle $(a_{1},a_{2})\in {\mathbb {Z} }/({p})\times {\mathbb {Z} }/({q})$.

Mit dem eben erhaltenen Isomorphismus ist die Korrektheit des RSA-Verfahrens bewiesen.

Erzeugung von RSA-Schlüsselpaaren

Mit der Definition einer gültigen Chiffrierfunktion ist ein wichtiger Schritt zum praktikablen Kryptoverfahren getan. Im Folgenden soll nun darauf eingegangen werden, wie die Schlüsselparameter $d$, $e$ und $n$ bestimmt werden.
Es ist nachvollziehbar, dass dabei auch ein Auge darauf geworfen werden sollte, inwiefern sich der Aufwand für die Schlüsselerzeugung in einem akzeptablen Rahmen bewegt.

Um neben den notwendigen mathematischen Grundlagen und Algorithmen auch die Anwendung vorzuführen, wird nach jedem Abschnitt ein kurzes Beispiel folgen.

Beispiel

Angela hat vor Kurzem Barack kennen gelernt. Weil sie nicht möchte, dass ihre Kommunikation von anderen Personen mitgehört werden kann, plant sie, sich ein RSA-Schlüsselpaar zu generieren, mit dem Barack ihr Nachrichten zukommen lassen kann. Angelas Bemühungen werden im weiteren Verlauf als durchgehendes Beispiel dienen, um den Weg von zwei Primzahlen bis zur ersten Nachricht von Barack an Angela zu verfolgen.

Bestimmung des RSA-Moduls $n$

Zu Beginn der RSA-Schlüsselerzeugung wird zunächst der Modul bestimmt, der die Restklassen festlegt. Dazu wählt man zwei große Primzahlen $p,q$ bestimmter Länge und setzt

$n=p\cdot q$.

Mit $n$ ist gleichzeitig der Raum der Klar- und Geheimtexte festgelegt: Er wird, wie schon erwähnt, repräsentiert durch die Menge der Elemente im Restklassenring $\mathbb {Z} /(n)$.

Da RSA ein Kryptoverfahren ist, das aufgrund seiner Komplexität die Verwendung von Computern verlangt, wird die Länge der Primzahl in Bit angegeben. $p$ und $q$ haben im Binärsystem eine feste Anzahl Ziffern, üblicherweise $2^{9}=512$ Bit, in besonders sicherheitskritischen Bereichen häufig auch 1024 oder sogar 2048 Bit.

Was in der Theorie einfach klingt, stellt in der Praxis ein relativ großes Problem dar. Wie aus der Zahlentheorie-Vorlesung bekannt ist, besagt das Betrandsche Postulat , dass sich in Intervallen $[n,2n],n\in \mathbb {N}$ immer eine Primzahl finden lässt. Ein nicht triviales Verfahren zur Bestimmung dieser Primzahl existiert hingegen nicht.

Lemma (Aufwand der Primzahlbestimmung)

Der Aufwand, eine Primzahl $p$ der Länge $k=\log _{2}(p)$ in einem gegebenem Intervall $[2^{\lfloor \log _{2}(p)\rfloor },2^{\lceil \log _{2}(p)\rceil }]$ zu finden, ist in der Komplexitätsklasse ${\mathcal {O}}(kR)$, wobei $R$ der Aufwand ist, eine Zahl auf Primalität zu testen.

Beweis

Der Primzahlsatz von Hadamard und de la Vallée Pousin liefert eine grobe Abschätzung für die Anzahl der Primzahlen, die kleiner als eine gegebene Zahl $n$ sind. Für die die Primzahlfunktion $\pi (n):=|\{x<n:x$ prim$\}|$ gilt demnach die Abschätzung

$\pi (n)\sim {\frac {n}{\ln(n)}}$.

Für Zahlen der festen Länge $k$ aus dem Intervall $[2^{k-1},2^{k})$ ergibt sich aus dieser Formel durch Einsetzen:

$\pi (2^{k})-\pi (2^{k-1})\approx {\frac {2^{k}}{k\cdot \ln(2)}}-{\frac {2^{k-1}}{(k-1)\cdot \ln(2)}}={\frac {(k-1)2^{k}-k2^{k-1}}{k(k-1)\ln(2)}}>{\frac {(k-1)2^{k}-k2^{k-1}}{k^{2}}}$.

Der Anteil der Primzahlen unter den $2^{k-1}$ Binärzahlen der Länge $k$ liegt also etwa bei

${\frac {(k-1)2^{k}-k2^{k-1}}{k^{2}2^{k-1}}}={\frac {2(k-1)-k}{k^{2}}}={\frac {k-2}{k^{2}}}$.

Zum Finden einer solchen Primzahl benötigt man also durchschnittlich etwa

${\frac {k^{2}}{k-2}}\approx {k}$

Versuche.$\square$

Beispiel

Angela entscheidet sich der Übersichtlichkeit wegen für Zahlen der Länge 8 im Binärsystem. Die Primzahlen $p=151$ und $q=251$ entnimmt sie einer Primzahltabelle. Ihr RSA-Modul ist also $n=151\cdot 251=37901$.

Bestimmung des Verschlüsselungs-Exponenten $e$

Nach der Bestimmung des Moduls erfolgt als nächstes die Wahl des Verschlüsselungsexponenten $e$. Dieser muss teilerfremd zur Mächtigkeit von $\mathbb {Z} /(n)^{\times }$ und kleiner als dieselbe sein.
Da sich $e$ innerhalb der gegebenen Beschränkungen frei wählen lässt, wird in der Praxis häufig $e=2^{16}+1=65537$ verwendet.
Ist das $e$ relativ klein, hat dies den Vorteil, dass die Verschlüsselung schneller ist, da weniger Zeit zum Potenzieren aufgewendet werden muss. Zudem wird bei größerem $e$ der Aufwand größer, die Teilerfremdheit von $e$ und $\varphi (n)$ sicherzustellen.

Beispiel

Angela sucht also ein $e\in \mathbb {Z}$ mit $1<e<\varphi (n)$ und $\operatorname {ggT} (e,\varphi (n))=1$.
Sie berechnet $\varphi (n)=\varphi (37901)=\varphi (151)\cdot \varphi (251)=150\cdot 250=37500$ und wählt als dazu teilerfremdes $e$ die Zahl $e=91$.

Bestimmung des Entschlüsselungs-Exponenten $d$

Ist $e$ bestimmt, kann der Dechiffrier-Exponent $d$ berechnet werden. Während $n$ und $e$ wegen der wenigen Anforderungen, die an sie gestellt wurden, noch recht einfach zu bestimmen waren, ist die Bestimmung von $d$ ungleich aufwendiger und benötigt einige Vorbereitung.

Der Entschlüsselungs-Exponent soll das Inverse von $e$ in $\mathbb {Z} /(n)^{\times }$ sein. Um $d$ zu ermitteln, wird wieder das bereits erwähnte Lemma von Bézout benötigt.
Die allgemeine Version wurde in der Vorlesung behandelt. Im Speziellen wird die Aussage für zwei teilerfremde Elemente in $\mathbb {Z}$ benötigt.

Lemma (Lemma von Bézout)

Zwei Elemente $a_{1},a_{2}\in \mathbb {Z}$ besitzen stets einen größten gemeinsamen Teiler $g$, und dieser lässt sich als Linearkombination von $a_{1}$ und $a_{2}$ darstellen, d.h. es gibt Elemente $r_{1},r_{2}\in \mathbb {Z}$ mit $r_{1}a_{1}+r_{2}a_{2}=g$.
Insbesondere besitzen teilerfremde Elemente $a_{1},a_{2}$ eine Darstellung der 1.

Beweis

Sei $I=(a_{1},a_{2})$ das von den Elementen erzeugte Ideal. Da $\mathbb {Z}$ ein Hauptidealring ist, handelt es sich um ein Hauptideal. Es gibt also ein Element $g$ mit $I=(g)$. Wir behaupten, dass $g$ ein größter gemeinsamer Teiler von $a_{1}$ und $a_{2}$ ist. Weil sowohl $a_{1}\in I=(g)$ als auch $a_{2}\in I=(g)$ ist, muss $g$ beide teilen. Sei nun $h$ ein weiterer gemeinsamer Teiler von $a_{1}$ und $a_{2}$. $h$ teilt dann alle Elemente in $I$, speziell also auch $g\in I$. Aus $g\in I=(a_{1},a_{2})$ folgt unmittelbar auch die Existenz der gesuchten Darstellung.
Im teilerfremden Fall ist $I=(a_{1},a_{2})=(g)=\mathbb {Z}$ wegen $g=1$.$\square$

Da $\varphi (n)$ und $e$ teilerfremd gewählt wurden, muss für das gesuchte $d$ gelten:

$d\cdot e+k\cdot \varphi (n)=1$ für ein $k\in {\mathbb {Z} }$.

Um $d$ und $k$ zu bestimmen, wird der erweiterte euklidische Algorithmus verwendet. Dazu wird zunächst ein Blick auf die euklidische Restfolge und ihre Eigenschaften geworfen:

Definition

Seien zwei Elemente $a,b\neq 0$ eines euklidischen Bereichs $R$ mit euklidischer Funktion $\delta$ gegeben. Dann nennt man die durch die Anfangsbedingungen $a_{0}=a$ und $a_{1}=b$ und die mittels der Division mit Rest $a_{i}=q_{i}a_{i+1}+a_{i+2}$ rekursiv bestimmte Folge $(a_{i})$ die Folge der euklidischen Reste.

Satz (Eigenschaften der euklidischen Restfolge)

Seien zwei Elemente $a_{0}=a,a_{1}=b\neq 0$ eines euklidischen Bereichs $R$ mit euklidischer Funktion $\delta$ gegeben. Dann besitzt die Folge $(a_{i})_{i\geq 0}$ der euklidischen Reste folgende Eigenschaften:

1. Es ist $a_{i+2}=0\,\,{\mbox{ oder }}\,\,\delta (a_{i+2})<\delta (a_{i+1})\,$.
2. Es gibt ein (minimales) $k\geq 2$ mit $a_{k}=0$.
3. Es ist $\mathrm {ggT} (a_{i+1},a_{i})=\mathrm {ggT} (a_{i},a_{i-1})$.
4. Sei $k\geq 2$ der erste Index derart, dass $a_{k}=0$ ist. Dann ist $\mathrm {ggT} (a,b)=a_{k-1}$.

Beweis

1. Ist eine direkte Folgerung aus der Definition der Division mit Rest.
2. Folgt direkt aus 1., da $\delta (a_{i})$ immer kleiner wird, also null erreichen muss.
3. Wenn $g$ ein gemeinsamer Teiler von $a_{i+1}$ und $a_{i+2}$ ist, so ist $g$ wegen $a_{i}=q_{i}a_{i+1}+a_{i+2}$ auch ein Teiler von $a_{i}$ und damit ein gemeinsamer Teiler von $a_{i+1}$ und $a_{i}$. Entsprechend folgt auch die Umkehrung.
4. Folgt aus 3. durch die Verkettung

$\mathrm {ggT} (a,b)=\mathrm {ggT} (b,a_{2})=\mathrm {ggT} (a_{2},a_{3})=\ldots =\mathrm {ggT} (a_{k-1},a_{k})=\mathrm {ggT} (a_{k-1},0)=a_{k-1}$.

Um nun zu $a$ und $b$ die passenden Koeffizienten nach Bézout zu ermitteln, werden zwei weitere Folgen $(x_{i})_{i\geq 0}$ und $(y_{i})_{i\geq 0}$ benötigt:

Satz (Erweiterter euklidischer Algorithmus)

Es seien $a$, $b$ und $(a_{i})_{i\geq 0}$ wie eben. Man setze

$x_{0}=1$, $x_{1}=0$, $y_{0}=0$, $y_{1}=1$.

Für $i\geq 1$ gelte:

$x_{i}=q_{i}x_{i+1}+x_{i+2}$
$y_{i}=q_{i}y_{i+1}+y_{i+2}$

Ist $k+1$ der erste Index, so dass $a_{k+1}=0$, dann ist

$\operatorname {ggT} (a,b)=a_{k}=x_{k}\cdot a+y_{k}\cdot b$

Beweis

Es reicht, per Induktion zeigen, dass für alle Glieder der euklidischen Restfolge $(a_{i})_{i\geq 0}$ gilt $a_{i}=x_{i}a+y_{i}b$.
Die getroffene Wahl von $a_{i},x_{i},y_{i}$ für $i\in \{0,1\}$ ergibt die Induktionsverankerung:

$a=a_{0}=x_{0}a+y_{0}b=1a+0b=a$
$b=a_{1}=x_{1}a+y_{1}b=0a+1b=b$

Der Induktionsschritt für $a_{i+2}$ folgt durch wiederholtes Einsetzen:

$a_{i+2}=a_{i}-q_{i}a_{i+1}=(x_{i}a+y_{i}b)-q_{i}(x_{i+1}a+y_{i+1}b)=(x_{i}-q_{i}x_{i+1})a+(y_{i}-q_{i}y_{i+1})b=x_{i+2}a+y_{i+2}b\square$

Beispiel

Angela hatte $\varphi (n)=37500$ berechnet und $e=91$ bestimmt. Jetzt muss sie also mit $d\cdot e+k\cdot \varphi (n)=1$ das $d$ bestimmen:

$d\cdot e+k\cdot \varphi (n)=1\Rightarrow d\cdot 91+k\cdot 37500=1$

Der Effizienz wegen wählt sie $a_{0}=37500,a_{1}=91$. Die $q_{i}$ ergeben sich aus $q_{i}={\lfloor {\frac {a_{i}}{a_{i+1}}}\rfloor }$. So nähert sich Angela Schritt für Schritt ihrem gesuchten $d$ an:

$i$	$a_{i}$	$q_{i}$	$x_{i}$	$y_{i}$
0	37500	412	1	0
1	91	11	0	1
2	8	2	1	-412
3	3	1	-11	4533
4	2	2	23	-9478
5	1	-	-34	14011
6	0	-	-	-

Da $x_{i}$ der Koeffizient von $\varphi (n)$ war und $y_{i}$ der von $e$, folgt also $d=y_{5}=14011$. Angelas Proberechnung ergibt $ed=91\cdot 14.011=1.275.001\equiv 1\mod 37500$, das $d$ ist also tatsächlich das multiplikative Inverse von $e\mod \varphi (n)$.

Mit der Berechnung von $d$ ist die Schlüsselerzeugung abgeschlossen. Nun kann der öffentliche Schlüssel $K_{E}=(e,n)$ bekannt gegeben werden, so dass andere Personen dem Schlüsseleigner verschlüsselte Nachrichten zukommen lassen können.
Es ist essentiell wichtig, dass kein anderer der zuvor verwendeten Parameter bekannt wird, da sonst problemlos ein Angriff auf das Kryptosystem möglich ist. Diese Restriktion gilt nicht nur für $d$, sondern in gleichem Maße auch für $\varphi (n)$ und natürlich für $p$ und $q$, wie im Abschnitt über die Sicherheit noch einmal kurz beleuchtet wird.

Kommunikation mit RSA

Ist der RSA-Schlüssel veröffentlich worden, kann die eigentliche Kommunikation mittels RSA erfolgen. Diese zerfällt im Wesentlichen in fünf einzelne Schritte:

1. Umwandlung der Nachricht in eine Zahlenfolge
2. Berechnung der Chiffre-Folge
3. Datenübertragung
4. Dechiffrierung der Chiffre
5. Rückgewinnung der Nachricht aus der Zahlenfolge

Besonderes Augenmerk wird hier auf die Chiffrierung und Dechiffrierung gelegt, da diese noch zum Kernbereich des RSA-Systems gehören.
Die Erzeugung gut gewählter Zahlenfolgen und die Übertragung der Daten ist zwar ebenfalls ein interessantes Teilgebiet der Algebra und algebraischen Zahlentheorie, allerdings ist sie unabhängig vom RSA-Algorithmus und würde den Rahmen dieser Arbeit bei weitem sprengen. Daher soll im weiteren Verlauf davon ausgegangen werden, dass die fehlerfreie Übermittlung einer verschlüsselten Nachricht sichergestellt ist und der Empfänger eines Chiffretextes diesen so erhält, wie ihn der Absender losgeschickt hat. Eine Einführung in das Thema Kodierungstheorie bietet zum Beispiel R.-H. Schulz.

Abbildung einer Nachricht auf eine Zahlenfolge

Um eine Nachricht mit RSA verschlüsseln zu können, muss sie als Folge $(p_{i})_{i\geq 0}$ von natürlichen Zahlen aus dem Intervall $[0,n-1]$ vorliegen. Dieses Problem ist mehr theoretischer Natur als eine echte Hürde in der Praxis.
Da in der elektronischen Datenverarbeitung ohnehin alle Daten in einer Binärkodierung vorliegen, kann $(p_{i})$ ohne zusätzlichen Aufwand gebildet werden. Man unterteilt die Bitsequenz schlicht sukzessive von vorne nach hinten, so dass jeder Abschnitt $p_{i}$ kleiner ist als $n$.

Selbstverständlich muss diese Zuordnung aus der Menge der Texte nach $[0,n-1]$ injektiv sein, damit der Empfänger der Nachricht diese am Ende wieder eindeutig in den originalen Klartext übersetzen kann. Andererseits sollte sie den Bildraum möglichst gut ausschöpfen, um keinen Angriffspunkt zu bieten.

Beispiel

Angela und Barack wollen ihre Nachrichten einfach halten. Sie beschränken sich auf die Kleinbuchstaben a bis z, die sie mit 1 bis 26 durchnummerieren, dazu ein \glqq,\grqq (27), den \glqq.\grqq (28) und das Leerzeichen (29). Ein schnelles Nachrechnen ergibt $30^{3}=27000$, die einzelnen Folgenglieder $k_{i}$ bestehen daher aus drei Buchstabenwerten $k_{i,1},k_{i,2},k_{i,3}$ und die beiden setzen $k_{i}=k_{i,1}+k_{i,2}\cdot 30+k_{i,3}\cdot 30^{2}$.

So vorbereitet kann Barack seine erste Nachricht an Angela vorbereiten: hello angie, it works. love, barack

Abschnitt	1	2	3	4	5	6
Text	hel	lo	ang	ie,	it	wo
$p_{i}$	10958	26562	6721	24459	18299	14219
Abschnitt	7	8	9	10	11	12
Text	rks	. l	ove	, b	ara	ck
$p_{i}$	17448	11698	5175	2697	1441	333

Verschlüsseln von Texten mit $e$ und $n$

Der Ersteller einer verschlüsselten Nachricht verfügt über die Kenntnis des Schlüssels $K_{E}=(e,n)$. Wie bereits erwähnt bildet man die Chiffre $c$ eines Klartextes $p$ durch $c\equiv p^{e}\mod n$.
Es steht außer Frage, dass diese Berechnung bei einem Exponenten im Bereich von $e=2^{512}$ auf den ersten Blick jeden Rahmen sprengt. Selbst modernste Rechner können nur etwa $2^{40}$ Operationen in der Sekunde durchführen, $e$-maliges Multiplizieren von $p$ führt also nicht zum Ziel.

Um die Berechnung zu beschleunigen, verwendet man daher einen optimierten Algorithmus zur Potenzierung, den Square-and-Multiply -Algorithmus. Dieser nutzt aus, dass jede Zahl eindeutig als Summe von Zweierpotenzen darstellbar ist:

Bemerkung

Sei $e$ eine natürliche Zahl und $l=\lfloor \log _{2}e\rfloor$. Dann gibt es eine Darstellung von $e$ wie folgt:

$e=\sum \limits _{i=0}^{l}{e_{i}2^{i}}$.

Dabei ist $e_{i}\in \{0,1\}$ die Charakteristik, die angibt, ob die Potenz $2^{i}$ in der Summendarstellung von $e$ vorkommt.
Diese Bemerkung ist lediglich eine Verklausulierung der Binärdarstellung einer Zahl.

Square-and-Multiply

Gegeben seien natürliche Zahlen $p$ und $e$. Gesucht ist $c=p^{e}$. Bestimme $c$ rekursiv durch

$c=p^{e}={\begin{cases}1&{\text{, wenn }}e=0\\p\cdot (p^{\lfloor {\frac {e}{2}}\rfloor })^{2}&{\text{, wenn }}e{\text{ ungerade}}\\(p^{\frac {e}{2}})^{2}&{\text{ sonst}}\end{cases}}$

Benutzt man für die Darstellung von $e$ die Form aus der vorhergehenden Bemerkung, ergibt sich

$p^{e}=p^{e_{0}}\cdot p^{2e_{1}}\cdot \ldots \cdot p^{2^{l}e_{l}}$

und durch Ausklammern folgt

$p^{e}=p^{e_{0}}\cdot (p^{e_{1}}\cdot (\ldots \cdot (p^{e_{l}})^{2})\ldots )^{2})^{2}$,

was der Beschreibung des Algorithmus entspricht, weil $p^{e_{i}}=p$ ist, wenn $e_{i}=1$, und $p^{e_{i}}=1$ ist, wenn $e_{i}=0$.

Es ist schnell zu erkennen, dass auf diese Weise $l$ Quadrierungen und zusätzlich $|\{e_{i}|e_{i}=1,i=0,\cdots l\}|$ Multiplikationen durchgeführt werden müssen, was in etwa $\log _{2}e$ Operationen entspricht. Bei Anwendung in RSA erfolgt nach jedem Schritt noch die Modulo-Berechnung zum Modul $n$, so dass sich eine Laufzeit von ${\mathcal {O}}(l\cdot \log _{2}(n)^{2})$ ergibt.

Beispiel

Barack hat Angelas Chiffrier-Schlüssel $K_{E}^{A}=(91,37901)$ erhalten und bestimmt als erstes die Darstellung von $e$ als Binärzahl, was ihm die Folge von $e_{i}$ gibt. $e=91_{10}=1011011_{2}$, wobei das höchstwertige Bit an erster Stelle für $i=l$ steht. Nun kann er die Potenzierungen vornehmen:
$c_{1}\equiv 10958^{91}\equiv 10958\cdot 10958^{2}\cdot 10958^{8}\cdot 10958^{16}\cdot 10958^{64}\mod 37901$
$10958^{2}\equiv 7396\mod 37901$
$10958^{4}\equiv 7396^{2}\equiv 9673\mod 37901$
$10958^{8}\equiv 7396^{4}\equiv 9673^{2}\equiv 27261\mod 37901$
$10958^{16}\equiv 7396^{8}\equiv 9673^{4}\equiv 27261^{2}\equiv 37214\mod 37901$
$10958^{32}\equiv 7396^{16}\equiv 9673^{8}\equiv 27261^{4}\equiv 37214^{2}\equiv 17157\mod 37901$
$10958^{64}\equiv 7396^{32}\equiv 9673^{16}\equiv 27261^{8}\equiv 37214^{4}\equiv 17157^{2}\equiv 23483\mod 37901$
$\Rightarrow c_{1}\equiv 10958^{91}\equiv 10958\cdot 7396\cdot 27261\cdot 37214\cdot 23483\equiv 1578\mod 37901$

${\begin{array}{c|c|c|c|c|c|c}i&1&2&3&4&5&6\\\hline p_{i}&10958&26562&6721&24459&18299&14219\\c_{i}&1578&36622&13694&35126&26869&37497\\i&7&8&9&10&11&12\\\hline p_{i}&17448&11698&5175&2697&1441&333\\c_{i}&329&7209&17540&12095&26624&26899\\\end{array}}$

So sendet Barack schließlich seinen Geheimtext, der aus der Folge seiner $c_{i}$ besteht, an Angela:

$C=(1578,36622,13694,35126,26869,37497,329,7209,17540,12095,26624,26899)$

Entschlüsseln von Nachrichten mit $d$ und $n$

Grundsätzlich funktioniert die Entschlüsselung einer Nachricht ebenso wie die Verschlüsselung. Die einzelnen Folgeglieder $c_{i}$ werden mit $d$ potenziert und am Ende erhalten wir ${\tilde {p_{i}}}\equiv c_{i}^{d}\mod n$. Da die Korrektheit des Verfahrens bereits bewiesen wurde und von einer fehlerfreien Übertragung ausgegangen wird, ist ${\tilde {p_{i}}}=p_{i}$.

Mit kleinen Modifikationen kann die Berechnung von $c^{d}\mod n$ allerdings noch spürbar verbessert werden. Da die entschlüsselnde Person Kenntnis von den Primzahlen $p$ und $q$ hat, die dem RSA-Modul $n$ zugrunde liegen, kann die Potenzierung auf die Restklassen modulo $p$ und modulo $q$ zurückgeführt werden. Statt also $p_{i}\equiv c_{i}^{d}\mod n$ zu berechnen, bestimmt sie $p_{i,p}\equiv c_{i}^{d}\mod p$ und $p_{i,q}\equiv c_{i}^{d}\mod q$.
Um daraus das korrekte $p_{i}$ zu bestimmen, wird die Folgerung des chinesischen Restsatzes benutzt, dass ein System simultaner Kongruenzen teilerfremder Moduln eine eindeutige Lösung modulo des Produkts besitzt:

Chinesischer Restsatz

Gegeben seien $a,b\in \mathbb {Z}$ und $p,q\in \mathbb {P}$ verschieden. Sei $n=pq$ und $y,z\in \mathbb {Z}$ so, dass $yp+zq=1$.
Zu den simultanen Kongruenzen $x\equiv a\mod p$ und $x\equiv b\mod q$ gibt es genau eine Lösung. Diese ist äquivalent zu der einfachen Kongruenz

$x\equiv a-yp(a-b)\mod p$.

Beweis

Die Existenz und Eindeutigkeit der Lösung wurde bereits an früherer Stelle durch den induzierten Isomorphismus ${\mathbb {Z} }/(n)\cong {\mathbb {Z} }/({p})\times {\mathbb {Z} }/({q})$ nachgewiesen. Auch die sich ergebende Formel sei noch schnell motiviert:
Es gilt $yp+zq=1$, Multiplikation mit $(a-b)$ ergibt $yp(a-b)+zq(a-b)=(a-b)$. Umstellen liefert $x:=b+zq(a-b)=a-yp(a-b)$, wobei $x\mod p$ äquivalent zu $a$ ist und $x\mod q$ äquivalent zu $b$ ist. $\square$

Beispiel

Angie hat Baracks Geheimtext $C$ erhalten. Nun muss sie nur noch jedes Folgenglied mit ihrem Entschlüsselungsexponenten potenzieren und weiß, was ihr neuer Bekannter geschrieben hat. Zuerst bestimmt sie mit dem erweiterten euklidischen Algorithmus $y,z\in \mathbb {Z}$, so dass $yp+zq=1$. Sie erhält $y=-123$ und $z=74$.

${\begin{array}{c|c|c|c|c|c|c}i&1&2&3&4&5&6\\\hline c_{i}&1578&36622&13694&35126&26869&37497\\p_{i,p}&86&137&77&148&28&25\\p_{i,q}&165&207&195&112&227&163\\p_{i}&10958&26562&6721&24459&18299&14219\\i&7&8&9&10&11&12\\\hline c_{i}&329&7209&17540&12095&26624&26899\\p_{i,p}&83&71&41&130&82&31\\p_{i,q}&129&152&155&187&186&82\\p_{i}&17448&11698&5175&2697&1441&333\\\end{array}}$

Aus Freude über die netten Worte beschließt sie, von nun an in engem Kontakt zu Barack zu bleiben und wartet darauf, dass auch er einen RSA-Schlüssel veröffentlicht.

Sicherheit

Faktorisierungsalgorithmen

Wie man bei der Konstruktion der RSA-Schlüssel gesehen hat, ist das Wissen über die Primzahlen $p$ und $q$ eine wesentliche Voraussetzung, um den Entschlüsselungsexponenten $d$ zu ermitteln. Die Sicherheit von RSA beruht darauf, dass derzeit kein Algorithmus bekannt ist, mit dem man in akzeptabler (das heißt polynomieller) Laufzeit die Primfaktorzerlegung einer gegebenen Zahl $n$ finden kann. Ob ein solcher Algorithmus allerdings wirklich nicht existieren kann, ist eine unbewiesene Annahme.
Auch wenn derzeit kein Algorithmus bekannt ist, der eine natürliche Zahl effizient faktorisieren kann, wurden in den letzten Jahrzehnten große Fortschritte auf dem Gebiet der Faktorisierungsalgorithmen erzielt. Viele dieser Erfolge sind auf John M. Pollard zurückzuführen, von dem unter anderem der Pollard-p-1-Algorithmus auf Grundlage des kleinen Satzes von Fermat stammt. Auch das so genannte Zahlkörpersieb stammt von Pollard. Mit dieser Methode wurde unter anderem 1992 die Fermat-Zahl $F_{9}$ komplett faktorisiert, die einen 49- und einen 99-stelligen Primfaktor besitzt. Ebenfalls wurde mit einer Version des Zahlkörpersiebs im Jahre 2005 ein 200-stelliger RSA-Modul faktorisiert. Aus diesem Grund gelten heute nur noch RSA-Schlüssel als sicher, deren zu Grunde liegenden Primzahlen eine Länge von mindestens 512 Bit besitzen.

Angriffe auf $\varphi (n)$ und $d$

Es liegt auf der Hand anzunehmen, dass man statt der Faktorisierung von $n$ einen direkten Angriff auf $\varphi (n)$ oder $d$ starten könnte. Es lässt sich allerdings recht einfach zeigen, dass aus der Kenntnis von $\varphi (n)$ oder $d$ mit wenig Aufwand auch die Primfaktorzerlegung von $n$ folgt, die Bestimmung von $\varphi (n)$ oder $d$ also nicht leichter sein kann als die Faktorisierung.
Der einfache Fall ist die Kenntnis von $\varphi (n)$. Es ergeben sich die beiden Gleichungen

$n=pq$ und $\varphi (n)=(p-1)(q-1)$,

wobei sowohl $n$ als auch $\varphi (n)$ bekannt sind. Es ergibt sich nach der Substitution $q={\frac {n}{p}}$ die quadratische Gleichung

$p^{2}-(n-\varphi (n)+1)p+n=0$,

deren Lösung schnell bestimmt werden kann. Die Bestimmung von $\varphi (n)$ ist also nicht leichter als die Zerlegung von $n$ in Primfaktoren.
Ebenfalls leicht einzusehen ist der Fall von bekanntem $d$. Der Beweis ist allerdings um einiges komplizierter, daher soll hier nur eine kurze Idee angeführt werden. Grundlage ist ein probalistischer Algorithmus, der eine Menge von Zahlen aus $\mathbb {Z} /(n)$ testet, ob für sie oder eine ihrer Potenzen die Kongruenz $x^{2}\equiv 1\mod n,x\neq -1$ erfüllt ist.

Lemma

Sei $n=pq$ eine natürliche Zahl mit den ungeraden Primfaktoren $p,q\in \mathbb {P}$ und $1<x<n-1$ eine nicht triviale Lösung von $x^{2}\equiv 1\mod n$. Dann sind

$\mathrm {ggT} (x-1,n)$ und $\mathrm {ggT} (x+1,n)$

die beiden Primfaktoren von n.

Beweis

Es gilt $x^{2}\equiv 1^{2}\mod {n}$ sowie $x\neq \pm 1\mod n$. Es folgt direkt $x^{2}-1^{2}\equiv (x+1)(x-1)\equiv 0\mod n$, oder anders ausgedrückt $kn=(x+1)(x-1)$ für ein $k\in \mathbb {Z}$. Da $x-1<x+1<n$, müssen echte Teiler von $n$ existieren, so dass $1<\mathrm {ggT} (x-1),n)<n$ und $1<\mathrm {ggT} <n$. Der größte gemeinsame Teiler von $x-1$ und $x+1$ kann maximal 2 sein, also teilt jeder der Faktoren $p,q$ genau einen der Faktoren $(x-1),(x+1)$. $\square$

Für den Faktorisierungsalgorithmus muss nun noch eine Faktorzerlegung von $de-1$ der Form $2^{s}t$ erzeugt werden, so dass $t$ eine ungerade Zahl ist. Der Algorithmus wählt nun zufällig eine Zahl $1<w<n$ aus und bestimmt den größten gemeinsamen Teiler von $w$ und $n$. Ist dieser ungleich 1, wurde bereits ein Primfaktor gefunden und der Algorithmus war erfolgreich. Ansonsten wird $w^{t}\mod n$ berechnet. Solange das folgende Zahl Ergebnis ungleich 1 ist, wird es quadriert. Gilt $(w^{t})^{2^{k}}\equiv 1\mod n$ und $(w^{t})^{2^{(k-1)}}\neq -1\mod n$, so war der Algorithmus ebenfalls erfolgreich, da nun das vorangegangene Lemma angewendet werden kann. Ansonsten bestimmt er ein neues $w$ und beginnt erneut.Die Erfolgswahrscheinlichkeit des Algorithmus liegt bei 50%.

Ein weiteres Risiko ist die Festlegung eines zu kleinen $d$, speziell $3d<{\sqrt[{4}]{n}}$. In diesem Fall existiert ein auf Kettenbrüchen basierender Angriffsalgorithmus, den Michael J. Wiener beschrieben hat. Es wird hier noch einmal deutlich, dass die Wahl von $e$ (und damit auch von $d$) nicht völlig willkürlich erfolgen sollte.

Andere Angriffe auf RSA

Die Public-Key-Kryptosysteme haben auch vollkommen neue Arten von Angriffen auf die Algorithmen hervorgebracht. So ist es möglich, eine grobe Abschätzung der Größe von $d$ vorzunehmen, wenn ein Angreifer in der Lage ist, die aufgewendete Zeit für eine Entschlüsselung zu bestimmen.
Da die Geschwindigkeit des Square-and-Multiply-Verfahrens von der Länge des Exponenten abhängig ist, lässt sich leicht erkennen, dass die Dechiffrierung bei kleinem $d$ weniger Zeit in Anspruch nimmt als bei einem $d$, dessen Länge in der Nähe des RSA-Moduls liegt. Solche Timing attacks , die zuerst von Paul C. Kocher beschrieben wurden, sind im Allgemeinen allerdings schwer zu kontrollieren, da sie nicht ausschließlich von $d$ abhängen, sondern auch von der eigentlichen Implementation der Algorithmen und der genutzten Hardware.

Andere Angriffe entfernen sich von der Idee, RSA an sich zu brechen, und wenden sich der umgebenden Architektur zu. Der bekannteste unter ihnen ist der Man-in-the-middle-Angriff, der sich die Problematik zunutze macht, zum Beispiel im Internet eine eindeutige Identifizierung des Gegenübers vorzunehmen.
So ist es zum Beispiel denkbar, dass Barack, der mit Angie kommunizieren möchte, in Wirklichkeit Hugos öffentlichen Schlüssel untergeschoben bekommt, da sich Hugo Barack gegenüber als Angie ausgibt und umgekehrt. So kann Hugo die eigentlich für Angie bestimmten Nachrichten mit seinem eigenen Schlüssel dechiffrieren, nach Belieben verändern und dann erst an Angie weiterleiten.

Nachteile und Grenzen von Public-Key-Systemen

Public-Key-Kryptosysteme wie RSA haben in der Praxis zwei entscheidende Nachteile:

• Die Berechnung der Geheim- und Klartexte ist extrem langsam
• Es muss zweifelsfrei sichergestellt werden, dass der Besitzer eines Schlüssels die Person ist, die er vorgibt zu sein

Aktuelle, in der Praxis eingesetzte Verfahren, die symmetrisch arbeiten, sind etwa um den Faktor 1000 schneller als RSA, weil die dort meistens eingesetzten nichtlinearen Substitutionen und Permutationen effizienter umzusetzen sind als Potenz- und Modulo-Operationen. Entsprechend ist es praktisch unmöglich, RSA in zeitkritischen Anwendungen einzusetzen, zum Beispiel bei der Telekommunikation. Abhörsichere Telefonleitungen sind in der Regel also nicht durch asymmetrische Verschlüsselung zu schützen.

Es ist häufig so, dass die Kommunikation über einen asymmetrisch gesicherten Kanal so kurz wie möglich ausfallen soll. In der Praxis ist es üblich, für den eigentlichen Datenaustausch ein symmetrisches Verfahren wie AES oder RC4 zu verwenden und Public-Key-Verfahren wie RSA lediglich zum Austausch der genutzten Schlüssel einzusetzen.
Es wird also eine sichere Verbindung mit RSA aufgebaut, der geheime Schlüssel für das symmetrische Verfahren übertragen und die weitere Kommunikation dann darüber abgewickelt.

Noch schwieriger ist das Problem der Authentifizierung des Schlüsselinhabers. Im Internet kann man nur selten davon ausgehen, dass es sich beim Gegenüber wirklich um die Person handelt, die sie zu sein vorgibt.
Entsprechend reicht es nicht aus, mit ihr sicher zu kommunizieren, man muss zuallererst klären, mit wem man es eigentlich zu tun hat. Dafür gibt es so genannte Trust Center, die mit der Verwaltung der öffentlichen Schlüssel betraut sind. Ein vertrauenswürdiger Kommunikationspartner authentifiziert sich dort und hinterlegt dann seinen persönlichen Schlüssel, womit sichergestellt ist, dass seine Identität geklärt ist.