RSA-Kryptosystem

aus Wikipedia, der freien Enzyklopädie

RSA ist ein asymmetrisches Kryptosystem, das sowohl zur Verschlüsselung als auch zur digitalen Signatur verwendet werden kann. Es verwendet ein Schlüsselpaar bestehend aus einem privaten Schlüssel, der zum Entschlüsseln oder Signieren von Daten verwendet wird, und einem öffentlichen Schlüssel, mit dem man verschlüsselt oder Signaturen prüft. Der private Schlüssel wird geheim gehalten und kann nicht oder nur mit extrem hohen Aufwand aus dem öffentlichen Schlüssel berechnet werden. RSA ist nach seinen Erfindern Ronald L. Rivest, Adi Shamir und Leonard Adleman benannt.

[Bearbeiten] Schlüsselverteilung

Der Vorteil asymmetrischer Verfahren besteht in der Vereinfachung der Schlüsselverteilung. Bei symmetrischen Verfahren ist der Austausch eines geheimen Schlüssels nötig, den Sender und Empfänger gemeinsam benutzen. Der Austausch muss dabei sicher erfolgen. Dies bedeutet, der Austausch muss abhörsicher sein. Es ist jedoch auch sicherzustellen, dass der Schlüssel tatsächlich von der Person stammt, mit der geheime Nachrichten ausgetauscht werden sollen.

Durch Public-Key-Systeme entfällt die Notwendigkeit, den Schlüsselaustausch gegen Abhören zu härten, da nur der öffentliche Schlüssel ausgetauscht werden muss. Es bleibt aber ein wesentliches Problem, da weiterhin sicherzustellen ist, dass der öffentliche Schlüssel tatsächlich von der Person stammt, mit der geheime Botschaften ausgetauscht werden sollen. In der Praxis ist dies oft nur dann möglich, wenn zugleich auch die Geheimhaltung gewährleistet werden kann.

Falls die Kommunikation zwar nicht abhörsicher ist, aber kein Zweifel über die Identität des Partners besteht und die Nachricht nicht von einem Dritten verändert werden kann, ist der Schlüsselaustausch beim Public-Key-Verfahren problemlos. Allerdings ist dies auch mit anderen Verfahren möglich.

Dazu kann der Schlüssel aus vielen Teilschlüsseln zusammengesetzt werden. Eine Hash-Funktion wie SHA erlaubt es, aus vielen längeren Teilschlüsseln ein Komprimat zu errechnen, welches als Schlüssel für die symmetrische Verschlüsselung benutzt werden kann. Die Teilschlüssel können zu unterschiedlichen Zeiten und mit höchst unterschiedlichen Methoden ausgetauscht werden.

[Bearbeiten] Geschichte

Wie oben angedeutet ist der Schlüsselaustausch eine logistische Schwachstelle bei symmetrischen Verschlüsselungsverfahren. Durch den Angriff auf diese Schwachstelle (z.B. durch in-Erfahrung-bringen des Schlüssels) wurde bei mehreren zwischenstaatlichen Auseinandersetzungen und Kriegen der Ausgang (mit-)entschieden, so zum Beispiel durch Aktivitäten von Alan Turing und anderen in Bletchley Park im Zweiten Weltkrieg. Daher wurde Anfang der 1970er Jahre im Government Communications Headquarters von Ellis, Cocks und Williamson ein dem späteren Verfahren von Diffie-Hellman ähnliches asymmetrisches Verfahren entwickelt, welches aber keine große praktische Bedeutung hatte und aus Geheimhaltungsgründen nicht (wissenschaftlich) publiziert wurde. RSA konnte daher zum Patent angemeldet werden, obgleich es nicht das erste Verfahren dieser Art war. Das Patent ist am 21. September 2000 ausgelaufen.

[Bearbeiten] Hybride Verfahren

RSA ist im Vergleich zu 3DES und AES um mindestens einen Faktor 1.000 langsamer. Für die Verschlüsselung größerer Datenmengen werden daher symmetrische Verfahren eingesetzt. Es genügt jedoch, RSA zum Austausch eines Schlüssels für die symmetrische Verschlüsselung zu benutzen.

[Bearbeiten] Verfahren

Nachdem Whitfield Diffie und Martin Hellman eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman, die Annahmen von Diffie und Hellman zu widerlegen. Nachdem sie den Beweis bei verschiedenen Verfahren durchführen konnten, stießen sie schließlich auf eines, bei dem sie keinerlei Angriffspunkte fanden. Hieraus entstand dann RSA.

