Donnerstag, 24. Mai 2012

Überprüfung von RSA-Moduli auf gemeinsame Primfaktoren

Allgemeine Neuigkeiten

Zuletzt aktualisiert am Dienstag, 15. September 2020

Der RSA-Algorithmus für Public-Key-Kryptografie basiert auf der angenommenen Schwierigkeit, die Produkte von großen Primzahlen zu faktorisieren, dem Faktorisierungsproblem. Wie in Lenstra et al. 1 dargelegt, ist es jedoch möglich, bei einer Menge von Moduli einige von ihnen zu faktorisieren, wenn man gemeinsame Primzahlen findet. Auf diese Weise wird das Faktorisierungsproblem durch eine einfache Operation des größten gemeinsamen Teilers (ggT) umgangen. Eine schnelle Beispielimplementierung ist weiter unten zu finden.

Die obige Methode ist nur gegen RSA-Schlüssel wirksam, bei denen die während der Generierung getroffenen Entscheidungen nicht wirklich zufällig waren. Da kryptografische Schlüssel "stark" sein sollten, ist es wichtig zu verifizieren, ob alle Schlüssel wirklich zufällig erzeugt wurden 2.

Unten können Sie eine Anwendung (in Python 3) herunterladen, die alle gemeinsamen Faktoren findet, die evtl. in einer endlichen Menge von Moduli vorhanden sind. Der Zweck dieser Anwendung ist es, Systemadministratoren und allen, die ihre eigenen RSA-Schlüssel testen müssen, die Möglichkeit zu geben, dies zu tun. Die Anwendung berechnet den ggT, um zu bestimmen, welche Modul-Paare sich Primzahlen teilen, und faktorisiert dann, basierend auf den bekannten Primzahlen, die Moduli vollständig. Die Anwendung wurde im Jahr 2020 verbessert und trägt jetzt den Namen "sanitychecker_v2.py".

Der gezippte Quellcode kann zusammen mit einigen Testfällen hier heruntergeladen werden.

 

Wesentliche Punkte

  • Die Implementierung ist in Python geschrieben. Dadurch ist der Quellcode leicht zu lesen und zu modifizieren, und dennoch ist das Programm relativ schnell.

  • Abhängig vom Setup kann das Python-Skript bis zu 1 Million Moduli in etwa 4 Stunden prüfen. Für größere Mengen von Moduli beachten Sie bitte den Hinweis* unten.

  • Das Python-Skript benötigt als Eingabe nur die Liste der Moduli ohne weitere Informationen. Diese Eingabedatei muss einen Modul (in HEX-Codierung) pro Zeile haben. Eventuell finden Sie das Shell-Hilfsskript moduli_extract.sh nützlich, das sich ebenfalls in der komprimierten Quelltextdatei befindet. Dieses Shell-Skript extrahiert die Moduli aus Ihren Zertifikaten (im PEM-Format) unter Verwendung von openssl und schafft die Verbindungen zu den entsprechenden Originaldateien.

  • Das Python-Skript kann auf allen Betriebssystemen verwendet werden, die einen Python-Interpreter und das Computer-Algebra-System SageMath 3 unterstützen.

 

Anforderungen

  • Python Version 3.6 oder höher
  • SageMath Version 9.0 oder höher (für das Python-Skript erforderlich)

 

Installation und Verwendung

  1. Laden Sie SageMath herunter und installieren Sie es, falls es nicht bereits auf Ihrem System installiert ist.

  2. (Optionaler Schritt) Extrahieren Sie mit dem oben angegebenen Shell-Skript die Moduli aus Ihren Zertifikaten und speichern Sie die Moduli in einer "moduli"-Datei.

    Führen Sie dazu in einem Terminal den folgenden Befehl aus: ./moduli_extract.sh <Pfad zum Verzeichnis mit den PEM-Dateien>

    Stellen Sie (mittels chmod) sicher, dass Sie die Berechtigung für die Ausführung des Shell-Skripts gesetzt haben. Das Shell-Skript wird zwei Dateien im lokalen Verzeichnis erstellen:

    • Die moduli-Datei, die einen Modul pro Zeile in HEX-Codierung enthält.
    • Die Datei filenames, die in jeder Zeile den Dateinamen einer PEM-Datei enthält. Sie kann verwendet werden, um die PEM-Dateien zurückzuverfolgen, deren Moduli gemeinsame (shared) Primzahlen enthalten.

  3. In einem Terminal ausführen: sage -python3 sanitychecker_v2.py -i <moduli-Datei>

    Das Python-Skript lädt alle Moduli aus der Datei, führt Berechnungen durch und gibt am Ende alle Moduli aus, die erfolgreich faktorisiert wurden. Zum Testen können Sie den Beispielsatz von 10000 Moduli verwenden, der ebenfalls in der gezippten Quellcodedatei enthalten ist.

    Optional können Sie die Ergebnisse auch in einer Berichtsdatei speichern, indem Sie einfach den Namen der Berichtsdatei als weiteres Argument angeben:

    sage -python3 sanitychecker_v2.py -i <moduli-Datei> -r <report-Datei>

    Zusätzlich kann dem Python-Skript die vom Shell-Skript in Schritt 2 erzeugte "filenames"-Datei übergeben werden, um die PEM-Dateien zurückzuverfolgen, die den Moduli entsprechen, die Primzahlen gemeinsam haben.

    sage -python3 sanitychecker_v2.py -i <moduli-Datei> -f <filenames-Datei>

  4. Weitere Hinweise zur Verwendung dieses Python-Skripts, um schwache Moduli mit gemeinsamen Primzahlen zu finden:

    • Die Liste der Moduli wird auf Duplikate überprüft.
    • Mit der Option -d können die Moduli auch als Dezimalwerte übergeben werden.
    • Im Vergleich zu Version 1 nutzt ein effizienterer Algorithmus mehrere Kerne parallel.
    • Das Shell- und das Python-Skript wurden unter Linux entwickelt, aber sie laufen auch unter Windows (in einer Bash-Shell und mit SageMath für Windows).

 

Hinweis: Neben dem Python-Code haben wir auch eine C++-Version entwickelt, die noch schneller arbeitet als die obige Python-Version. Dieser C++-Code wurde entwickelt, da der Code aus 4 im Jahr 2012 nicht für die Öffentlichkeit verfügbar war. Falls Sie eine große Menge (>1M) von Moduli auf gemeinsam genutzte Primzahlen überprüfen möchten und diesen C++-Code erhalten möchten, kontaktieren Sie uns bitte.

 

Quellen und Verweise

Footnotes

  1. Arjen K. Lenstra et al., "Ron was wrong, Whit is right", Cryptology ePrint Archive Report 2012/064, Februar 2012, http://eprint.iacr.org/2012/064. ↩

  2. Esslinger, Schneider, Simon: "RSA-Sicherheit in der Praxis", KES & Zeitschrift für Informationssicherheit, April 2012, pp. 18 ff. Dieser Artikel erklärt den Angriff auf Shared Primes, wie der oben beschriebene Sanity-Check entwickelt wurde und was Organisationen gegen dieses Risiko tun können. ↩

  3. SageMath – free and open-source mathematics software system, v9.1 (2020-05-21), August 2020, http://www.sagemath.org ↩

  4. Nadia Heninger et al., "Mining your P's and Q's: Detection of Widespread Weak Keys in Network Devices", in proceedings of the 21st USENIC Security Symposium, August 2012, https://factorable.net/weakkeys12.extended.pdf ↩

Gepostet von:

Volker Simon