e * d ≡ 1 mod φ(N)?

Wie kann ich aus e × d ≡ 1 mod(φ(N)) d berechnen, wenn e und φ(N) gegeben sind? Ich benötige das für das RSA Verschlüsselungsverfahren. Ich hoffe, ihr könnt mir da helfen.

Answer 1

[xxxcyberxxx]

Wie kann ich aus e × d ≡ 1 mod(φ(N)) d berechnen, wenn e und φ(N) gegeben sind?

Schau dir den erweiterten euklidischen Algorithmus an

Edit:

Ich check nicht wie ich aus dem d bekomme.

Als "Anleitung" kannst du das hier anschauen:

• https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels
• https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

Als Beispiel fändest du es auch auf Wikipedia, siehe hier, aber ich mach es einfach hier:

• Als Primzahlen wähle ich p = 3 und q = 11
• $n\ =\ p\cdot q\ =\ 33$
• $\phi\left(n\right)\ =\ \left(p-1\right)\ \cdot\ \left(q-1\right)\ =\ \left(3\ -\ 1\right)\ \cdot\ \left(11-1\right)\ =\ 2\cdot10\ =\ 20$
• als e wähle ich 7. e muss teilerfremd zu ϕ(n) sein und es muss 1 < 3 < ϕ(n) gelten

Jetzt habe ich alles, was ich zur Berechnung des privaten Schlüssels d brauche: ϕ(n) und e

$e\ \cdot\ d\ \ \equiv1\ mod\ \phi\left(n\right)$

Um das ganze übersichtlicher zu machen, setze ich schonmal e und ϕ(n) ein:

$7\ \cdot\ d\ =\ 1\ mod\ 20$ offensichtlich wäre hier d = 3 eine Lösung, aber wir wollen das als ausgerechneten Lösungsweg zeigen. Wir rechnen also erstmal den normalen euklidischen Algorithmus mit 7 und 20 aus - bis zu der Zeile, wo wir als Rest eine 1 stehen haben

$20\ =\ 2\cdot7\ +\ 6$ $7\ =\ 1\cdot6\ +\ 1$

Das ganze stellen wir jetzt um (und ich setz die letzte Zeile gleich nach oben):

$1\ =\ 7\ -\ 1\cdot6$ $6\ =\ 20\ -\ 2\cdot7$ Hier jetzt arbeiten wir von oben nach unten und ersetzen die entsprechenden Zahlen mit den folgenden Zeilen

$1\ =\ 7\ -\ 1\ \cdot\ \left(20\ -\ 2\cdot7\right)$ da wir nur zwei Zeilen haben, ist der Schritt schnell erledigt. Wir rechnen jetzt noch die Klammer aus und addieren alles zusammen - aber behalten die Trennung in 20 und 7 bei

$1\ =\ 7\ -\ 1\cdot20\ +\ 2\cdot7$ $1\ =\ 3\cdot7\ -\ 1\cdot20$

Jetzt kannst du hier sehen, dass das multiplikative Inverse von 7 bezüglich 20 eben die 3 ist, wie oben schon genannt. Das kannst du als d nutzen.

=> öffentlicher Schlüssel (e, n) = (7, 33), privater Schlüssel (d, n) = (3, 33)

Comments

[SpeedyGo55]

Ich check nicht wie ich aus dem d bekomme.

[xxxcyberxxx]

@SpeedyGo55

Ich check nicht wie ich aus dem d bekomme.

Indem du dir die Funktionsweise des euklidischen Algorithmus anschaust. Wikipedia hat dafür ein Beispiel beigefügt: https://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus#Funktionsweise_am_Beispiel

Ich hab aber auch meine ursprüngliche Antwort mal mit einem einfachen Beispiel zu RSA erweitert, kannst dir das ja mal anschauen

[SpeedyGo55]

@xxxcyberxxx

Oh je. Mal schauen, ob ich das In Scratch hinbekomme. Falls du Tipps hast. Gerne melden. Weiss nämlich nicht wie das umstellen soll.

Answer 2

[Schachpapa]

Das ist der Knackpunkt beim RSA Verfahren. Wenn man das so ohne Weiteres berechnen könnte, wäre das Verfahren wertlos.

Kurzum: Es gibt kein (öffentlich bekanntes) Verfahren, dieses d zu ermitteln, wenn n einigermaßen groß ist.

Ups, war Quatsch. Obiges gilt, wenn e und n gegeben ist. Du hast aber phi(n) also die Zerlegung von n in Primfaktoren.

Also erweiterter Euklid, wie andere bereits schrieben.

Comments

[xxxcyberxxx]

Es ist aber laut der Frage nicht n, sondern φ(n) gegeben. Damit lässt sich das multiplikative Inverse bzgl e und damit der private Schlüssel bestimmen

[Schachpapa]

@xxxcyberxxx

Hab's gemerkt, während du deinen Kommentar schriebst ...

Answer 3

[eterneladam]

Das geht mit dem erweiterten euklidischen Algorithmus. Guckst du https://de.wikipedia.org/wiki/RSA-Kryptosystem#Erzeugung_des_%C3%B6ffentlichen_und_privaten_Schl%C3%BCssels