Das Verfahren wurde 1977 entwickelt und basiert auf dem aktuellen Wissensstand, dass die Faktorisierung einer großen Zahl, also ihre Zerlegung in ihre Primfaktoren, eine sehr aufwändige Angelegenheit ist, während das Erzeugen einer Zahl durch Multiplikation zweier Primzahlen recht einfach ist. Wenn nun eine Nachricht einem Empfänger verschlüsselt zugeleitet werden soll, generiert dieser einen öffentlichen Schlüssel. Der Nachrichtenabsender verwendet diesen öffentlich bekanntgemachten Schlüssel, indem er damit seine Botschaft verschlüsselt. Nur der Empfänger kann diese „dekodieren“, da nur er die „Zusammensetzung“ des von ihm erzeugten (öffentlichen) Schlüssels kennt.

[Bearbeiten] Einwegfunktionen

Funktionen wie die Multiplikation/Faktorisierung, bei denen eine Richtung leicht, die andere schwierig zu berechnen ist, bezeichnet man als Einwegfunktionen (engl. one-way function). Um allerdings die Entschlüsselung tatsächlich möglich zu machen, muss es sich um Falltürfunktionen (engl. trap door one-way function) handeln, die mit Hilfe einer Zusatzinformation auch rückwärts leicht zu berechnen sind.

Das Verfahren ist mit dem Rabin-Verschlüsselungsverfahren verwandt.

[Bearbeiten] Erzeugung des öffentlichen und privaten Schlüssels

Der öffentliche Schlüssel (public key) ist ein Zahlenpaar $(e, N)$ und der private Schlüssel (private key) ein Zahlenpaar $(d, N)$ , wobei $N$ bei beiden Schlüsseln gleich ist. Man nennt $N$ den RSA-Modul, $e$ den Verschlüsselungsexponenten und $d$ den Entschlüsselungsexponenten. Diese Zahlen werden durch das folgende Verfahren erzeugt:

Wähle zufällig und stochastisch unabhängig zwei Primzahlen $p \neq q$ . In der Praxis rät man dazu jeweils eine Zahl und führt mit dieser anschließend einen Primzahltest durch.
Berechne den RSA-Modul

$N = p \cdot q$ .
Berechne die Eulersche φ-Funktion von $N$

$\varphi(N) = (p-1) \cdot (q-1)$
Wähle eine zu $\varphi(N)$ teilerfremde Zahl $e$ , für die gilt $1 < e < \varphi(N)$ .
Berechne den Entschlüsselungsexponent $d$ als Multiplikativ Inverses von $e$ bezüglich des Modulus $\varphi(N)$ . Es soll also die folgende Kongruenz gelten

$e \cdot d \equiv 1 \pmod{\varphi(N)}$

Die Zahlen $p$ , $q$ und $\varphi(N)$ werden nicht mehr benötigt und sollten nach der Schlüsselerstellung auf sichere Weise gelöscht werden. Aus Effizienzgründen wird $e$ klein gewählt, üblich ist $216 + 1 = 65537$ . Kleinere Werte von $e$ können zu Angriffsmöglichkeiten führen, etwa in Form des von Johan Hastad publizierten „Broadcast“-Angriffs, bei dem der Versand einer Nachricht an mehrere Empfänger zu einer Dechiffrierung über den chinesischen Restsatz führen kann.^[1] Bei Wahl eines $d$ mit weniger als einem Viertel der Bits des RSA-Moduls kann $d$ – sofern nicht bestimmte Zusatzbedingungen erfüllt sind – mit einem auf Kettenbrüchen aufbauenden Verfahren effizient ermittelt werden.^[2]

[Bearbeiten] Beispiel

Wir wählen $p = 11$ und $q = 13$ für die beiden Primzahlen.
Der RSA-Modul ist $N = p \cdot q = 143$ .
Die eulersche φ-Funktion nimmt damit den Wert $\varphi(N) = \varphi(143) = (p-1)(q-1) = 120$ an.
Die Zahl $e$ muss zu 120 teilerfremd sein. Wir wählen $e = 23$ . Damit bilden $e = 23$ und $N = 143$ den öffentlichen Schlüssel.
Berechnung der Inversen zu $e$ :
Es gilt: $e \cdot d + k \cdot \varphi(N) = 1 = ggT(e,\varphi(N))$
bzw. im konkreten Beispiel: $23 \cdot d + k \cdot 120 = 1 = ggT(23,120)$
Mit dem erweiterten euklidischen Algorithmus berechnet man nun die Faktoren $d = 47$ und $k = - 9$ , so dass die Gleichung aus dem Beispiel wie folgt aussieht: $23 \cdot 47 + (-9 )\cdot 120 = 1$
d ist der private Schlüssel, während k nicht weiter benötigt wird.

