Der RSA-Algorithmus in der Kryptografie: Rivest-Shamir-Adleman erklärt

RSA ist ein etablierter und sicherer kryptografischer Algorithmus zur Ver- und Entschlüsselung von Daten. Der Algorithmus ermöglicht die sichere Übertragung sensibler Daten über das Internet. Trotz bekannter Schwachstellen findet RSA weiterhin Anwendung, etwa bei digitalen Signaturen zur Authentifizierung von Nachrichtenquellen.

Dieser Artikel erklärt RSA, die Funktionsweise und die wichtigsten Anwendungen. Außerdem erläutert er Sicherheitslücken von RSA und Möglichkeiten zur Risikominderung.

Was ist RSA?

Bei Rivest Shamir Adleman (RSA) handelt es sich um einen bekannten Public-Key- bzw. asymmetrischen Verschlüsselungsalgorithmus. RSA schützt sensible Daten durch Ver- und Entschlüsselung mittels privatem und öffentlichem Schlüsselpaar.

RSA wurde 1977 von Ron Rivest, Adi Shamir und Leonard Adleman am Massachusetts Institute of Technology entwickelt und nach deren Initialen benannt.

RSA verwendet ein privates und öffentliches Schlüsselpaar. Der private Schlüssel bleibt geheim und ist nur dem Hersteller des Schlüsselpaars bekannt, während der öffentliche Schlüssel allen zugänglich ist. Zur Verschlüsselung dient wahlweise der öffentliche oder private Schlüssel, während der jeweils andere bei der Entschlüsselung zum Einsatz kommt.

Dies macht RSA zu einem der meistbenutzten Verschlüsselungsverfahren weltweit. Die rechnerische Komplexität von RSA führt allerdings zu vergleichsweise geringer Effizienz und hohem Ressourcenbedarf. Deshalb eignet sich RSA nicht zur Verschlüsselung großer Nachrichten oder Dateien.

(Lest unser Grundlagenwissen über AES, einen weiteren gängigen Verschlüsselungsstandard.)

Wie funktioniert RSA?

RSA basiert auf der Faktorisierung großer Ganzzahlen. Zunächst müsst ihr für das Schlüsselpaar zwei große, schwer zu faktorisierende Primzahlen wählen. Die Primzahlen müssen dafür zufällig gewählt werden und sich deutlich unterscheiden. Die beiden gewählten Primzahlen werden beispielsweise als p und q bezeichnet.

Der Algorithmus berechnet dann deren Produkt, bezeichnet als n = p * q. Die Werte p und q bleiben geheim, während n, das als Maßeinheit (Modulus) für die öffentlichen und privaten Schlüssel zum Einsatz kommt, öffentlich gemacht werden muss.

Anschließend wird die Carmichael-Funktion mit p und q berechnet und die Ganzzahl e als öffentlicher Exponent gewählt. Danach erfolgt die Berechnung von d als privater Exponent.

Wie erfolgen die Ver- und Entschlüsselung bei RSA?

Der öffentliche Schlüssel besteht aus dem Paar (n, e), der private aus (n, d).

• Verschlüsselung. Bei der Verschlüsselung einer Nachricht verwendet der Absender den öffentlichen Schlüssel (n, e) des Empfängers, um den Chiffretext zu berechnen, wobei der Chiffretext = m^e mod n ist. Dabei steht m für die Klartextnachricht.
• Entschlüsselung. Bei der Entschlüsselung einer mit RSA verschlüsselten Nachricht nutzt der Empfänger seinen privaten Schlüssel (n, d) zur Berechnung der Klartextnachricht nach der Formel: Klartext = c^d mod n.

Anwendungen und Einsatzgebiete von RSA

RSA findet Anwendung in diversen Bereichen der Informationssicherheit und Kryptografie. Zu den häufigsten Anwendungen zählen:

Digitale Signaturen

Bei der digitalen Signatur handelt es sich um eine Technik, mit der der Empfänger einer Nachricht deren Authentizität, Integrität und Unverfälschtheit überprüfen kann. Das beweist, dass die Nachricht während der Übertragung unverändert blieb.

Bei der Erstellung digitaler Signaturen erzeugt der Absender zunächst einen Hash-Wert der Nachricht mithilfe einer kryptografischen Hash-Funktion. Anschließend erfolgt die Signierung durch Anwendung des RSA-Algorithmus mit dem privaten Schlüssel, wodurch die digitale Signatur entsteht. Der Empfänger kann dann mit dem öffentlichen Schlüssel des Absenders den RSA-Algorithmus auf die digitale Signatur anwenden.

