RSA-Kryptosystem

Grundidee und Bedeutung

RSA (Rivest-Shamir-Adleman) ist ein asymmetrisches kryptographisches Verfahren. Es kann zum Verschluesseln von Daten und fuer digitale Signaturen verwendet werden. Asymmetrisch bedeutet: Es gibt ein Schluesselpaar aus einem oeffentlichen Schluessel und einem privaten Schluessel. Mit dem oeffentlichen Schluessel kann man Nachrichten verschluesseln oder Signaturen pruefen. Mit dem privaten Schluessel kann man Nachrichten entschluesseln oder Signaturen erzeugen. Der private Schluessel muss geheim bleiben und kann nach heutigem Wissen nicht mit realistischem Aufwand aus dem oeffentlichen Schluessel berechnet werden.

RSA wurde 1977 von Ronald L. Rivest, Adi Shamir und Leonard Adleman am MIT veroeffentlicht und war das erste veroeffentlichte asymmetrische Verschluesselungsverfahren. Ein aehnliches Verfahren war bereits Anfang der 1970er Jahre beim britischen GCHQ entwickelt worden, wurde aber aus Geheimhaltungsgruenden nicht wissenschaftlich publiziert. Das RSA-Patent erlosch am 21. September 2000.

Mathematische Grundlage und Schluessel

RSA beruht auf sogenannten Einwegfunktionen: In eine Richtung sind sie leicht zu berechnen, in die Gegenrichtung sehr schwer. Ein Beispiel ist die Multiplikation zweier grosser Primzahlen: Das Produkt ist leicht zu bilden, aber die Zerlegung einer sehr grossen Zahl in ihre Primfaktoren ist nach heutigem Wissen sehr aufwendig. Eine Falltuerfunktion ist eine Einwegfunktion, die mit einer geheimen Zusatzinformation leicht umkehrbar wird. Bei RSA ist der private Schluessel diese Falltuer.

Die Schluessel bestehen aus den Zahlen e, d und N. N heisst RSA-Modul, e Verschluesselungsexponent und d Entschluesselungsexponent. Der oeffentliche Schluessel ist (e,N), der private Schluessel ist (d,N).

Zur Schluesselerzeugung waehlt man zwei verschiedene, zufaellige und stochastisch unabhaengige Primzahlen p und q. Sie sollen ungefaehr gleich gross sein, aber nicht zu dicht beieinander liegen, ungefaehr mit 0,1 < |log2 p - log2 q| < 30. Dann berechnet man N = p * q und die Eulersche phi-Funktion phi(N) = (p - 1)(q - 1). Danach waehlt man e teilerfremd zu phi(N) mit 1 < e < phi(N). Der Wert d wird als multiplikatives Inverses von e modulo phi(N) berechnet, also e * d ≡ 1 mod phi(N). Das kann mit dem erweiterten euklidischen Algorithmus geschehen.

p, q, phi(N) und d muessen geheim bleiben. In der Praxis waehlt man haeufig zuerst einen kleinen Exponenten e mit 2^16 < e < 2^64. Ein e kleiner als die Fermat-Zahl F4 = 2^16 + 1 = 65537 kann Angriffe erleichtern, etwa Håstads Broadcast-Angriff. Ist d zu kurz, kann es unter bestimmten Bedingungen mit Kettenbruechen effizient gefunden werden; bei e < 2^64 ist diese Moeglichkeit ausgeschlossen.

Verschluesseln, Entschluesseln und Signieren

Zum Verschluesseln einer Nachricht m verwendet der Absender den oeffentlichen Schluessel des Empfaengers und berechnet c ≡ m^e mod N. Das Ergebnis c ist der Geheimtext. Dabei muss m kleiner als N sein. Zum Entschluesseln berechnet der Empfaenger mit dem privaten Schluessel m ≡ c^d mod N.

Ein kleines Beispiel aus dem Artikel verwendet e = 23, p = 11 und q = 13. Daraus folgt N = 143 und phi(N) = 120. Das multiplikative Inverse von 23 modulo 120 ist d = 47. Der oeffentliche Schluessel ist also (23,143), der private Schluessel (47,143). Die Zahl 7 wird verschluesselt durch 7^23 mod 143 = 2. Der Geheimtext ist c = 2. Entschluesselt wird durch 2^47 mod 143 = 7.

