Diskussion:RSA

Aus Foxwiki

Geschichte

Nachdem Whitfield Diffie und Martin Hellman im Jahr 1976 eine Theorie zur Public-Key-Kryptografie veröffentlicht hatten, versuchten die drei Mathematiker Rivest, Shamir und Adleman am MIT, 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 1977 RSA, das erste veröffentlichte asymmetrische Verschlüsselungsverfahren. Der Name RSA steht für die Anfangsbuchstaben ihrer Familiennamen. Da Adleman seinen Anteil als gering einschätzte und anfangs gar nicht als Autor genannt werden wollte, kam es zur nicht-alphabetischen Reihenfolge der Autoren und damit zur Abkürzung RSA.

Bereits Anfang der 1970er Jahre war im britischen GCHQ von Ellis, Cocks und Williamson ein ähnliches asymmetrisches Verfahren entwickelt worden, welches aber keine große praktische Bedeutung erlangte und aus Geheimhaltungsgründen nicht wissenschaftlich publiziert wurde. RSA konnte daher 1983 zum Patent angemeldet werden, obgleich es nicht das erste Verfahren dieser Art war. Das Patent erlosch am 21. September 2000.

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 im praktischen Einsatz müssen die Sicherheit des Public-Key-Verfahrens und die praktische Sicherheit des Gesamtsystems betrachtet werden. Angriffe auf das RSA-Verfahren erfolgen oft über Seitenkanäle. Das Gesamtsystem kann unsicher sein, wenn nur eine Komponente, beispielsweise ein Computer, kompromittiert wurde.

Beziehung zwischen RSA und dem Faktorisierungsproblem

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

  • RSA-Problem (): Gegeben sind der öffentliche Schlüssel sowie der Geheimtext . Gesucht wird der Klartext , wobei gilt:
Das Problem liegt hier in der Schwierigkeit, -te Wurzeln modulo zu ziehen, was zur Bestimmung der Nachricht notwendig ist.
  • RSA-Schlüsselproblem (): Gegeben ist der öffentliche Schlüssel . Gesucht wird der geheime Schlüssel , wobei gilt:
Das Problem liegt hier in der Schwierigkeit, die Eulersche φ-Funktion von ohne Kenntnis der Faktoren p und q zu berechnen.

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

Die Beziehung 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 zurzeit unbekannt.

