RSA - Verständnisproblem

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

RSA - Verständnisproblem

Beitrag von hstr » 3. Jan 2013 18:05

Hi,
ich habe eine Frage zum RSA-Verfahren:
Nehmen wir an, wir haben n=253, e=3 und m=165 (aus dem Buch von Prof. Buchmann, S. 140).
Damit ergibt sich c = 110.
So jetzt meine Überlegung zum Entschlüsseln von RSA:
c = m^e mod n
Wieso kann ich jetzt nicht einfach mit dem erweiterten euklidischen Algorithmus das Inverse von e bezüglich des Moduls n berechnen.
Also 3*x = 1 mod 253. Und damit ist x (Inverses von e) = 169.
Dann folgende Umformung machen:
c ^ x mod n = (m ^ e) ^ x mod n = m mod n
Eingesetzt: 110 ^ 169 mod 253 = m mod 253
Und schließlich einfach m berechnen?
(110 ^ 169 mod 253 = 165, was m entspricht!)
Dabei habe ich nur e und n verwendet, die der Angreifer durch den öffentlichen Schlüssel auch zur Verfügung hat.

Zusammengefasst ist mein Problem wohl folgendes:
Wieso ist c = m^e mod n <=> c^(e^-1) = m^e^(e^-1) mod n <=> c^(e^-1) = m mod n nicht erlaubt/möglich?

sabse
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 29. Sep 2009 22:19

Re: RSA - Verständnisproblem

Beitrag von sabse » 3. Jan 2013 20:03

Kann es sein, dass du annimmst, dass [ a^b (mod n) ]^c = a^bc (mod n ) ?

Benutzeravatar
DB_420
Mausschubser
Mausschubser
Beiträge: 89
Registriert: 24. Nov 2010 15:12

Re: RSA - Verständnisproblem

Beitrag von DB_420 » 3. Jan 2013 20:49

sabse hat geschrieben:Kann es sein, dass du annimmst, dass [ a^b (mod n) ]^c = a^bc (mod n ) ?
Das gilt sogar (fast). Nach Mathe I Skript und darin Satz 2.1.5 lässt sich
\((a^b \ mod \ n)^c \ mod \ n = (a^{b^c} \ mod \ n) = (a^{bc} \ mod \ n)\)
setzen (durch Substitution von \(a^b\)).

Zum Problem: M.m.n dürfte \(e\) nicht immer ein Inverses \(mod \ n\) haben. n ist ja nicht prim, daher ist \((\mathbb{Z}/n\mathbb{Z})\) nicht immer ein Körper. Im oben genannten Fall scheint es das multiplikative Inverse dummerweise aber zu geben. Für den Anwendungsfall ist das hier genannte System also nicht verwendbar...
Tutor:
Mathe II Inf (SS12)
Mathe I Inf (WS11/12)

sabse
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 29. Sep 2009 22:19

Re: RSA - Verständnisproblem

Beitrag von sabse » 3. Jan 2013 21:19

Hm, aber nur fast. Reicht es dann nicht als Argument? Interessiert mich nur;P

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Re: RSA - Verständnisproblem

Beitrag von hstr » 4. Jan 2013 01:19

DB_420 hat geschrieben: Zum Problem: M.m.n dürfte e nicht immer ein Inverses mod n haben. n ist ja nicht prim, daher ist (ZnZ) nicht immer ein Körper. Im oben genannten Fall scheint es das multiplikative Inverse dummerweise aber zu geben. Für den Anwendungsfall ist das hier genannte System also nicht verwendbar...
Aber wieviele solcher Fälle gibt es? Wieso schließt man diese nicht explizit aus?
Bei solchen Fällen ist die komplette Verschlüsselung unsicher.

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Re: RSA - Verständnisproblem

Beitrag von hstr » 4. Jan 2013 02:43

Also ich bin jetzt nochmal alles durchgegangen und habe auch eine Lücke bei meiner Überlegung gefunden, habe aber auch noch ein weiteres Beispiel gefunden, welches trotz dieser Lücke (Herleitung von c^(e^-1) mod n = m) noch funktioniert (m kann entschlüsselt werden). Lücke deshalb, weil ich glaube das die Herleitung aus dem Startpost falsch ist.

Ich schreibe jetzt nochmal alle Schritte genau hin, vielleicht seht ihr ja noch Fehler:

1.) p und q (beide Primzahlen) wählen
p = 3 und q = 5
2.) e finden, s.d. 1 < e < (p-1)(q-1) und gcd(e,(p-1)*(q-1)) = 1
e = 7
1 < 7 < 8 und gcd(7,8) = 1
3.) Testen ob es ein Inverses e^-1 von e bezüglich des Modulos n gibt, also e*(e^-1) == 1 mod n
e^-1 = 13
7 * 13 mod 15 = 91 mod 15 = 1 mod 15 = 1 mod n
4.) Nachricht m wählen
m = 4
5.) c erstellen
c = m^e mod n = 4^7 mod 15 = 4

Jetzt der eigentliche Angriff:
(n,e) sind durch den öffentlichen Schlüssel bekannt. c wurde mitgehört.
Ich berechne
c^(e^-1) mod n = 4^13 mod 15 = 4 = m.

Da aber die Herleitung von c^(e-1) mod n = m fehlt (oder gar nicht existiert, vielleicht sind das alles Spezialfälle?!)
kann ich aber leider noch nicht zeigen, dass das auch wirklich immer so funktioniert, falls e^-1 aus Schritt 3 existiert.
Es hat mich aber schon ziemlich überrascht, gleich noch ein Beispiel zu finden bei dem c^(e^-1) mod n = m klappt(!)
Und ich werde jetzt auch noch mehr Beispiele dazu suchen.

