Demonstration des Determinismus von RSA

Ich weiß, dass dieses Problem jedem bekannt ist. Ich wollte es nur anhand eines Tools demonstrieren.

Liebe Mitglieder,

ich bin diesem Forum frisch beigetreten, da andere Hacking- und Codingforen mich aufgrund der erhöhten kriminellen Energie enttäuscht haben. Ich möchte zukünftig regelmäßig zu der Community beitragen. Aber nun zum Thema: Wenn man sich ein wenig mit dem RSA-Verfahren beschäftigt hat, ist einem bestimmt schon aufgefallen, dass im unmodifizierten RSA-Verfahren (Textbook-RSA) Ergebnisse voraussehbar sind. Es ist also ein deterministisches Verfahren. Verschlüssele ich eine Nachricht mit dem bekannten öffentlichen Schlüssel einer Person, erhalte ich den verschlüsselten Text, der erst mit dem privaten Schlüssel der Zielperson wieder entschlüsselt werden kann. Sollte mir nun als Angreifer dieser öffentliche Schlüssel bekannt sein, kann ich auch eine Nachricht für den Empfänger verschlüsseln. Allerdings, weiß ich dank des Determinismus von RSA, welche Klarzahl nun der Geheimzahl entspricht. So kann ich ein "Wörterbuch" anlegen, mit dem ich auch zukünfigt abgefangene Nachrichten, entschlüsseln kann, da ich ja weiß, welche Klarzahl welcher Geheimzahl entspricht. Ich verschlüssele beispielsweise die Zahl 1 und bekomme als Ergebnis 32. Wenn ich in einem Chiffrat die Zahl 32 entdecke, weiß ich, dass es eine 1 bedeuten muss (vorrausgesetzt, die gleichen Schlüssel werden noch benutzt). Dieses Problem dürfte aber den meisten bekannt sein. Um das ganze zu demonstrieren, hab ich dafür ein kleines Tool in Java geschrieben. Man gibt dem Tool einfach den bekannten öffentlichen Schlüssel und das Chiffrat. Das Tool verschlüsselt von einer Startzahl bis zu einer Endzahl alle dazwischenliegenden Zahlen und speichert Klar- und Geheimzahl in einem Wörterbuch. Danach wird sich das Chiffrat zur Hand genommen und es werden automatisch alle Zahlen, die im Wörterbuch gespeichert sind und auch im Chiffrat vorhanden sind durch die bekannte und vom Wörterbuch erfasste Klarzahl ersetzt. Mit dieser Strategie ist es möglich, verhältnismäßig kleine Zahlen, die sogar mit RSA-4096bit verschlüsset wurden, in einer Minute herauszubekommen. Dieses Tool ist keine Neuentdeckung, ich wollte es einfach dazu verwenden, mal du demonstrieren, wie gefährlich Determinismus bei Verschlüsselungsverfahren sein kann. Zum Glück wird das reine RSA-Verfahren nicht mehr angewandt, es wird heute entweder gepadded oder mit anderen Verschlüsselungsverfahren kombiniert (hybride Verfahren). Um das Tool kurz zu zeigen, hab ich ein kleines Demo-Video erstellt. Hier wird erst durch RSAEncryption.java die Nachricht "1337" mit RSA-4096 verschlüsselt, dann wird mit meinem Tool RSAGuess.java der Determinismus ausgenutzt.

Deterministic RSA (only works with small numbers) - YouTube

Ich hoffe, dass euch mein erster Beitrag gefällt.
Liebe Grüße,

Antigone
 
Zuletzt bearbeitet:
Moin,
wenn die endliche Körperarithmetik nicht wäre, hättest du recht. Allerdings hier mal ein minimales Beispiel. Diese Ringe sind nicht kollisionsfrei. Angenommen, wir betrachten eine Untergruppe mit p=5 und q=7 also n=5*7=35. D.h. die Gruppe der natürlichen Zahlen modulo 35. (in Sage kannst du diese durch den Befehl "IntegerModRing(35)" konstruieren.)

So gilt folgende Kongruenz:
2=2^1=2^13 (mod 35).

Hast du nun also eine Nachricht, die größer als dein Modulus ist, landest du automatisch auf einem Element der endlich erzeugten Gruppe des Rings und hast zwangsläufig eine Kollision aufgrund der Entropien. Die Urbildmenge (Anzahl aller Nachrichten und Länge der Ziffern) ist größer als die Bildmenge (Zahlen von 1 bis 34, multiplikative Gruppe).

Zu deinem Beispiel.
Nehmen wir die Nachricht m=1337, RSA-4096 bedeutet, dass der Private-Key 4096 Bits lang ist. Solch ein Beispiel möchte ich nicht konstruieren, da die Free-Cloud_Version von Sage dann abschmiert :p Nehmen wir einfach die "next_prime()"s, dann sind p=1361 & q=1367, also n=1860487. Dann sind auch hier 1337 = 1337^(1860487) (mod n). Du hast also mindestens eine Kollision gefunden.
(Diese Kollisionen sind nicht verwunderlich, nach dem Satz von Euler ;) )

Code:
p = 1337.next_prime() 
q = (p+1).next_prime()
n = p*q
R = IntegerModRing(n)
m = R(1337) #message as Ring.element
y=m^2 #chiffre
e=2 #exponent
while(y != m):
    e+=1
    y*=m
e #ausgabe des Exponenten

Dein Ansatz ist folglich für alle Zahlen, kleiner dem Modulus, korrekt, danach aber nicht mehr anwendbar.


Übrigens arbeitet jedes sog. Orakel nach deinem Prinzip. Man schmeißt dem Orakel einen Klartext rein, dieser wird mit Chiffre als DB gespeichert. Chiffre zurückgegeben. Ist ein Klartext in der DB, kommt immer der gleiche Wert, ansonsten wird ein neuer, rein zufälliger Wert als Chiffre erzeugt und nachgetragen. Empfehlenswert ist das "Einführung in die Kryptographie" Buch von "Johannes Buchmann".

PS: Gerne mehr dieser Diskussionen :D
 
Zuletzt bearbeitet:
bin dabei

"Gerne mehr dieser Diskussionen"

Na, da bringe ich mich doch gerne mit ein, Jungs ich verstehe ABSOLUT nur Bahnhof, aber es liest sich sensationell :D

Ich hab euch im Auge

Beste Grüße
 
Zurück
Oben