8.2.7. RSA

Auf Grund der großen Bedeutung von RSA als weltweit genutzter Standard für Public-Key-Verfahren wollen wir in diesem Abschnitt etwas genauer auf diesen Algorithmus eingehen. Die nachfolgende Abhandlung hat primär informativen Charakter. Es geht darum, Ihnen einen Eindruck davon zu vermitteln, welche mathematischen Operationen beim Ver- und Entschlüsseln sowie beim Erstellen und Verifizieren von Signaturen ablaufen, worauf die Sicherheit des Verfahrens beruht und wie die Schlüssel erzeugt werden.

Beschreibung des Algorithmus

Jeder Teilnehmer (Mensch oder Rechner), der Daten mittels RSA chiffrieren, dechiffrieren oder signieren möchte, benötigt ein Paar aus privatem und öffentlichem RSA-Schlüssel. Dies ist Ihnen vermutlich von PGP 2.x her vertraut. Die Schlüssellänge ist variabel. Mit wachsendem Key steigt der Rechenaufwand etwas an, dafür gewinnt man aber deutlich an Sicherheit.

Um nun ein RSA-Schlüsselpaar zu erzeugen, wählt man zufällig zwei große, ungefähr gleich lange Primzahlen p und q und multipliziert sie miteinander:

n = pq

Das Ergebnis n, auch Modul (modulus) genannt, soll nach aktuellen Empfehlungen mindestens 768 Bit lang sein. Die für PGP 2.x typischen 1024 Bit stellen sicher momentan (noch) eine gute Wahl dar. Demnach müßten unseren beiden Faktoren p und q eine Länge von ca. 512 Bit haben.

Generell sollten diese zwei Primzahlen nicht extrem nahe beieinander liegen. Unter "extrem nah" versteht man in den RSA-FAQ, daß sie mit Ausnahme von z.B. 100 bis 200 Bits identisch sind. An gleicher Stelle wird aber auch darauf hingewiesen, daß die Wahrscheinlichkeit dafür, bei zufälliger Wahl zwei so extrem nahe Primzahlen zu finden, vernachlässigbar ist.

Um den öffentlichen Schlüssel zu generieren, wählt man eine zufällige ganze Zahl e mit 1 < e < phi(n), so daß

ggT(e, phi(n)) = 1

gilt. Das bedeutet, der größte gemeinsame Teiler (ggT) von e und phi(n) ist 1. Man nennt diese beiden Zahlen daher teilerfremd. Wir können auch sagen, sie haben nur die 1 als gemeinsamen Faktor.

Die Funktion phi(n) gibt an, wieviele Zahlen kleiner n teilerfremd zu n sind. Sie wird mitunter als Eulersche phi-Funktion (benannt nach dem bedeutenden schweizer Mathematiker Leonhard Euler) bzw. im Englischen auch als Euler's totient function bezeichnet. Wir verzichten hier auf den sonst als Symbol üblichen griechischen Buchstaben , da er sich in HTML nicht bequem handhaben läßt.

Im allgemeinen ist es schwer, phi(n) für sehr große n zu bestimmen. Bei uns liegt aber ein Sonderfall vor. Wir haben n gezielt als Produkt zweier Primzahlen p und q konstruiert. Damit läßt sich der Funktionswert sehr leicht berechnen:

phi(n) = (p-1)(q-1).

Das Zahlenpaar (e, n) stellt den öffentlichen Schlüssel dar.

Für die Erzeugung des privaten Schlüssels ist die Zahl d zu ermitteln, die bezüglich der Multiplikation modulo phi(n) das inverse Element (im Englischen multiplicative inverse und im Deutschen manchmal auch modulare Inverse genannt) zu e darstellt, so daß

ed mod phi(n) = 1
bzw.
ed = k × phi(n) + 1

gilt, wobei k eine ganze Zahl ist und das Zeichen × die Multiplikation symbolisiert.

Das gesuchte inverse Element ist immer eindeutig bestimmt. Es gilt stets 1 < d < phi(n). Aus der Tatsache, daß d ein inverses Element (nämlich e) besitzt, folgt zwangsläufig, daß d genau wie e teilerfremd zu phi(n) ist, da nur genau in diesem Falle das inverse Element existiert.

