Gemeinsame Faktoren als Schwachstelle: Wie Common Factor Attacks RSA-Schlüssel knacken können

Die RSA-Verschlüsselung gilt seit Jahrzehnten als fundamentale Methode, um digitale Kommunikation zu sichern. Grundlage dieser Methode ist die Zerlegung großer Zahlen in ihre Primfaktoren – eine Aufgabe, die äußerst schwer zu lösen ist, während die Multiplikation zweier Primzahlen dagegen sehr einfach ist. Genau in diesem Unterschied liegt die Sicherheit der RSA-Verschlüsselung. Doch moderne Forschungen zeigten, dass trotz starker mathematischer Grundlagen Schwachstellen entstehen können, wenn bei der Schlüsselgenerierung Fehler in der Zufallszahlenerzeugung gemacht werden. Ein solcher Fehler kann dazu führen, dass unterschiedliche Schlüssel unabsichtlich gemeinsame Primfaktoren verwenden, was eine einfache Attacke auf diese Schwäche ermöglicht – bekannt als Common Factor Attack oder Angriff über gemeinsame Faktoren.

Um das Problem zu verstehen, lohnt sich zunächst ein Blick auf die Grundprinzipien von RSA. Bei dieser Methode wird ein Schlüsselpaar erzeugt, bestehend aus einem öffentlichen und einem privaten Schlüssel. Der öffentliche Schlüssel besteht im Wesentlichen aus der Zahl n, die das Produkt zweier großer Primzahlen p und q ist, sowie einer Verschlüsselungsexponente e. Die Sicherheit beruht auf der Tatsache, dass es extrem schwierig ist, n in seine Primfaktoren p und q zu zerlegen, wenn n sehr groß ist – beispielsweise 1024 Bit oder mehr. Der private Schlüssel enthält neben p und q die Entschlüsselungsexponente d, die nur mit Kenntnis der Primfaktoren berechnet werden kann.

Die Schwierigkeit der Faktorisierung großer Zahlen ist keine bloße Spekulation, sondern ein gut untersuchtes Problem in der Zahlentheorie und Informatik. Das Zerlegen einer 1024-Bit-Zahl in ihre Primfaktoren erfordert je nach verfügbarem Know-how und Rechenleistung Jahre, Jahrzehnte oder sogar länger. Dennoch zeigte sich in der Praxis, dass manche Schlüssel leichter zu knacken sind. Hier spielt die Qualität der Zufallszahlengeneratoren eine entscheidende Rolle. Sind diese schlecht implementiert oder nicht richtig mit genügend entropiereichen Quellen initialisiert, kann es vorkommen, dass zwei unterschiedlich erscheinende Schlüssel dennoch eine Primzahl gemeinsam haben.

Warum ist das gefährlich? Das liegt am mathematischen Konzept des größten gemeinsamen Teilers, kurz gcd (greatest common divisor). Der größte gemeinsame Teiler zweier Zahlen ist der größte Wert, durch den beide Zahlen ohne Rest teilbar sind. Für zwei Schlüssel n1 = p × q und n2 = r × s, bei denen keinerlei Primfaktoren geteilt werden, ist der gcd gewöhnlich 1. Findet sich jedoch ein gemeinsamer Primfaktor, etwa p = r, ergibt der gcd den Wert dieses Primfaktors – und dieser Wert kann dann zur Faktorisierung beider Schlüssel verwendet werden. So wird aus einer enorm schwer zu knackenden Aufgabe eine sehr einfache.

Der große Vorteil von gcd gegenüber klassischer Faktorisierung ist die Rechenzeit. Während die Faktorisierung großer Zahlen eine hochkomplexe Aufgabe ist, kann der gcd über den sogenannten Euklidischen Algorithmus in Bruchteilen von Sekunden auch bei riesigen Zahlen berechnet werden. Dieser Algorithmus basiert auf der wiederholten Division mit Rest und bietet eine elegante, uralte Methode, um aus zwei Zahlen deren größten gemeinsamen Teiler zu ermitteln. Gerade diese Effizienz macht Common Factor Attacks so praktisch: Man kann relativ einfach viele Schlüsselpaare vergleichen, um Schwachstellen aufzudecken. Die reale Relevanz dieses Problems zeigte sich im Februar 2012, als Forschergruppen um Arjen Lenstra und Nadia Heninger unabhängig voneinander eine erschreckende Entdeckung machten.