EDIT:
Wenn ich in dem obigen Beispiel m = 6 setze, geht es auch:
c^(e^-1) mod n = 6^13 mod 15 = 6 = m

EDIT2:
Ich habe jetzt auch ein Gegenbeispiel für c^(e^-1) mod n = m gefunden:
p=7, q=13
n = 91
e = 17
e^-1 = 75
m = 20
c = 76
aber c^(e^-1) mod n = 14 != 20 = m

Vielleicht haben die Variablen der beiden obigen Beispiele irgendwelche Eigenschaften, die das letzte Beispiel (p=7, q=13, m=20) nicht hat,
die aber gefordert sind, damit man c^(e^-1) mod n = m anwenden kann.
Zweimal c entschlüsseln zu können scheint mir schon ein sehr großer Zufall zu sein...
Mache ich irgend einen groben Fehler bei den Beispielen?

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Re: RSA - Verständnisproblem

Beitrag von hstr » 4. Jan 2013 13:53

Jetzt habe ich ein Programm geschrieben, das gezielt nach solchen Fällen sucht.
Das Programm ist nicht wirklich gut implementiert, d.h. man würde nach einer Optimierung wohl noch (viel?) mehr Fälle finden.
Aber schon jetzt findet man nach (10000 Runden mit zufälligen p und q (beide 7 bit lang)) * (Anzahl verschiedener e's) 358 verschiedene Fälle, in denen man c mit dem erklärten Verfahren entschlüsseln kann.
Ich werde nochmal genau nachrechnen wie lange man braucht um solche Fälle zu finden, da dies ja sehr wichtig ist, um zu wissen, ob es vielleicht doch nur Zufall ist.
Hier einige Beispiele:
p: 73 q: 79 n: 5767 e: 49 c: 24 m: 24 decrypted with attack: 24
p: 83 q: 101 n: 8383 e: 79 c: 499 m: 84 decrypted with attack: 84
p: 67 q: 107 n: 7169 e: 37 c: 1605 m: 107 decrypted with attack: 107
p: 89 q: 107 n: 9523 e: 81 c: 5242 m: 106 decrypted with attack: 106
p: 107 q: 109 n: 11663 e: 65 c: 108 m: 108 decrypted with attack: 108
p: 113 q: 127 n: 14351 e: 73 c: 4096 m: 16 decrypted with attack: 16
p: 109 q: 127 n: 13843 e: 71 c: 1035 m: 107 decrypted with attack: 107

Die Frage ist jetzt natürlich, ob das alles kompletter Zufall ist oder ob die gewählten Variablen der gezeigten Beispiele
irgendwelche Eigenschaften haben, die das Entschlüsseln mit c^(e^-1) mod n erlauben.

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: RSA - Verständnisproblem

Beitrag von AlexPi11 » 4. Jan 2013 17:00

Wieso kann ich jetzt nicht einfach mit dem erweiterten euklidischen Algorithmus das Inverse von e bezüglich des Moduls n berechnen.
Hierzu kann ich sagen, dass man das mit dem modulo n nicht auf die Potenzen übertragen darf. Bei den Potenzen benutzt man \(mod\ \varphi(n)\). Mathematisch hab' ich da nichts parat, aber du hast ja schon ein Gegenbeispiel.

Lass dein Programm doch mal für beliebige Zahlen ungleich \(e^{-1}\ mod\ n\) laufen und schau, ob etwa genauso viel Fälle bei raus kommen.

Edit:
Also die neue Fragen hieße dann: Wieviele Zahlen x, wobei \(x \neq e^{-1}\ mod\ \varphi (n)\) und \(c^{x} = m\), gibt es denn so durchschnittlich.
Eine weitere Anmerkung: Man weiß, wenn man eine zufällige Zahl nimmt ja nicht, ob dass jetzt geklappt hat. Das müsste man dann an dem entschlüsselten Text erkennen.

hstr
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 14. Apr 2011 22:52

Re: RSA - Verständnisproblem

Beitrag von hstr » 6. Jan 2013 22:27

AlexPi11 hat geschrieben: Lass dein Programm doch mal für beliebige Zahlen ungleich \(e^{-1}\ mod\ n\) laufen und schau, ob etwa genauso viel Fälle bei raus kommen.
Edit:
Also die neue Fragen hieße dann: Wieviele Zahlen x, wobei \(x \neq e^{-1}\ mod\ \varphi (n)\) und \(c^{x} = m\), gibt es denn so durchschnittlich.
So, endlich mal wieder Zeit dafür gehabt, also ich habe das Programm jetzt mal mit x, wobei \(x \neq e^{-1}\ mod\ n\) und \(c^{x} = m\) laufen lassen.
Und es gab sogar noch mehr Zahlen, die sich so entschlüsseln ließen. Daraus folgere ich jetzt einfach mal, dass alles was ich bisher vermutet hatte falsch ist. (... zum Glück :D) Danke für die Antwort, das mal so zu probieren ist mir nicht eingefallen.
AlexPi11 hat geschrieben: Eine weitere Anmerkung: Man weiß, wenn man eine zufällige Zahl nimmt ja nicht, ob dass jetzt geklappt hat. Das müsste man dann an dem entschlüsselten Text erkennen.
Ich vermute mal das Programme wie gpg in die verschlüsselte Datei einen Hash von m speichern, sonst könnte gpg beim Entschlüsseln von Dateien
keine Meldung über ein falsches Passwort bringen.

Antworten

Zurück zu „Archiv“