Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

RSA Low Exponent Attack
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> RSA Low Exponent Attack
 
Autor Nachricht
miranda
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.07.2005
Beiträge: 3

BeitragVerfasst am: 24 Jul 2005 - 14:25:19    Titel: RSA Low Exponent Attack

Hi,

ich verstehe folgendes bei der Lox-Exponent-Attacke nicht:

Man wählt zbB. einen kleinen Exponenten 3 und verschlüsselt damit einen Klartext m mehrfach zu teilerfremden Moduli n1, n2, n3. Für diese gilt: n1 = p1*q1 usw., also auch phi1 = (p1-1)*(q1-1).

Damit ist aber doch nicht gewährleistet, dass ggT(e,phi) = 1 gilt, für alle 3 phi gilt. Das muss aber doch eigentlich gewährleistet sein, um eine Nachricht mit RSA verschlüsseln zu können.

Außerdem hab ich mich gefragt, wie die 3 Empfänger die verschlüsselte Nachricht entschlüsseln können, wenn m nicht mit ihrem öffentlichen e verschlüsselt wurde, sondern mit dem einheitlichen e?!

Kann mir jemand helfen?!
In der Literatur finde ich nix dazu, was mir das erklärt ...
trinkMilch
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 19.06.2005
Beiträge: 228

BeitragVerfasst am: 24 Jul 2005 - 15:11:42    Titel:

Hi,

du meinst bestimmt mit e den Exponeten oder??

also ggT(e, phi(n)) = 1 muss natuerlich immer gelten.

Aber das ist ja nicht das Problem, nach diesem Kriterium kann man
ja n1, n2 und n3 bzw das e wählen

Ferner können die Empfänger die Nachricht nur entschlüsseln, wenn sie
die Faktorisierung des n kennen (bzw. so das phi(n) errechnen koennen)
das einheitliche e ist egal ;p


aber wenn man z.B. als e = 3 wählt , ist so ein low exponent abgriff möglich

Der Angreifer verschlüsselt die Klartexte ja selber, er kennt also deren inhalt.

dann könnte er mit dem chinesichen restsatz (simultane kongruenz)
c = c_{i} mod m_{i} und c = m*e

Durch berechnen der e-ten Wurzel von c kann das m gefunden werden.

Beispiel: e=3, n1=143, n2=391, n3=899, m=135. Damit ist c1=60, c2= 203, c3=711.

Die Attacke kann verhindert werden, indem die letzten Bits eines Klartextblocks zufällig gewählt werden. So kann verhindert werden, dass zweimal derselbe Block verschlüsselt wird. So ist RSA also nicht mehr
deterministisch.
Oder der Verschlüsselungsexponent wird groß genug gewählt.

cu..
miranda
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.07.2005
Beiträge: 3

BeitragVerfasst am: 24 Jul 2005 - 15:34:31    Titel: RSA Low Exponent Attack

Danke schonmal.

Das Beispiel kenne ich. Hab auch noch kein anderes gefunden in der Literatur Smile
Aber genau deshalb hatte ich ja die Frage: Denn in dem Beispiel ist ja e = 3 und n1 = 143 = 13*11. Das phi wäre also 12 * 10, also gilt auf jeden Fall nicht: ggT(3;phi) = 1.

Ist das jetzt ein Fehler in dem Beispiel?? So, kann Empfänger Nr.1 doch nicht mehr ein d zum entschlüsseln errechnen, oder?!
trinkMilch
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 19.06.2005
Beiträge: 228

BeitragVerfasst am: 25 Jul 2005 - 10:22:44    Titel:

Hi,

hmm darüber habe ich garnicht nachgedacht , als och das Beispiel kopiert habe .p


Also ich meine auch, dass ggT(e, phi(n)) = 1 sein muss, denn sonst
hatt ja e keine Inverse in Z/phi(n)Z.

Also kann Nr1 die nachricht wohl nicht entschlüsseln, da
er kein d = e^(-1) berechnen kann (multiplikative Inverse).

Aber das ist ja nicht so wichtig, hauptsache man versteht, wie man
diesen Angriff starten kann.

Nimmste halt fuer e = 23 anstatt e = 3, dann stimmts wieder,
natuerlich mit anderen c1, c2 und c3.


cu...
miranda
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.07.2005
Beiträge: 3

BeitragVerfasst am: 25 Jul 2005 - 12:08:58    Titel:

Hm, es kann doch nicht sein, dass dieses Beispiel in 50 Büchern bzw. Links falsch abgeschrieben wurde?! Die meisten haben es vermutlich aus dem Buchmann "Einführung in die Kryptographie" ...

Ich muss die Attacke implementieren und ein bißchen damit rumexperimentieren, indem ich e immer weiter erhöhe. Am besten wähle ich die ni's dann immer so, dass ggT(e,phi)=1 gilt. Dann hab ich keine Schwierigkeiten, aber irritiert und etwas unsicher bin ich doch noch bei der Sache.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> RSA Low Exponent Attack
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum