Algorithmische Zahlentheorie und Kryptographie
Vorlesung von O. Forster im WS 2015/16am Mathematischen Institut der LMU München
Mi, Fr 14-16, HS A027, Theresienstr. 39
mit 2std.
Übungen
Mi 16-18 (A027)
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
- Einleitung
- Monoalphabetische Substitutionen
- Der Ring Z/mZ
- Vigenère-Verschlüsselung. Kappa- und Phi-Index
- Das One-Time-Pad
- Endliche Körper. LFSR-Folgen
- Moderne Blockverschlüsselungs-Verfahren
- Das Quadratische Reziprozitäts-Gesetz
- Primzahl-Tests
- Das RSA-Krypto-System
- Das (p-1)- und das Rho-Faktorisierungs-Verfahren
- Faktorisierung mit dem Quadratischen Sieb
- Der Diskrete Logarithmus
- Digitale Signaturen
- Elliptische Kurven
ARIBAS-Code zu einigen besprochenen Algorithmen
- Berechnung von Primitivwurzeln: primroot.ari
- AES-Blockverschlüsselung: AES.ari
- Zum Satz von Pocklington: pockl.ari
- (p-1)- und Rho-Faktorisierungs-Algorithmen: pollfact.ari
- Quadratisches Sieb: QS1fact.ari
- Multipolynomiales Quadratisches Sieb: QSfact.ari
- Pollard Rho und Pohlig/Hellman für Diskreten Logarithmus: dlog_rho.ari
- Secure Hash Algorithm SHA-1: SHA1.ari
- Arithmetik auf Elliptischen Kurven über Z/p: ECarith.ari
- Faktorisierung mit Elliptischen Kurven: ECfact.ari
Literatur
- J. Buchmann: Einführung in die Kryptographie. 5. Aufl. Springer 2010
- O. Forster: Algorithmische Zahlentheorie, 2.Aufl. Springer-Spektrum 2015
- J. Hoffstein / J. Pipher / J.H. Silverman: An Introduction to Mathematical Cryptography. Springer 2009
- C. Karpfinger / H. Kiechle: Kryptologie. ViewegTeubner 2009
- J.S. Kraft / L.C. Washington: An Introduction to Number Theory with Cryptography. Taylor & Francis 2013
- C. Paar / J. Pelzl: Understanding Cryptography: A Textbook for Students and Practitioners. Springer 2011
- D. Stinson: Cryptography. Theory and Practice. Taylor & Francis 2005
- S. Wagstaff: Cryptanalysis of Number Theoretic Ciphers. Chapman and Hall 2002
|
Vorlesungen vergangener Semester
|
| Bücher/Books | Eprints | Software |
Otto Forster 2018-07-06