Das inverse Element läßt sich relativ einfach mit Hilfe einer Erweiterung des Euklidischen Algorithmus berechnen, dessen eigtl. Anliegen die Ermittlung des größten gemeinsamen Teilers zweier Zahlen ist. Für Details sei auf mathematische oder kryptologische Lehrbücher verwiesen.

Man nennt d und e zueinander reziprok modulo phi(n) und schreibt auch

d = e^-1 mod phi(n).

Die Zahl d dient als privater Schlüssel.
Anmerkung: Manche Autoren bezeichnen auch das Zahlenpaar (d, n) als Private Key.

Sobald die beiden Keys generiert wurden, benötigt man die Primzahlen p und q nicht mehr. Manche Autoren empfehlen, sie deshalb zu vernichten. Anderenfalls muß man sie genauso sicher wie den privaten Schlüssel aufbewahren und darf sie niemals offenlegen, da sonst jeder auf die oben genannte Weise den Private Key ermitteln kann.

Klar- und Geheimtexte werden blockweise ver- bzw. entschlüsselt. Der numerische Wert eines jeden Blocks muß stets kleiner als n sein. Bei Binärdaten ergibt sich daher dessen maximale Bitanzahl als Exponent der größten Zweierpotenz, die kleiner als oder gleich n ist. Wenn n z.B. den Wert 3220 hat, so darf jeder Block höchstens 11 Bits umfassen, da 2¹¹ = 2048 noch unterhalb und 2¹² = 4096 bereits oberhalb von 3220 liegt.

Die Verschlüsselung des Klartextblocks m_i erfolgt durch dessen Exponentiation unter Verwendung des öffentlichen Schlüssels nach der folgenden einfachen Formel, wodurch der Geheimtextblock c_i entsteht:

c_i = m_i ^e mod n.

Die Umkehroperation, also die Dechiffrierung von c_i, hat dieselbe Struktur, wobei natürlich diesmal der private Schlüssel zum Einsatz kommt:

m_i = c_i ^d mod n.

Es läßt sich relativ leicht zeigen, daß jede der beiden Formeln die durch die jeweils andere vorgenommene Transformation rückgängig macht. Wir beginnen mit einem Satz von Euler, der besagt, daß für zwei teilerfremde natürliche Zahlen m und n immer

m ^phi(n) mod n = 1

gilt. Unter Beachtung dieses Satzes sowie der oben gezeigten Gleichung

ed = k × phi(n) + 1

läßt sich die Dechiffrierung des zu einem Klartextblock M gehörenden Geheimtextes C so beschreiben (alle Operationen verstehen sich wieder modulo n):

C^d = (M^e)^d = M^ed = M^{k × phi(n)+1} = [M^phi(n)]^k M = 1^k M = M.

Wir erkennen, daß der Klartext bei der Entschlüsselung wieder korrekt entsteht. Das ist auch der Fall, wenn wir mit dem privaten Schlüssel chiffrieren und mit dem öffentlichen Schlüssel dechiffrieren (alles modulo n):

(M^d)^e = M^de = M^ed = M.

Das dabei im ersten Schritt entstehende Chiffrat stellt eine digitale Signatur dar:

S = M^d mod n.

Sie kann nur vom Inhaber des privaten Schlüssels erzeugt werden. Die Gegenoperation, d.h. die Verifikation der Signatur, ist dagegen jedermann möglich, da dafür nur der öffentliche Schlüssel benötigt wird. Die Unterschrift ist genau dann korrekt, wenn

M = S^e mod n

gilt.

Wir hatten an anderer Stelle schon darauf hingewiesen, daß man in der Regel nicht die Nachricht selbst, sondern deren Hashwert unterschreibt. In diesem Falle dürfte ein einzelner Datenblock ausreichen, da die Ergebnisse der üblichen Hashfunktionen deutlich kleiner als jeder praxistaugliche Modul n sind. Deshalb wurde bei S im Gegensatz zu c_i bewußt auf eine Indexierung verzichtet.

Ein signierter Hashwert, wie er für Signaturverfahren mit Anhang üblich ist, gestattet eine sehr schnelle und sichere Verifikation der digitalen Unterschrift. Man muß dazu lediglich selbst den Hashwert der Nachricht ermitteln und diesen mit dem Ergebnis von S^e mod n vergleichen. Stimmen beide überein, ist die Unterschrift korrekt und die Nachricht somit authentisch und integer.

Sofern bei Signaturverfahren mit Nachrichtenrückgewinnung die Nachricht nicht explizit in der Signatur enthalten ist, dann berechnet der Verifizierer über den Ausdruck

S^e mod n

die vermeintliche Originalnachricht und überprüft anschließend mit geeigneten Mitteln deren Integrität und Authentizität. Speziell bei natürlichsprachigen Nachrichten testet man dazu gewöhnlich, ob die zurückgewonnene Information einem zuvor festgelegten Redundanzschema genügt.

Der besseren Übersicht wegen fassen wir nachfolgend die wichtigsten Punkte des RSA-Algorithmus kurz zusammen:

Schlüsselerzeugung:
- Wähle zwei große Primzahen p und q
- Berechne n = pq
- Wähle e mit 1 < e < phi(n) und ggT(e, phi(n)) = 1
- Berechne d = e^-1 mod phi(n)
- öffentlicher Schlüssel: (e, n)
- privater Schlüssel: d
Verschlüsselung:
- Klartext: M < n
- Chiffrat: C = M^e mod n
Entschlüsselung:
- Chiffrat: C
- Klartext: M = C^d mod n
Signieren:
- Nachricht bzw. deren Hashwert: M < n
- Signatur: S = M^d mod n
Verifikation einer Signatur:
- Signatur: S
- Test, ob folgendes gilt: M = S^e mod n

Hinweis: Die bisher dargestellten Operationen zeigen das Prinzip der Anwendung des RSA. In der Praxis sind beim Ver- und Entschlüsseln sowie beim Berechnen und Verifizieren von Signaturen einige zusätzliche Vorkehrungen und Schritte empfehlenswert, um bestimmten potentiellen Fehlern und Problemen von vornherein aus dem Weg zu gehen. Speziell für den Einsatz des RSA wurden die mit PKCS abgekürzten Public-Key Cryptography Standards entwickelt.

Beispiel für eine RSA-Verschlüsselung

Wir wollen uns nun wenigstens einmal an relativ kleinen Zahlen ansehen, wie eine RSA-Verschlüsselung abläuft. Das Beispiel wurde von Schneier übernommen. Es seien

p = 47, q = 71, n = 3337, phi(n) = 46×70 = 3220, e = 79 und d = 1019.

Unser Klartext laute DR DOBBS (der Name einer bekannten Computer-Zeitschrift). Es gibt verschiedene Möglichkeiten, ihn in eine Zahl zu konvertieren. Wir wollen einfach die numerischen Werte der einzelnen ASCII-Zeichen aneinanderreihen, also 68 für D, 82 für R und so weiter. Dann ergibt sich als zu chiffrierende Nachricht die Zahl

m = 6882326879666683.

Der Wert jedes Blocks muß kleiner als 3337 sein. Wenn man die Nachricht als Zahl und nicht als Bitfolge betrachtet, bietet es sich im konkreten Fall an, immer 3 aufeinanderfolgende Ziffern zu einem Block zusammenzufassen. Wir erhalten so insgesamt 6 Blöcke:

m₁ = 688
m₂ = 232
m₃ = 687
m₄ = 966
m₅ = 668
m₆ = 3

Der erste Geheimtextblock ergibt sich zu

c₁ = 688⁷⁹ mod 3337 = 1570

Analog entstehen die anderen Blöcke des Chiffrats:

c = 1570 2756 2091 2276 2423 158

Die Entschlüsselung erfordert ebenfalls eine Exponentiation, diesmal allerdings mit d statt e:

m₁ = 1570¹⁰¹⁹ mod 3337 = 688
...
m₆ = 158¹⁰¹⁹ mod 3337 = 3

Effiziente Exponentiation mit großen Zahlen

Schon in diesem kleinen Beispiel entstehen recht große Zwischenwerte, wenn man bei den Ver- und Entschlüsselungsoperationen ohne weitere Überlegungen einfach zuerst potenziert und dann den Rest modulo n bestimmt. Bei 158¹⁰¹⁹ ergibt sich z.B. eine Dezimalzahl mit 2241 Stellen.

Derartige Werte sind zwar auf einem PC unter Verwendung einer geeigneten Langzahl-Arithmetik, also einer Arithmetik mit "beliebiger" Genauigkeit, noch recht gut beherrschbar, allerdings nehmen der Rechenaufwand sowie der Speicherplatzbedarf mit wachsenden Exponenten und Moduln rapide zu. Um beim RSA eine hohe Sicherheit zu erreichen, nutzt man heute Dezimalzahlen mit 200 und mehr Stellen. Mit derartigen Werten wäre eine Potenzierung entweder überhaupt nicht mehr realisierbar oder würde extrem lange dauern.

Diesem Problem kann man durch zwei relativ einfache Maßnahmen effektiv begegnen, wenngleich eine Langzahl-Arithmetik dadurch keinesfalls entbehrlich wird:

In der Modulo-Arithmetik gilt:
[(a mod n) × (b mod n)] mod n = (a × b) mod n
Wir können also Zwischenprodukte jeweils modulo n reduzieren und so die Werte relativ klein und damit praktikabel halten.
Die Exponentiation läßt sich durch eine wiederholte Quadrierung beschleunigen. An einem Beispiel wird das am ehesten deutlich. Die weiter oben benötigte Potenz 688⁷⁹ könnten wir nach der Vorschrift
688^m+1 = 688^m × 688 (0 < m < 79)
iterativ bilden. Dieses Vorgehen erfordert 78 Multiplikationen und ist daher relativ langsam. Wenn wir dagegen durch wiederholte Quadrierung zunächst die Potenzen
p₁ = 688²
p₂ = p₁² = 688⁴
p₃ = p₂² = 688⁸
p₄ = p₃² = 688¹⁶
p₅ = p₄² = 688³²
p₆ = p₅² = 688⁶⁴
und dann das Produkt
p₆ × p₃ × p₂ × p₁ × 688 = 688⁷⁹
bilden, erhalten wir das gewünschte Resultat bereits nach 10 Multiplikationen.

Drückt man den Exponenten m als Binärzahl b_ib_i-1b_i-2 ... b₀ aus, dann ergeben sich folgende Gleichungen:

Daraus kann man folgenden, auch bei großen Zahlen relativ effizienten Algorithmus für die Berechnung von d = a^b mod n entwickeln (die Notation erfolgt in einem Pascal-ähnlichen Pseudo-Code):

d = 1

for k = i downto 0

do

d = (d × d) mod n

if (b_k=1) then d = (d × a) mod n

return d

Finden großer Primzahlen

Das Erzeugen solch großer Primzahlen, wie sie beim RSA benötigt werden, stellt ein schwieriges Problem dar. Es gibt keinen bekannten praktikablen Weg, um mit Sicherheit festzustellen, daß eine derart große Zahl wirklich eine Primzahl ist. Man arbeitet daher mit Pseudoprimzahlen, d.h. solchen, die mit sehr hoher Wahrscheinlichkeit prim sind.

Zum Test, ob es sich bei einer gegebenen Zahl um eine Pseudoprimzahl handelt, wird der Kleine Fermatsche Satz (benannt nach dem bedeutenden französischen Mathematiker Pierre de Fermat) genutzt:

Wenn p eine Primzahl ist und a eine ganze Zahl, die sich nicht ohne Rest durch p teilen läßt, so ist a ^p-1 - 1 durch p teilbar.

Man kann ihn auch so schreiben:

a ^p-1 mod p = 1.

Anmerkung: Dieselbe Aussage erhalten wir durch den Satz von Euler, der eine Generalisierung des Kleinen Fermatschen Satzes darstellt. phi(p) hat im konkreten Fall den Wert p-1.

Nun stellt sich die Frage, ob obige Gleichung auch gilt, wenn p eine zusammengesetzte Zahl, d.h. keine Primzahl ist. Die Antwort lautet: normalerweise nicht. Man könnte daher den Test, ob es sich bei einer Zahl n um eine Primzahl handelt, so vornehmen, daß man eine beliebige Zahl a mit 1 < a < n wählt und überprüft, ob bei a^n-1 mod n der Wert 1 entsteht. Falls das nicht zutrifft, ist n definitiv keine Primzahl. Anderenfalls ist n mit hoher Wahrscheinlichkeit prim.

