Mind your Ps and Qs
In diesem Post zeige ich euch, wie man eine schwache RSA Verschlüsselung für die Challenge „Mind your Ps and Qs“ von picoCTF bricht.
Die Challenge Beschreibung stellt uns die Frage: „In RSA, a small e
value can be problematic, but what about N
?“
Solltest du nicht wissen, wie die RSA Verschlüsselung funktioniert oder was RSA überhaupt ist, gebe ich dir eine kleine Einführung, ohne zu tief in die damit verbundene Mathematik einzusteigen:
RSA Basics
RSA ist ein asymetrisches Verschlüsselungsverfahren, das nach seinen Erfindern Ron Rivest, Adi Shamir and Leonard Adleman benannt ist.
Asymetrische Verschlüsselungen arbeiten mit zwei unterschiedlichen Schlüsseln, dem öffentlichen Schlüssel und dem privaten Schlüssel. Wenn Alice eine verschlüsselte Nachricht an Bob schicken möchte, braucht sie seinen öffentlichen Schlüssel, damit Bob die nachricht mit seinem privaten Schlüssel entschlüsseln kann.
Um die beiden für die RSA Verschlüsselung benötigten Schlüssel zu generieren, benötigen wir zwei Primzahlen „p“ und „q“, die auch die Namensgeber für die Challenge „Mind your Ps and Qs“ sind. Diese beiden Primzahlen miteinander multipliziert bilden einen Teil sowohl des privaten als auch des öffentlichen Schlüssels, den wir „N“ nennen.
Um die anderen Teile des privaten und öffentlichen Schlüssels zu berechnen, müssen wir φ(N) berechnen. φ(N) ist (p – 1) * (q – 1).
Um jetzt den öffentlichen Schlüssel zu vervollständigen, müssen wir einen Wert für „e“ auswählen, der zwischen 1 und φ(N) liegt und mit φ(N) keinen anderen Teiler als 1 hat. Am besten wählen wir dafür eine Primzahl, denn dann müssen wir nur noch prüfen, ob φ(N) nicht durch diese Zahl teilbar ist.
Mit diesem „e“ haben wir jetzt unseren öffentlichen Schlüssel zusammen. Dieser besteht aus „N“ und „e“.
Jetzt wird es mathematisch etwas komplizierter. Für unseren privaten Schlüssel benötigen wir einen weiteren Wert, der „d“ genannt wird. Dabei ist „d“ die modulare multiplikative Umkehrung von „e“ modulo φ(N). Das hört sich etwas kompliziert an. Um „d“ zu berechnen, kannst du den „erweiterten Euklidischen Algorithmus“ verwenden, aber etwas weiter unten zeige ich, wie man das mit einer einzigen Zeile Python Code erledigen kann.
Mit „N“ und „d“ haben wir alles für unseren privaten Schlüssel.
Um einen Klartext m zu verschlüsseln, benutzen wir die Funktion c = me modulo N und zum entschlüsseln eines Ciphertexts c benutzen wir die Funktionm m = cd modulo N wobei jeweils m der Klartext und c ser Ciphertext ist.
Einfaches RSA Beispiel
- Als erstes benötigen wir zwei Primzahlen. Für dieses Beispiel nehmen wir zwei ganz kleine:
p = 11, q = 13
2. Um N zu berechnen, bilden wir das Produkt von p und q:
N = p * q = 143
3. Jetzt müssen wir φ(N), also (p – 1) * (q – 1) berechnen:
φ(N) = (11 – 1) * (13 – 1) = 10 * 12 = 120
4. Wir müssen ein e wählen, dass zwischen 1 und φ(N) liegt und keinen gemeinsamen Teiler außer 1 mit φ(N) hat:
e = 17; 17 ist kleiner als 120 and kein Teiler von 120. Außerdem ist 17 eine Primzahl und kann somit auch keine anderen gemeinsamen Teiler außer 1 mit 120 haben.
5. Um d – die multiplikative Umkehrung von e modulo φ(N) zu berechnen, nehmen wir die Python Funktion „pow“:
d = pow(17, -1, 120) = 113
6. Da wir nun unseren privaten und öffentlichen Schlüssel haben, sind wir in der Lage, Nachrichten zu Ver- und Entschlüsseln. Wir verschlüsseln eine super geheime Nachricht mit dem Inhalt 100 wieder mit der gleichen Python-Funktion pow:
c = me modulo N = 10017 % 143 = pow(100, 17, 143) = 133
133 ist unsere verschlüsselte Nachricht. Zum Entschlüsseln benutzen wir wieder die pow-Funktion:
m = cd modulo N = 133113 % 143 = pow(133, 113, 143) = 100
Wir haben erfolgreich eine Nachricht mittels RSA ver- und entschlüsselt.
Löse die Challenge
Mitr diesem Wissen sind wir in der Lage, die Challenge zu lösen. Die Beschreibung gibt uns einige Werte:
c: 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n: 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e: 65537
„c“ ist unsere verschlüsselte Nachricht. Zusätzlich haben wir den öffentlichen Schlüssel, der aus „N“ und „e“ besteht.
Wenn „N“ groß genug ist, gibt es keine effiziente Möglichkeit, aus dem öffentlichen Schlüssel den privaten Schlüssel abzuleiten. Wie wir oben gesehen haben, muss man dafür die beiden Primzahlen finden, dessen Produkt „N“ ist, was nur durch sehr viel Rechenpower möglich ist. Hier ist N ’nur‘ 81 Stellen lang. Somit besteht eine gute Chance, die beiden Teiler von „N“ in einer Web-Datenbank namens FactorDB zu finden.
Ich habe ein kleines Python-Script erstellt, dass die Ganze Arbeit für uns erledigt. Einschließlich suchen der Primfaktoren, der Berechnung des privaten Schlüssels und der Entschlüsselung der Nachricht:
import requests
c = 240986837130071017759137533082982207147971245672412893755780400885108149004760496
n = 831416828080417866340504968188990032810316193533653516022175784399720141076262857
e = 65537
# get devisors from factordb
def get_factor(n):
f = requests.get('http://factordb.com/api', params={'query': str(n)}).json()
return int(f['factors'][0][0]), int(f['factors'][1][0])
print(f"Getting factors of n = {n} ...")
f = get_factor(n)
print(f"p = {f[0]}, q = {f[1]}")
phi_n = (f[0]-1) * (f[1]-1)
print(f"phi(n) = {phi_n}")
d = pow(e, -1, phi_n)
print(f"d = {d}")
print("decrypting ...")
m = pow(c, d, n)
print("converting to text ...")
print(f"Result: {bytearray.fromhex(hex(m)[2:]).decode('ascii')}")
Schaut euch auch meine anderen CTF-WriteUps an.
Hi,
dein Python Script funktioniert nicht da es für „n“ keinen Factor gibt.
Getting factors of n = 831416828080417866340504968188990032810316193533653516022175784399720141076262857 …
{‚id‘: ‚1100000003894103158‘, ’status‘: ‚C‘, ‚factors‘: [[‚831416828080417866340504968188990032810316193533653516022175784399720141076262857‘, 1]]}
Ich denke „n“ ist hier falsch, Es sollten 82 statt 81 zahlen sein.
VG
mw.
Hallo mw,
das Script ist richtig, aber FactorDB.com schien probleme mit der Datenbank gehabt zu haben.
Die beiden Faktoren sind 1593021310640923782355996681284584012117 und 521911930824021492581321351826927897005221.
Ich habe die Faktoren bei FactorDB neu eingegeben und das Skript geht wieder.
Du kannst aber auch die Zeile
f = get_factor(n)
auskommentieren, die sich die Faktoren von FactorDB holt und testweise die beiden Faktoren stattdessen von Hand eingeben:f = [1593021310640923782355996681284584012117, 521911930824021492581321351826927897005221]
. Damit funktioniert das Script auch wieder.Beste Grüße
Dominik