RSA-Algorithmus -> Inverse d von e berechnen

Hey,

ich habe den RSA-Algorithmus als Thema für meine Facharbeit ausgewählt.
Jetzt bin ich aber an den Punkt angelangt, an dem ich nicht weiter komme.
Unzwar muss ich den Entschlüsselungexponenten d mithilfe des erweiterten euklidischen
Algorithmus berechnen, aber ich komm auf den Algorithmus einfach nicht klar.
Vielleicht kann mir hier einer den Algorithmus an einem Beispiel erklären.

LuIgI

Du willst also quasi einen größten gemeinsamen Teiler (ggT) berechnen?

Schau mal hier: http://www.mathepower.com/ggt.php
Da kannste zwei Zahlen eingeben und auf Berechnen drücken, anschliessend werden dir
ausführliche Berechnungsmöglichkeiten angezeigt; unter anderem der Euklidischer Algorithmus.


Bei Wiki (Erweiterter_euklidischer_Algorithmus, RSA-Kryptosystem) sind doch auch Beispiele dabei.

Mfg Rushh0ur

schau mal da
http://board.raidrush.ws/showthread.php?t=592150&highlight=rsa

Danke im voraus.

Der erweiterten Euklidschen-Algorithmus ist doch da gut erklärt, in deinem Beispiel:

m = 72
a = 5

72 = 14*5 + 2
5 = 2*2 + 1
2 = 2*1 + 0

1 = 5 - 2*2
1 = 5 - 2*(72 - 14*5)

Bis hier hin alles verstanden, aber dann geht es weiter...

1 = 5 - 2*72 + 28*5

1 = 2*72 + 29*5


wie kommen diese beiden Zeilen zustande?
-> 29

Gruß LuIgI

du fängst ganz unten an das neu zu schreiben nach normalen Mathe Gesetzen halt

hier fängst du an das nach 1 aufzulösen:
5 = 2*2 + 1
-> 1 = 5 - 2*2

das hier nach 2 auflösen:
72 = 14*5 + 2
2 = 72 - 14*5

nun zusammensetzen:
1 = 5 - 2*(72 - 14*5)

und jetzt nur noch auflösen, so dass alles passt
1 = 5 - 2*72 + 28*5

Die alleinstehende 5 muss noch weg, deshalb 5 + 28*5 = 29*5 <- diese Umformung lernt man in der 4. klasse^^5+5 = 5*2


Da du sowieso eine Arbeit darüber schreibst solltest du aber auch den Algorithmus für Programmiersprachen angeben... das ist nämlich sehr einfach mit Hilfe von modulo.

du fängst ganz unten an das neu zu schreiben nach normalen Mathe Gesetzen halt

hier fängst du an das nach 1 aufzulösen:
5 = 2*2 + 1
-> 1 = 5 - 2*2

das hier nach 2 auflösen:
72 = 14*5 + 2
2 = 72 - 14*5

nun zusammensetzen:
1 = 5 - 2*(72 - 14*5)

und jetzt nur noch auflösen, so dass alles passt
1 = 5 - 2*72 + 28*5

Die alleinstehende 5 muss noch weg, deshalb 5 + 28*5 = 29*5 <- diese Umformung lernt man in der 4. klasse^^5+5 = 5*2


Da du sowieso eine Arbeit darüber schreibst solltest du aber auch den Algorithmus für Programmiersprachen angeben... das ist nämlich sehr einfach mit Hilfe von modulo.

Wow, danke endlich habe ich es verstanden.
Wsa meinst du mit den programmierten Teil?

wieos verschwindet das - bei der 2 ?

wieos verschwindet das - bei der 2 ?
das verschwindet natürlich nicht^^ hab es in meinem alten post vergessen


1 = - 2*72 + 29*5
1 = -144 + 145


Von Hand ist das sehr schwer und umständlich auszurechnen, aber mit einer Programmiersprache sind es nur paar Zeilen code. Das würde ich jedenfalls reinschreiben^^

Das hier ist ein Beispiel in Java:
int m = 72;
int a = 5;
int count = 0;

do {
count++;
} while (((a*count) % m) != 1);

System.out.println("Ergebnis: "+count);
Ausgabe:
Ergebnis: 29
Siehst also wie einfach es in wirklichkeit ist...

mal ne frage wenn ich eine nachricht wieder entschlüssel will bekomme ich bei nebenrechnungen immer solche zahlen raus
http://www.google.de/#hl=de&source=hp&q=40^13&meta=&aq=f&aqi=g8&aql=&oq=&gs_rfai=&fp=ac502b885c4 c6cfd

wie kann ich sie mir komplett anzeigen lassen?

Gruß LuIgI

Windows Taschenrechner auf wissenschaftlich stellen. Wenn der Taschenrechner nicht mehr ausreicht brauchst du ein spezielles Mathe Programm, so eins: http://de.wikipedia.org/wiki/Computeralgebrasystem

40^13 = 671088640000000000000

Wieso klappt es nicht, wenn ich 40^13 (mod51) rechne, ich bekomme keine 10 raus wie es sein sollte.

Jetzt klappt es

Von Hand ist das sehr schwer und umständlich auszurechnen, aber mit einer Programmiersprache sind es nur paar Zeilen code. Das würde ich jedenfalls reinschreiben^^

Das hier ist ein Beispiel in Java:
int m = 72;
int a = 5;
int count = 0;

do {
count++;
} while (((a*count) % m) != 1);

System.out.println("Ergebnis: "+count);
Ausgabe:
Ergebnis: 29
Siehst also wie einfach es in wirklichkeit ist... VORSICHT: Dieser Quellcode funktioniert nur bei kleinem m und nicht mit praxisnahmen Zahlen welche >1024-bit Länge haben! Für diese Größe der Zahlen musst du den EEA oder andere effiziente Algorithmen zur Invertierung implementieren. Wikipedia zeigt dazu die beiden Varianten zur Implementierung des EEA, welche du verstehen solltest.

Zu deinem Berechnungsproblem: Für Berechnungen 40^13 (mod 51) solltest du die den Square and Multiply Algorithmus ansehen, welcher auch für deine Facharbeit interessant sein sollte, denn neben den mathematischen Grundlagen solltest du auch die Praxis, dh Sicherheit bzw die große Unsicherheit des naiven RSA und die Algorithmen zur Benutzung/Berechnung u.ä. zeigen!

http://www.wolframalpha.com/

Dort kannste dir die ganzen sachen auch berechnen lassen!

Benutz ich immer wenns um größere sachen geht!

Knusperkeks

Alle Posts zum Thema RSA-Algorithmus -> Inverse d von e berechnen, stammen von Mitgliedern des Forums.