Seminar Kryptographie^(VKomm)

Zufall ist Absicht
oder: Wie erzeugt man Zufall?

Schon lange ist klar, dass Zufall bei der Lösung vieler Probleme helfen kann:

Natürliche Prozesse, wie etwa Schadstoffausbreitung in der Luft oder Strömungen um Flugzeugflügel oder Schiffsrümpfe, können nur mit Hilfe von Zufall gut simuliert werden,
Polynome und Zahlen können mit Zufall schneller und einfacher faktorisiert werden,
Optimierungsaufgaben, etwa bei der Erstellung von Flugplänen oder Auslieferungsrouten, können oft erst mit Zufall wenigstens näherungsweise gelöst werden,
Routingprobleme in Netzwerken können mit Zufall einfacher gelöst werden und
Kryptographie wird erst mit Zufall sicher.

Es stellt sich also die Frage, woher bekommt man denn überhaupt diesen Zufall? Darum soll es in diesem Seminar gehen, wobei unser besonderes Augenmerk dem letzten Punkt gilt. Die Kryptographie stellt nämlich die höchsten Anforderungen an den Zufall. Viele Verfahren, die zur Simulation physikalischer und chemischer Prozesse hervorragend geeignet sind, sind in der Kryptographie nicht zu gebrauchen. Das liegt natürlich daran, dass einem Angreifer in der Kryptographie alles zugetraut wird, was innerhalb polynomieller Zeit berechenbar sein könnte, während natürliche Vorgänge da meistens wesentlich harmloser sind.
Wie erzeugt man also Zufall? Und wie gut muß er sein? Welche Kriterien sind richtig? Kann man Zufall berechnen? Woher bekommt man kleine Mengen ``echten'' Zufalls?

Nützliche Parallelveranstaltungen

Blömer, Angewandte Aspekte der Kryptographie^(VKomm).
von zur Gathen, Kryptographische Protokolle^(VKomm).

Organisatorisches

Zeit und Ort:	Montag 14-16 Uhr, C4.224.
Vorbesprechung:	23. April 2001, 14⁰⁰ Uhr, C4.224.
Studiengänge:	Informatik Diplom, Mathematik Diplom, LS II (Medienschein möglich).
Scheinerwerb:	Vortrag und schriftliche Ausarbeitung.
Qualifizierter SN:	Ja.

Themen

30.04.2001	Stromchiffren - Pseudozufallsgeneratoren, Blockchiffren - Pseudozufallsfunktionen (.ps, .gz)	`belgol99` `lub96` `sch99` `sti95`	Marina Schnellen
07.05.2001	Physikalische Erzeugung von Zufall: Echter Zufall (.pdf, .ps.gz)	`agn87` `daviha94` `eascro94` `faimor84`	Kristian Wilkening
14.05.2001	Pseudozufallsgeneratoren, Unterscheider und Propheten (.ps, .gz)	`belgol99` `berfri01` `gat99a` `yao82`	Dani Kräutle
21.05.2001	Der Blum-Blum-Shub Generator (.ps, .gz)	`blublu86` `gat99a` `golmic84` `sti95`	Hubert Hardes
28.05.2001	Der Gennaro-Generator (.ps, .gz)	`gen00`	Julia Faflek
18.06.2001	Der Goldreich-Goldwasser-Micali-Funktionengenerator (.ps, .gz)	`belgol99` `golgol86` `gol99`	Larissa Timajev
25.06.2001	The Nisan-Wigderson Generator (.ps, .gz) Lateinische Zusammenfassung und Einführung (.ps, .gz)	`gat99a` `niswig94`	Kathrin Tofall
02.07.2001	Extraktoren, min-Entropie	`nis96` `tre98`	Ulrich Block
-	Extraktoren II	`reivad01` `sudtre99`

Links und Literatur

agn87: G.B. Agnew, Random Sources for Cryptographic Systems.
belgol99: S. Goldwasser and M. Bellare, Lecture Notes on Cryptography.
berfri01: Stefan Bertels und Barbara Fritsch, Pseudozufallsgeneratoren.
blublu86: L. Blum and M. Blum and M. Shub, A Simple Unpredictable Pseudo-Random Number Generator.
daviha94: Don Davis and Ross Ihaka and Philip Fenstermacher, Cryptographic Randomness from Air Turbulence in Disk Drives.
eascro94: D. Eastlake and S. Crocker and J. Schiller, Randomness Recommendations for Security.
faimor84: R. C. Fairfield and R. L. Mortenson and K. B. Coulthart, An LSI random number generator (RNG).
gat99a: Joachim von zur Gathen, Lecture Notes on Cryptography.
gen00: Rosario Gennaro, An Improved Pseudo-random Generator Based on Discrete Log.
gol99: Oded Goldreich, Fragments of a Book.
golgol86: Oded Goldreich and Shafi Goldwasser and Silvio Micali, How to construct random functions.
golmic84: Shafi Goldwasser and Silvio Micali, Probabilistic Encryption.
lag90: J. C. Lagarias, Pseudorandom Number Generators in Cryptography and Number Theory.
lub96: Michael Luby, Pseudorandomness and cryptographic applications (60 TVB3381).
men96: Alfred J. Menezes and Paul C. van Oorshot and Scott A. Vanstonbe, Handbook of Applied Cryptography.
nis96: Noam Nisan, Extracting Randomness: How and Why -- A survey.
niswig94: Noam Nisan and Avi Wigderson: Hardness vs Randomness.
reivad01: Omer Reingold and Salil Vadhan and Avi Wigderson, Entropy Waves, The Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors.
sch99: Markus Schneider, Über Methoden der Generierung binärer Pseudozufallsfolgen zur Stromverschlüsselung.
sti95: Douglas R. Stinson, Cryptography, Theory and Practice
sudtre99: Madhu Sudan and Luca Trevisan and Salil Vadhan, Pseudorandom Generators Without the XOR Lemma.
tre98: Luca Trevisan, Constructions of Near-Optimal Extractors Using Pseudo-Random Generators.
yao82: Andrew C. Yao, Theory and Applications of Trapdoor Functions.

LaTeX

Literatur:

Michel Goossens, Der LaTeX-Begleiter bzw. The LaTeX companion.
Helmut Kopka, LaTeX bzw. A guide to LaTeX.
Leslie Lamport, Das LaTeX-Handbuch bzw. LaTeX.

Downloads:

teTeX (UNIX compatible systems)
MiKTeX (Windows)
OzTeX und Alpha (Macintosh)

Author: Michael Nüsken, Olaf Müller, last change:

Sommersemester 2001

Seminar Kryptographie(VKomm)

Zufall ist Absicht oder: Wie erzeugt man Zufall?