#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: 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 + Multi-Zitat Zitieren
#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! + Multi-Zitat Zitieren
#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 + Multi-Zitat Zitieren