Veröffentlicht am: 01.05.2017
Von: JLusiardi
In Kategorie: Software
Schlagwörter: Crypto Kommandozeile Python
Als Einstiegshürde für ein CTF (Capture the Flag) dient gerne mal ein RSA Schlüsselpaar, von dem nur der öffentliche Teil bekannt ist. Also kein unrealistischer Ansatz, lediglich die Schlüssellängen sollten entsprechend klein sein.
Vorbereiten der Challenge
Diese Schritte werden vom Spielleitder durchgeführt. Wichtig ist eine geeignete, nicht zu lange Schlüssellänge zu wählen. Hier wählen wir 256 Bit als Schlüssellänge. Das sollte die Teilnehmer vor keine Probleme stellen.
Generieren des Schlüsselpaars
Der wesentliche Schritt bei der Erzeugung eines RSA-Schlüsselpaars ist die Wahl von 2 Primzahlen p und q, deren Produkt n (der RSA-Modulus) die gewünschte Schlüssellänge besitzt.
Dank OpenSSL ist es einfach ein RSA-Schlüsselpaar zu erzeugen:
openssl genrsa -des3 -out private.pem 256
openssl rsa -in private.pem -outform PEM -pubout -out public.pem
Daraus ergibt sich als Public Key beispielsweise:
-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhALRUOO0rvPEA282wqL4VF5GibnA1kcux
LHdIOcT807+DAgMBAAE=
-----END PUBLIC KEY-----
Den privaten Schlüssel private.pem können wir nun löschen, da wir diesen zum Einen nicht mehr benötigen und zum Anderen ja rekonstruieren wollen.
Verschlüsseln der Probedatei
Eine Probedatei lesbar.txt wird mit dem öffentlichen Schlüssel mit OpenSSL verschlüsselt:
openssl rsautl -encrypt -inkey public.pem -pubin -in lesbar.txt -out geheim.txt
Das Ergebnis der Verschlüsselung ist eine Datei, die nur unlesbare binäre Daten enthält. Sie kann hier heruntergeladen werden: geheim.txt. Diese Datei und der öffentliche Schlüssel gehen an die Teilnehmer.
Lösen der Challenge
Diese Schritte werden durch die Teilnehmer durchgeführt.
Knacken der Schlüssel
Zunächst müssen wir aus dem öffentlichen Schlüssel die beiden Parameter n (Modulus) und e (Exponent) extrahieren:
from Crypto.PublicKey import RSA
public_key = RSA.importKey(open('public.pem', 'r').read())
print 'n =', public_key.n
print 'e =', public_key.e
Dazu verwenden wir die Bibliothek pycrypto (Debian: python-crypto). Ausgegeben werden die beiden oben genannten Werte, in unserem Beispiel also:
n = 815651207903382691105573612057017618852
64115611526254943458542612275141001091
e = 65537
Nun muss der Modulus faktorisiert werden (n ist das Produkt der beiden Primzahlen p und q). Dazu kann das msieve von Jason Papadopoulos verwendet werden.
Für unsere Zahl n liefert msieve auf einem Core2Duo T7400 nach knapp 10 Minuten die beiden Primfaktoren:
p = 264446414907090989475638551039611206507
q = 308437234133027923039636551098640509513
Alternativ können wir auch factordb.com verwenden, wenn die Zahl dort bereits faktorisiert vorliegt.
Nun müssen wir aus p und q den privaten Exponenten d berechnen:
d = 1/e mod (p-1)*(q-1)
oder mit Python und dem Modul gmpy2:
import gmpy2
p = 264446414907090989475638551039611206507
q = 308437234133027923039636551098640509513
e = 65537
d = gmpy2.invert(e,(p-1)*(q-1))
Aus den Werten n,e und d wird nun der private Schlüssel erstellt und ausgegeben:
from Crypto.PublicKey import RSA
key = RSA.construct((n,e,d))
print key.exportKey()
In unserem Beispiel ergibt das:
-----BEGIN RSA PRIVATE KEY-----
MIGrAgEAAiEAtFQ47Su88QDbzbCovhUXkaJucDWRy7Esd0g5xPzTv4MCAwEAAQIh
ALFDhX4nG6FxbaChww6vnyzjasWei1L/rUg3aG/c6MaxAhEA6ArZu41/pzoKRlXH
MfYqSQIRAMbyhuPv26I/S0+zokene2sCEDxkfpDK3huHBp+RubtuJ0kCECAEWecG
6+7Rhto9y4kCkB8CEQCSSbMXMjOybMpz3gCOQYeS
-----END RSA PRIVATE KEY-----
Wir speichern den privaten Schlüssel wieder in der Datei private.pem ab.
Entschlüsseln der Probedatei
Wurde alles richtig durchgeführt, so kann man mit folgender OpenSSL Anweisung die Probedatei entschlüsseln:
openssl rsautl -decrypt -inkey private.pem -in geheim.txt -out lesbar.txt
Der genaue Inhalt von lesbar.txt wird hier jedoch nicht verraten.
Abschluss
Man erkennt hier am Zeitaufwand zur Faktorisierung eines 256 Bit Schlüssels bereits, dass die Sicherheit von RSA auf genau dieser Schwierigkeit basiert. In der Praxis verwendet man daher Schlüssellängen von mindestens 2000 Bit (siehe dazu die Technische Richtilinie des BSI: Kryptographische Verfahren: Empfehlungen und Schlüssellängen (Seite 39, Kapitel 3.5 - RSA).