Sie fanden heraus, dass bei Millionen von im Internet eingebetteten RSA-Schlüsseln gemeinsame Primfaktoren auftauchen. Die Ursache waren oftmals fehlerhafte oder unzureichend gesicherte Zufallszahlengeneratoren auf verschiedenen Netzwerkgeräten und Servern. Spannend war, dass diese Geräte oft Hardware wie Firewalls, Router, VPN-Endpunkte oder sogar Projektoren und VoIP-Telefone betrafen, die bei der Erzeugung ihrer Schlüssel keine ausreichend zufälligen Werte nutzten. Die Vermeidung solcher Schwächen erfordert eine wirklich gute Zufallszahlengenerierung mit genügend Entropie. In Desktop-Computern kann beispielsweise die Bewegung der Maus oder die Tastatureingabe als Quelle fungieren.

Alltagsgeräte ohne solche Eingaben müssen alternative physikalische Phänomene erfassen oder besonders sorgfältig initialisierte Zufallsquellen nutzen. Versäumnisse in dieser Hinsicht führen unweigerlich zu einer deutlich reduzierten Schlüsselvielfalt, was wiederum die Wahrscheinlichkeit erhöht, dass zwei Schlüssel dieselbe Primzahl teilen. Dieses Sicherheitsproblem illustriert ein fundamentales Paradox der Kryptographie: Zwar basiert die Sicherheit großer Teile der Verschlüsselung auf tiefen mathematischen Prinzipien, doch kleine praktische Implementierungsfehler können ganze Systeme kompromittieren. Neben dem technischen Aspekt hat dies auch Folgen für die Akzeptanz und das Vertrauen in digitale Sicherheitssysteme – ein Grund, weshalb Softwareentwickler, Hardwarehersteller und Sicherheitsexperten diese Problematik mit höchster Priorität angehen. Das Aufspüren und Knacken der so genannten schwachen Schlüssel erfolgt typischerweise, indem man größere Sammlungen von öffentlichen Schlüsseln analysiert.

Bereits beim Paarweisen Vergleich der Moduli lassen sich mit Hilfe des gcd untersuchen, ob gemeinsame Primfaktoren vorhanden sind. Bei einer Menge von hundert oder mehr Schlüsselpaare skaliert die Anzahl der Vergleiche zwar quadratisch, doch die Geschwindigkeit des Algorithmus macht dies meist handhabbar. Für größere Datensätze setzen Spezialisten zudem optimierte Algorithmen ein. Um einen schwachen Schlüssel effektiv zu knacken, ist es nötig, die gemeinsamen Primfaktoren zu extrahieren und dann darauf aufbauend den privaten Schlüssel zu rekonstruieren. Die Infrastruktur dafür ist vorhanden, da die mathematischen Grundlagen gut verstanden und durch diverse Softwarebibliotheken abgedeckt sind.

Einmal extrahiert, erlaubt es der private Schlüssel, die verschlüsselten Nachrichten zu entschlüsseln, was natürlich für die Sicherheit der Kommunikation katastrophal ist. Ein besonders prägnantes Beispiel für fehlerhafte Zufallszahlengeneratoren war der OpenSSL-Bug in Debian-Systemen zwischen 2006 und 2008. Dort führte eine Änderung am Zufallsgenerator dazu, dass nur eine kleine Menge von etwa 32.000 verschiedenen Schlüsseln erzeugt wurde. Angreifer konnten so mit überschaubarem Aufwand alle möglichen Schlüssel vorab berechnen und entsprachen Nachrichten entschlüsseln.

Die Lektion daraus lautet, dass Kryptographie zwar auf mathematischen Prinzipien basiert, aber ohne sorgfältige und sichere Implementierung ihre Sicherheit verloren geht. Selbst eine so solide Methode wie RSA kann versagen, wenn die Grundlagen fehlerhaft sind. Deshalb sind sichere Zufallsquellen, regelmäßige Sicherheitsprüfungen und bewährte Standards unerlässlich. Für Entwickler und Sicherheitsexperten bedeutet dies konkret, dass beim Erzeugen von Schlüsseln ausschließlich sichere, kryptographisch geprüfte Zufallszahlengeneratoren zum Einsatz kommen sollten. Auch sollten Systemadministratoren und Anwender regelmäßig prüfen, ob ihre Schlüssel zu den als schwach bekannten Gruppen zählen oder ob ein Austausch empfohlen wird.