Bei einer zufällig erzeugten, ca. 100-stelligen Dezimalzahl beträgt die in der Literatur angegebene Irrtumswahrscheinlichkeit bei diesem Verfahren ungefähr 10^-13. Verwendet man beim RSA für p oder q eine zusammengesetzte Zahl statt einer Primzahl, so kann es passieren, daß sich ein Chiffrat nicht entschlüsseln läßt oder daß es jemandem gelingt, den privaten Schlüssel mit weniger Aufwand als angenommen zu bestimmen.

Durch eine mehrfache Anwendung des Tests mit jeweils verschiedenen Werten für a läßt sich dessen Zuverlässigkeit in der Regel immer weiter erhöhen, natürlich auf Kosten der Rechenzeit. Es gibt allerdings einige n, die sog. Carmichael-Zahlen, die, obwohl sie keine Primzahlen sind, für alle Werte von a die Gleichung a^n-1 mod n = 1 erfüllen.

Carmichael-Zahlen kommen sehr selten vor, so daß die Wahrscheinlichkeit dafür, daß man zufällig eine wählt, äußerst gering ist. In der Praxis verwendet man dennoch meist Erweiterungen des obigen Primzahlentests, die mit sehr hoher Wahrscheinlichkeit zusammengesetzte Zahlen inkl. Carmichael-Zahlen erkennen, da der hierfür benötigte zusätzliche Rechenaufwand verhältnismäßig gering ist.

Ein sehr häufig eingesetztes Verfahren ist der probabilistische Primzahlentest nach Michael Rabin, der teilweise auf Ideen von Gary Miller basiert und deshalb auch als Miller-Rabin-Test bezeichnet wird. Ausgangspunkt ist die Tatsache, daß man n-1 immer als Produkt einer Zweierpotenz und einer ungeraden Zahl ausdrücken kann: 2^bc. Man wählt b so, daß 2^b die größte Zweierpotenz ist, die n-1 teilt. Damit läßt sich a^n-1 mod n bestimmen, indem man a^c mod n berechnet und das Ergebnis b Mal quadriert.

Wenn dabei keine Eins entsteht, dann ist n definitiv keine Primzahl. Ergibt sich die Zahl 1, dann schaut man sich die als Zwischenergebnisse gebildeten Quadrate an (in einer effizienten Implementierung tut man dies sinnvollerweise parallel zur Berechnung). Stellt sich dabei heraus, daß irgendwo eine Eins entstanden ist, obwohl der Ausgangswert weder 1 noch n-1 war, dann handelt es sich ebenfalls definitiv um keine Primzahl, denn wenn n prim wäre, kämen nur die Werte 1 und n-1 (letzterer ist kongruent zu -1 modulo n) als Quadratwurzeln modulo n von 1 in Frage.

Jede Zahl a, die nicht anzeigt, daß n definitiv zusammengesetzt ist, wird als Zeuge (witness) für die Primzahleigenschaft von n bezeichnet. Rabin hat bewiesen, daß bei zusammengesetzten Zahlen n die Anzahl derartiger Zeugen kleiner als (n-1)/4 ist. Wenn n ungerade ist und sich k zufällig gewählte Werte a mit 1 < a < n als Zeugen erweisen, dann ist die Wahrscheinlichkeit dafür, daß n keine Primzahl ist, geringer als 4^-k.

Anmerkung: Viele Autoren nutzen den Begriff Zeugen genau umgekehrt, also für Zahlen, die mit Sicherheit anzeigen, daß n zusammengesetzt ist. In diesem Falle gilt analog zur obigen Aussage: Wenn n eine ungerade zusammengesetzte Zahl ist, dann sind mehr als drei Viertel der ganzen Zahlen a mit 1 < a < n Zeugen der "Zusammengesetztheit" (compositeness) von n.

Schneier gibt folgende Notation des Algorithmus an:

Wähle eine Zufallszahl a kleiner als n.
Setze j = 0 und z = a^c mod n.
Falls z = 1 oder z = n-1, dann besteht n diesen Test und ist möglicherweise eine Primzahl.
Falls j > 0 und z = 1, dann ist n keine Primzahl.
Setze j = j+1. Falls j < b und z ungleich n-1, dann setze z = z² mod n und gehe zu Schritt 4.
Falls z = n-1, dann besteht n diesen Test und ist möglicherweise eine Primzahl.
Falls j = b und z ungleich n-1, dann ist n keine Primzahl.

