Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » RSA-Verschlüsselung

RSA-Verschlüsselung

Schüler

Tags: RSA, Verschlüsselung

LivoKing aktiv_icon

01:22 Uhr, 05.03.2013

Wie ist die Rechnung bei RSA auszuführen bzw. wie muss man da Vorgehen?

Gegeben sind Verschlüsslungsparameter

p = 97, q = 89

und

e = 13

a)

Berechne den öffentlichen und privaten Schlüssel

b)

Verschlüssele die folgenden Zahlen:

m 1 = 18; m 2 = 30; m 3 = 67;

c)

Entschlüssele die Geheimtexte aus Aufgabenteil

b)

d)

Welche Werte für

e

sind erlaubt / nicht erlaubt? Warum?

zu a (mein Ansatz):

Berechnung des RSA-Moduls:

n = p \cdot q

n = 97 \cdot 89 = 8633

Anwendung der eulersche Phi-Funktion:

φ (n) = (p

–

1) (q

–

1)

φ (n) = (97

–

1) (89

–

1) = 8448

Yokozuna aktiv_icon

14:14 Uhr, 05.03.2013

Hallo,

fangen wir mal mit Teil

a)

an:

den öffentlichen Schlüssel hast Du ja schon. Er lautet:

(e, n) = (13,8633)

Jetzt mußt Du noch den privaten Schlüssel berechnen. Dazu braucht man eine Zahl

d

mit der Eigenschaft

e \cdot d = 1 mod φ (n)

Das bedeutet, daß es eine ganze Zahl

k

gibt mit

e \cdot d = 1 + k \cdot φ (n) \Rightarrow e \cdot d - k \cdot φ (n) = 1 \Rightarrow e \cdot d + k' \cdot φ (n) = 1,

wobei

k' = - k

ist.
Setzen wir mal die bekannten Zahlen ein:

13 \cdot d + 8448 \cdot k' = 1

Eine Lösung dieser diophantischen Gleichung und damit

d

bekommt man mit dem erweiterten Euklidischen Algorithmus. Eine Erklärung findest Du

z . B

. auf der Seite
http//de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus
Ein sehr gutes Video zu diesem Thema ist
http//www.youtube.com/watch?v=QORmBQo8-j0
Dieses Video besteht glaube ich aus 3 Teilen.

Viele Grüße
Yokozuna

LivoKing aktiv_icon

19:20 Uhr, 08.04.2013

Wie errechnet man jetzt

d,

dass habe ich leider nicht ganz verstanden.

Also wie erkennt man welche natürliche Zahl man für Konstante

s

benötigt, bei dieser Formel:

d = (s \cdot (p - 1) \cdot (q - 1) + 1) : e

Yokozuna aktiv_icon

20:21 Uhr, 08.04.2013

Hallo,

da gibt es zwei Möglichkeiten. Bei nicht zu großen Zahlen kann man die Lösung durch Probieren finden. Man probiert der Reihe nach für

s

alle ganzen Zahlen beginnend bei 1 aus und schaut, ob

s \cdot φ

durch

e

ohne Rest teilbar ist. Ist

s \cdot φ

durch

e

ohne Rest teilbar, dann hat man

d

gefunden. Von Hand ist das etwas mühsam, aber mit einem programmierbaren Taschenrechner durchaus lösbar.
Diese Methode kommt natürlich bei größeren Zahlen nicht mehr in Betracht. Dann bleibt nur noch die Ermittlung von

d

und

k

(wobei das

k

letztendlich nicht interessiert) aus der diophantischen Gleichung

13 \cdot d + k \cdot 8448 = 1

mit Hilfe des erweiterten euklidischen Algorithmus. Ich hatte Dir ja in meiner ersten Antwort den Link
http//www.youtube.com/watch?v=QORmBQo8-j0
genannt. Dort wird der erweiterte euklidische Algorithmus meiner Meinung nach sehr gut erklärt (ich kann es auch nicht besser erklären). Hast Du Dir denn das Video (es sind insgesamt 3 Teile) mal angeschaut?

Viele Grüße
Yokozuna

LivoKing aktiv_icon

20:25 Uhr, 08.04.2013

Habe es gesehen in youtube, aber so recht klar ist mir das noch nicht geworden.

Ich habe es mal ausgeführt mit dem Euklidischen Algorithmus ,nur welche Zahlen muss ich da nehmen, weil bei

e -

nehme ich die Zahl als Divident und teile es durch eine natürliche Zahl.

Nur hier:
d=(s⋅(p−1)⋅(q−1)+1):e

ist mir das noch unklar.

Yokozuna aktiv_icon

22:26 Uhr, 08.04.2013

Ich rechne Dir das mal mit Deinen Zahlen vor. Es fängt damit an, daß man mit dem euklidischen Algorithmus den ggt von

8448

und

13

bestimmt. Eigentlich bräuchte man in diesem Fall den euklidischen Algorithmus nicht, um den ggt von

8448

und

13

zu bestimmen, da dieser ja 1 ist

(e = 13

ist ja teilerfremd zu

φ = 8448)

