RSA - Algorithmus: Verständnisfrage

Dieses Thema im Forum "Sicherheit & Datenschutz" wurde erstellt von aRiGaT0, 8. Mai 2009 .

  1. 8. Mai 2009
    Zuletzt von einem Moderator bearbeitet: 14. April 2017
    Hallo,

    bin gerade dabei, mir den RSA-Verschlüsselungs-Algo anzuschauen. Doch leider komme ich an folgender Stelle nicht weiter:
    Bild
    Kann mir bitte jemand helfen? Den erweiterten Euklidschen-Algorithmus versteh ich nicht wirklich.

    Link ist folgender:

    http://www.mathe-online.at/materialien/Franz.Embacher/files/RSA/

    Danke
     
  2. 8. Mai 2009
    AW: RSA - Algorithmus: Verständnisfrage

    Mit dem Erweiterten Euklidschen Algorithmus berechnet man: EEA( a, b ) = ggT( a, b ) = s * a + t * b. Sofern man a teilerfremd zu b wählt, ist der ggT = 1 und aus der Summe folgt: 1 = s * a + t * b. Damit kann man diese Rechnung modulus a oder b reduzieren und erhält:
    1 = s * a + t * b mod a = 1 = t * b
    ODER
    1 = s * a + t * b mod b = 1 = s * a
    Hier sieht man nun, dass t * b bzw. s * a 1 ergeben, sodass t die Inverse zu b bzw s die inverse zu a darstellt! Mit den EEA lässt sich also die Inverse einer Zahl berechnen!
     
  3. 8. Mai 2009
    AW: RSA - Algorithmus: Verständnisfrage

    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)
    1 = 5 - 2*72 + 28*5

    1 = 2*72 + 29*5

    -> 29
     
  4. Video Script

    Videos zum Themenbereich

    * gefundene Videos auf YouTube, anhand der Überschrift.