Neue Technologie beschleunigt das Faktorisieren enorm – Bedrohung für RSA-Verschlüsselung?


Die RSA-Verschlüsselung benötigt zwei verschiedene Schlüssel, damit Nachrichten signiert bzw. verschlüsselt werden können. Die beiden Schlüssel, privater und öffentlicher Schlüssel, bestehen, bei dem RSA20148, aus einer 2048bit langen Zahl und dem RSA-Modul. Um diese Schlüssel zu erzeugen benötigt man zwei Primzahlen und genau diese bieten einen Angriffsvektor, denn eine neue Technologie lässt eine Faktorisierung deutlich schneller geschehen.

Die RSA-Verschlüsselung

Arbeiten Sie täglich mit E-Mails? Wenn dem so ist, haben Sie täglich etwas mit der RSA-Verschlüsselung zu tun. Diese Verschlüsselung schauen wir uns nun etwas genauer an und versuchen den Angriffsvektor zu verstehen, der durch eine neue Technologie deutlich gefährlicher wird.


Deep Dive ins Darknet – Suchmaschinen, Browser und Nutzen!

Jetzt kostenfrei zum Webinar anmelden und am 29.01.2021 von 10:00 – 10:30 Uhr teilnehmen.



Öffentlicher und Privater Schlüssel

Um mit der RSA-Verschlüsselung Nachrichten zu signieren bzw. verschlüsseln zu können, benötigen wir den privaten und den öffentlichen Schlüssel. Beide Schlüssel bestehen jeweils aus dem sogenannten RSA-Modul, welches bei beiden Schlüsseln gleich ist und der Verschlüsselungs- bzw. Entschlüsselungsexponente. Der öffentliche Schlüssel ist nicht geheim. Das bedeutet das er öffentlich z.B. auf einem Schlüsselserver zu finden ist. Es ist lediglich wichtig, dass ein öffentlicher Schlüssel genau einer Person zuzuordnen ist, da andernfalls andere Personen Nachrichten mit Ihrem Namen signieren könnten.

Der private Schlüssel dagegen sollte geheim bleiben. Jeder der den privaten Schlüssel kennt, kann die Geheimtexte entschlüsseln und mitlesen. Zudem ist eine Signatur nur dann einzigartig, wenn der private Schlüssel nicht in fremde Hände gerät. Der genaue Prozess zur Erstellung der Schlüssel ist aufwändig. Für einen Überblick reicht jedoch unsere Zusammenfassung.

Ein Überblick über die RSA-Verschlüsselung

Als Sender wird die Formel:   c = m^e mod(N) benutzt. Dies bedeutet, dass jede Zeichen meiner Nachricht m, mit der Verschlüsselungskomponente des Empfängers faktorisiere. Die Verschlüsselungskomponente liegt im öffentlichen Schlüssel, sodass jeder eine Nachricht für den Empfänger verschlüsseln kann. Nachdem das Zeichen faktorisiert wurde, wird es mit dem ebenfalls öffentlich liegenden N, dem RSA-Modul, modulo geteilt. Das Ergebnis dieser Rechnung ist das c, das sogenannte Chiffrat.

Beispiel: Wir möchten das Zeichen 6 verschlüsseln. Der öffentliche Schlüssel des Empfängers lautet (N=143, e=23).

               128 = 6^23 mod(143)

Die Nachricht die wir unserem Empfänger senden lautet 128, diese Zahl stellt das Chiffrat zu der oben genannten Nachricht mit dem öffentlichen Schlüssel (143, 23) dar.

Die Entschlüsselung der RSA-Verschlüsselung

Als Empfänger erhalten wir die Nachricht 128. Diese Nachricht wurde mit unserem öffentlichen Schlüssel verschlüsselt, sodass wir sie mit unserem privaten Schlüssel (N=143, d=47) entschlüsseln können.

6 = 128^47 mod(143)

Als Ergebnis erhalten wir das Zeichen 6 und haben somit eine Nachricht ver- und entschlüsselt. Wenn niemand außer mir den privaten Schlüssel kennt, kann das Chiffrat nur mit erheblichen Aufwand entschlüsselt werden.

Eine wesentliche Komponente – die Zeit

In der Realität werden wichtige Dokumente mit einem möglichst großen Schlüssel verschlüsselt, damit der Angreifer nicht per Brute-Force-Angriff den Schlüssel erraten kann. Häufig verwendet wird die RSA-Verschlüsselung in der ein Schlüssel aus einer 2048bit großen Zahl besteht. Im Dezimalraum entspricht die höchste Zahl einer 617 stelligen Zahl.

Da wir während der Ver- und Entschlüsselung mit unserem Schlüssel potenzieren, kommt es zu einem großen Rechenlast. Bislang werden in Quantencomputer die sogenannten Qubits verwendet. Ein Qubit ist ein System innerhalb des Quantencomputers, welches nur zwei Zustände annehmen kann. Eine 2048bit große Zahl in ihre einzelnen Primzahlen zu zerlegen (faktorisieren) ist praktisch nicht durchführbar, da die Rechenlast aktuell noch nicht bearbeitet werden konnte.

