Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » RSA-Verschlüsselung (berechnen von d)

RSA-Verschlüsselung (berechnen von d)

Schüler Gesamtschule, 12. Klassenstufe

Tags: modulo, RSA

Tungsten aktiv_icon

20:45 Uhr, 11.02.2009

Hallo zusammen,

ich habe folgendes Problem. Ich versuche eine RSA-Verschlüsselung für einen Vortrag durchzuführen, also selbst zu erstellen, nur bekomm ich leider d nicht raus (ausser mit z.B.: cryptool) aber ich möchte es ja rechnerisch erhalten.

Folgende Werte hab ich genommen:

p= 5
q= 11
e= 7

n= 55
m= 40

Wie komm ich mit beispielsweise diesen Werten auf d? Ich hab zwar bei diversen Seiten gelesen, man soll den inversen Modulo verwenden, aber ich verstehe diesen gar nicht (hab schon nachgelesen was er bedeutet), die Formeln sind einfach zu kompliziert.

Hab mit dem erweiterten euklidischen Algorithmus versucht d zu berechnen aber es funktioniert irgendwie nicht...

mit irgendwie ist gemeint:
40=7*5+5
7 =1*5+2
5 =2*2+1
2 =1*2+0

Ich vermute das mit dem Umkehren hat etwas damit zutun, auf manchen Seiten wird nämlich der Weg umgekehr (ich denke mal das ist dieses inverse) durchgeführt, aber dort schaltet alles völlig bei mir ab.

Wäre nett wenn mir jemand von euch veranschaulichen könnte wie man d berechnet.

Danke euch schonmal im Vorraus.

MfG
Erik

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich bräuchte bitte einen kompletten Lösungsweg." (setzt voraus, dass der Fragesteller alle seine Lösungsversuche zur Frage hinzufügt und sich aktiv an der Problemlösung beteiligt.)

HP7289 aktiv_icon

23:17 Uhr, 12.02.2009

Ich versuche es mal.

Du hast

p = 5

und

q = 11

N = p \cdot q = 55

φ (N) = (p - 1) \cdot (q - 1) = 4 \cdot 10 = 40

e = 7

ist teilerfremd zu

40

7 d + 40 k = 1 = g g T (7,40)

40 = 5 \cdot 7 + 5

7 = 1 \cdot 5 + 2

5 = 2 \cdot 2 + 1

2 = 2 \cdot 1 + 0

\Rightarrow

1 = 5 - 2 \cdot 2

1 = 5 - 2 \cdot (7 - 1 \cdot 5)

1 = (40 - 5 \cdot 7) - 2 \cdot (7 - 1 \cdot (40 - 5 \cdot 7))

1 = 1 \cdot 40 - 5 \cdot 7 - 2 \cdot 7 + 2 \cdot 40 - 10 \cdot 7

1 = 3 \cdot 40 - 17 \cdot 7

d = - 17

Tungsten aktiv_icon

16:36 Uhr, 13.02.2009

Hi,
danke für deine Bemühung,

ich entnehme deinem Beitrag, dass mit invers modulo einfach das Rückwärts rechnen der Schritte gemein ist... okay soweit ist es mir jetzt klar.

Allerdings sagt mir das Programm etwas anderes, wenn ich den d= -17 verwende, kommt kein plausibles Ergebnis heraus. Sprich ich verschlüssele die Zahl a und nach dem entschlüsseln hab ich j (als Beispiel)...

Also wäre meine Frage jetzt an dich, bzw. an euch andere, wie komm ich von -17 auf 23?

Gruß
Erik

HP7289 aktiv_icon

16:59 Uhr, 13.02.2009

- 17 + 40 = 23 = d

3 - 7 = - 4 = k

Funktioniert, weil es die gleichen Restklassen sind.

Tungsten aktiv_icon

22:59 Uhr, 13.02.2009

Genial... okay vielen Dank. Hat endlich Klick gemacht^^...

Gruß

Erik

SwedSter aktiv_icon

22:51 Uhr, 03.10.2010

hallo tungsten, bzw. an die, die den Thread nochmal lesen sollten, ich habe gerade auch gesehen, dass es bei cryptool nun auch eine ganz gut gemacht animation zum rsa verfahren gibt:

http//cryptool.org/download/RSA/RSA-Flash-de/player.html

800245

575058

	Status: nicht eingeloggt	Noch nicht registriert?