Sicherheitslücke in Druckern: Über 300 Jahre alter Algorithmus knackt RSA-Keys

Drucker von Canon und Fujifilm erzeugen schwache RSA-Schlüssel, die sich mit dem Faktorisierungsalgorithmus von Fermat angreifen lassen.

Artikel von Hanno Böck veröffentlicht am 15. März 2022, 11:15 Uhr

An Internetverschlüsselung dachte Pierre de Fermat wohl noch nicht, als er vor über 300 Jahren einen Faktorisierungsalgorihtmus entwickelte. (Bild: François de Poilly)

Im Jahr 1643 hat der Mathematiker Pierre de Fermat einen Algorithmus beschrieben, mit dem sich in bestimmten Fällen die Primfaktoren einer großen Zahl schnell berechnen lassen. Voraussetzung dafür ist, dass die Primzahlen ähnlich groß sind.

Das Verschlüsselungs- und Signaturverfahren RSA wiederum basiert darauf, dass die Primfaktorzerlegung von großen Zahlen schwierig ist - ein öffentlicher RSA-Schlüssel enthält einen Zahlenwert N, der das Produkt aus zwei großen Primzahlen p und q ist (N=p*q).

Der Autor dieses Textes hat versucht, mit Hilfe von Fermats Faktorisierungsalgorithmus RSA-Schlüssel aus öffentlich zugänglichen Datensätzen zu knacken. In einigen Fällen war dies erfolgreich, die Schlüssel gehörten zu TLS-Zertifikaten, deren Schlüssel von Druckern der Hersteller Fujifilm und Canon erzeugt wurden.

Algorithmus funktioniert bei zwei ähnlich großen Primzahlen

Bei korrekt erzeugten RSA-Schlüsseln scheitert Fermats Algorithmus natürlich. Wenn die beiden Primzahlen, mit denen ein RSA-Schlüssel erzeugt wurde, zufällig erzeugt wurden, unterscheiden sie sich prakisch immer bereits in den ersten Bits - und Fermats Algorithmus funktioniert nur effizient, wenn die beiden Zahlen ähnlich groß sind. Doch fehlerhafte Schlüsselerzeugungsroutinen können schwache Schlüssel erzeugen, die angreifbar sind.

Fermats Faktorisierungsalgorithmus ist relativ einfach zu verstehen: Hat man eine große Zahl, die das Produkt zweier Primzahlen ist, so kann man die beiden Primzahlen als a+b und a-b definieren. Der Wert a ist dabei die Mitte zwischen den beiden Primzahlen - da große Primzahlen ungerade sind, gibt es immer einen ganzzahligen Wert in der Mitte. Der Wert b ist der Abstand von dieser Zahl in der Mitte zu den beiden Primzahlen.

Daraus ergibt sich N=(a+b)(a-b), dies lässt sich durch einfache algebraische Regeln zu b^2=a^2-N umformen.

Nun wird versucht, den Wert a zu raten. Wir erinnern uns: Dabei handelt es sich um die Mitte zwischen den beiden Primzahlen - und die ist bei ähnlich großen Primzahlen etwa gleich groß wie die Wurzel von N. Die Wurzel von N ist keine Ganzzahl, sie wird also zunächst gerundet.

Es wird versucht, die Mitte zwischen den Primzahlen zu erraten

Die gerundete Wurzel von N dient somit als erster geratener Wert für a. Mittels der bereits genannten Formel b^2=N-a^2 lässt sich errechnen, ob das korrekte a geraten wurde: Wenn b^2 das Quadrat einer Ganzzahl ist, wurde a richtig geraten. Falls nicht, wird der geratene Wert um eins erhöht und das Ganze wiederholt. Das kann beliebig oft wiederholt werden, je länger, desto höher die Chance, die Zahl zu faktorisieren. Bei verwundbaren Schlüsseln funktioniert das meist bei sehr wenigen Versuchen, letztendlich habe ich nach 100 Versuchen abgebrochen.

Hat man a richtig geraten, ist der Rest einfach: Man kennt nun b^2. Daraus lässt sich b berechnen und daraus die Primzahlen p und q. Wenn man die beiden Primzahlen kennt, lässt sich der gesamte private RSA-Schlüssel berechnen.

Dass es theoretisch schwache RSA-Schlüssel geben könnte, die mit diesem Algorithmus knackbar sind, ist nichts Neues. Doch nach meiner Kenntnis wurden bislang keine solchen Schlüssel gefunden, die real genutzt wurden.