RSA - Rivest, Shamir und Adleman

ELektronik-KOmpendium.de
Online

Preis auf Anfrage

Wichtige informationen

  • Kurs
  • Online
Beschreibung

RSA - Rivest, Shamir und Adleman RSA ist das ein asymmetrisches kryptografisches Verfahren bzw. ein Public-Key-Verfahren von den Kryptografen Ron Rivest, Adi Shamir und Leonard Adleman aus dem Jahr 1977. Kein anderes asymmetrisches Verfahren ist so vielseitig einsetzbar, so gut erforscht und so einfach zu implementieren, wie RSA. An RSA kommt man im Zusammenhang mit asymmetrischen Verfahren einfach nicht vorbei.
Im Vergleich zum Diffie-Hellman-Schlüsselaustausch eignet sich RSA auch für die Verschlüsselung und als Signaturverfahren. Der RSA-Algorithmus basiert auf dem Faktorisierungsproblem.

Wichtige informationen

Was lernen Sie in diesem Kurs?

Verschlüsselung
Sicherheit

Themenkreis

Wie funktioniert die RSA-Verschlüsselung?

Der RSA-Algorithmus beruht darauf, dass es mathematisch extrem schwierig ist, große Zahlen zu faktorisieren. Also aus dem Produkt zweier sehr großer Primzahlen die beiden Faktoren in annehmbarer Zeit zerlegen zu können (Faktorisierung). Bis heute ist kein Faktorisierungsverfahren bekannt, das die ganzzahligen Teiler einer Zahl effizient berechnen kann. Das bedeutet, dass ein enormer Rechenaufwand notwendig ist, um eine Zahl mit mehreren hundert Stellen zu faktorisieren. So lange diese Annahme richtig ist und keine Abkürzung entdeckt wird, gilt das RSA-Verfahren als sicher.

Man wählt also zwei zufällig Primzahlen p und q, die geheim bleiben müssen und von denen nur das Produkt aus einer Multiplikation bekannt ist.
Dann konstruiert man zwei Exponenten, die nach dem Prinzip der asymmetrischen Kryptografie als Schlüssel dienen. Einer davon ist „öffentlichen“ (d), der andere "privat" (e). Die Schlüssellänge ist hierbei variabel. Je länger der Schlüssel, desto sicherer das Verfahren.

Bei der Chiffrierung wird die Nachricht als Zahl m mit dem öffentlichen Schlüssel d und dem Produkt aus p und g zum Geheimtext c verschlüsselt:

c = md mod pq

Zur Entschlüsselung benötigt man e:

m = ce mod pq

Dabei lässt sich e nicht aus d berechnen, ohne die Primzahlen p und q zu kennen

Wieso die dieses Verfahren sicher ist soll das folgende vereinfachte Beispiel verdeutlichen: Bei der Verschlüsselung von Daten durch ein kryptografisch mathematisches Verfahren ist die Zahl "36" herausgekommen. Dabei handelt es sich um die verschlüsselten Daten (Geheimtext). Das Verfahren ist bekannt und sagt aus, dass diese Zahl das Produkt aus zwei Zahlen ist. Bestehend aus dem Schlüssel und dem Klartext. Ein Angreifer, der die "36" abgehört hat und sich auch in Kenntnis des Verschlüsselungsalgorithmus befindet, muss nur noch den verwendeten Schlüssel herausfinden, um an den Klartext zu kommen. Wenn der Schlüssel nicht bekannt ist, dann muss der Angreifer raten oder durchprobieren. Da das Faktorisieren nicht so einfach möglich ist, kann der Angreifer die Reihe der möglichen Schlüssel nicht ermitteln. Deshalb bleibt ihm nichts anderes übrig als alle nur denkbaren Schlüssel durchzuprobieren. Das macht er natürlich mit einem Computer, den er so lange rechnen lässt, bis er auf lesbare Daten stößt. Die folgende Liste zeigt beispielhaft die Kombination aus Schlüssel und Daten, die möglich sind, um auf das Ergebnis "36" zu kommen.

  • 1 x 36
  • 2 x 18
  • 3 x 12
  • 4 x 9
  • 5 x keine Ganzzahl
  • 6 x 6
  • 7 x keine Ganzzahl
  • 8 x keine Ganzzahl
  • 9 x 4
  • ... keine Ganzzahl
  • 12 x 3
  • ... keine Ganzzahl
  • 18 x 2
  • ... keine Ganzzahl
  • 36 x 1

In diesem Beispiel müsste der Angreifer unter Umständen 36 mal ausprobieren. Aus statistischer Sicht natürlich nur die Hälfte. Denn irgendwann hat der Angreifer die richtige Kombination gefunden, bevor er komplett durch ist. Nehmen wir an die ursprünglichen Daten wäre die "3" gewesen, dann hätte der Angreifer zwölf Versuche gebraucht. In diesem Beispiel geht das recht schnell. Doch wenn die Zahl groß genug ist, dann gibt es so viele Möglichkeiten, dass der Angreifer ewig lange ausprobieren müsste, um auf den richtigen Schlüssel zu kommen.
Um es für dem Angreifer praktisch unmöglich zu machen, muss man nur dafür sorgen, dass der Schlüssel lang genug ist. Dann ist auch die Zahl groß genug, dass aktuelle Computer ewig lange rechnen müssten, um die Daten durch ausprobieren zu entschlüsseln.
In der Regel sind alle guten Verschlüsselungsalgorithmen so konstruiert, dass die aktuelle Rechenleistung zu gering ist, um den richtigen Schlüssel durch Ausprobieren herauszufinden.

