Das
Seminar beschäftigt sich mit Themen aus der Algebra und
Zahlentheorie im Zusammenspiel mit interessanten
kryptographischen Anwendungen.
Zeitabschätzung
elementarer Algorithmen. Erläutern Sie die
Zeitabschätzung von Algorithmen (groß-O-Notation).
Erinnern Sie an einige elementare Algorithmen wie die Umwandlung
von Dezimalzahlen in Binärzahlen und auch an den
Euklidischen Algorithmus bzw. den Chinesischen Restsatz. Wie
schnell können die besprochenen Algorithmen durchgeführt
werden?
Endliche
Körper. Zu jeder Primzahlpotenz q gibt es einen (bis auf
Isomorphie eindeutig bestimmten) Körper mit q Elementen. Wie
rechnet man explizit etwa in einem Körper mit 9 Elementen?
Kryptosysteme,
Public Key und RSA. Bei der Verschlüsselung von Daten
kommt es darauf an, dass verschlüsselte Daten nur von
berechtigten Lesern entschlüsselt werden können. Wie
funktionieren kryptographische Verfahren mit öffentlichem
Schlüssel etwa für die Kommunikation im Internet? Die
Sicherheit des RSA-Verfahrens beruht darauf, dass zwei große
Primzahlen einfach (schnell) zu multiplizieren sind, die
umgekehrte Operation, das Zerlegen in die Primfaktoren jedoch
schwierig ist.
Diskreter
Logarithmus, ElGamal, Massey-Omura. Statt der Multiplikation
von großen Primzahlen wird nun das Potenzieren von Zahlen
in großen endlichen Körpern betrachtet. Auf der
Schwierigkeit der umkehrenden Operation (diskreter Logarithmus)
beruhen einige Kryptosysteme.
Quadratische
Reste und Jacobi-Symbol. Ist p>2 eine Primzahl und
berechnet man Quadrate von ganzen Zahlen modulo p, so treten die
quadratischen Reste (modulo p) auf. Man definiert Legendre- und
Jacobi-Symbole. Skizzieren Sie einen Beweis des Quadratischen
Reziprozitätsgesetzes.
Primzahltests
und Pseudoprimzahlen. Der kleine Satz von Fermat führt
zu einem ersten Primzahltest. Besteht eine Zahl n den Test nicht,
so ist n sicher keine Primzahl. Besteht n den Test, könnte n
auch eine Pseudoprimzahl sein. Beschreiben Sie die Tests von
Solovay-Strassen und Miller-Rabin.
Die
Rho-Methode. Stellen Sie die Rho-Methode von Pollard zur
Faktorisierung von Zahlen vor.
Faktorbasen
und Kettenbrüche. Mit Hilfe von Faktorbasen und
Kettenbrüchen gelangt man zu sehr effizienten
Faktorisierungsmethoden.
Elliptische
Kurven - Kryptographie. Eine Addition von Punkten auf
elliptischen Kurven führt zu einer Gruppenstruktur. Es gibt
ein Analogon des diskreten Logarithmus-Problems. Wie
funktionieren nun kryptographische Verfahren - etwa ElGamal -
über elliptischen Kurven?
Elliptische Kurven
- Faktorisierung von Zahlen. Im letzten Vortrag soll gezeigt
werden, dass elliptische Kurven auch für die Faktorisierung
von Zahlen genutzt werden können.