www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Krypto,Kodierungstheorie,Computeralgebra" - RSA Verschlüsselung
RSA Verschlüsselung < Krypt.+Kod.+Compalg. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

RSA Verschlüsselung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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? :)

        
Bezug
RSA Verschlüsselung: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
RSA Verschlüsselung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
RSA Verschlüsselung: Antwort
Status: (Antwort) fertig Status 
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


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Krypto,Kodierungstheorie,Computeralgebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]