Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » RSA Verschlüsselung, Privater Schlüssel D berechne

RSA Verschlüsselung, Privater Schlüssel D berechne

Universität / Fachhochschule

Kryptologie

Tags: Erweiterter Euklidischer Algorithmus, Kryptologie, RSA

Kiwi92 aktiv_icon

19:09 Uhr, 13.07.2014

Hallo ich habe ein Problem und zwar will ich für die RSA-Verschlüsselung den Privaten Schlüssel

(d)

berechnen.

Gegeben ist:

e = 7, (p - 1) (q - 1) = 40

also ggT(40,7)

Hier schon meine erste Frage macht das ein Unterschied? Also ggT(7,40) oder ggT(40,7)?

Dann Rechne ich:

\frac{40}{7} = 5 R 5 \Leftrightarrow 40 = 5 \cdot 7 + 5

\frac{7}{5} = 1 R 2 \Leftrightarrow 7 = 1 \cdot 5 + 2

\frac{5}{2} = 2 R 1 \Leftrightarrow 5 = 2 \cdot 2 + 1

\frac{2}{1} = 2 R 0 \Leftrightarrow 2 = 2 \cdot 1 + 0

Und jetzt steht da:
Also gilt

1 = 5 - 2 \cdot 2

Ich versteh das man das nun Rückwerts hochrechnen kann, aber warum

1 = 5 - 2 \cdot 2

?
Jedenfalls wird dann immer die Zeile davor genommen und den Wert dafür eingesetzt und am Ende erhält man

3 \cdot 40 - 17 \cdot 7

Woher weis man das

- 17 mod 40

das

d

ist und nicht die 3?

Grüße

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

Quaaam aktiv_icon

20:20 Uhr, 14.07.2014

Hallo Kiwi92,

Es gilt: ggT(40,7)=ggT(7,40).

Nunja, wie kommt man denn auf

1 = 5 - 2 \cdot 2

?
Sieh die 'mal deine dritte Gleichung an.

Am Ende bekommt man

3 \cdot 40 - 17 \cdot 7 = 1

.
Rechnet man diese Gleichung

mod 40

dann steht da:

- 17 \cdot 7 = 1 (mod 40)

Also ist

- 17

das inverse Element zu 7.

LG Quam

Kiwi92 aktiv_icon

13:55 Uhr, 15.07.2014

Hallo vielen dank diese Aufgabe habe ich nun gelöst.
Zur Übung habe ich mich noch an einer anderen Aufgabe versucht und komischerweise kam ich dann trozdem nicht auf das

d

p = 5 q = 13 N = 65 φ

von

N = 48

ggt(48,23)

48 : 23 = 2 R 2

2 = 48 - 2 \cdot 23

23 : 2 = 11 R 1

1 = 23 - 11 \cdot 2

2 : 1 = 2 R 0

0 = 2 - 2 \cdot 1

1 = 23 - 11 \cdot 2

1 = 23 - 11 (48 - 2 \cdot 23)

1 = - 11 \cdot 48 + 14 \cdot 23

d = 14

? Online RSA Generator sagt

d = 23

.

Ich komme nicht weiter bitte um hilfe :-)

Stephan4

18:27 Uhr, 15.07.2014

Mal ganz langsam:

1 = 23 - 11 (48 - 2 \cdot 23)

= 23 - 11 \cdot 48 + 11 \cdot 2 \cdot 23

= - 11 \cdot 48 + 23 + 11 \cdot 2 \cdot 23

= - 11 \cdot 48 + 23 \cdot (1 + 11 \cdot 2)

= - 11 \cdot 48 + 23 \cdot (1 + 22)

= - 11 \cdot 48 + 23 \cdot 23

Deshalb.

Kiwi92 aktiv_icon

22:09 Uhr, 15.07.2014

vielen Dank habs nun verstanden, ein ganz kleiner Fehler im letzten Schritt beim zusammenrechnen.

1178021

1177724

	Status: nicht eingeloggt	Noch nicht registriert?