Modul: Kryptokomplexität I

Wintersemester 2023/2024

• Vorlesung (4 SWS):
  • Dienstag 10:30 - 12:00 im HS 5K in Geb. 25.31, außer
    • am 31.10.2023: im HS 2E in Geb. 22.21
  • Donnerstag 14:30 - 16:00 im HS 6C in Geb. 26.11, außer
    • am 12.10.2023: im HS 2D in Geb. 22.01;
    • am 19.10.2023: im HS 2A in Geb. 22.01;
    • am 26.10.2023: im Interimshörsaal in Geb. 16.12

• Übungen (2 SWS): Informationen zum Ablauf und zur Klausurzulassung finden Sie auf der ILIAS-Seite zu diesem Modul; die Übungsblätter weiter unten auf dieser Website.
  • Mittwoch 08:30 - 10:00 im Raum 25.13.U1.22
  • Donnerstag 08:30 - 10:00 im Raum 25.13.U1.22
  • Freitag 10:30 - 12:00 im Raum 25.12.02.33
  • Freitag 14:30 - 16:00 im HS 5H

Dozent: Prof. Dr. Jörg Rothe

Übungsleitung: Paul Nüsken und Roman Zorn

---

Prüfung:

• findet in Form einer schriftlichen Klausur am Dienstag, dem 13.02.2024 ab 11:30 Uhr im Hörsaal 5B (Geb. 25.11) statt und dauert 90 Minuten.

  Die Nachprüfung findet in schriftlicher Form am 28.03.2024 ab 11:30 Uhr im Hörsaal 5G (Geb. 25.22) statt.

• Bitte bringen Sie Ihren Personal- und Studentenausweis mit zur Klausur. Falls der Platz auf den von uns ausgeteilten Klausurblättern nicht reicht, sollten Sie sich auch eigene Blätter mitbringen.

• Erlaubte Hilfsmittel: Vorlesungsmitschriften, Bücher, Übungsblätter, nicht programmierbare Taschenrechner, Gedächtnis.

• Nicht erlaubte Hilfsmittel: Mobiltelefone und ähnliche Kommunikationsgeräte, Kommiliton/inn/en, programmierbare Taschenrechner.

• Anmeldung: Melden Sie sich rechtzeitig (nach Ihrer PO) vor dem Klausurtermin beim Akademischen Prüfungsamt über das Studierendenportal zur Prüfung an. Haben Sie sich zur Klausur angemeldet, so können Sie bis eine Woche vor der Klausur noch zurücktreten. Die Abmeldung von der Klausur muss über das Akademische Prüfungsamt erfolgen.

Probeklausur:

Musterlösung der Probeklausur.

Übungen:

• Für die Übungen sind die Aufgaben auf den Übungsblättern zu lösen. Die Lösungen werden in den Übungen besprochen und es wird eine aktive Beteiligung aller Studierenden erwartet (also die Vorstellung eigener Lösungen in der Übung). Weitere Informationen zur Klausurzulassung finden Sie auf der ILIAS-Seite zu diesem Modul.

• Die Übungsblätter können jeweils am Dienstag ab 12 Uhr mittags hier von dieser Website heruntergeladen werden.

  Woche Nr.	Übungsblätter	Vorlagen für die Übungen	Musterlösungen
  1	Übungsblatt 1	Vorlage 1	Musterlösung 1
  2	Übungsblatt 2	Vorlage 2	Musterlösung 2
  3	Übungsblatt 3	Vorlage 3	Musterlösung 3
  4	Übungsblatt 4	Vorlage 4	Musterlösung 4
  5	Übungsblatt 5	Vorlage 5	Musterlösung 5
  6	Übungsblatt 6	Vorlage 6	Musterlösung 6
  7	Übungsblatt 7	Vorlage 7	Musterlösung 7
  8	Übungsblatt 8	Vorlage 8	Musterlösung 8
  9	Übungsblatt 9	Vorlage 9	Musterlösung 9
  10	Übungsblatt 10	Vorlage 10	Musterlösung 10
  11	Übungsblatt 11	Vorlage 11	Musterlösung 11
  12	Übungsblatt 12	Vorlage 12	Musterlösung 12

Pingo:

• Pingo 1
• Pingo 2
• Pingo 3
• Pingo 4
• Pingo 5
• Pingo 6

Empfohlene Literatur:

• Jörg Rothe: "Komplexitätstheorie und Kryptologie. Eine Einführung in Kryptokomplexität", eXamen.press, Springer-Verlag, Berlin, Heidelberg, 2008.
• Jörg Rothe: "Complexity Theory and Cryptology. An Introduction to Cryptocomplexity", EATCS Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, 2005.

Ergänzende Literatur zur Kryptologie:

• Douglas R. Stinson: "Cryptography: Theory and Practice", Chapman & Hall/CRC, 2. Auflage, 2002
• Johannes Buchmann: "Einführung in die Kryptographie", Springer-Verlag, 2. Auflage, 2001
• Arto Salomaa: "Public-Key Cryptography", Springer-Verlag, 1990
• Oded Goldreich: "Foundations of Cryptography", Cambridge University Press, 2001
• Bruce Schneier: "Applied Cryptography", John Wiley & Sons, 1996
• Neal Koblitz: "Algebraic Aspects of Cryptography", Springer-Verlag, 2. Auflage, 1999

Ergänzende Literatur zur Komplexitätstheorie:

• Gerd Wechsung: "Vorlesungen zur Komplexitätstheorie", Teubner-Verlag, Stuttgart, 2000.
• Lane A. Hemaspaandra and Mitsunori Ogihara: "The Complexity Theory Companion", EATCS Texts in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, New York, 2002.
• Christos Papadimitriou: "Computational Complexity", 2. Auflage, reprinted with corrections, Addison-Wesley, 1995.
• Danielo Bovet and Pierluigi Crescenzi: "Introduction to the Theory of Complexity", Prentice Hall, 1993.
• D. Du and K. Ko: "Theory of Computational Complexity", John Wiley and Sons, 2000.
• J. Balcázar, J. Díaz, and J. Gabarró: "Structural Complexity I + II", EATCS Monographs on Theoretical Computer Science, Berlin, Heidelberg, New York, vol. I (1995, 2. Auflage), vol. II (1990).
• Ingo Wegener: "Komplexitätstheorie. Grenzen der Effizienz von Algorithmen", Springer-Verlag, Berlin, Heidelberg, New York, 2003.
• Klaus W. Wagner and Gerd Wechsung: "Computational Complexity", D. Reidel Publishing Company, 1986.

Skript:

• Chapter 1: Tasks and Aims of Cryptology (pdf)
• Chapter 2: Some Classical Cryptosystems and Their Cryptanalysis (pdf)

  Zwei Arbeiten von Alan M. Turing zum Thema Häufigkeitsanalyse in der Kryptologie:

  • Paper on Statistics of Repetitions
  • The Applications of Probability to Cryptography

  Und so können Sie sich Ihre eigene Enigma basteln: Eine Keksrolle leeressen, dieses Blatt (pdf) farbig ausdrucken und gemäß eines YouTube-Bastelvideos zusammenkleben, fertig!

• Chapter 3: Perfect Secrecy (pdf)
• Chapter 4: RSA Cryptosystem, Primality, and Factoring (pdf)
• Chapter 5: Tasks and Aims of Complexity Theory (pdf)

  Zur Erinnerung: Turingmaschinen werden in meinem Skript (download als pdf) zur Vorlesung "Theoretische Informatik (Info IV)" in Kapitel 5 ab Seite 97 beschrieben.

• Chapter 6: Complexity Measures and Classes (pdf)
• Chapter 7: Speed-Up, Compression, and Hierarchy Theorems (pdf)
• Chapter 8: Between Logarithmic and Polynomial Space (pdf)
• Chapter 9: Reducibilities and Completeness (pdf)

Außerdem finden Sie hier einige Rätsel, die ebenfalls im Laufe des Semesters ergänzt werden. Lösungen schicken Sie bitte per E-Mail an: rothe@hhu.de mit Subject: "Kryptokomplextät I: Rätsel x", wobei x die Nr. des gelösten Rätsels ist. Einsendeschluss: Silvester 2023.

© Copyright seit 2000 Komplexitätstheorie & Kryptologie • Impressum • Datenschutz • Kontakt