0 Daumen
596 Aufrufe

Aufgabe:

beim RSA-Verfahren ist der Schlüssel N = 391 und e = 145. Sie fangen die Nachricht 7 ab.
Wie lautet die unverschlüsselte Nachricht?


Problem/Ansatz:
Angabe: verschlüsselte Nachricht c = 7
gesucht: unverschlüsselte Nachricht m ?

c = me  mod n
7 = m145  mod 391


dann komme ich nicht weiter

m = cd mod n

Avatar von

1 Antwort

0 Daumen
 
Beste Antwort

Es gilt

      \(e\cdot d\equiv 1\mod \varphi(391)\) .

Bestimme \(d\), zum Beispiel mit dem erweiterten euklidischen Algorithmus

Avatar von 5,6 k

Erweiterter Euklidscher Algorithmus für 391, 145

bekomme man dann

56·391 - 151·145 = 1 

ist das richtig oswald ? und damit ist d = 151  oder?

ist das richtig oswald ?

Ja,

        \(56\cdot 391 - 151\cdot145 = 1\)

ist richtig. Das kann man ganz einfach überprüfen indem man die linke Seite in den Taschenrechner eintippt.

und damit ist d = 151  oder?

Nein. Dazu hätte man das \(d\) in der Kongruenz

        \(e\cdot d\equiv 1\mod \varphi(391)\)

bestimmen müssen, und nicht das \(d\) in der Kongruenz

        \(e\cdot d\equiv 1\mod 391\).

hmm.. ich bin etwas verwirrt jetzt. könntest du bite denn erklären, welchen Wert d hat?

Löse die Kongruenz

        \(e\cdot d\equiv 1\mod \varphi(391)\).

Was ist daran so schwer zu verstehen?


Das \(N = 391\) ist Teil des öffentlichen Schlüssels \((d,N)\).

Der euklidische Algorithmus kann effizient implementiert werden.

Wenn also tatsächlich nur die Kongurenz

  \(e\cdot d\equiv 1\mod N\)

gelöst werden sollte, dann könnte man einfach aus dem öffentlichen Schlussel den privaten Schlüssel berechnen.

Der eigentlich rechenaufwändige Teil bei der Berechnung des privaten Schlüssel aus \((d,N)\) ist die Berechnung von \(\varphi(N)\).

um φ(N) herauszufinden

entweder:

φ(N) = (p-1)(q-1)

aber p und q unbekannt


oder

e*d ≡ 1 mod φ(N)

aber d unbekannt.


deswegen bin ich verwirrt.

also mit anderen Worten d und φ(N) sind unbekannt

aber p und q unbekannt

Dann haben wir aber echtes Glück, dass \(N\) dieses mal so klein ist. Hoffentlich hat der Professor das nicht bemerkt, sonst wird die Aufgabe nächstes mal viel schwieriger.

aha moment.  Hoffentlich ja :) 

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community