Wie lautet die unverschlüsselte Nachricht? RSA-Verfahren

Question

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 = m^e  mod n
7 = m145  mod 391

dann komme ich nicht weiter

m = c^d mod n

Answer 1

Es gilt

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

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

Comments

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 :)