Übung 3 - Aufgabe 2 (RSA)

Benutzeravatar
LinuxFan
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 29. Sep 2008 15:21
Wohnort: Bensheim
Kontaktdaten:

Übung 3 - Aufgabe 2 (RSA)

Beitrag von LinuxFan »

Hallo,

Ich habe für den öffentlichen Schlüssel (n = 143, e = 7) herausbekommen.
Bei der Berechnung des privaten Schlüssels ergibt sich jedoch für mich das Problem, dass der private Schlüssel d folgende Bedingungen erfüllen muss:
a) 1 < d < (p-1)(q-1)
b) d*e == 1 mod (p-1)(q-1) ==> de - (p-1)(q-1)*k = 1 ==> 7*d + 120*(-k) = 1

Wenn ich jetzt den euklidischen Algorithmus mit 7 / 120, 7 / 120 starte,
erhalte ich das Ergebnis, dass entweder der private Schlüssel d NEGATIV sein muss (was er laut Bedingung a nicht sein darf) oder dass der größte gemeinsame Teiler -1 lauten muss (was nicht der Fall ist).

Habe ich einen Fehler gemacht oder stimmt in der Aufgabe etwas nicht oder ist die Bedingung a bei dieser Aufgabe außen vor (habe diese Bedingung aus dem Buch "Einführung in die Kryptographie"?
Victor-Philipp Negoescu
http://www.viathinksoft.de

Benutzeravatar
Blub
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 244
Registriert: 24. Dez 2007 14:06

Re: Übung 3 - Aufgabe 2 (RSA)

Beitrag von Blub »

hey,

nein du hast dich nicht verrechnet ;) da kommt wirklich d=-17 glaub ich wars.

Aber wie du sagtest muss d positiv sein. Hast du also mal den Fall das dein d negativ wird, so rechnest du dieses einfach mod n. In deinem Fall also
d = -17 mod 120 = 103
und dann erfüllt es die Bedingung :-)



Christian
Tutor GDI II SS12
Tutor Trusted Systems WS11/12, Tutor GDI II SS11
Tutor Trusted Systems WS10/11, GDI I WS10/11
Tutor GDI II SS10, Tutor Trusted Systems WS09/10

Benutzeravatar
LinuxFan
Mausschubser
Mausschubser
Beiträge: 73
Registriert: 29. Sep 2008 15:21
Wohnort: Bensheim
Kontaktdaten:

Re: Übung 3 - Aufgabe 2 (RSA)

Beitrag von LinuxFan »

Vielen Dank :-)
Victor-Philipp Negoescu
http://www.viathinksoft.de

peter@seceng
Mausschubser
Mausschubser
Beiträge: 72
Registriert: 31. Aug 2009 12:30

Re: Übung 3 - Aufgabe 2 (RSA)

Beitrag von peter@seceng »

Hi!
Blub hat geschrieben:Aber wie du sagtest muss d positiv sein. Hast du also mal den Fall das dein d negativ wird, so rechnest du dieses einfach mod n. In deinem Fall also
d = -17 mod 120 = 103
Hier hat sich ein kleiner Schreibfehler eingeschlichen: Du willst natuerlich d modulo \(\varphi(n)\) rechnen und nicht modulo \(n\).

Einen Kommentar moechte ich auch noch zu der Positivitaet von d abgeben: Aus Bequemlichkeitsgruenden moechte man natuerlich das d positiv haben, damit man einfacher exponenzieren kann. Diese Positivitaet ist jedoch nicht gefordert (siehe Folie 5, Teil 4 des Skripts). Es wuerde auch alles funktionieren, wenn man d=-17 waehlt. Beachte, dass die Exponenten immer eindeutig modulo \(\varphi(n)\) sind (damit kann auch e negativ gewaehlt werden).

Viele Gruesse, Andreas

tzeenie
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 14. Okt 2008 20:04

Re: Übung 3 - Aufgabe 2 (RSA)

Beitrag von tzeenie »

Mmh, wenn ich dann m=34 verschlüssel, erhalte ich \(c = 34^7 \mathbb{\;mod\;} 120 = 64\). Trotz zigmal nachrechnen erhalte ich bei der Entschlüsselung aber \(m' = 64^{103} \mathbb{\;mod\;} 120 = 64 \neq 34\)! :shock:

c_elbert
Erstie
Erstie
Beiträge: 19
Registriert: 24. Apr 2006 11:39
Kontaktdaten:

Re: Übung 3 - Aufgabe 2 (RSA)

Beitrag von c_elbert »

Du darfst nicht modulo Phi von N (120) rechnen sondern
modulo n (143)
Dann klappt das auch

tzeenie
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 14. Okt 2008 20:04

Re: Übung 3 - Aufgabe 2 (RSA)

Beitrag von tzeenie »

:oops: Palm? Meet face. :lol: Oh mann, na klar, danke, war wohl n etwas langer Lerntag gestern, hehe.

Antworten

Zurück zu „Archiv“