Weil der Versuch verschlüsselte Daten experimentell zu entschlüsseln zu lange dauert (vollständige Schlüsselsuche), versucht man den Algorithmus zu knacken. Knacken bedeutet, den Raum, den ein Schlüssel einnehmen kann so weit einzuschränken oder das Verfahren des Algorithmus so weit abzukürzen, dass sich die verschlüsselten Daten in erheblich kürzerer Zeit und mit weniger Aufwand entschlüsseln lassen.
Für die Faktorisierung hat man aber noch keine mathematische Lösung gefunden, die eine Abkürzung erlauben würde.

RSA als Signaturverfahren

RSA ist eigentlich ein asymmetrisches Verfahren, das in der Hauptsache zum Verschlüsseln und Schlüsselaustausch eingesetzt wird. Weil Signaturverfahren mit Public-Key-Verfahren zusammenhängen, kann man RSA auch als Signaturverfahren einsetzen.

  • Weitere Informationen zu digitale Signaturen mit RSA
Wie sicher ist RSA?

Der RSA-Algorithmus basiert darauf, dass es schwer ist, große Zahlen in ihre Primfaktoren zu zerlegen. Die vollständige Schlüsselsuche ist bei ausreichender Schlüssellänge von beispielsweise 256 Bit nahezu aussichtslos. Im Schnitt müsste der Angreifer 2255 bzw. 1076 Schlüssel durchprobieren. Das ist eindeutig zu viel, weil unser Universum nur 1018 Jahre alt ist. Wenn dem Angreifer nichts besseres als die vollständige Schlüsselsuche einfällt, dann ist RSA sicher.
Nun ist es aber so, dass die vollständige Schlüsselsuche nicht der beste Angriff ist. Viel gefährlicher ist der Faktorisierungsangriff, der darauf ausgelegt ist die Einwegfunktion umzukehren, was äußerst aufwendig ist. Trotzdem besteht Gefahr wenn die verwendeten Primzahlen zu klein sind.

RSA-Miterfinder Adi Shamir präsentierte 1999 mit TWINKLE und 2003 mit TWIRL zwei fiktive optisch-elektronische Maschinen, die mehrere hundert bzw. tausend PCs bei der Faktorisierung ersetzen könnten. Shamir geht davon aus, dass sich ein RSA-1024-Bit-Schlüssel innerhalb eines Jahres faktorisieren lässt. Die Kosten lägen bei mehreren Millionen Euro. Für staatlich finanziertes Militär und Geheimdienste wäre das nicht undenkbar.

Im Vergleich zu symmetrischen Verfahren bietet das asymmetrisch arbeitende RSA-Verfahren mehr Angriffsfläche für eine Angreifer. Beispielsweise sind die Zahlen, mit denen das Schlüsselpaar generiert wird frei wählbar. Das bedeutet, dass man als Anwender oder die Implementierung eine schlechte Wahl treffen kann, wodurch es für den Angreifer leichter wird.

Die Sicherheit von RSA hängt im wesentlichen von einer sauberen Implementierung und der Schwierigkeit der Faktorisierung eines Produkts zweier Primzahlen ab. Da die Schwierigkeit der Faktorisierung nicht so schwer ist, wie ursprünglich gedacht, hängt die Sicherheit von RSA auch von der Schlüssellänge ab.
Wenn das Verfahren richtig programmiert ist, dann bleibt dem Angreifer nur noch mit einem extrem hohen Aufwand den geheimen Schlüssel aus dem öffentlichen Schlüssel abzuleiten.
Eine Schlüssellänge von 512 Bit gilt für einen Geheimdienst wie die NSA (USA) als in kurzer Zeit knackbar. Es sind aber auch Faktorisierungsverfahren bekannt, die mit einem realistischen Aufwand einen Schlüssel von 1.024 Bit zerlegen. Von deren Nutzung wird allgemein abgeraten. Beispielsweise vom BSI, der NIST und der ENISA. Daher sollte ein Schlüsselpaar mindestens 2.048 Bit oder gleich besser 4.096 Bit aufweisen.

Doch so einfach ist das nicht. Die Sicherheit eines 1.024-Bit-Schlüssels in einem asymmetrischen verfahren entspricht lediglich einem 80 Bit Schlüssel bei einem symmetrischen Verfahren. Das ist recht nah, um mit vertretbarem Aufwand, an den Schlüssel zu kommen. Eine Verdopplung auf 2.048 Bit würde nur ein Niveau von 112 Bit bei symmetrischen Verfahren bringen. Um eine vergleichbare Sicherheit von mindestens 128 Bit zu erreichen, bräuchte man einen RSA-Schlüssel von 3.070 Bit. Für eine langfristige Sicherheit mit vergleichbaren 256 Bit müssten es 15.360 Bit sein.

Asymmetrische Verschlüsselung mit RSA hat das Problem, dass die erforderlichen Schlüssellängen sehr lang sind. Geht man von weiteren methodischen Durchbrüchen beim Lösen der Faktorisierung aus, dann muss die Schlüssellänge in Zukunft deutlich länger werden, damit RSA sicher bleibt. Diese Schlüssellängen sind bald nicht mehr handhabbar. Deshalb werden ECC-Verfahren mit elliptischen Kurven empfohlen, die mit kürzeren Schlüsseln auskommen.

  • Weitere Informationen zu ECC-Verfahren
Übersicht: Asymmetrische Kryptografie
  • Asymmetrische Kryptografie
  • Diffie-Hellman-Merkle-Schlüsselaustausch
  • Digitale Signatur
  • ECC - Elliptic Curve Cryptography (elliptische Kurven)
  • PGP - Pretty Good Privacy (OpenPGP)
Weitere verwandte Themen:
  • Kryptografie
  • Verschlüsselung
  • Digitale Schlüssel (Verschlüsselung)