RSA-Algorithmus -> Inverse d von e berechnen

Dieses Thema im Forum "Sicherheit & Datenschutz" wurde erstellt von -=LuIgI=-, 18. März 2010 .

Schlagworte:
Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. 18. März 2010
    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
     
  2. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

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

    Schau mal hier:
    GGT berechnen (gr

    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
     
  3. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    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
     
  4. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    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.
     
  5. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

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

    wieos verschwindet das - bei der 2 ?
     
  6. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    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:
    Code:
     int m = 72;
     int a = 5;
     int count = 0;
     
     do {
     count++; 
     } while (((a*count) % m) != 1);
    
     System.out.println("Ergebnis: "+count);
    Ausgabe:
    Code:
    Ergebnis: 29
    Siehst also wie einfach es in wirklichkeit ist...
     
  7. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    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
     
  8. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    Windows Taschenrechner auf wissenschaftlich stellen. Wenn der Taschenrechner nicht mehr ausreicht brauchst du ein spezielles Mathe Programm, so eins: Computeralgebrasystem – Wikipedia

    Code:
    40^13 = 671088640000000000000
     
  9. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

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

    Jetzt klappt es
     
  10. 18. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    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!
     
  11. 24. März 2010
    AW: RSA-Algorithmus -> Inverse d von e berechnen

    Wolfram|Alpha: Computational Knowledge Engine

    Dort kannste dir die ganzen sachen auch berechnen lassen!

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

    Knusperkeks
     
  12. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.