[Bearbeiten] Alternativer privater Schlüssel

Gewöhnlich wird in der Praxis der private Schlüssel etwas ausführlicher gespeichert, da diese Form der Speicherung das Entschlüsseln von Krypttexten effizienter macht (mit Hilfe des Chinesischen Restsatzes). Der private Schlüssel besteht daher dann, im Gegensatz zu dem, was im Rest dieses Artikels angenommen wird, aus folgenden Komponenten:

$N$ , der RSA-Modul,
$e$ , der Verschlüsselungsexponent,
$p$ , die erste Primzahl,
$q$ , die zweite Primzahl,
$d mod (p - 1)$ , häufig dmp1 genannt,
$d mod (q - 1)$ , häufig dmq1 genannt und
$(1 / q)mod p$ , häufig iqmp genannt.

[Bearbeiten] Verschlüsseln von Nachrichten

Verschlüsselung

Um eine Nachricht $K$ zu verschlüsseln, verwendet der Absender die Formel

$C \equiv K^e \mod N$

und erhält so aus dem Klartext $K$ den Geheimtext $C$ .

[Bearbeiten] Beispiel

Es soll die Zahl 7 verschlüsselt werden.
Der Nachrichtenabsender benutzt den veröffentlichten Schlüssel $N = 143$ , $e = 23$ und rechnet

$C \equiv 7^{23} \mod 143$

Zur Berechnung von $723 mod 143$ kann die Kongruenzarithmetik verwendet werden. Mit Hilfe der modularen Exponentiation berechnet man schnell:

$7^{23} \ \bmod \ 143 \ = \ ((( 7^2 )^2\cdot 7)^2\cdot 7)^2\cdot 7 \ \bmod \ 143 = 2$

Dabei wendet man nach jedem Rechenschritt auf die zu handhabenden Zahlen die Modulo-Operation (kurz: mod) an, um die Ergebnisse möglichst „klein“ zu halten.

Aus dem Klartext 7 haben wir somit den Geheimtext 2 erhalten.

[Bearbeiten] Entschlüsseln von Nachrichten (Decodierung)

Entschlüsselung

Der Geheimtext $C$ kann durch modulare Exponentiation wieder zum Klartext $K$ entschlüsselt werden. Der Empfänger benutzt die Formel

$K \equiv C^d \mod N$

mit dem nur ihm bekannten Wert $d$ sowie $N$ .

[Bearbeiten] Beispiel

$K \equiv 2^{47} \ \bmod\ 143 = ((((2^2)^2 \cdot 2)^2 \cdot 2)^2 \cdot 2)^2 \cdot 2 \ \bmod\ 143 = 7$

Aus $C = 2$ wird also wieder $K = 7$ .

Siehe auch Schnelles Potenzieren

[Bearbeiten] Signieren von Nachrichten

Um eine Nachricht $K$ zu signieren, wird diese vom Sender mit dem eigenen privaten Schlüssel verschlüsselt. Zum Prüfen entschlüsselt der Empfänger die Nachricht mit dem öffentlichen Schlüssel des Senders und vergleicht diese mit der zusätzlich übermittelten unverschlüsselten Nachricht $K$ . Wenn sie übereinstimmen, ist die Signatur gültig und der Empfänger kann sicher sein, dass derjenige, der das Dokument signiert hat, auch den privaten Schlüssel besitzt und dass niemand seit der Signierung das Dokument geändert hat. Es wird also die Integrität und Authentizität garantiert, vorausgesetzt der private Schlüssel ist wirklich geheim geblieben.

Da asymmetrische Verfahren nicht geeignet sind, um größere Datenmengen zu verarbeiten, wird in der Praxis nicht die Nachricht selbst mit dem privaten Schlüssel verschlüsselt. Stattdessen wird der Hash-Wert $H$ der Nachricht berechnet. Dieser bildet dann (meist zusammen mit einigen technisch notwendigen Informationen, wie zum Beispiel der Spezifizierung des verwendeten Hashverfahrens) die Eingabe $K *$ für eine Verschlüsselung mit dem privaten Schlüssel, deren Resultat dann die eigentliche Signatur ist. Der Empfänger kann die so erhaltene Signatur mit dem öffentlichen Schlüssel entschlüsseln und erhält so $K *$ und somit den Hash-Wert $H$ der ursprünglichen Nachricht. Anschließend kann er selber den Hash-Wert $H 1$ der ihm vorgelegten Nachricht bestimmen und mit dem in $K *$ gespeicherten Hash-Wert $H$ vergleichen. Wenn die beiden Hash-Werte übereinstimmen, kann mit hoher Wahrscheinlichkeit davon ausgegangen werden, dass die Nachricht fehlerfrei übertragen wurde und nicht gefälscht ist.

Siehe auch Elektronische Unterschrift

[Bearbeiten] Sicherheit

Public-Key Verschlüsselungs-Verfahren wie RSA werden in der Praxis immer als hybride Verfahren in Verbindung mit symmetrischen Verfahren verwendet. Bei der Analyse der Sicherheit müssen die Sicherheit des Public-Key-Verfahrens und die praktische Sicherheit des Gesamtsystems betrachtet werden.

[Bearbeiten] Sicherheit von RSA

Bei der Kryptanalyse des RSA-Verfahrens unterscheidet man zwischen zwei Problemen:

RSA-Problem ( $RSAP$ ): Gegeben sind der öffentliche Schlüssel $(N, e)$ sowie der Geheimtext $C$ . Gesucht wird der Klartext $K$ wobei gilt: $K^e\equiv C\pmod{N}$

Das Problem liegt hier in der Schwierigkeit Wurzeln modulo

N

zu ziehen, was zur Bestimmung des Klartexts

K

notwendig ist.

RSA-Schlüsselproblem ( $RSAP *$ ): Gegeben ist der öffentliche Schlüssel $(N, e)$ . Gesucht wird der geheime Schlüssel $d$ wobei gilt: $ed\equiv 1\pmod{\varphi(N)}$

Das Problem liegt hier in der Schwierigkeit die Eulersche φ-Funktion von

N

ohne Kenntnis der Faktoren p und q zu berechnen.

Folgende Beziehungen zwischen den RSA-Problemen und $FACTORING$ , dem Faktorisierungsproblem, sind bekannt:

$\mathrm{RSAP} \leq_p \mathrm{RSAP^*} =_p \mathrm{FACTORING}$

Die Beziehung $\mathrm{RSAP} \leq_p \mathrm{RSAP^*}$ ist trivial, denn wenn man den privaten Schlüssel hat, kann man damit wie oben jeden beliebigen Geheimtext entschlüsseln. Ob die Umkehrung gilt, ist zur Zeit unbekannt.

Auch die Beziehung $\mathrm{RSAP^*} \leq_p \mathrm{FACTORING}$ ist trivial, denn wenn man $N = p q$ faktorisiert hat, kann man damit leicht $\varphi(N)=(p-1)(q-1)$ berechnen, und dann mit dem euklidischen Algorithmus zu gegebenem öffentlichen Schlüssel den zugehörigen privaten Schlüssel effizient berechnen, wie in der Schlüsselerzeugung.

Für die Beziehung $\mathrm{FACTORING} \leq_p \mathrm{RSAP^*}$ ist schon lange ein probabilistischer Polynomialzeitalgorithmus bekannt. Vor kurzem wurde gezeigt, dass sich diese Reduktion im balancierten RSA (d.h. $p$ und $q$ haben gleiche Bitlänge) auch deterministisch durchführen lässt. Der Beweis verwendet das Coppersmith-Verfahren zur Bestimmung von Nullstellen eines irreduziblen bivariaten Polynoms mit ganzzahligen Koeffizienten, welches sich auf eine Gitterreduktion zurückführen lässt.

Da alle gängigen Implementierungen balanciertes RSA verwenden, ist in der Praxis das Brechen des geheimen Schlüssels nur mit der Kenntnis des öffentlichen Schlüssels genau so schwer wie das Faktorisieren von $N$ . Wegen $\mathrm{RSAP} \leq_p \mathrm{FACTORING}$ ist im Fall der zusätzlichen Kenntnis eines Geheimtexts die Schwierigkeit des Faktorisierungsproblems von zentralem Interesse.

Man möchte $N = p q$ für sehr große Primzahlen $p$ und $q$ faktorisieren. Diese Primfaktorzerlegung ist für große Zahlen mit den heute bekannten Verfahren praktisch nicht durchführbar. Es ist aber nicht bewiesen, dass es sich bei der Primfaktorzerlegung um ein prinzipiell schwieriges Problem handelt. Es sind aber nur Algorithmen, welche in NP und außerhalb von P liegen, bekannt.

Mit dem Quadratischen Sieb wurde 1994 die Zahl RSA-129 mit 129 Dezimal-Stellen in 8 Monaten von ca. 600 Freiwilligen faktorisiert. Mit der Methode des Zahlkörpersiebs wurde im Jahr 2005 von Wissenschaftlern der Universität Bonn die im Rahmen der RSA Factoring Challenge von RSA Laboratories vorgegebene 200-stellige Dezimalzahl RSA-200 in ihre zwei großen Primfaktoren zerlegt. Die Faktorisierung begann Ende 2003 und dauerte bis Mai 2005. Unter anderem kam ein Rechnerverbund von 80 handelsüblichen Rechnern an der Universität Bonn zum Einsatz. Im November 2005 zahlten RSA Laboratories für die Faktorisierung von RSA-640, einer Zahl mit 640 Bits bzw. 193 Dezimalstellen, eine Prämie von 20.000 US-Dollar. Mittlerweile wurde das RSA Factoring Challenge beendet.

