Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » erweiterter euklidischer Algorithmus/RSA-Algorithm

erweiterter euklidischer Algorithmus/RSA-Algorithm

Schüler Gesamtschule, 12. Klassenstufe

Tags: euklidischer, RSA

XenoX aktiv_icon

17:42 Uhr, 04.01.2009

Hallo Leute,

also meine Frage bezieht sich eig. direkt auf den RSA-Algorithmus:

Ich hab die beiden Primzahlen

p = 17

und

q = 23

also

n = 391 (n = p \cdot q)

Euler(n)(sorry weiß nicht wie das Zeichen von Euler geht)=

(p - 1) \cdot (q - 1)

= 352

Gut, das war kein Problem, die erste Frage ist, die Zufallszahl / öffentlicher Schlüssel

e,

muss die kleiner sein als das euler(n) oder kann diese auch größer sein

(z . B 763

(ggT

(352,763) = 1)

?

So Frage 2: Wie berechnet man nun mit Hilfe des erweiterten Euklidischen Algorithmus den Geheimschlüssel ? (falls eine größere Zahl als

(n)

nicht geht, würde ich die Zahl 243(ebenfalls ggT(243,352)=1) verwenden). Wie stellt man den erweiterten Euklidischen Algorithmus auf?

Ich komm mit dem erweiterten Euklidischen Algorithmus im moment einfach nicht klar!
Hoffe ihr könnt mir helfen!
Grüße XenoX / Philipp :-)

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

FelixK

17:02 Uhr, 05.01.2009

Das ganze wird in Wikipedia eigentlich ganz gut erklärt: de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

Das ganze ist ein Algorithmus, den du also Schrittweise durchgehen musst.
Wesentlich einfacher ist es eine kleinere Zahl zu nehmen, es verbietet dir aber niemand eine größere zu nehmen (meines Wissens).

Zu deinem Beispiel:

Ich nehme mal Euler(N)=352 und

e = 243 :

Dadurch sieht das ganze erstmal so aus:

352 = 1 \cdot 243 + 109

243 = 2 \cdot 109 + 25

109 = 4 \cdot 25 + 9

25 = 2 \cdot 9 + 7

9 = 1 \cdot 7 + 2

7 = 3 \cdot 2 + 1

2 = 2 \cdot 1 + 0

\Rightarrow 1

ist ggT (das war aber schon bekannt ;-) doch nun kommen wir auf die beiden Koeffizienten mit Hilfe dieser Ergebnisse:

109 = 1 \cdot 352 - 1 \cdot 243

25 = 1 \cdot 243 - 2 \cdot 109 = 1 \cdot 243 - 2 \cdot (1 \cdot 352 - 1 \cdot 243) = - 2 \cdot 352 + 3 \cdot 243

9 = 1 \cdot 109 - 4 \cdot 25 = 1 \cdot (1 \cdot 352 - 1 \cdot 243) - 4 \cdot (- 2 \cdot 352 + 3 \cdot 243) = 9 \cdot 352 - 13 \cdot 243

7 = 1 \cdot 25 - 2 \cdot 9 = 1 \cdot (- 2 \cdot 352 + 3 \cdot 243) - 2 \cdot (9 \cdot 352 - 13 \cdot 243) = - 20 \cdot 352 + 29 \cdot 243

2 = 1 \cdot 9 - 1 \cdot 7 = 1 \cdot (9 \cdot 352 - 13 \cdot 243) - 1 \cdot (- 20 \cdot 352 + 29 \cdot 243) = 29 \cdot 352 - 42 \cdot 243

1 = 1 \cdot 7 - 3 \cdot 2 = 1 \cdot (- 20 \cdot 352 + 29 \cdot 243) - 3 \cdot (29 \cdot 352 - 42 \cdot 243) = - 107 \cdot 352 + 155 \cdot 243

Damit hast du

d = - 107

und

k = 155,

wobei

d

dein privater Schlüssel und

k

Müll ist.

XenoX aktiv_icon

17:36 Uhr, 05.01.2009

Top :-) Danke dir habs verstanden,

hatte Probleme die Gleichungen aufzustellen, jetzt hab ichs aber kapiert :-)

Enrico aktiv_icon

11:47 Uhr, 29.08.2013

Ein freundlicher Gast-User hat mich gebeten folgendes hier beizutragen:

"Bei der Antwort von FelixK ist nicht

d = - 107

und

k = 155,

sonder genau andersherum.

d = 155,

dann funktioniert auch die Überprüfung von

d \cdot e mod Φ (n) = 1

1110361

561444

	Status: nicht eingeloggt	Noch nicht registriert?