Bestimmung von e und d

Wir wissen, daß e und phi(n) teilerfremd sein müssen. Das kann man mit folgenden zwei Strategien erreichen:

Nach der Generierung von p und q wählt man e so lange zufällig, bis ein Wert gefunden wurde, der der geforderten Bedingung entspricht.
Man legt zuerst e fest und wählt danach p und q so, daß sowohl p-1 als auch q-1 teilerfremd zu e sind.

Der zweite Weg ist deshalb sehr interessant, weil (nach momentanem Erkenntnisstand) die Sicherheit von RSA im allgemeinen nicht negativ beeinflußt wird, wenn man immer denselben Wert für e verwendet, wobei dieser auch sehr klein sein kann. Kleine Exponenten beschleunigen deutlich die mit dem öffentlichen Schlüssel ausgeführten Operationen, also Chiffrierung sowie die Verifikation von Unterschriften, ohne diejenigen negativ zu beeinflussen, die den privaten Schlüssel verwenden.

Die am häufigsten genutzten Exponenten sind 3, 17 und 65537. Bei letzterem handelt es sich um die vierte Fermat-Zahl F₄ (ebenfalls nach Pierre de Fermat benannt). Sie läßt sich in der Form 2^2⁴+1 = 2¹⁶+1 darstellen. Ihre Binärrepräsentation enthält neben 15 Nullen genau zwei Einsen, so daß man mit ihr sehr einfach potenzieren kann.

Die einzelnen Standards enthalten unterschiedliche Empfehlungen für e:

X.509 65537

PEM 3

PKCS #1 3 oder 65537

Sicherheit des RSA-Algorithmus

Man geht davon aus, daß die Sicherheit des RSA-Verfahrens auf dem schweren Problem der Faktorisierung großer Zahlen beruht. Es gibt dafür zwar keinen mathematischen Beweis, aber wir können feststellen, daß trotz intensiver Kryptoanalyse kein (öffentlich beschriebener) Weg gefunden wurde, den Algorithmus zu brechen.

Es wird allgemein angenommen, daß die als Verschlüsselungsfunktion verwendete Potenzierung modulo n unter bestimmten Voraussetzungen eine Einwegfunktion mit Falltür darstellt:

f(M) = M^e mod n.

Der Modul n ist bekanntlich das Produkt der zwei großen Primzahlen p und q. Diese beiden Zahlen stellen die Falltür dar. Wenn man sie kennt, kann man sofort phi(n) und damit relativ einfach ein d (den privaten Schlüssel) finden, so daß

(M^e)^d mod n = M

gilt. Sind die Primfaktoren dagegen nicht bekannt, könnte man nun versuchen,

alle möglichen privaten Schlüssel durchzuprobieren (Brute-force-Attacke),
den Modul n zu faktorisieren und so p und q zu bestimmen,
phi(n) direkt, d.h. ohne p und q, zu berechnen oder
d direkt, d.h. ohne phi(n), zu ermitteln.

All dies erscheint nicht erfolgversprechend:

Vor der Brute-force-Attacke schützt ein hinreichend großer Schlüsselraum.
Die Faktorisierung großer Zahlen (z.B. 2048 Bits) ist mit den heute öffentlich bekannten Algorithmen wegen der extrem hohen Rechenzeit nicht realisierbar.
Eine direkte Bestimmung von phi(n) aus n oder von d aus e und n ist mit den gegenwärtig verfügbaren Methoden mindestens so aufwendig wie die Faktorisierung.

Auch wenn der Basis-Algorithmus sicher erscheint, so reicht dies in der Praxis nicht aus. Generell gilt, daß das ganze Kryptosystem sowie das verwendete Protokoll ebenfalls sicher sein müssen. So haben verschiedene Attacken Erfolg, die sich gegen die konkrete Implementation von RSA richten. Details sind hierbei sehr entscheidend.

Wenn z.B. der Exponent e wie üblich relativ klein gewählt wird, so sollte man die zu chiffrierende Nachricht immer durch ein Padding mit in der Regel zufälligen Werten auffüllen. Nehmen wir an, daß e den Wert 3 hat. Falls dann die Nachricht sehr klein ist, konkret kleiner als die dritte Wurzel des Moduls n, dann ergibt sich als Chiffrat der Ausdruck m³. Daraus kann der Klartext durch Bestimmung der dritten Wurzel sehr einfach ermittelt werden.