Doch mit einer neuen Technologie, ist die Qubit-Anzahl die für solch eine Zerlegung notwendig ist von ca. 1 Milliarde auf lediglich 2 Millionen gesunken. Das bedeutet, dass es weniger Ressourcen in Form von Qubits braucht um eine Faktorisierung durchzuführen. Dementsprechend sinkt auch die Dauer, denn es sind nun mehr Ressourcen vorhanden. Die aktuelle Dauer beträgt ca. 8h um eine 2048bit lange Zahl zu faktorisieren.

Bedeutung für die IT-Sicherheit

Das RSA-Modul setzt sich aus der Multiplikation zweier Primzahlen zusammen. Dieses Modul liegt öffentlich, da es ein Bestandteil des öffentlichen Schlüssels ist. Sowohl die Entschlüsselungs- als auch die Verschlüsselungsexponente hängen von den beiden Primzahlen ab, sodass Fremde keine Informationen über die beiden gewählten Primzahlen haben sollten. Dadurch dass es nun nur noch 8h dauert eine 2048bit lange Zahl zu faktorisieren erhält der Angreifer eine Liste von möglichen Primzahlen, die Sie verwendet haben könnten und kann somit einen Brute-Force-Angriff starten. Die Bundesnetzagentur empfiehlt bei der Verwendung der RSA-Verschlüsselung bis 2022 eine 2000bit lange Zahl. Es wird jedoch zukünftig eine Schlüssellänge von 3000bit verpflichtet, damit die Sicherheitsrisiken der Primzahlzerlegung minimiert werden.


Exkurs – Was ist Verschlüsselung?

Heutzutage liest man im Internet viel über „sicher Kommunikation“, Datenschutz und Privatsphäre. Im selben Atemzug wird von den selben Autoren von Verschlüsselung geschrieben. Aber was ist  eigentlich Verschlüsslung und was kann ich mir darunter Vorstellen?

Warum soll ich verschlüsseln?

Heute läuft der größte Teil aller Kommunikation über das Internet. Der größte Teil dieser Kommunikationen wird mittlerweile verschlüsselt übertragen. Um sich Verschlüsselung nun etwas bildlicher vorstellen zu können, versetzen wir uns einmal in unsere Schulzeit zurück. Wer hat damals nicht mal ein Zettelchen geschrieben und es quer durch den Klassenraum an einen Klassenkameraden oder eine Klassenkameradin geben lassen?

Wenn wir nun einen Zettel an das andere Ende Klasse durchreichen lassen, wandert dieser durch eine menge Hände. Ganz ähnlich sieht es auch im Internet eine E-Mail wird auf ihrem Weg ebenfalls von vielen Router und Switches weitergeleitet bis sie an ihrem Ziel ankommt. Bei unserem unverschlüsselten Zettel, kann man sich gut vorstellen, dass jeder der diesen Zettel in der Hand hat diesen auch öffnen und lesen kann. Im Internet ist dies ebenso möglich, jeder Server und Router auf dem Weg einer E-Mail kann diese unverschlüsselte Nachricht mitlesen. Unangenehm wird es nun, wenn es eine vertrauliche Nachricht wie die Frage „Willst du mit mir gehen?“ war.

Ohne Verschlüsselung
Kommunikation ohne Verschlüsselung Quelle: Eigen

Mit einer Verschlüsselung wäre dieses Schlamassel nicht passiert. Eine Verschlüsselung hätte dafür gesorgt, dass nur man selbst und der/die Kommunikationspartner*in die Nachricht lesen kann. Es kann noch immer jeder das Zettelchen öffnen und sehen, dass etwas darin steht, aber dank der Verschlüsselung kann keiner irgendwelche Informationen daraus ziehen und sieht nur Kauderwelsch.

Arten der Verschlüsselung

Eine der ersten Verschlüsselungen (auch Chiffren genannt) war die sogenannte Cäsar-Chiffre. Wie der Name auch schon vermuten lässt hat Julius Cäsar diese seiner Zeit schon verwendet. Dabei wurde das Alphabet nur um eine bestimmte Anzahl an Stellen verschoben. Diese Anzahl an Stellen ist der sogenannte Schlüssel. Diese ist heute natürlich nicht mehr sicher. Versuchen Sie einfach mal folgenden Satz zu dechiffrieren „IJW JWXYJ MFHP BFW JWKTQLWJNHM!“. Die Auflösung gibt es am Ende dieses Artikels. (Kleiner Tipp: Groß- und Kleinschreibung ist irrelevant und wenn ein Z um zwei Stellen verschoben wir, wird es ein B)