Auch die Beziehung ist trivial, denn wenn man faktorisiert hat, kann man damit leicht 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 ist schon lange ein probabilistischer Polynomialzeitalgorithmus bekannt. Vor kurzem wurde gezeigt, dass sich diese Reduktion im balancierten RSA (d. h. und 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 Gitterbasenreduktion 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 . Wegen ist im Fall der zusätzlichen Kenntnis eines Geheimtexts die Schwierigkeit des Faktorisierungsproblems von zentralem Interesse.

Schwierigkeit des Faktorisierungsproblems

Man möchte für sehr große Primzahlen und 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.

Mit dem Quadratischen Sieb wurde 1994 die Zahl RSA-129 mit 129 Dezimalstellen in 8 Monaten von ca. 600 Freiwilligen faktorisiert. Mit der Methode des Zahlkörpersiebs wurde im Jahr 2005 von Wissenschaftlern der Friedrich-Wilhelms-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 ersten RSA-Zahlen bis RSA-500 wurden entsprechend der Anzahl der Dezimalstellen benannt, weitere RSA-Zahlen nach der Anzahl der Binärstellen. 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. Obwohl mittlerweile für das Faktorisieren der RSA-Challenge-Zahlen keine Prämien mehr gezahlt werden, wurde im Dezember 2009 die Zahl RSA-768 faktorisiert.

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 die RSA Factoring Challenge beendet, nachdem die o. g. Wissenschaftler der Universität Bonn im selben Monat eine 1039-Bit Mersennezahl (312 Dezimalstellen) faktorisiert hatten. Aufgrund der ungleichen Stellenzahl der Faktoren war das aber wesentlich leichter, als eine RSA-Zahl gleicher Länge zu faktorisieren. 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 der während der Dauer der beabsichtigten Verwendung nicht faktorisiert werden kann. Nicht vorhersehbare Entwicklungen wie die Entdeckung deutlich schnellerer Algorithmen oder gar Schaffung eines leistungsfähigen Quantencomputers, der die Faktorisierung von Zahlen durch Verwendung des Shor-Algorithmus effizient durchführen könnte, bergen zumindest für die mittel- und langfristige Sicherheit der verschlüsselten Daten gewisse Risiken.

Zum konkreten Sicherheitsniveau bestimmter Schlüssellängen gibt es unterschiedliche Aussagen. Laut Bundesnetzagentur sind für RSA-basierte Signaturen bis Ende 2020 Schlüssel mit einer Mindestlänge von 1976 Bit geeignet (Empfehlung 2048 Bit). Für Signaturverfahren nach den Anforderungen aus Vorlage:§ Abs. 1 bis 3 SigG, „für die die besten bekannten Angriffe auf dem Problem der Faktorisierung großer Zahlen oder auf dem Problem der Berechnung diskreter Logarithmen in endlichen Körpern beruhen (RSA und DSA), werden Schlüssellängen von mindestens 3 000 Bit verpflichtend werden“, um perspektivisch mindestens ein Sicherheitsniveau von 120 Bit zu etablieren.

Schwierigkeit des RSA-Problems

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 . Wiener verwendete dabei die Tatsache, dass unter der Abschätzung für der Bruch (für eine ganze Zahl ) in der Kettenbruchentwicklung von auftaucht. Die Schranke wurde mit Mitteln der Gitterbasenreduktion auf 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üsselungsexponenten (etwa ) 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 Gitterbasenreduktion beruht.

Angriffe gegen das unmodifizierte RSA-Verfahren („Textbook-RSA“)

RSA ist in der oben beschriebenen Version, die auch als „Textbook-RSA“ bekannt ist, weder als Verschlüsselungs- noch als Signaturverfahren geeignet, da es in beiden Fällen auf gravierende Weise unsicher ist und als Signaturverfahren auch keine langen Nachrichten signieren kann.

Die RSA-Verschlüsselung ist deterministisch. Das erlaubt es einem Angreifer, einen Klartext zu raten, ihn mit dem öffentlichen Schlüssel zu verschlüsseln und dann mit einem Chiffrat zu vergleichen. Dies kann insbesondere bei sehr kurzen Nachrichten wie “Ja” und „Nein“ sehr praktikabel und verheerend sein. Hieraus folgt, dass unmodifiziertes RSA nicht IND-CPA-sicher ist, heute eine absolute Minimalanforderung an Verschlüsselungsverfahren.

Wenn der Klartext und der Verschlüsselungsexponent so klein sind, dass sogar ist, dann kann ein Angreifer die -te Wurzel aus ziehen und das Chiffrat auf diese Weise entschlüsseln. Wurzelziehen ist nur modulo einer großen Zahl schwierig, aber in diesem Fall kann als ganze Zahl betrachtet werden.

Wenn dieselbe Nachricht zu mehreren Empfängern geschickt wird, die zwar alle unterschiedliche (und teilerfremde) Moduli benutzen, aber als öffentlichen Schlüssel den gleichen Exponenten , dann kann aus Nachrichten mit dem Chinesischen Restsatz berechnet werden. Weil (nach Voraussetzung ist für alle ), kann diese Zahl wieder als in den ganzen Zahlen liegend aufgefasst werden und Wurzelziehen ist dort einfach. Dieser Angriff wird nach seinem Entdecker Johan Håstad als „Håstads Angriff“ bezeichnet.

Da die RSA-Funktion multiplikativ ist (d. h. gilt), kann man aus jedem Chiffrat ein weiteres gültiges Chiffrat erzeugen. Wenn man den Besitzer des zugehörigen geheimen Schlüssels davon überzeugen kann, diese Zahl zu entschlüsseln oder zu signieren, kann man aus dem Ergebnis leicht gewinnen.

Dieselbe Eigenschaft erlaubt auch einen Angriff auf das Signaturverfahren. Aus bekannten Klartext-Signaturpaaren lassen sich weitere gültige Signaturen

zu Nachrichten

berechnen.

Padding

Um solche Angriffe zu verhindern, werden bei RSA-Verschlüsselung und RSA-Signatur sogenannte Padding-Verfahren eingesetzt. Standards für Padding-Verfahren für RSA werden z. B. in PKCS#1 oder ISO 9796 definiert. Diese nutzen aus, dass die Länge des Klartextes bzw. Hash-Wertes deutlich kleiner als die Länge von ist, und fügen dem Klartext bzw. dem Hash-Wert vor der Verschlüsselung oder Signatur eine Zeichenfolge R mit vorgegebener Struktur an, die unter mehreren möglichen zufällig gewählt wird und dadurch das Chiffrat randomisiert. Es wird also die RSA-Funktion nicht auf die Nachricht oder auf den Hash-Wert angewandt, sondern auf den Klartext (bzw. seinem Hashwert) mit angehängtem . In der Regel enthält eine Angabe über die Länge der Nachricht oder des Hash-Wertes oder eine eindeutige Zeichenfolge, die den Beginn von kennzeichnet. Dies erleichtert nicht nur die Dekodierung, sondern erschwert auch Angriffe. Padding-Verfahren können für die Berechnung von auch Zufallszahlen und Hashfunktionen verwenden. Einige moderne Paddingverfahren – beispielsweise das Optimal Asymmetric Encryption Padding (OAEP) oder das Probabilistic Signature Scheme (PSS) – verwenden kryptographische Hashfunktionen, um den Klartext vor der Verschlüsselung weiter zu randomisieren, und sind unter idealisierenden Annahmen an die verwendete Hashfunktion beweisbar sicher unter der RSA-Annahme.

Chosen-Ciphertext-Angriff

Daniel Bleichenbacher stellte 1998 einen Angriff auf die in PKCS#1 v1 spezifizierte RSA-Verschlüsselung vor. Dabei nutzte er aus, dass PKCS#1 v1 ein Nachrichtenformat vorgibt und einige Implementierungen nach dem Entschlüsseln Fehlermeldungen ausgeben, falls dieses Format nicht eingehalten wurde. Um den Angriff gegen ein Chiffrat durchzuführen, wählt man eine Zahl und berechnet daraus ein neues Chiffrat . Bei dem Nachrichtenformat sind die ersten zwei Bytes 00 und 02, wenn also keine Fehlermeldung kommt, weiß man, dass sowohl bei der ursprünglichen Nachricht als auch bei der neuen Nachricht die ersten beiden Bytes 00 02 sind. Mehrfache Wiederholung mit geschickt gewählten erlauben es, nach und nach den gesamten Klartext aufzudecken. RSA nach PKCS#1 ab Version 2 ist immun gegen diesen Angriff.

Sicherheit hybrider Verfahren

RSA wird aus Effizienzgründen in der Regel in Hybridverfahren mit symmetrischen Verfahren kombiniert. Zur hybriden Verschlüsselung wird zufällig ein Sitzungsschlüssel für ein symmetrisches Verschlüsselungsverfahren generiert, der dann per RSA verschlüsselt und zusammen mit der Nachricht übertragen wird. Zum Signieren wird nicht die gesamte Nachricht, sondern nur ein Hash-Wert signiert.

Für die Sicherheit von RSA sind Primzahlen mit mehreren hundert Dezimalstellen (mindestens 2048 Bit) erforderlich. Damit können symmetrische Schlüssel jeder üblichen Länge verschlüsselt werden. Gängige Verfahren zur symmetrischen Verschlüsselung basieren beispielsweise auf der Blockchiffre AES mit einer Schlüssellänge von 128, 192 oder maximal 256 Bit.

Eine sichere Hashfunktion wie SHA-2 erzeugt Hashwerte mit einer Länge von 224 bis 512 Bit. Damit lassen sich Signaturverfahren mittels RSA realisieren, die nur einen Signaturschritt benötigen.

Die Sicherheit des Gesamtsystems hängt sowohl im Fall der Verschlüsselung als auch der Signatur von der Sicherheit beider verwendeter Verfahren ab. Da bei RSA für ein ähnliches Sicherheitsniveau wie beim symmetrischen Verfahren deutlich längere Schlüssel nötig sind, wird die Sicherheit des Hybridverfahrens meistens von der Sicherheit des Public-Key-Verfahrens bestimmt.

Vollständiges Beispiel

Anmerkung

  • RSA direkt auf Texte anzuwenden, birgt erhebliche Risiken. RSA wird deshalb, anders als im Beispiel, in der Praxis praktisch nur in Kombination mit anderen Verfahren verwendet. (Siehe: Hybride Verschlüsselung und Abschnitt Angriffe gegen das unmodifizierte RSA-Verfahren.)
  • Um das Beispiel übersichtlich zu halten, wurden relativ kleine Primzahlen verwendet. Zur sicheren Verschlüsselung werden typischerweise mindestens 600-stellige empfohlen.

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über hinaus 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 Modul muss also größer als 262626 sein. 

Klartext: W I K I P E D I A
Kodierung: 23 09 11 09 16 05 04 09 01

Schlüsselerzeugung

Zunächst werden geheim zwei Primzahlen gewählt, beispielsweise und . Damit ergibt sich:

   (zufällig, teilerfremd zu )
   (das multiplikative Inverse zu mit Hilfe des erweiterten euklidischen Algorithmus)

Öffentlicher Schlüssel:

 und 

Privater Schlüssel:

 und 

Verschlüsselung

Cn = Kne mod N für n=1,2,3(,...)
C1 = 2309111721 mod 263713 = 001715
C2 = 0916051721 mod 263713 = 184304
C3 = 0409011721 mod 263713 = 219983

Entschlüsselung

Kn = Cnd mod N für n=1,2,3(,...)
K1 = 0017151373 mod 263713 = 230911
K2 = 1843041373 mod 263713 = 091605
K3 = 2199831373 mod 263713 = 040901

Signatur

Cn = Knd mod N
C1 = 2309111373 mod 263713 = 219611
C2 = 0916051373 mod 263713 = 121243
C3 = 0409011373 mod 263713 = 138570

Verifikation

Kn = Cne mod N
K1 = 2196111721 mod 263713 = 230911
K2 = 1212431721 mod 263713 = 091605
K3 = 1385701721 mod 263713 = 040901

Die Berechnung der modularen Exponentiation kann durch binäre Exponentiation (Square-and-multiply) beschleunigt werden.

Dabei wendet man nach jedem Rechenschritt auf die zu handhabenden Zahlen die Modulo-Operation „mod“ an, um die Zwischenergebnisse möglichst klein zu halten. Aus dem Klartext „7“ erhalten wir somit den Geheimtext „2“.

Programmierung

Das folgende Programm in der Programmiersprache C++ zeigt die Implementierung des RSA-Verfahrens mit , und , was den privaten Schlüssel ergibt. Das Programm gibt den verschlüsselten und den entschlüsselten Text (in diesem Beispiel Werde Mitglied bei Wikipedia!) auf der Konsole aus. 

#include <iostream>
using namespace std;

// berechnet aus dem öffentlichen Schlüssel e den privaten Schlüssel (das multiplikative Inverse von e modulo phi)
unsigned getPrivateKey(unsigned e, unsigned phi)
{
	unsigned a = phi, b = e;
	unsigned d = 0, u = 1;
	while (b != 0)
	{
		unsigned q = a / b;
		unsigned x = b; // Variable zum Zwischenspeichern
		b = a - q * b;
		a = x;
		x = u;
		u = d - q * u;
		d = x;
	}
	if (a > 1) {
		cout << "Fehler: e und phi nicht teilerfremd" << endl;
		exit(1);
	}
	return d;
}

// Diese Funktion berechnet die Potenz a ^ b modulo n
unsigned modularPower(unsigned a, unsigned b, unsigned n)
{
	unsigned res = (b & 1) ? a : 1;
	b >>= 1;
	while (b)
	{
		a = a * a % n;
		if (b & 1) res = res * a % n;
		b >>= 1;
	}
	return res;
}

// Diese Funktion ver- oder entschlüsselt den Klartext 'text' elementweise mit dem Schlüssel 'key'
void RSA(unsigned *text, int len, unsigned n, unsigned key)
{
	for (int i = 0; i < len; i++) // for-Schleife, die die Zeichen des Textes durchläuft
	{
		unsigned c = modularPower(text[i], key, n); // ver- bzw. entschlüsselt text[i]
		text[i] = c;
	}
}

int main()
{
	unsigned p = 223; // die Primzahlen p und q
	unsigned q = 127;
	unsigned n = p * q;
	unsigned e = 121; // Der öffentlichen Schlüssel
	unsigned phi = (p - 1) * (q - 1);
	unsigned d = getPrivateKey(e, phi); // Erzeugt den privaten Schlüssel

	const char *klartext = "Werde Mitglied bei Wikipedia!";
	unsigned text[100];
	int len = 0;
	while (klartext[len])
		text[len] = klartext[len], ++len;

	RSA(text, len, n, e); // Verschlüsseln
	// Ausgabe des verschlüsselten Texts auf der Konsole:
	for (int i=0 ; i < len ; ++i)
		cout << ' ' << text[i];
	cout << '\n';

	RSA(text, len, n, d); // Entschlüsseln
	// Ausgabe des Dechiffrats:
	for (int i=0 ; i < len ; ++i)
		cout << (char)text[i];
	cout << '\n';
}

Anwendung

Hybride Verfahren

Hybride Verschlüsselung

RSA ist im Vergleich zu Verfahren wie 3DES und AES mindestens um den Faktor 100 langsamer. In der Praxis wird RSA daher meist nur zum Austausch eines Schlüssels für die symmetrische Verschlüsselung benutzt. Für die Verschlüsselung der Daten werden dann symmetrische Verfahren eingesetzt. Damit sind die Vorteile beider Systeme vereint: einfacher Schlüsselaustausch und effiziente Verschlüsselung.

Anwendungsgebiete

Weblinks

Vorlage:Wikibooks

Abgerufen von „https://wiki.foxtom.de/index.php?title=Diskussion:RSA&oldid=99337“