Für die Faktorisierung von RSA-1024 (309 Dezimalstellen) oder gar RSA-2048 (617 Dezimalstellen) waren 100.000 $ bzw. 200.000 $ ausgelobt; die RSA Laboratories haben im Mai 2007 das RSA Factoring Challenge beendet, nachdem die o.g. Wissenschaftler der Universität Bonn im selben Monat eine 1039-Bit Zahl (312 Dezimalstellen) faktorisiert haben ^[3]. Die wachsende Rechenleistung moderner Computer stellt für die kurzfristige Sicherheit von RSA im Wesentlichen kein Problem dar, zumal diese Entwicklung vorhersehbar ist: Der Nutzer kann bei der Erzeugung seines Schlüssels darauf achten, dass er während der Dauer der beabsichtigten Verwendung nicht faktorisiert werden kann. Nicht vorhersehbare Entwicklungen, wie die Entwicklung deutlich schnellerer Algorithmen oder gar eines leistungsfähigen Quantencomputers bergen zumindest für die mittel- und langfristige Sicherheit der verschlüsselten Daten gewisse Risiken.

In einigen Spezialfällen kann man das RSA-Verfahren brechen, ohne das Faktorisierungsproblem gelöst zu haben. Der Angriff von Wiener bei balanciertem RSA löst das RSA-Schlüsselproblem effizient unter der Annahme, dass der private Schlüssel nur eine geringe Bitlänge aufweist, genauer $d<\frac{\sqrt[4]{N}}{3}$ . Wiener verwendete dabei die Tatsache, dass unter der Abschätzung für $d$ der Bruch $\frac{k}{d}$ (für eine ganze Zahl $k$ ) in der Kettenbruchentwicklung von $\frac{e}{N}$ auftaucht. Die Schranke wurde mit Mitteln der Gitterreduktion auf $d < N 0.292$ verbessert.

Auch das RSA-Problem kann unter einigen Annahmen effizient ohne Faktorisieren gelöst werden. Der Angriff von Håstad ermittelt einen Klartext, der mit kleinem Verschlüsselungsexponent (etwa $e = 3$ ) für mehrere Empfänger vor dem Verschlüsseln speziell aufbereitet wurde, etwa wenn die Nummer des Empfängers in den Klartext codiert wurde. Dieser Angriff verwendet die Coppersmith-Methode, um kleine Nullstellen eines Polynoms in einer Unbestimmten zu berechnen, welche wiederum auf Gitterreduktion basiert.

[Bearbeiten] Praktische Sicherheit

Da die RSA-Funktion $x$ → $x d mod n$ multiplikativ ist (d. h. $(x y) d = x d y d mod n$ gilt), lassen sich aus bekannten Klartexten $M_1, \ldots,M_k$ von Chiffretexten $C_1, \ldots, C_k$ zu einem Chiffretext $C$ , der sich als Produkt

$C=\prod C(M_i)^{e_i}\bmod n$

mit ganzzahligen $e i$ darstellen lässt, der Klartext M als

$M=\prod M_i^{e_i}\bmod n$

berechnen. Analog dazu lässt sich aus bekannten (echten) Signaturen $S_1,\ldots,S_k)$ zu Nachrichten $M_1, \ldots,M_k$ weitere (gefälschte) Signaturen

$S(M)=\prod S_i^{e_i}\bmod n$

berechnen. Da bei digitalen Signaturen in der Regel nur Hashwerte signiert werden, ist der Angriff dann erfolgreich, wenn diese multiplikative Relation auch für die Hash-Werte der Nachrichten $M$ und $M_1, \ldots,M_k$ gilt.