Heute wird die Verschlüsselung in zwei Arten aufgeteilt zum einen, in symmetrische und zum anderen in asymmetrische Verschlüsselungen. Der Hauptunterschied zwischen diesen beiden Arten liegt darin, wie mit dem Schlüssel umgegangen wird der zum Verschlüsseln bzw. zum Entschlüsseln benötigt wird. Die bekanntesten symmetrischen Verschlüsselungen sind AES und Blowfish und die bekanntesten asymmetrischen Verschlüsselungen sind RSA, und der Diffie-Hellman-Schlüsselaustausch. Wer sich mit den Protokollen an sich gern näher beschäftigen möchten, dem sei Cryptool2 empfohlen. Dort sind diese sehr verständlich und visuell dargestellt.

Symmetrische Verschlüsslung

Die Symmetrische Verschlüsselung ist die „klassische“ Art der Verschlüsselung. Hier haben die beiden Kommunikationspartner A (auch Alice genannt) und B (auch Bob genannt) beide den gleichen Schlüssel. Bei der oben genannten Cäsar-Chiffre wissen Alice und Bob, dass sie das Alphabet um 12 Zeichen verschoben haben. Da beide Seiten den gleichen Schlüssel haben, können sie nun so viele Nachrichten ver- und entschlüsseln wie sie möchten. Oskar (Der Gegenspieler oder auch Opponent) kann die Nachrichten ohne den Schlüssel zu kennen nicht entschlüsseln. Das Problem an der ganzen Sache ist nur, dass der Schlüssel auf eine sichere Art und Weise zwischen den Kommunikationspartnern ausgetauscht werden muss. Dies ist gerade in Zeiten des Internets kein leichtes Problem. Zu Zeiten des ersten und zweiten Weltkriegs wurden beispielsweise jedem Funker Schlüsselbücher mitgegeben. Wenn diese aufgebraucht waren konnte nicht mehr sicher kommuniziert werden.

Kommunikation mit Verschlüsselung
Kommunikation mit Verschlüsselung Quelle: Eigen

Asymmetrische Verschlüsselung

Es ist sehr umständlich jedes mal wenn wir eine Whatsapp-Nachricht versenden oder eine Webseite aufrufen möchte einen Brief oder eine CD zu verschicken, auf der sich der Schlüssel befindet. Dafür wurden Asymmetrische Verschlüsselungen entwickelt. Das besondere hier ist, dass Alice und Bob unterschiedliche Schlüssel haben. Damit das ganze funktioniert haben beide einen privaten und einen öffentlichen Schlüssel. Wie die Namen schon sagen , ist der private Schlüssel nur den Eigentümern bekannt und der öffentliche Schlüssel ist jedem bekannt.

Bildlich kann man sich das jetzt so vorstellen, als wäre der öffentliche Schlüssel ein Briefkasten. Der private Schlüssel der passende Briefkastenschlüssel. Wenn Alice Bob eine Nachricht zukommen lassen möchte, kann sie diese in den Briefkasten von Bob werfen. Bob kann jetzt seinen Briefkastenschlüssel nutzen um seinen Briefkasten zu öffnen und die Nachricht lesen.

Die öffentlichen Schlüssel kann man sich also ohne Probleme über das Internet zuschicken. Das einzige Problem hier ist, dass jede Art einer asymmetrischen Verschlüsselung anfällig für einen sogenannten „Man-in-the-Middle“-Angriff ist. Das heißt, dass Oskar, unser Angreifer, auf seinen Briefkasten einfach Bob schreibt und Alice vorgaukelt, dass dieser Bob gehören würde. Jetzt wirft Alice versehentlich Ihren an Bob andressierten Brief in Oskars Briefkasten. Für den Briefkasten hat Oskar seinen eigenen Schlüssel und kann so die Nachricht von Alice lesen, die an Bob gerichtet war. Dieses Problem wird aber mithilfe von Zertifikaten gelöst, die  zum Beispiel bestätigen, das der Briefkasten mit der Aufschrift Bob auch wirklich Bob gehört.

Eine andere häufige Anwendung für asymmetrische Verschlüsselung ist, dass sie dafür benutzt wird den Schlüssel für die symmetrische Verschlüsselung auf eine sichere Art und Weise auszutauschen. Im Prinzip die CD im Briefkasten auf digitale Art und Weise.




Asymmetrische Verschlüsselung
Asymmetrische Verschlüsselung Quelle: Eigen

Zuletzt ist hier noch die Lösung der Cäsar-Chiffre: „DER ERSTE HACK WAR ERFOLGREICH!“. Diese Chiffre wurde mit dem Schlüssel 5 erstellt. Alle Buchstaben des deutschen Alphabets wurden also um 5 Stellen nach Links verschoben und so wurde aus einem D ein I und einem E ein J.


Sevencast – der IT-Security Podcast

Von unterwegs, im Büro oder zu Hause hören und auf dem aktuellen Stand bleiben!

Sevencast bei Spotify
Sevencast bei Apple Podcast
Sevencast bei Overcast


Schreibe einen Kommentar