Die RSA-Verschlüsselung ist das Rückgrat einer sicheren Internetkommunikation. Es handelt sich um eine Art Public-Key-Kryptographie, die E-Mails, digitale Transaktionen und sensible Daten schützt, die über Netzwerke fließen. Der Algorithmus ist nach seinen Erfindern benannt: Ronald L. Rivest, Adi Shamir und Leonard M. Adleman. Sie entwickelten das System während ihrer Lehrtätigkeit am Massachusetts Institute of Technology.
Die Sicherheit von RSA beruht auf einer einfachen mathematischen Hürde, die leicht zu erstellen, aber kaum rückgängig zu machen ist. Ein Benutzer beginnt mit der Auswahl zweier großer Primzahlen, p und q. Diese Zahlen sind so groß, dass es trivial ist, sie zu multiplizieren, um n zu erhalten, aber n wieder in p und q zu faktorisieren, ist rechnerisch unerschwinglich.
Stellen Sie sich das so vor: Die Multiplikation zweier großer Zahlen dauert den Bruchteil einer Sekunde. Versuchen Sie herauszufinden, welche zwei Zahlen multipliziert wurden, um dieses Ergebnis zu erhalten? Mit der aktuellen Technologie könnte das Milliarden von Jahren dauern.
Ab 2015 erfordern die Sicherheitsstandards der US-Regierung, dass der Modulus n mindestens 2.048 Bit beträgt. Dezimal ausgedrückt bedeutet dies, dass p und q jeweils etwa 308 Ziffern haben, was eine 617-stellige Zahl für n ergibt. Die größten Zahlen, die wir erfolgreich faktorisiert haben, sind nur halb so groß. Die Schwierigkeit der Faktorisierung verdoppelt sich ungefähr für jede weitere drei Ziffer im Modul. Dieses exponentielle Wachstum der Komplexität stellt sicher, dass 617-stellige Schlüssel jahrzehntelang vor Brute-Force-Angriffen geschützt bleiben.
Die Mechanismen der Schlüsselgenerierung
Sobald p und q ausgewählt sind, generiert das System einen öffentlichen und einen privaten Schlüssel. Der Benutzer wählt eine Ganzzahl e kleiner als n. Diese Zahl muss teilerfremd zum Produkt aus (p – 1) und (q – 1) sein. Im Klartext hat e außer 1 keine gemeinsamen Faktoren mit diesem Produkt.
Diese spezielle Wahl garantiert die Existenz einer anderen Zahl d. Wenn Sie e mit d multiplizieren und durch das kleinste gemeinsame Vielfache von (p – 1) und (q – 1) dividieren, ist der Rest 1.
d zu finden ist einfach, wenn Sie p und q kennen. Der euklidische Algorithmus berechnet es in wenigen Augenblicken. Wenn Sie jedoch p und q nicht kennen, ist das Finden von d aus e genauso schwierig wie das Faktorisieren von n. Dieses Problem ist die gesamte Grundlage der Kryptosicherheit von RSA.
Die Sicherheit von RSA ist keine Zauberei; es ist Mathe. Konkret geht es um die Asymmetrie zwischen einfacher Multiplikation und unmöglicher Faktorisierung.
Öffentliche Schlüssel vs. private Schlüssel
Die Bezeichnungen d und e beschreiben Funktionen, keine strengen Rollen. Die Schlüssel sind austauschbar. Diese Flexibilität ermöglicht es RSA, zwei unterschiedliche Zwecke zu erfüllen: Geheimhaltung und Authentifizierung.
Um einen Geheimhaltungskanal zu erstellen, veröffentlicht Benutzer A e und n in einem öffentlichen Verzeichnis. Benutzer A hält d geheim. Wenn jemand eine private Nachricht an A senden möchte, wandelt er die Nachricht in Zahlen kleiner als n um und verschlüsselt sie mit e und n. Nur A kann es entschlüsseln, da nur A d enthält. Die Annahme – und starke Beweise – besagen, dass niemand sonst die Nachricht entschlüsseln kann, ohne n zu faktorisieren.
Die Authentifizierung funktioniert anders. Benutzer A veröffentlicht d und n und hält e geheim. Benutzer B möchte bestätigen, dass er mit A spricht. B sendet eine Challenge-Nachricht an A. Wenn A die verschlüsselte Version mit e zurückgibt, kann B sie mit dem öffentlichen d entschlüsseln. Wenn die entschlüsselte Nachricht der Herausforderung entspricht, weiß B, dass der Absender e besitzt. Da nur A e hat, ist die Identität verifiziert.
Digitale Signaturen und Hashing
Das digitale Signieren erhöht die Komplexität. Es erfordert eine kryptosichere Hashing-Funktion. Dies ist eine öffentliche Funktion, die jede Nachricht in einen kleineren Digest komprimiert. Jedes Bit des Digests hängt von jedem Bit der ursprünglichen Nachricht ab. Wenn Sie ein Bit in der ursprünglichen Nachricht ändern, wird etwa die Hälfte der Bits im Digest umgedreht.
Ein kryptosicherer Hash macht es rechnerisch unmöglich, eine Nachricht zu finden, die einen bestimmten vorab zugewiesenen Digest erzeugt. Es macht es außerdem schwierig, eine andere Nachricht mit demselben Digest wie eine bekannte zu finden.
Um eine Nachricht zu signieren, verschlüsselt A den Digest mit seinem geheimen e und hängt ihn an die Nachricht an. Die Nachricht selbst muss nicht geheim sein. Jeder kann den öffentlichen Schlüssel d von A verwenden, um die Signatur zu entschlüsseln und den Digest wiederherzustellen. Anschließend berechnen sie selbstständig den Digest der empfangenen Nachricht. Wenn die beiden Digests übereinstimmen, ist die Signatur gültig. Nur A hätte den Digest verschlüsseln können, da nur A e kennt.
Die hybride Realität
Diese Sicherheit ist mit Kosten verbunden. Die asymmetrische Verschlüsselung erfordert deutlich mehr Rechenaufwand als die symmetrische (Einzelschlüssel-)Verschlüsselung. Dieser hohe Verarbeitungsbedarf verringert den Durchsatz drastisch. Seit etwa 20 Jahren erreichen Ein-Schlüssel-Algorithmen bei vergleichbaren Sicherheitsstufen einen 1.000- bis 10.000-mal höheren Durchsatz als Zwei-Schlüssel-Algorithmen.
Da RSA langsam ist, wird es selten zur direkten Verschlüsselung großer Datenmengen verwendet. Stattdessen treibt es Hybridsysteme an. RSA übernimmt die schwere Arbeit der Authentifizierung und digitalen Signaturen. Außerdem wird ein zufällig generierter Sitzungsschlüssel sicher ausgetauscht. Sobald dieser Schlüssel geteilt wird, wechselt das System zu einem Einzelschlüsselalgorithmus für die Hochgeschwindigkeitsübertragung der tatsächlichen Daten. Wenn die Sitzung endet, wird der Schlüssel verworfen.
Diese Kombination bietet uns das Beste aus beiden Welten. Für den Großteil unserer Daten erhalten wir den sicheren Schlüsselaustausch der Public-Key-Kryptografie mit der Geschwindigkeit der symmetrischen Verschlüsselung.
Die Rechnung hält. Die Schlüssel bleiben sicher. Doch mit zunehmender Rechenleistung verschiebt sich die Definition von „groß“. Was heute unzerbrechlich ist, könnte morgen lösbar sein. Wir bauen immer größere Primzahlen. Wir hoffen weiterhin, dass die Kluft zwischen einfacher Multiplikation und harter Faktorisierung groß genug bleibt, um unser digitales Leben zu schützen.