Um solche Angriffe zu verhindern, werden bei RSA-Verschlüsselung und RSA-Signatur so genannte Padding-Verfahren eingesetzt. Diese nutzen aus, dass die Länge des Klartextes bzw. Hash-Wertes deutlich kleiner als die Länge von $n$ ist, und fügen dem Klartext bzw. dem Hash-Wert vor der Verschlüsselung oder Signatur einen String R mit vorgegebener Struktur (d. h. mit Redundanz) an. Es wird also die RSA-Funktion nicht auf die Nachricht $M$ oder auf den Hash-Wert $h (M)$ angewendet, sondern auf $M$ | $R$ bzw. $h (M)$ | $R$ , wobei "|" eine Konkatenation bezeichnet. In der Regel enthält $R$ eine Angabe über die Länge der Nachricht oder des Hash-Wertes oder eine eindeutige Zeichenfolge, die den Beginn von $R$ kennzeichnet. Dies erleichtert nicht nur die Dekodierung, sondern erschwert auch Angriffe. Padding-Verfahren können für die Berechnung von $R$ auch Zufallszahlen und Hashfunktionen verwenden. Standards für Padding-Verfahren für RSA werden z. B. in PKCS#1 oder ISO 9796 definiert. Einige moderne Paddingverfahren – beispielsweise das Optimal Asymmetric Encryption Padding (OAEP) oder das Probabilistic Signature Scheme (PSS) – verwenden kryptographische Hashfunktionen und sind (unter idealisierten Annahmen) beweisbar ebenso schwierig zu brechen, wie RSA selbst.^[4] ^[5]

RSA wird in der Regel in Hybridverfahren mit symmetrischen Verschlüsselungsverfahren kombiniert. Dabei wird zufällig ein Sitzungsschlüssel für eine symmetrische Verschlüsselung generiert, der dann per RSA verschlüsselt und zusammen mit der Nachricht übertragen wird.

Bei der Signatur wird nicht die gesamte Nachricht sondern nur ein Hash-Wert signiert. Der symmetrische Schlüssel bzw. der Hash-Wert sind dabei relativ kurz. Für den symmetrischen Schlüssel gilt also

$K_{sym} < N = p\cdot q$ .

Daher kann der symmetrische Schlüssel mit einer einzigen RSA-Verschlüsselung verschlüsselt werden. Für die Sicherheit von RSA sind Primzahlen mit über 100 Stellen erforderlich. Daher könnte ein symmetrischer Schlüssel mit über 200 Stellen verschlüsselt werden.

Als sehr sicher eingestufte Algorithmen zur symmetrischen Verschlüsselung gelten 3DES und AES. Diese verwenden 112, 128, 168 oder maximal 256 Bit. Dies entspricht bei 256 Bit etwa 77 Dezimalstellen. Damit ist ein Brute-Force-Angriff faktisch auszuschließen. Eine sichere Hashfunktion wie SHA-256 erzeugt Funktionswerte mit einer Länge von ebenfalls 256 Bit. Damit lassen sich Signaturverfahren mittels RSA realisieren, die nur einen Verschlüsselungsschritt benötigen.

Die Sicherheit und die Performance des Gesamtsystems werden durch die Sicherheit des Public-Key-Verfahrens limitiert, sofern nur als sicher eingestufte Algorithmen verwendet werden und die Wahl des Schlüssel als hinreichend zufällig betrachtet werden kann.

[Bearbeiten] Beweis

Das RSA-Verfahren arbeitet korrekt, wenn für alle Klartexte $a$ die folgende Kongruenz erfüllt ist.

$(a^e)^d \equiv (a^d)^e \equiv a \mod N$

Die in der Kongruenz auftretenden Variablen genügen den folgenden Bedingungen:

Der RSA-Modul ist das Produkt zweier verschiedener Primzahlen.

$N=p \cdot q$
Der Verschlüsselungsexponent ist teilerfremd zu $\varphi (N)$ .

$\operatorname{ggT}(e,\varphi(N))=1$ .
Für das Produkt aus Verschlüsselungs- und Entschlüsselungsexponent gilt

$ed \equiv 1 \mod \varphi(N)$

Direkt aus den Potenzgesetzen folgt, dass die beiden Kongruenzen

$(a^e)^d \equiv a^{ed} \mod N$

$(a^d)^e \equiv a^{ed} \mod N$

gelten. Es muss deshalb nur noch die Kongruenz

$a^{ed} \equiv a \mod N$

bewiesen werden. Ausgangspunkt zu deren Beweis bildet die Funktionalität zur Berechnung des Entschlüsselungsexponenten d.

ed ≡ 1 mod φ(N)

Die multiplikative Eigenschaft der Eulerschen φ-Funktion führt dann zu

ed ≡ 1 mod p-1

Der modulo-Operator kann umgeschrieben werden. So existiert eine ganze Zahl u mit ed = u(p-1)+1. Dies wird in den zu beweisenden Ansatz eingefügt.

a^ed ≡ a^u(p-1)+1 ≡ a $\cdot$ (a ^p-1)^u mod p

Nach dem kleinen Satz von Fermat gilt für alle zu p teilerfremden Zahlen a der Zusammenhang a^p-1 ≡ 1 mod p. Mit Einsetzen und Umformen kommt man so zu

