Von Euklid zum RSA-Coding


Jörg Waldvogel
Seminar für Angewandte Mathematik SAM
ETH, 8092 Zürich

Emeritenstamm der ETH, Restaurant Wartmann, Winterthur, 30. April 2007

Der Vortrag gibt eine Einführung in die Verschlüsselungsmethode von Rivest, Shamir und Adleman (1978), genannt RSA-Codierung. Dazu werden zunächst die der elementaren Zahlentheorie entstammenden mathematischen Grundlagen diskutiert. Insbesondere werden algorithmische Aspekte betrachtet und durch konkret durchgerechnete Beipiele illustriert. Eine besonders wichtige Rolle spielt hier der Euklidische Algorithmus.

Die Sicherheit der RSA-Codierug beruht auf der Schwierigkeit der Faktorisierung grosser ganzer Zahlen (über 200 Ziffern). An einem übersichtlichen Beispiel illustrieren wir den Algorithmus des quadratischen Siebes. Die stärksten heute bekannten Faktorisierungsalgorithmen (zur Zeit möglich: 150 bis 200 Ziffern) sind Varianten davon.

Wegen der engen Beziehung des Euklidischen Algorithmus zur modernen Theorie der Kettenbrüche offerieren wir als Anhang einen bisher wenig bekannten Zyklus von 7 Bildern aus der Pionierzeit des elektronischen Rechnens an der ETH, in Bleistift gezeichnet von Alfred Schai, ehem. Direktor des Rechenzentrums der ETH. Die Zeichnungen erinnern an die bei Entwicklung und Bau der ERMETH massgeblich beteiligten Persönlicheiten. Man beachte die gebrochene Kette auf dem Bild von Heinz Rutishauser, einem profunden Kenner und unermüdlichen Vermittler der Theorie der Kettenbrüche.

Folienskript des Vortrages, handgeschrieben (16 Blätter) mit Beilagen (7 Blätter): JWaldvogel.pdf

Bildzyklus ERMETHIA, 7 Bleistiftzeichnungen von Alfred Schai: ERMETH-Schai.pdf


Home Jörg Waldvogel