RSA-Verschlüsselung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:42 So 23.10.2011 | | Autor: | julsch |
| Aufgabe | Alice feiert eine weitere Party und schickt eine Einladung m an Bob und Berta. Dabei verschlüsselt Alice m mit den öffentlichen RSA-Schlüsseln [mm] (N,e_{1}) [/mm] und [mm] (N,e_{2}) [/mm] von Bob und Berta, wobei [mm] e_{1} [/mm] und [mm] e_{2} [/mm] teilerfremd sind.
Wieder ist Eve nicht zur Party eingeladen. Helfen Sie Eve auch diesmal und zeigen Sie, dass man aus den Chiffretexten die Einladung m effizient berechnen kann. |
Hallo zusammen,
ich hatte mich noch kurzfristig entschieden "Kryptanalyse" zu hören und leider die ersten beiden Vorlesungswochen verpasst. Ich sitze nun an der Aufgabe und habe mit Hilfe des Skripts ein paar Überlegungen angestellt, jedoch versteh ich es leider noch nicht so richtig, sodass ich hier Hilfe suche.
Ich habe mir überlegt, dass [mm] ggT(e_{1},e_{2})=1 [/mm] ist, obwohl ich noch nicht genau weiß, ob ich das brauche.
zu zeigen ist ja, dass ich aus den Chiffretexten [mm] c_{1} [/mm] und [mm] c_{2} [/mm] die Einladung m berechnen kann. Die Chiffretexte sind wie folgt definiert:
[mm] c_{1}=e_{1}(m)=m^{e_{1}} [/mm] mod N
[mm] c_{2}=e_{2}(m)=m^{e_{2}} [/mm] mod N
so wie ich es verstehe, muss ich nun [mm] d_{1} [/mm] und [mm] d_{2} [/mm] finden mit [mm] d_{1}(c_{1})=c_{1}^{d_{1}} [/mm] mod N und [mm] d_{2}(c_{2})=c_{2}^{d_{2}} [/mm] mod N, sodass [mm] d_{1}(e_{1}(m))=m [/mm] und [mm] d_{2}(e_{2}(m))=m [/mm] gilt. Stimmt das soweit?
Ich weiß nun, dass gilt
[mm] d_{i}(e_{i}(m))=(m^{e_{i}})^{d_{i}} [/mm] mod N = [mm] m^{e_{i}d_{i}} [/mm] mod N für i=1,2
Ich vermute nun, dass ich in irgendeiner Form entweder den Brute Force Angriff oder den Meet-in-the-Middle Angriff auf d ausführen muss, um die Aufgabe zu lösen, jedoch versteh ich nicht wie. Kann mir jemand weiterhelfen?
Mit freundlichen Grüßen
Julsch
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:11 So 23.10.2011 | | Autor: | felixf |
Moin Julsch!
> Alice feiert eine weitere Party und schickt eine Einladung
> m an Bob und Berta. Dabei verschlüsselt Alice m mit den
> öffentlichen RSA-Schlüsseln [mm](N,e_{1})[/mm] und [mm](N,e_{2})[/mm] von
> Bob und Berta, wobei [mm]e_{1}[/mm] und [mm]e_{2}[/mm] teilerfremd sind.
> Wieder ist Eve nicht zur Party eingeladen. Helfen Sie Eve
> auch diesmal und zeigen Sie, dass man aus den Chiffretexten
> die Einladung m effizient berechnen kann.
>
> Hallo zusammen,
> ich hatte mich noch kurzfristig entschieden "Kryptanalyse"
> zu hören und leider die ersten beiden Vorlesungswochen
> verpasst. Ich sitze nun an der Aufgabe und habe mit Hilfe
> des Skripts ein paar Überlegungen angestellt, jedoch
> versteh ich es leider noch nicht so richtig, sodass ich
> hier Hilfe suche.
>
> Ich habe mir überlegt, dass [mm]ggT(e_{1},e_{2})=1[/mm] ist, obwohl
> ich noch nicht genau weiß, ob ich das brauche.
Das ist der zentrale Punkt bei dieser Aussage 
Wie du vielleicht weisst, kann man mit dem erweiterten euklidischen Algorithmus zu den Zahlen [mm] $e_1, e_2$ [/mm] ganze Zahlen $a, b [mm] \in \IZ$ [/mm] berechnen mit $a [mm] e_1 [/mm] + b [mm] e_2 [/mm] = [mm] ggT(e_1, e_2)$, [/mm] was in diesem Fall gleich $1$ ist.
Wenn du das noch geschickt anwendest (Stichwort: Potenzgesetze), bist du fertig.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:35 So 23.10.2011 | | Autor: | julsch |
Hallo Felix,
danke für die schnelle Antwort. Das mit dem euklidischen Algorthimus ist mir klar, ich kann also ganze Zahlen a und b finden, sodass [mm] ae_{1}+be_{2}=1 [/mm] gilt.
Ich stell mir nun die Frage, wie ich das mit Potenzgesetzen in Verbindung stellen soll. Muss ich eigentlich [mm] d_{1} [/mm] und [mm] d_{2} [/mm] finden mit [mm] d_{i}(e_{i}(m))=m?
[/mm]
Das was mit zu Potenzgesetzen einfiehl war m zu betrachten:
[mm] m=m^{1}=m^{ae_{1}+be_{2}}=m^{ae_{1}} m^{be_{2}}
[/mm]
Wenn ich das mal mit [mm] d_{1}(e_{1}(m))=m^{e_{1}d_{1}} [/mm] mod N bzw. [mm] d_{2}(e_{2}(m))=m^{e_{2}d_{2}} [/mm] mod N vergleiche, könnte der Eindruck entstehen, dass [mm] d_{1}=a [/mm] und [mm] d_{2}=b [/mm] gilt, wie zeig ich das jedoch dann?
Lg Julsch
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:43 So 23.10.2011 | | Autor: | felixf |
Moin Julsch!
> danke für die schnelle Antwort. Das mit dem euklidischen
> Algorthimus ist mir klar, ich kann also ganze Zahlen a und
> b finden, sodass [mm]ae_{1}+be_{2}=1[/mm] gilt.
> Ich stell mir nun die Frage, wie ich das mit
> Potenzgesetzen in Verbindung stellen soll. Muss ich
> eigentlich [mm]d_{1}[/mm] und [mm]d_{2}[/mm] finden mit [mm]d_{i}(e_{i}(m))=m?[/mm]
> Das was mit zu Potenzgesetzen einfiehl war m zu
> betrachten:
> [mm]m=m^{1}=m^{ae_{1}+be_{2}}=m^{ae_{1}} m^{be_{2}}[/mm]
Das ist eine gute Idee.
> Wenn ich das mal mit [mm]d_{1}(e_{1}(m))=m^{e_{1}d_{1}}[/mm] mod N
> bzw. [mm]d_{2}(e_{2}(m))=m^{e_{2}d_{2}}[/mm] mod N vergleiche,
> könnte der Eindruck entstehen, dass [mm]d_{1}=a[/mm] und [mm]d_{2}=b[/mm]
> gilt, wie zeig ich das jedoch dann?
Ignoriere die [mm] $d_i$.
[/mm]
Beachte einach, dass [mm] $m^{a e_1} [/mm] = [mm] (m^{e_1})^a$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:05 So 23.10.2011 | | Autor: | julsch |
Wenn ich die [mm] d_{i} [/mm] nicht beachten soll, was muss ich dann eigentlich genau zeigen?
ich weiß ja jetzt, dass [mm] m=(m^{e_{1}})^{a}(m^{e_{2}})^{b} [/mm] ist. also weiß ich auch, dass m mod N = [mm] (m^{e_{1}})^{a}(m^{e_{2}})^{b} [/mm] mod N. Nur was bringt mir das jetzt? Ich versteh die Aufgabe glaub ich nicht richtig.
Lg
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:30 So 23.10.2011 | | Autor: | felixf |
Moin!
> Wenn ich die [mm]d_{i}[/mm] nicht beachten soll, was muss ich dann
> eigentlich genau zeigen?
> ich weiß ja jetzt, dass [mm]m=(m^{e_{1}})^{a}(m^{e_{2}})^{b}[/mm]
> ist. also weiß ich auch, dass m mod N =
> [mm](m^{e_{1}})^{a}(m^{e_{2}})^{b}[/mm] mod N. Nur was bringt mir
> das jetzt? Ich versteh die Aufgabe glaub ich nicht
> richtig.
Kennst du die Rechenregeln [mm] $(a^b)^c \mod [/mm] N$ = [mm] $(a^n \mod N)^c \mod [/mm] N$ und $(a [mm] \mod [/mm] N) (b [mm] \mod [/mm] N) [mm] \mod [/mm] N = (a b) [mm] \mod [/mm] N$?
Du hast ja [mm] $m^{e_1} \mod [/mm] N$ und [mm] $m^{e_2} \mod [/mm] N$ gegeben und willst [mm] $m^1 \mod [/mm] N$ bestimmen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:38 So 23.10.2011 | | Autor: | julsch |
ah super, vielen Dank, ich hab es jetzt hinbekommen. Nein, die Regeln kamen mir jetzt nicht bekannt vor, aber mit den Regeln war es recht schnell gelöst.
Schönen Abend noch und liebe Grüße
Julia
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:44 So 23.10.2011 | | Autor: | felixf |
Moin Julia,
> ah super, vielen Dank, ich hab es jetzt hinbekommen. Nein,
> die Regeln kamen mir jetzt nicht bekannt vor, aber mit den
> Regeln war es recht schnell gelöst.
dann kannst du dir ja jetzt noch ueberlegen, warum die Regeln gelten  Ich vermute, ihr hattet sie irgendwann (evtl. in einer anderen Vorlesung?) schonmal...
Die wichtigere der beiden Regeln ist uebrigens $(a [mm] \mod [/mm] N) (b [mm] \mod [/mm] N) [mm] \mod [/mm] N = (a b) [mm] \mod [/mm] N$; daraus kann man dann [mm] $(a^b) \mod [/mm] N = (a [mm] \mod N)^b \mod [/mm] N$ folgern und damit schliesslich die andere Regel die ich geschrieben hatte zeigen.
Dir auch noch einen schoenen Abend!
LG Felix
|
|
|
|
