Algorithmische Zahlentheorie und Kryptographie

Vorlesung von O. Forster im WS 2015/16
am Mathematischen Institut der LMU München

Mi, Fr 14-16, HS A027, Theresienstr. 39
mit 2std. Übungen Mi 16-18 (A027)

Letzte Vorlesung 2015:   Freitag, 18. Dezember
Erste Vorlesung 2016:     Freitag, 8. Januar
Letzte Vorlesung WS:     Freitag, 5. Februar 2016

Beschreibung
Die Vorlesung gibt zunächst eine Übersicht über die klassische Kryptographie und geht dann auf die moderne Kryptographie, vor allem die Public Key Kryptographie, ein. Ein Merkmal der modernen Kryptographie ist die Benutzung mathematischer Methoden, insbesondere aus der Zahlentheorie. Deshalb bietet es sich an, parallel zur Darstellung der Kryptographie eine Einfürung in die einschlägige Zahlentheorie und deren algorithmische Aspekte zu geben.
Einige Stichpunkte, kryptographische Seite: Monoalphabetische Substitutionen, One-Time-Pad, moderne Blockverschlüsselungs-Verfahren (DES, AES), Betriebsmodi, RSA-Verfahren, Diffie-Hellman Schlüsselaustausch, ElGamal-Verschlüsselung, Digitale Signaturen, Hash-Funktionen.
Zahlentheoretische Seite: Euklidischer Algorithmus, Chinesischer Restsatz, Primitivwurzeln modulo p, Quadratisches Reziprozitätsgesetz, Wurzelziehen modulo p, probabilistische und deterministische Primzahltests, Faktorisierungs-Algorithmen, Diskreter Logarithmus.

Vorkenntnisse: Anfänger-Vorlesungen Lineare Algebra, Analysis.
Nützlich ist auch eine Vorlesung Algebra, sowie Spass am Programmieren.

Für: Interessierte Studierende der Mathematik, Physik und Informatik

Inhalt

  1. Einleitung
  2. Monoalphabetische Substitutionen
  3. Der Ring Z/mZ
  4. Vigenère-Verschlüsselung. Kappa- und Phi-Index
  5. Das One-Time-Pad
  6. Endliche Körper. LFSR-Folgen
  7. Moderne Blockverschlüsselungs-Verfahren
  8. Das Quadratische Reziprozitäts-Gesetz
  9. Primzahl-Tests
  10. Das RSA-Krypto-System
  11. Das (p-1)- und das Rho-Faktorisierungs-Verfahren
  12. Faktorisierung mit dem Quadratischen Sieb
  13. Der Diskrete Logarithmus
  14. Digitale Signaturen
  15. Elliptische Kurven
ARIBAS-Code zu einigen besprochenen Algorithmen Literatur
Otto Forster (email), 2015-09-11