a $\cdot$ (a ^p-1)^u ≡ a $\cdot$ 1^u ≡ a mod p

Somit wurde für alle zu p teilerfremden Zahlen a gezeigt, dass a^ed ≡ a mod p gilt. Falls p aber a teilt, gilt die Gleichung trivialerweise, da beide Seiten ≡ 0 sind. Analog gilt auch a^ed ≡ a mod q für alle ganzen Zahlen a. Mithilfe eines Spezialfalles des chinesischen Restsatzes können nun die Kongruenzen modulo p und modulo q unter der Bedingung N=pq zu der gesuchten Kongruenz modulo N kombiniert werden.

a^ed ≡ a mod N

[Bearbeiten] RSA ist kein Primzahltest

Wenn $p$ und $q$ Primzahlen sind, funktioniert das RSA-Verfahren. Umgekehrt kann aber aus dem funktionierenden RSA-Verfahren nicht geschlossen werden, dass $p$ und $q$ Primzahlen sind, denn bei Carmichael-Zahlen funktioniert das Verfahren, obwohl Carmichael-Zahlen keine Primzahlen sind.

Beweis

Gegeben:

$n=p \cdot c$ , wobei $c=\prod q_i$ eine Carmichael-Zahl ist
$q i - 1 | c - 1$ , Eigenschaft von Carmichael-Zahlen
$\varphi(n)=(p-1)(c-1)$ , fälschliche Annahme, da angenommen wird, dass $c$ eine Primzahl sei
$(p-1)(c-1)=(q_i-1)\cdot b_i$ , weil $c - 1$ von $q i - 1$ geteilt wird
$\operatorname{ggT}(e,(p-1)(c-1))=1$
$d\cdot e \equiv 1 \mod{(p-1)(c-1)}$

Zu zeigen:

$a^{d\cdot e} \equiv a \mod n$

Betrachten wir nun den Primteiler $p$

Fall 1: $p | a$

$a^{d\cdot e} \equiv 0 \equiv a \mod p$

Fall 2: $p \nmid a$

$a^{d\cdot e} \equiv a^{(p-1)(c-1)} \cdot a \equiv a \mod p$

Betrachten wir nun die Primteiler $q i$ von $c i$

Fall 1: $q i | a$

$a^{d\cdot e} \equiv 0 \equiv a \mod{q_i}$

Fall 2: $q_i \nmid a$

$a^{d\cdot e} \equiv a^{(q_i-1)(b_i)} \cdot a \equiv a \mod{q_i}$

Unabhängig von der Zahl $a$ folgt aus dem Chinesischen Restsatz, dass $a^{e \cdot d} \equiv a \mod n$ .

$\Rightarrow q.e.d$

Dieser Beweis hält offensichtlich auch dann stand, wenn $n$ das Produkt von zwei Carmichael-Zahlen ist.

[Bearbeiten] Vollständiges Beispiel

[Bearbeiten] Vorarbeiten

Die oben genannten Schritte sollen nun an einem vollständigen Beispiel erläutert werden. Um einen Text zu verschlüsseln, müssen zunächst Buchstaben in Zahlen umgewandelt werden. Dazu verwendet man in der Praxis zum Beispiel den ASCII-Code. Hier sei willkürlich die folgende Zuordnung gewählt:

A=01 B=02 C=03 usw. (00 = Leerzeichen)

Darüberhinaus sei angenommen, dass jeweils drei Zeichen zu einer Zahl zusammengefasst werden. Die Buchstabenfolge AXT wird also zu 012420. Die kleinste zu verschlüsselnde Zahl ist dann 000000 (drei Leerzeichen), die größte 262626 (ZZZ). Der Modulus $N = p \cdot q$ muss also größer 262626 sein.

Klartext:  W I K  I P E  D I A
Kodierung: 230911 091605 040901

[Bearbeiten] Schlüsselerzeugung

Zunächst werden geheim zwei Primzahlen gewählt, beispielsweise $p = 307$ und $q = 859$ . Damit ergibt sich:

$N = p \cdot q = 263713$

$\varphi(N) = (p-1) \cdot (q-1) = 262548$

$e = 1721$ (zufällig, teilerfremd zu $\varphi(N)$ )

$d = 1373$ (das multiplikative Inverse zu $e \bmod \varphi(N)$ mit Hilfe des Erweiterten euklidischen Algorithmus)

Öffentlicher Schlüssel: $e = 1721$ und $N = 263713$

Geheimer Schlüssel: $d = 1373$ und $N = 263713$

[Bearbeiten] Verschlüsselung