Durch Padding erreicht man, daß m³ den Wert des Moduls übersteigt und so beim Chiffrieren eine Reduktion modulo n stattfindet. Als Geheimtext erhalten wir dann wirklich wie erwartet m³ mod n statt m³. Außerdem verhindert das Auffüllen mit verschiedenen Werten noch eine weitere Attacke: Wenn man nämlich bei n = 3 ein und diesselbe Nachricht an drei Empfänger verschickt, kann man unter Verwendung des sog. Chinesischen Restesatzes aus den drei Chiffraten und den drei öffentlichen Schlüsseln ohne Probleme den Klartext ermitteln.

Ein weiterer Ansatzpunkt ist eine chosen-ciphertext attack, also ein Angriff, bei dem sich der Kryptoanalytiker verschiedene, von ihm gezielt konstruierte Chiffrate entschlüsseln lassen kann, und zwar, indem er sie dem Opfer, nennen wir es Anton, zum Signieren vorlegt. Mit den dabei entstehenden Ergebnissen (d.h. den Signaturen) kann er je nach Situation Nachrichten dechiffrieren, die mit Antons öffentlichem Schlüssel chiffriert worden sind, oder sich Antons Unterschrift für ein Dokument berechnen, daß dieser nie zuvor gesehen hat.

Letzteres wird durch folgendes Beispiel illustriert: Berta benötigt Antons Unterschrift für eine Nachricht m₃. Da er den Inhalt nicht kennen soll, generiert sie zwei Nachrichten m₁ und m₂, so daß

m₃ = m₁ m₂ mod n

gilt. Wenn es ihr gelingt, diese beiden von Anton signieren zu lassen, kann sie die gesuchte Unterschrift sehr leicht selbst berechnen:

m₃^d = (m₁^d mod n) (m₂^d mod n) mod n

Als wichtige Erkenntnis sollte man daraus mitnehmen, daß RSA nie dazu genutzt werden darf, irgendein beliebiges Dokument, daß ein Fremder vorlegt, zu unterschreiben. Signiert werden darf maximal der über eine Einweg-Hashfunktion berechnete Hashwert, da dann die auf Gesetzmäßigkeiten der Modulo-Arithmetik beruhenden Attacken nicht mehr funktionieren.

Für weitere Details zu Angriffen auf RSA-Implementierungen sei auf entsprechende Literatur verwiesen (z.B. Schneier, Kaufman und Menezes).

PKCS

Es ist sinnvoll, Standards für die Kodierung von Informationen zu verwenden, die mittels RSA verschlüsselt bzw. signiert werden sollen, da so unterschiedliche Implementationen zusammenarbeiten können und auch verschiedene der oben erwähnten Angriffe gegen sie vermieden werden.

Die von der Firma RSA Data Security, Inc. (RSADSI) in Zusammenarbeit mit einem inoffiziellen Konsortium (zu dem usrprünglich Apple, Microsoft, DEC, Lotus, Sun und das MIT gehörten) entwickelten Public-Key Cryptography Standards (PKCS) stellen einen Satz von Standards für Public-Key-Kryptographie dar, die neben syntaktischen Festlegungen auch algorithmenspezifische sowie algorithmenunabhängige Vorschriften für die Schlüsselerzeugung, die Ver- und Entschlüsselung von Nachrichten sowie die Berechnung und Verifikation von digitalen Signaturen enthalten.

PKCS ist kompatibel zu PEM (Privacy Enhanced Mail), erweitert diese aber z.B. um die Möglichkeit, allgemeine Binär- und nicht nur reine ASCII-Daten verarbeiten zu können. PKCS ist auch kompatibel zum Standard X.509 der ITU-T.

Die einzelnen Dokumente werden numeriert (z.B. PKCS #1, #3, #5). Einen Überblick über die aktuell gültigen Standards und neue Entwicklungen finden Sie z.B. in den RSA-FAQ oder unter http://www.rsa.com/rsalabs/pubs/PKCS/. Über diesen URL können Sie die PKCS-Dokumente in verschiedenen Formaten kostenfrei beziehen.

d = 1
for k = i downto 0
do
	d = (d × d) mod n
	if (b_k=1) then d = (d × a) mod n
return d