Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Hauptseminar im SS 2004:
Kryptographische Algorithmen

Donnerstag, 14 - 16 Uhr
im Seminarraum MI 03.11.018


[Themen & Literatur] [Termine] [Zusammenfassung] [Hinweise]

Nächsten drei Vorträge am 22.07.2004, 14h - 17h, im Raum MI 03.11.018

Zusammenfassung

War Kryptographie jahrhundertelang eine hauptsächlich von Militärs und Herrschern benutzte Technik, um Nachrichten auszutauschen, ist sie heute aus dem Alltag in modernen Gesellschaften nicht mehr wegzudenken. Man denke nur an Internet-Sicherheit, Mobiltelefone, Smart-Cards und auch Decoder für Pay-TV (und vieles mehr). Obwohl die Bekanntheit von kryptographischen Verfahren gestiegen ist, ist das Wissen über ihre Funktionsweise bzw. über ihre Sicherheit nur sehr gering. Worauf aber beruht die Sicherheit bekannter Verfahren wie RSA, Rabin, Diffi-Hellman, etc?
Vereinfacht gesehen beruht sie einerseits auf der Kenntnis großer Primzahlen und andererseits auf dem Glauben, dass Faktorisieren einer hinreichend großen Zahl mit der heutigen Rechenkapazität nicht durchführbar ist. (Siehe z.B. den Übersichtsartikel Kryptographie - Chancen und Risken, oder die WWW Seiten CryptoWorld! und The prime pages)

Damit ist der Inhalt des Seminars bereits abgedeckt. Es werden Methoden zur Auffindung großer Primzahlen (Primzahltests) und zur Faktorisierung vorgestellt. Da jede effiziente Implementierung dieser Verfahren auf effiziente Algorithmen für die Arithmetik großer (ganzer) Zahlen angewiesen ist, werden diese ebenfalls behandelt. Im Seminar werden Algorithmen aus den folgenden 4 Blöcken behandelt.

  1. Primzahltests
  2. Faktorisierung
  3. Primzahltests und Faktorisierung mit elliptischen Kurven
  4. Zahlentheoretische Algorithmen
Pro Block stehen 3 - 4 Themen zur Auswahl, wobei zu jedem Block mindestens 2 Vorträge stattfinden sollten.

Voraussetzung für die Teilnahme am Seminar sind neben guten mathematischem Verständnis auch Englischkenntnisse, die zumindest ausreichend für die Bearbeitung der ausschließlich englischsprachigen Literatur sind.


Anmeldung: Schicken Sie bitte eine Präferenz für 1-2 Themen (oder für einen Block) an Thomas Bayer

Vorträge (vorläufig)

Primzahltests
22.04.04 Name Hildisch Andreas
Thema: (n + 1)-Test für Mersenne-Zahlen
29.04.04 Name Savova Slatina
Thema: (n - 1)-Test für Fermat-Zahlen
06.05.04 Name Kamman Markus
Thema: Siebmethoden
13.05.04 Name Ainhauser Christoph
Thema: Primes is in P
Faktorisierung
27.05.04 Name Kammermeier Christoph
Thema: Pollard rho und p-1 Methode
03.06.04 Name Gougas Alexandros
Thema: Quadratisches Sieb (QS)
17.06.04 Name Markl Christian
Thema: Zahlenkörper Sieb (NFS)
Primzahltests und Faktorisierung mit elliptischen Kurven
24.06.04 Name Weinmann Andreas
Thema:Elliptische Kurven: Grundlagen und Arithmetik
01.07.04 NameDollinger Andreas
Thema: Faktorisierung mit elliptischen Kurven
22.07.04, 14h NameBorgwardt Steffen
Thema: Primzahltests mit elliptischen Kurven
Zahlentheoretische Algorithmen
22.07.04, 15h Name Lasser Tobias
Thema: Schnelle Multiplikation großer Zahlen (FFT, DWT)
22.07.04, 16h Name Guezelarslan Oezcan
Thema: GGT, Exponentiation, Modulare Arithmetik

Hinweise

Ein Schein für die erfolgreiche Teilnahme am Hauptseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin).
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Hinweis: Es empfiehlt sich, den Vortrag mit dem prosper-Style in LaTeX zu verfassen (style-file). Ein (Mini)Vortrag sieht so aus pdf-Datei und besteht aus LaTeX Quellcode.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Votrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten (ohne Literaturverzeichnis) im LNCS-Style (Springer-Verlag) unter LaTeX (Hinweise siehe unten).
Anwesenheit bei den Vorträgen Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortragerstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem VortragProbevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortragfertige Ausarbeitung abgeben.

Hinweise zur Anfertigung einer Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung gemeinsam in einem Seminarband zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
* Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Seminarvorträge

* Merkblatt zur Gestaltung eines Seminarvortrags. (Die Tipps auf diesem Merkblatt sind keine offiziellen Anforderungen oder Bewertungskriterien der TU München, sondern aus der Praxis eines Seminarleiters heraus entstandene Ratschläge.)
* Tipps zur Erstellung von Folien mit LaTeX (einschließlich Rahmen-Datei als Vorlage)
* Es empfiehlt sich, den Vortrag mit dem prosper-Style in LaTeX zu verfassen (style-file). Ein (Mini)Vortrag sieht so aus pdf-Datei und besteht aus LaTeX Quellcode.

Weitere Auskünfte bei Thomas Bayer.
Thomas Bayer, January/26/2004.