Zusätzlich lässt sich die Signatur durch Abgleich mit dem aus der Nachricht erzeugten Hash-Wert verifizieren.

Digitale Zertifikate

Das RSA-Verfahren findet breite Anwendung in digitalen Zertifikaten wie SSL-Zertifikaten. Diese Zertifikate dienen der Identitätsprüfung von Personen oder Organisationen hinter Websites.

Digitale Zertifikate nutzen RSA zur Verschlüsselung der digitalen Signatur des Zertifikatausstellers, die sich mit dessen öffentlichem Schlüssel prüfen lässt. Das digitale Zertifikat enthält Informationen wie Domainnamen und die Organisation hinter der Website. Es belegt deren Identität gegenüber den Nutzern.

Sichere Kommunikationsprotokolle

RSA verschlüsselt die Kommunikation zwischen zwei Parteien über unsichere Netzwerke wie das Internet. RSA kommt beispielsweise mit Transport Layer Security (TLS) für sichere Verbindungen zwischen Webservern und Browsern zum Einsatz. RSA unterstützt zudem die sichere E-Mail-Kommunikation durch Ver- und Entschlüsselung von Nachrichten.

Das Verfahren kommt auch in virtuellen privaten Netzwerken (VPNs) zum Einsatz. VPNs nutzen TLS für den Handshake zwischen zwei kommunizierenden Parteien, die Informationen austauschen. Der TLS-Handshake verwendet den RSA-Algorithmus zur Authentifizierung beider beteiligten Parteien.

Sicherer Schlüsselaustausch

Ein weiterer Anwendungsfall von RSA ist der sichere Schlüsselaustausch zwischen zwei Parteien, die zuvor keinen geheimen Schlüssel ausgetauscht haben. Die beteiligten Parteien erzeugen ein Paar aus öffentlichem und privatem Schlüssel mittels RSA-Algorithmus.

• Der Sender erzeugt einen symmetrischen Schlüssel, verschlüsselt ihn mit dem öffentlichen Schlüssel des Empfängers und sendet den verschlüsselten Schlüssel an den Empfänger.
• Der Empfänger entschlüsselt ihn anschließend mit seinem privaten Schlüssel.

Sender und Empfänger verfügen dann über denselben symmetrischen Schlüssel für die sichere Kommunikation.

Sicherheitslücken beim RSA-Algorithmus

Der RSA-Algorithmus lässt sich bei Einhaltung der Empfehlungen nur schwer knacken. In den letzten Jahren wurden jedoch mehrere RSA-Schwachstellen entdeckt. Diese Schwachstellen sind:

Seitenkanalangriffe

Seitenkanalangriffe zielen auf Schwachstellen bei der Datenverarbeitung eines Computersystems (wie Programmausführungszeit, Stromverbrauch und elektromagnetische Abstrahlung) statt direkt auf Software oder Code.

Ein Angreifer kann beispielsweise Informationen aus der elektromagnetischen Strahlung eines Computers während kryptografischer Operationen gewinnen.

Energieanalyse und Timing-Angriffe zählen zu den häufigsten Seitenkanalangriffen auf RSA-Verschlüsselung:

• Energieanalyse-Angriffe entstehen durch rechenintensive RSA-Operationen mit variablem Stromverbrauch.
• Bei Timing-Angriffen messen Angreifer die Dauer von RSA-Verschlüsselungsoperationen.

Angreifer können aus diesen Daten den geheimen RSA-Schlüssel ableiten. Deshalb sollten geeignete Maßnahmen gegen Seitenkanalangriffe eingeleitet werden.

Unzureichende Schlüssellänge

Die Sicherheit des RSA-Algorithmus basiert im Wesentlichen auf großen, schwer zu faktorisierenden Primzahlen für die Schlüsselerzeugung. Die Faktorisierung des Produkts zweier großer Primzahlen gestaltet sich mit zunehmender Schlüssellänge schwieriger.

Die Schlüssellänge sollte mit steigender Rechenleistung zunehmen. Leistungsstarke Computer können große Zahlen relativ leicht und schnell faktorisieren. Dadurch gelingt es, kürzere Schlüssel schneller zu knacken.

Der früher empfohlene 1024-Bit-RSA-Schlüssel gilt heute als unsicher und ist nicht mehr gültig. Daher ist es am besten, eine Schlüssellänge von mindestens 2048 Bit für RSA zu verwenden.