. Aber wenn man danach den euklidischen Algorithmus sozusagen rückwärts rechnet, bekommen wir eine Darstellung der Form

k \cdot 8448 + 13 \cdot d = 1

.
Also fangen wir an. Wenn wir

8448

durch

13

dividieren erhalten als Ergebnis a und den Rest

r

. Man kann das schreiben als:

8448 = a \cdot 13 + r

Nun kann man a und

r

leicht ausrechnen. Es ist:

8448 = 649 \cdot 13 + 11

Nun wird das ganze wiederholt, wobei die

13

jetzt den Platz von

8448

und der Rest

11

den Platz von

13

einnimmt:

13 = a \cdot 11 + r

Das ist einfach:

13 = 1 \cdot 11 + 2

Das ganze nochmal:

11 = 5 \cdot 2 + 1

und schließlich

2 = 2 \cdot 1 + 0

Wenn der Rest 0 ist, haben wir den ggt gefunden. Er steht unmittelbar vor dem Rest 0 und heißt 1. Ich schreibe die 4 Gleichungen noch einmal untereinander:

1) 8448 = 649 \cdot 13 + 11

2) 13 = 1 \cdot 11 + 2

3) 11 = 5 \cdot 2 + 1

4) 2 = 2 \cdot 1 + 0

Nun gehen wir die Zeilen von unten nach oben zurück. Die vorletzte Gleichung

3)

wird nach dem Rest 1 aufgelöst:

⋆) 1 = 11 - 5 \cdot 2

Nun lösen wir Gleichung

2)

nach 2 auf und setzen den dabei entstehenden Ausdruck in die Gleichung

⋆)

ein:

2 = 13 - 1 \cdot 11 \Rightarrow

⋆) 1 = 11 - 5 \cdot 2 = 11 - 5 \cdot (13 - 1 \cdot 11) = 11 - 5 \cdot 13 + 5 \cdot 11 = 6 \cdot 11 - 5 \cdot 13

Und zum Schluß lösen wir noch Gleichung

1)

nach

11

auf und setzen den dabei entstehenden Ausdruck in die Gleichung

⋆)

ein:

11 = 8448 - 649 \cdot 13 \Rightarrow

⋆) 1 = 6 \cdot 11 - 5 \cdot 13 = 6 \cdot (8448 - 649 \cdot 13) - 5 \cdot 13 = 6 \cdot 8448 - 6 \cdot 649 \cdot 13 - 5 \cdot 13 =

6 \cdot 8448 - 3894 \cdot 13 - 5 \cdot 13 = 6 \cdot 8448 - 3899 \cdot 13

Damit haben wir

⋆) 1 = 6 \cdot 8448 - 3899 \cdot 13

Das ist eine Darstellung der Form

k \cdot 8448 + 13 \cdot d = 1

Damit haben wir eine Lösung mit

k = 6

und

d = - 3899

.
Wir hätten nun aber für

d

gern eine positive ganze Zahl zwischen 1 und

8447

. Nun, wenn

d = - 3899

eine Lösung der Gleichung

⋆)

ist, dann ist auch

d = - 3899 + n \cdot 8448

eine Lösung,

z . B

d = - 3899 + 8448 = 4549

. Damit haben wir unser

d = 4549

gefunden. Du kannst Dich selbst davon überzeugen, daß

13 \cdot 4549 = 1 mod 8448

ist.
Ich hoffe, daß alles nachvollziehbar ist.

Viele Grüße
Yokozuna

LivoKing aktiv_icon

22:41 Uhr, 08.04.2013

Ich habe es mal ganz blöde geteilt:

der vorletzte step:

11 : 2 =

Rest 1

also wird für

s, s = 1

eingesetzt, in dieser gleichung:?

d=(s⋅(p−1)⋅(q−1)+1):e

Yokozuna aktiv_icon

23:17 Uhr, 08.04.2013

Das kannst Du doch ganz leicht selbst nachprüfen, daß das nicht richtig ist. Wenn Du da

s = 1

einsetzt, hast Du

d = \frac{1 \cdot 8448 + 1}{13} = \frac{8449}{13}

und das ist leider keine ganze Zahl.
Du mußt das schon so rechnen, wie ich das oben vorgemacht habe:

6 \cdot 8448 - 3899 \cdot 13 = 1 \Rightarrow

6 \cdot 8448 + (- 3899) \cdot 13 = 1 \Rightarrow

6 \cdot 8448 + (- 3899 + 8448 - 8448) \cdot 13 = 1 \Rightarrow

6 \cdot 8448 + (4549 - 8448) \cdot 13 = 1 \Rightarrow

6 \cdot 8448 + 4549 \cdot 13 - 8448 \cdot 13 = 1 \Rightarrow

- 7 \cdot 8448 + 4549 \cdot 13 = 1 \Rightarrow

4549 \cdot 13 = 7 \cdot 8448 + 1 \Rightarrow

4549 = \frac{7 \cdot 8448 + 1}{13}

Also ist

s = 7

.

Viele Grüße
Yokozuna

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1086555

1078991

	Status: nicht eingeloggt	Noch nicht registriert?