Achtung:                                                                                                                Stand: 10.04.2008

Anstelle der hier zunächst angekündigten Lehrveranstaltung

"Programmieren mathematischer Fragestellungen aus dem Grundstudium
   mit Excel / VBA - Möglichkeiten und Einschränkungen"

werde ich im SS 2008 aufgrund des vom Fachbereich angekündigten unerwartet aufgetretenen Bedarfs ein

"ProSeminar / Seminar über Zahlentheorie/Kryptographie (lehramtsspezifisch)"

im Rahmen des Bachelorstudiums Mathematik als Kernfach oder als Modul anbieten.

Eine Vorbesprechung mit Themenverteilung hat am 19.03.08  um 10 Uhr in Raum K 40 des Informatik-Gebäudes Takustr. 9 stattgefunden. Das Seminar beginnt wegen der am 16. April stattfindenden Immatrikulationsfeier für das SS erst am 23.04.08 um 10 Uhr c.t. (ebenfalls im Raum K 40 des Informatik-Gebäudes Takustr. 9).

Für die Seminarteilnehmer ist ein "schwarzes Brett" im Internet eingerichtet worden, auf dem Informationen und Ausarbeitungen von Seminarvorträgen, sowie Tutorien zu einzelnen Themen zu finden sind. Die Teilnehmer am Seminar können unter Angabe eines in der Vorbesprechung ausgegebenen Benutzernamens und Passworts hier auf diese Seite zugreifen. Wenn Sie Ihr Passwort vergessen haben, schreiben Sie mir bitte eine e-mail: berendt@zedat.fu-berlin.de.

Das Seminar war ursprünglich für 10 Vorträge konzipiert und in zwei Teile gegliedert. In 4 Vorträgen sollte ein Überblick über die "klassischen" Verfahren der Kryptographie, in weiteren 6 Vorträgen eine Einführung in die modernen Methoden gegeben werden. Aufgrund der vorliegenden Anmeldezahlen hält sich der Andrang von Interessenten jedoch offenbar in Grenzen. Ich habe daher eine neue reduzierte Disposition für das Seminarprogramm entworfen: Wir werden uns bei der Gliederung des Seminars auf diejenigen modernen (asymmetrischen) Kryptosysteme beschränken, die wesentlich auf Ergebnissen der elementaren Algebra/Zahlentheorie beruhen. Als Voraussetzung für eine sinnvolle Mitarbeit gehe ich daher davon aus, dass die Seminarteilnehmer die LV Elementare Algebra/Zahlentheorie (oder äquivalente Veranstaltungen) mit Erfolg besucht haben. Einige benötigte Voraussetzungen, die nicht notwendig Bestandteil der genannten LV sind, werden im Rahmen des Seminars selbständig entwickelt. Das Seminar wird deshalb wechselweise Stoffvermittlung seitens des Dozenten und Vorträge der Seminarteilnehmer enthalten. Die Beiträge der Teilnehmer sollten dem Dozenten in der Regel spätestens 14 Tage vor dem Vortrag im Plenum schriftlich in einem Umfang von 8 - 14 Seiten DIN A4 per e-mail zugesandt werden. Sie werden dann zur Kenntnisnahme und zur Vorbereitung für alle Teilnehmer auf das schwarze Brett (s.o.) gestellt. Es wird angestrebt, dass die Vortragenden die vorgestellten Algorithmen in einfachen Beispielprogrammen computergestützt in einer (nicht zu exotischen) Sprache ihrer Wahl implementieren und als Demo-Programme in den Vortrag integrieren.

Eine vorläufige Übersicht über das Seminarprogramm sieht derzeit wie folgt aus:

"Moderne" Kryptographie auf zahlentheoretischer Grundlage

  1. Wdhlg: Grundbegriffe aus der Zahlentheorie (Dividierbarkeit, Kongruenzen, Restklassen und endliche Körper)

  2. Wdhlg: Rechenaufwand für Algorithmen mit grossen Zahlen,

  3. "Grosse" Zahlen und ihre Probleme: Primzahlen, Faktorisierung, diskreter Logarithmus, (vorgemerkt: A. Schüler)

  4. Asymmetrische Kryptosysteme:  Grundidee, Einweg- und Falltürfunktionen, kryptographische Protokolle, (vorgemerkt: M. Jain)

  5.  Pseudozufallsgeneratoren,

  6. Diffie-Hellman-Schlüsselaustausch,

  7. El-Gamal und verwandte asymmetrische Verfahren,

  8. RSA, (vorgemerkt: S. Hoedt)

  9. Quadratische Reste und kryptographische Anwendungen,

  10. Zero-Knowledge-Protokolle