C_n = K_n^e mod N   für n=1,2,3(,...)
C₁ = 230911¹⁷²¹ mod 263713 = 001715
C₂ = 091605¹⁷²¹ mod 263713 = 184304
C₃ = 040901¹⁷²¹ mod 263713 = 219983

[Bearbeiten] Entschlüsselung

K_n = C_n^d mod N   für n=1,2,3(,...)
K₁ = 001715¹³⁷³ mod 263713 = 230911
K₂ = 184304¹³⁷³ mod 263713 = 091605
K₃ = 219983¹³⁷³ mod 263713 = 040901

[Bearbeiten] Signatur (Verschlüsselung mit dem geheimen Schlüssel)

C_n = K_n^d mod N
C₁ = 230911¹³⁷³ mod 263713 = 219611
C₂ = 091605¹³⁷³ mod 263713 = 121243
C₃ = 040901¹³⁷³ mod 263713 = 138570

[Bearbeiten] Verifikation (Entschlüsselung mit dem öffentlichen Schlüssel)

K_n = C_n^e mod N
K₁ = 219611¹⁷²¹ mod 263713 = 230911
K₂ = 121243¹⁷²¹ mod 263713 = 091605
K₃ = 138570¹⁷²¹ mod 263713 = 040901

[Bearbeiten] Anwendungsgebiete

Internet- und Telefonie-Infrastruktur: X.509-Zertifikate
Übertragungs-Protokolle: IPSec, TLS, SSH, WASTE
E-Mail-Verschlüsselung: PGP, S/MIME
Authentifizierung französischer Telefonkarten
Kartenzahlung: EMV

[Bearbeiten] Literatur

c't 25/99, Story „Der Dialog der Schwestern“ Liegt auch dem E-Learning-Programm CrypTool bei.
Alexander May: Computing the RSA Secret Key is Deterministic Polynomial Time Equivalent to Factoring, in Advances in Cryptology (Crypto 2004), Lecture Notes in Computer Science Volume 3152, pages 213-219, Springer Verlag, 2004.
Dan Boneh: Twenty Years of Attacks on the RSA Cryptosystem, in Notices of the American Mathematical Society (AMS), Vol. 46, No. 2, pp. 203--213, 1999.

[Bearbeiten] Quellen

↑ D. Boneh: “Twenty Years of Attacks on the RSA Cryptosystem”. In: Notes of the AMS. 46, Nr. 2, Februar 1999, S. 203–213 (PDF).
↑ MJ Wiener: “Cryptanalysis of short RSA secret exponents”. In: IEEE Transactions on information theory. 36, Nr. 3, May 1990, S. 553–558 (doi:10.1109/18.54902).
↑ http://www.crypto-world.com/announcements/m1039.txt
↑ What is OAEP?(englisch)
↑ What is PSS/PSS-R? (englisch)

[Bearbeiten] Weblinks

Von „http://de.wikipedia.org/wiki/RSA-Kryptosystem“

Kategorie: Kryptologisches Verfahren

RSA-Kryptosystem

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis

[Bearbeiten] Schlüsselverteilung

[Bearbeiten] Geschichte

[Bearbeiten] Hybride Verfahren

[Bearbeiten] Verfahren

[Bearbeiten] Einwegfunktionen

[Bearbeiten] Erzeugung des öffentlichen und privaten Schlüssels

[Bearbeiten] Beispiel

[Bearbeiten] Alternativer privater Schlüssel

[Bearbeiten] Verschlüsseln von Nachrichten

[Bearbeiten] Beispiel

[Bearbeiten] Entschlüsseln von Nachrichten (Decodierung)

[Bearbeiten] Beispiel

[Bearbeiten] Signieren von Nachrichten

[Bearbeiten] Sicherheit

[Bearbeiten] Sicherheit von RSA

[Bearbeiten] Praktische Sicherheit

[Bearbeiten] Beweis

[Bearbeiten] RSA ist kein Primzahltest

[Bearbeiten] Vollständiges Beispiel

[Bearbeiten] Vorarbeiten

[Bearbeiten] Schlüsselerzeugung

[Bearbeiten] Verschlüsselung

[Bearbeiten] Entschlüsselung

[Bearbeiten] Signatur (Verschlüsselung mit dem geheimen Schlüssel)

[Bearbeiten] Verifikation (Entschlüsselung mit dem öffentlichen Schlüssel)

[Bearbeiten] Anwendungsgebiete

[Bearbeiten] Literatur

[Bearbeiten] Quellen

[Bearbeiten] Weblinks

Ansichten

Persönliche Werkzeuge

Navigation

Mitmachen

Suche

Werkzeuge

Andere Sprachen