Schwachstellen bei Primzahlen

Bei Primzahlschwächen unterscheidet man zwischen Zufälligkeit und Nähe.

Die Zufälligkeit von Primzahlen. Der RSA-Algorithmus hängt von der Erzeugung zufälliger Primzahlen bei der Schlüsselgenerierung ab. Diese werden dann multipliziert, um den öffentlichen und den privaten Schlüssel zu erzeugen.

Angenommen, die Organisation verwendet einen schwachen Zufallszahlengenerator oder einen Algorithmus, der leicht vorhersehbare oder leicht zu beeinflussende Zufallszahlen erzeugt. In diesem Fall können Angreifer das Muster der Primzahlerzeugung erraten und die Schlüssel leicht faktorisieren.

Die Nähe von Primzahlen. Die Sicherheit des RSA-Schlüssels gerät auch in Gefahr, wenn die beiden verwendeten Primzahlen zu nahe beieinanderliegen oder eine zu klein ist. In solchen Fällen können Angreifer die Faktoren des RSA-Modulus leicht bestimmen, die Verschlüsselung knacken und an den privaten Schlüssel herankommen.

Verlorene oder gestohlene Schlüssel

Verlorene, gestohlene oder kompromittierte Schlüssel ermöglichen Angreifern direkten Zugriff und das Entschlüsseln von Nachrichten mit dem zugehörigen öffentlichen Schlüssel. Deshalb müssen Schlüssel sorgfältig verwaltet werden, um solche Schwachstellen zu vermeiden.

Störungsbasierte Angriffe

Bei Störungsangriffen handelt es sich um Attacken, bei denen Angreifer absichtlich die Hardware oder Software stören, die zur Implementierung der kryptografischen Anwendung dient. Ein Angreifer kann beispielsweise einen Laser-Fehlerinjektionsangriff oder einen gezielt herbeigeführten Bit-Flip verwenden, um Fehler in kryptografischen Funktionen zu verursachen. Dadurch können schwächere Schlüssel mit vorhersehbaren Werten entstehen, was die Sicherheit des Systems beeinträchtigt.

RSA-Implementierungen können für Störungsangriffe anfällig sein, falls es keine geeigneten Gegenmaßnahmen gibt.

Vermeidung von RSA-Schwachstellen

Zur Abschwächung von RSA-Schwachstellen stehen mehrere Möglichkeiten zur Verfügung.

• Verwendet einen starken Primzahlgenerator. Das stellt sicher, dass die Primzahlen nicht vorhersehbar sind und von Angreifern nicht leicht erraten werden können.
• Vermeidet es, schwache Primzahlen wie kleine Primzahlen oder Primzahlen, die zu nah beieinanderliegen, zu verwenden.
• Der RSA-Schlüssel sollte eine Mindestlänge von 2048 Bit aufweisen.
• Zum Schutz vor störungsbasierten Angriffen sind geeignete Maßnahmen erforderlich, beispielsweise die Verwendung manipulationssicherer Hardware.
• RSA-Schlüssel erfordern eine angemessene Verwaltung und Sicherung durch Techniken wie regelmäßige Schlüsselrotation und unterschiedliche Schlüssel für verschiedene Anwendungen.
• Haltet den RSA-Algorithmus durch die regelmäßige Überprüfung auf Schwachstellen und Updates aktuell.

RSA im Überblick

RSA ist ein weitverbreiteter kryptografischer Algorithmus, der 1977 eingeführt wurde. Der Algorithmus verwendet öffentliche und private Schlüsselpaare zur Ver- und Entschlüsselung von Daten. Obwohl RSA in verschiedenen Anwendungen zum Einsatz kommen kann, eignet er sich aufgrund seiner rechnerischen Komplexität nicht für die Verschlüsselung großer Nachrichten oder Dateien. RSA erzeugt digitale Signaturen und Zertifikate für sichere Authentifizierung, Kommunikation, Webzugriff, E-Mail-Nachrichten und Schlüsselaustausch.

RSA weist verschiedene Schwachstellen auf, darunter Seitenkanalangriffe, ungeeignete Schlüssellängen, Schwächen bei Primzahlen, störungsbasierte Angriffe und Risiken durch gestohlene oder verlorene Schlüssel. Bei der Verwendung von RSA für kryptografische Anwendungen müsst ihr die beschriebenen Empfehlungen berücksichtigen.