Beim Signieren wird die RSA-Funktion mit dem privaten Schluessel angewendet. Der Empfaenger prueft die Signatur mit dem oeffentlichen Schluessel und vergleicht das Ergebnis mit der uebermittelten Nachricht. Damit sollen Integritaet und Authentizitaet gesichert werden: Die Nachricht wurde nicht veraendert, und der Signierende besitzt den privaten Schluessel. Das einfache Signaturverfahren ist aber wegen der Homomorphieeigenschaft von RSA unsicher. Aus vorhandenen Signaturen koennen neue gueltige Signaturen konstruiert werden. Deshalb wird nicht die Nachricht selbst signiert, sondern ein Hash-Wert H(m), der mit einer kollisionsresistenten Hashfunktion gebildet wird. Auch diese einfache Variante erfuellt moderne Anforderungen nicht vollstaendig; fuer RSA-Signaturen werden Verfahren wie RSA-PSS verwendet.

Mit dem Chinesischen Restsatz kann RSA beim Entschluesseln oder Signieren beschleunigt werden. Dabei rechnet man nicht direkt modulo N, sondern getrennt modulo p und modulo q und setzt die Ergebnisse anschliessend wieder zusammen. Diese Variante heisst CRT-RSA.

Sicherheit und Angriffe

Die Sicherheit von RSA haengt eng mit dem Faktorisierungsproblem zusammen: Man muesste N = p q in seine beiden grossen Primfaktoren zerlegen, um phi(N) und daraus den privaten Schluessel zu bestimmen. Es ist aber nicht bewiesen, dass Faktorisierung prinzipiell schwierig ist. Bekannt ist: Das RSA-Schluesselproblem, also aus (N,e) den geheimen Schluessel d zu finden, ist polynomial aequivalent zum Faktorisierungsproblem. Ob das reine RSA-Problem, also aus c und (N,e) den Klartext m zu finden, genauso schwer ist, ist unbekannt.

Fuer grosse Zahlen ist Faktorisieren mit bekannten Verfahren praktisch sehr schwer. Beispiele aus der RSA Factoring Challenge zeigen die Entwicklung: RSA-129 mit 129 Dezimalstellen wurde 1994 in 8 Monaten von etwa 600 Freiwilligen faktorisiert. RSA-200 mit 200 Dezimalstellen wurde 2005 zerlegt. RSA-640 mit 640 Bits beziehungsweise 193 Dezimalstellen brachte im November 2005 eine Praemie von 20.000 US-Dollar. RSA-768 wurde im Dezember 2009 faktorisiert. Fuer RSA-1024 (309 Dezimalstellen) und RSA-2048 (617 Dezimalstellen) waren 100.000 US-Dollar beziehungsweise 200.000 US-Dollar ausgelobt; die Challenge wurde im Mai 2007 beendet.

Die wachsende Rechenleistung ist kurzfristig kein grundsaetzliches Problem, wenn ausreichend lange Schluessel gewaehlt werden. Unvorhersehbare Entwicklungen wie deutlich schnellere Algorithmen oder leistungsfaehige Quantencomputer mit Shor-Algorithmus koennten aber mittel- und langfristig Risiken schaffen. Zur Schluessellaenge nennt der Artikel unterschiedliche Aussagen: Die Bundesnetzagentur hielt fuer RSA-basierte Signaturen bis Ende 2020 mindestens 1976 Bit fuer geeignet und empfahl 2048 Bit. Fuer bestimmte Signaturverfahren sollten mindestens 3000 Bit verpflichtend werden, um perspektivisch ein Sicherheitsniveau von 120 Bit zu erreichen.

Unmodifiziertes RSA, auch Textbook-RSA genannt, ist unsicher. Da die Verschluesselung deterministisch ist, kann ein Angreifer vermutete kurze Klartexte selbst verschluesseln und mit einem Chiffrat vergleichen; dadurch ist Textbook-RSA nicht IND-CPA-sicher. Ist m^e kleiner als N, kann ein Angreifer einfach die e-te Wurzel ziehen. Wird dieselbe Nachricht mit gleichem kleinen Exponenten an mehrere Empfaenger gesendet, kann Håstads Angriff mit dem Chinesischen Restsatz greifen. Wegen der multiplikativen Eigenschaft lassen sich ausserdem neue Chiffrate oder Signaturen aus bekannten Werten erzeugen.

Padding und hybride Verwendung

Um Angriffe auf Textbook-RSA zu verhindern, nutzt man Padding-Verfahren. Padding bedeutet, dass vor der RSA-Berechnung eine strukturierte und oft zufaellig gewaehlte Zeichenfolge R an den Klartext oder an den Hash-Wert angehaengt wird. Dadurch wird das Chiffrat randomisiert und die Dekodierung erleichtert. Standards fuer RSA-Padding stehen zum Beispiel in PKCS#1 oder ISO 9796. Moderne Verfahren wie Optimal Asymmetric Encryption Padding (OAEP) fuer Verschluesselung und Probabilistic Signature Scheme (PSS) fuer Signaturen verwenden kryptographische Hashfunktionen und sind unter idealisierenden Annahmen an die Hashfunktion beweisbar sicher unter der RSA-Annahme.

Ein wichtiger Angriff auf Padding war Bleichenbachers Chosen-Ciphertext-Angriff von 1998 gegen RSA-Verschluesselung nach PKCS#1 v1. Dabei wurden Fehlermeldungen einiger Implementierungen ausgenutzt, wenn ein entschluesselter Text nicht das vorgeschriebene Format hatte. Durch wiederholtes Veraendern eines Chiffrats mit geschickt gewaehlten Werten konnte der Klartext schrittweise aufgedeckt werden. RSA nach PKCS#1 ab Version 2 ist gegen diesen Angriff immun.

In der Praxis wird RSA fast immer in hybriden Verfahren verwendet, weil es im Vergleich zu 3DES und AES mindestens um den Faktor 100 langsamer ist. Typisch ist: RSA verschluesselt nur einen zufaellig erzeugten Sitzungsschluessel, und die eigentlichen Daten werden mit einem symmetrischen Verfahren verschluesselt. Geraeuchliche symmetrische Verfahren beruhen zum Beispiel auf AES mit 128, 192 oder 256 Bit Schluessellaenge. Beim Signieren wird nicht die ganze Nachricht signiert, sondern ein Hash-Wert, etwa aus SHA-2 mit 224 bis 512 Bit. Die Sicherheit des Gesamtsystems haengt von beiden Verfahren ab, wird aber oft durch das Public-Key-Verfahren bestimmt, weil RSA fuer ein aehnliches Sicherheitsniveau deutlich laengere Schluessel braucht.

Beispiel und Anwendungen

Das vollstaendige Beispiel im Artikel zeigt eine Textverschluesselung mit kleinen Zahlen, die nur der Veranschaulichung dienen. RSA direkt auf Texte anzuwenden, birgt erhebliche Risiken; in der Praxis wird RSA fast nur mit anderen Verfahren kombiniert. Fuer sichere Verschluesselung werden im Artikel typischerweise mindestens 600-stellige N empfohlen.

Im Beispiel wird Text zunaechst in Zahlen umgewandelt: Leerzeichen = 00, A = 01, B = 02, C = 03 usw. Je drei Zeichen werden zu einer Zahl zusammengefasst, etwa AXT zu 012420. Fuer den Klartext WIKIPEDIA ergibt sich die Kodierung 23 09 11 09 16 05 04 09 01. Gewaehlt werden p = 307 und q = 859. Daraus folgen N = 263713 und phi(N) = 262548. Mit e = 1721 und d = 1373 ist der oeffentliche Schluessel (1721,263713), der private Schluessel (1373,263713). Die drei Klartextbloecke werden zu 001715, 184304 und 219983 verschluesselt und mit d wieder zu 230911, 091605 und 040901 entschluesselt. Fuer Signaturen wird im Beispiel mit d gerechnet und mit e verifiziert.

Anwendungsgebiete von RSA sind unter anderem X.509-Zertifikate in Internet- und Telefonie-Infrastruktur, Protokolle wie IPsec, TLS, SSH und WASTE, E-Mail-Verschluesselung mit OpenPGP und S/MIME, die Authentifizierung franzoesischer Telefonkarten, Kartenzahlung mit EMV, der RFID-Chip im deutschen Reisepass und Electronic Banking mit HBCI.