Diese Woche befassen wir uns mit dem Euklidschen Algorithmus und seinen Anwendungen. Dieser grundlegende Algorithmus ist das wichtigste Sprungbrett für das Verständnis eines Großteils der modernen Kryptographie! Dieser Algorithmus findet nicht nur den größten gemeinsamen Teiler zweier Zahlen (was an sich schon ein unglaublich wichtiges Problem ist), sondern seine erweiterte Version bietet auch einen effizienten Weg, diophantische Gleichungen zu lösen und modulare Inversionen zu berechnen.

Die Kryptographie untersucht, wie man Geheimnisse sicher austauschen kann, so dass selbst Lauscher keine Informationen aus dem, was sie hören oder dem Netzwerkverkehr, den sie abfangen, entnehmen können. Einer der populärsten kryptographischen Algorithmen namens RSA basiert auf der einzigartigen ganzzahligen Faktorisierung, dem Chinese Remainder Theorem und der schnellen modularen Potenzierung. In diesem Modul werden wir diese Eigenschaften und Algorithmen untersuchen, die die Bausteine für RSA sind. Im nächsten Modul werden wir diese Bausteine verwenden, um RSA zu implementieren und auch einige clevere Angriffe gegen RSA durchzuführen und einige Geheimcodes zu entschlüsseln.

Die moderne Kryptographie hat sich während des Ersten und Zweiten Weltkriegs am meisten entwickelt, weil jeder jeden ausspioniert hat. Sie werden diese Geschichte hören und sehen, warum einfache Verschlüsselungen nicht mehr funktionierten. Sie werden lernen, dass der gemeinsam genutzte geheime Schlüssel bei jeder Kommunikation geändert werden muss, wenn man will, dass sie sicher ist. Das ist problematisch, wenn die Nachfrage nach sicherer Kommunikation sprunghaft ansteigt und sich die Kommunikationspartner auf verschiedenen Kontinenten befinden können. Sie werden dann das RSA-Kryptosystem studieren, das es den Parteien ermöglicht, geheime Schlüssel auszutauschen, so dass kein Lauscher in der Lage ist, diese geheimen Schlüssel in einer angemessenen Zeit zu entschlüsseln. Danach werden Sie einige Angriffe auf ein falsch implementiertes RSA-Verfahren studieren und später implementieren. So können Sie einige geheime Codes entschlüsseln und sogar eine kleine kryptografische Aufgabe bestehen!