(Diese Disposition kann bei Bedarf modifiziert werden.)

Alle Interessenten, die an dem Seminar teilnehmen möchten, werden gebeten, mich per e-mail (berendt@zedat.fu-berlin.de) davon zu unterrichten, speziell dann, wenn sie an einem Vortrag über einen oder mehrere der Dispositionspunkte interessiert sind.

Falls Sie sich schon einmal ein wenig mit der Materie befassen möchten -  hier einige (in keiner Weise vollständige) Literaturempfehlungen:

Berendt, G.: Elemente der Kryptologie. In: Schulz, R.H.: Mathematische Aspekte der angewandten Informatik. BI-Wissenschaftsverlag Mannheim, Wien, Zürich

Beutelspacher A. et al.: Kryptographie in Theorie und Praxis. Vieweg

Brands, G.: Verschlüsselungsalgorithmen. Vieweg

Buchmann, J.: Einführung in die Kryptographie. Springer

Horster, P.: Kryptologie. BI-Wissenschaftsverlag Mannheim, Wien, Zürich

Miller, M.: Symmetrische Verschlüsselungsverfahren. Teubner

Für eher praktische Anwendungen:

Schneier, B.: Applied Cryptography. Wiley&Sons

Etwas anspruchsvollere Mathematik:

Koblitz, N.: A Course in Number Theory and Cryptography. Springer

Koblitz, N.: Algebraic Aspects of Cryptography. Springer

___

*********************************************************

Angesichts des zahlentheoretischen Hintergrunds der meisten "modernen" Verfahren in der Kryptologie werden im Seminar (s.o.) ständig elementare Kenntnisse aus den Grundlagen der Zahlentheorie benutzt. Hierzu gehören insbesondere die wichtigsten Aussagen über lineare Kongruenzen (einige einführende Bemerkungen über quadratische Kongruenzen werden im Verlauf der Lehrveranstaltung angefügt). Um Ihr Wissen über den EUKLIDischen Algorithmus und über Aussagen und Folgerungen aus der Rechnung mit Kongruenzen zu prüfen, können Sie beispielsweise Aufgaben aus der folgenden Liste bearbeiten:

1. Wie viele Teiler hat 945 ? Geben Sie sie sämtlich an.

2. Finden Sie den ggT für die folgenden Zahlenpaare, und geben Sie ihn als Linearkombination der beiden Zahlen an: a): 26,19;  b): 187,34;  c): 2613,2171.

3. Geben Sie alle Lösungen der folgenden Kongruenzen an: a): 3x º 4 mod 7,  b): 9x º 12 mod 21,   c): 27x  º 25 mod 256

4. Beweisen Sie, dass n5 - n immer durch 30 teilbar ist.

5. Geben Sie den kleinsten (positiven) Generator der Restklasse Z / 31 Z an.

6. Finden Sie eine Zahl mit 3 Dezimalstellen, die einen Rest von 4 liefert, wenn sie durch 7, 9 oder 11 geteilt wird.

7. 17 chinesische Piraten erbeuten eine Truhe mit Goldstücken. Beim Versuch, diese gleichmässig zu verteilen, bleiben 7 Goldstücke übrig. Um diese entbrennt ein heftiger Streit, bei dem einer der Piraten das Leben lässt. Die verbleibenden 16 versuchen erneut, die Goldstücke gerecht zu verteilen, behalten jedoch 11 Stücke übrig. Bei der folgenden Auseinandersetzung geht wieder einer der Streitenden über Bord. Den 15 Überlebenden gelingt dann die Teilung. Wie viele Goldstücke müssen es mindestens gewesen sein ?

8. Welches ist die letzte Ziffer in der Dezimaldarstellung von 21000 ?

 

Zuletzt geändert am 10.04.2008