RSA Verschlüsselung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:38 So 26.08.2012 | | Autor: | Blake512 |
| Aufgabe | Der RSA-key (n,e) is bekannt, wobei n der Modulus und e der Exponent ist.
2 Nachrichten [mm] m_1 [/mm] und [mm] m_2 [/mm] werden verschlüsselt.
Ist es möglich, die RSA-Verschlüsselung von m = [mm] m_1 [/mm] * [mm] m_2 [/mm] mit Hilfe von [mm] c_1 [/mm] und [mm] c_2 [/mm] herauszufinden ohne m zu kennen? |
Berechnung von [mm] c_1 [/mm] und [mm] c_2:
[/mm]
[mm] c_1 [/mm] = [mm] {m_1}^e [/mm] mod n
[mm] c_2 [/mm] = [mm] {m_2}^e [/mm] mod n
Berechnung von [mm] m_1 [/mm] und [mm] m_2:
[/mm]
[mm] m_1 [/mm] = [mm] {c_1}^d [/mm] mod n
[mm] m_2 [/mm] = [mm] {c_2}^d [/mm] mod n
Berechnung von m:
m = [mm] m_1 [/mm] * [mm] m_2
[/mm]
oder
m = [mm] {c_1}^d [/mm] * [mm] {c_2}^d [/mm] mod n
Das heisst, d muss bekannt sein, um die Berechung durchführen zu können. Dies ist aber nicht möglich, weil die Faktorisierung von n schwierig ist (und nicht bekannt).
Wenn die Faktorisierung von n kein Problem wäre, kann mit Hilfe der Euler-Phi-Funktion d berechnet werden:
[mm] \phi(n) [/mm] = (p-1)*(q-1)
Da e bekannt ist, findet man d mit dem erweiterten euklidischen Algorithmus EEA(e, [mm] \phi(n)) [/mm] heraus:
e*d [mm] \equiv [/mm] 1 mod [mm] \phi(n)
[/mm]
Kann jemand meine Überlegungen bestätigen oder widerlegen? :)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:57 So 26.08.2012 | | Autor: | felixf |
Moin!
> Der RSA-key (n,e) is bekannt, wobei n der Modulus und e der
> Exponent ist.
>
> 2 Nachrichten [mm]m_1[/mm] und [mm]m_2[/mm] werden verschlüsselt.
>
> Ist es möglich, die RSA-Verschlüsselung von m = [mm]m_1[/mm] * [mm]m_2[/mm]
> mit Hilfe von [mm]c_1[/mm] und [mm]c_2[/mm] herauszufinden ohne m zu kennen?
> Berechnung von [mm]c_1[/mm] und [mm]c_2:[/mm]
>
> [mm]c_1[/mm] = [mm]{m_1}^e[/mm] mod n
> [mm]c_2[/mm] = [mm]{m_2}^e[/mm] mod n
>
> Berechnung von [mm]m_1[/mm] und [mm]m_2:[/mm]
>
> [mm]m_1[/mm] = [mm]{c_1}^d[/mm] mod n
> [mm]m_2[/mm] = [mm]{c_2}^d[/mm] mod n
>
> Berechnung von m:
>
> m = [mm]m_1[/mm] * [mm]m_2[/mm]
> oder
> m = [mm]{c_1}^d[/mm] * [mm]{c_2}^d[/mm] mod n
>
> Das heisst, d muss bekannt sein, um die Berechung
> durchführen zu können. Dies ist aber nicht möglich, weil
> die Faktorisierung von n schwierig ist (und nicht
Moment! Du willst doch gar nicht $m$ berechnen, sondern [mm] $m^e \mod [/mm] n$. Und dazu brauchst du $d$ garnicht.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:11 So 26.08.2012 | | Autor: | Blake512 |
| Aufgabe | | Das heisst c = [mm] c_1 [/mm] * [mm] c_2 [/mm] wobei c = [mm] m^e [/mm] mod n und somit [mm] m^e [/mm] mod n = [mm] c_1 [/mm] * [mm] c_2. [/mm] In anderen Worten: Ja es ist möglich, die RSA-Verschlüsselung von m = [mm] m_1 [/mm] * [mm] m_2 [/mm] mit Hilfe von [mm] c_1 [/mm] und [mm] c_2 [/mm] herauszufinden ohne m zu kennen? |
Wenn ich aber m berechnen möchte, würden meine Überlegungen stimmen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:05 So 26.08.2012 | | Autor: | felixf |
Moin!
> Das heisst c = [mm]c_1[/mm] * [mm]c_2[/mm] wobei c = [mm]m^e[/mm] mod n und somit [mm]m^e[/mm]
> mod n = [mm]c_1[/mm] * [mm]c_2.[/mm] In anderen Worten: Ja es ist möglich,
> die RSA-Verschlüsselung von m = [mm]m_1[/mm] * [mm]m_2[/mm] mit Hilfe von
> [mm]c_1[/mm] und [mm]c_2[/mm] herauszufinden ohne m zu kennen?
Genau.
> Wenn ich aber m berechnen möchte, würden meine
> Überlegungen stimmen?
Ja, mehr oder weniger.
Wenn [mm] $m_1$ [/mm] und [mm] $m_2$ [/mm] jetzt nicht ein paar spezielle Werte annehmen (eins davon ist etwa Vielfaches von $p$ oder $q$, falls $n = p q$), und damit [mm] $c_1$ [/mm] und [mm] $c_2$ [/mm] beim Faktorisieren helfen, dann ist das Finden von $m$ in etwa so schwierig wie das Knacken von RSA, was (wenn man ein paar spezielle andere Faelle ausschliesst wie schlechte Parameterwahlen) nach bisherigem Kenntnisstand auf Faktorisierung von $n$ herauslaeuft.
LG Felix
|
|
|
|
