Question

Berechnen Sie einen öffentlichen und dazu passenden privaten Schlüssel für die Primzahlen p = 229 und q = 233, wobei die beiden Zahlen des öffentlichen Schlüssels größer 30 sein sollen.

Answer 1

Wähle ein \(e\) mit \(30\leq e \leq (p-1)(q-1)\) und \(\operatorname{ggT}(e, (p-1)(q-1)) = 1\).

Öffentlicher Schlüssel ist \((e,pq)\).

Privater Schlüssel ist \((d,pq)\) mit \(de \equiv 1\mod (p-1)(q-1)\).

Comments

Also ich habe jetzt e=31 gewählt und meine diophantische Gleichung gelöst ist

-5•53357+6•31.

ich komm jetzt im letzten schritt leider nicht mehr weiter

---

Hast du die diophantische Gleichung

        \(31 \cdot d \equiv 1\mod 52896\)

gelöst?

---

meine Gleichung war 31x+52896y=1

diese hab ich dann mit dem erweiterten euklidischen Alg. gelöst

Ich bin jetzt glaube ich doch noch weitergekommen und habe nun d=-4

---

d = -4 ist falsch.

---

und d=1 oder warum it -4 falsch

---

\(d = 1\) ist ebenso falsch.

\(d = -4\) ist falsch, weil

        \(31 \cdot (-4) \not \equiv 1 \mod 52896\)

ist.

---

was wären dann richtig?

---

Die richtige Lösung ist irrelevant. Relevant ist, ob du den erweiterten euklidischen Algorithmus korrekt anwenden kannst.

Answer 2

Vielleicht hilft Dir

https://www.geogebra.org/m/wn4bappz

weiter - die modinverse berechnet man z.B. mit dem erweiterten Euklid

\(\small {\begin{array}{|r|r|r|r|r|r|}a&b&q&r&x&y \\ 52896&31&1706&10&-3&5119 \\ 31&10&3&1&1&-3 \\ 10&1&10&0&0&1 \\ \end{array}}\)