Eberhard Karls Universität Tübingen
Wilhelm-Schickard-Institut für Informatik (WSI)
Arbeitsbereich für Theoretische Informatik/Formale Sprachen
Impressum | Intern
Home | Lehre | Sommersemester 08 | Oberseminar

Oberseminar: Theoretische Informatik

Dozent(en):
Zeit:
Ort:

Das Oberseminar Theoretische Informatik bietet Vorträge von auswärtigen Gästen, Mitarbeitern, Doktoranden und fortgeschrittenen Studenten über neuere Ergebnisse und Forschungsfragen der Theoretischen Informatik und angrenzenden Gebieten. Schwerpunkte bilden dabei Algorithmen und Komplexität.

Vorträge

Datum Referent Titel
Mo 28.4.08, 15.15h
 Alexander Christ, Uni Tuebingen
 Eine AJAX Web-Anwendung zur Demonstration der Visuellen  Kryptographie
Dominik Reichl, Uni Tuebingen Moeglichst viele verschiedene Primfaktoren mit moeglichst wenigen arithmetischen Operationen
Mo 5.5.08, 14.45h Manfred Kufleitner, Uni Stuttgart
 Deterministische Produkte und Quantorenalternierung innerhalb von FO2 über Wörtern
Mo 19.5.08, 15.15h David Aschenbrenner, Uni Tuebingen
 Reaction attacks gegen ein public-key Verfahren basierend auf Gabidulin-Codes
Mo 16.6.08, 15.15h Joachim Schiele, Uni Tuebingen Being Qt in Theoretical Computer Science - Entwurf und Implementierung eines Programs zu Eingabe und Darstellung endlicher Automaten
Mo 14.7.08, 15.15h Henrik Maryns, Uni Tuebingen
 MonaSearch
Friederike Sobe, Uni Tuebingen Kryptologische Analyse eines Verfahrens zur abhörsicheren Eingabe der PIN


Abstracts

28.4.08, Alexander Christ: Eine AJAX Web-Anwendung zur Demonstration der Visuellen  Kryptographie

Im Rahmen dieser Studienarbeit wurde eine Internet-Applikation entwickelt,
die eine spielerische Anwendung der visuellen Kryptographie erlaubt.
Der Benutzer kann auf einer Leinwand Punkte, Linien und Buchstaben zeichnen.
Parallel dazu werden zwei Geheimnisbilder erzeugt. Die Entschlüsselung geschieht
durch Überlagerung der Bilder, die ebenfalls vom Benutzer ausgeführt werden kann.
Eine hohe Kompatibilität wird durch Verwendung der AJAX-Technologie erreicht.
Im Gegensatz zu JAVA-Applets oder Flash-Skripten erfordert sie nicht die Installation
eines Plugins. Stattdessen wird die erweiterte Funktionalität durch eine dynamische
Interaktion zwischen Server und Client realisiert.
Webseite mit der AJAX-Anwendung:
http://www-fs.informatik.uni-tuebingen.de/studdipl/christ/


28.4.08, Domink Reichl: Moeglichst viele verschiedene Primfaktoren
mit moeglichst wenigen arithmetischen Operationen

In dieser Studienarbeit wird experimentell untersucht, welche
arithmetischen { 1, +, -, * }-Schaltkreise einer bestimmten Größe
Ergebnisse erzeugen, die sich in sehr viele verschiedene Primfaktoren
zerlegen lassen. Parametrisiert wird einerseits durch die Größe der
Schaltkreise (Gesamtanzahl Knoten) und andererseits durch einen
zweidimensionalen Größenparameter (Anzahl *, Anzahl +/-).
Alle Schaltkreise bis einschließlich Größe 11 wurden untersucht.
Es wurde festgestellt, dass bis zu dieser Größe die maximale
Primfaktoranzahl immer durch schlanke Multiplikationstürme
mit Ergebniswerten der Form 2^(2^n) - 2^(2^m) erreicht wird (ab Größe 4).
Mit 9 Operationen sind maximal 16 verschiedene Primfaktoren möglich,
mit 10 Operationen 22 und mit 11 Operationen 34 verschiedene Primfaktoren.


5.5.08, Manfred Kufleitner: Deterministische Produkte
und Quantorenalternierung innerhalb von FO2 über Wörtern

In dem Vortrag führen wir eine Hierarchie von regulären Sprachen
ein. Ähnlich wie die Straubing-Th{\'e}rien Hierarchie als  
Schwierigkeitsmaß für sternfreie Sprachen angesehen werden kann, so
unterteilt die in  diesem Vortrag vorgestellte Hierarchie die Klasse der
Sprachen, deren syntaktisches Monoid in DA liegt.
Es werden Beziehungen dieser Hierarchie zu algebraischen Operationen und
zur Quantorenalternierung innerhalb der Logik erster Stufe mit nur zwei
Namen für die Variablen vorgestellt.


16.6.08, Joachim Schiele: Being Qt in Theoretical Computer Science - Entwurf
und Implementierung eines Programs zu Eingabe und Darstellung endlicher Automaten

Die Studienarbeit befasst sich mit der C++ Implementation eines in Qt 4
geschriebenen graphischen Editors für endliche Automaten unter Verwendung
des "Model View Controller (MVC)" sowie "Observer" Entwurfsmusters zur
synchronisierten graphischen sowie hierarchischen Darstellung von
DFAs/NFAs/epsilon-Automaten.


14.7.08, Hendrik Maryns: MonaSearch

MonaSearch ist ein Werkzeug, das dazu gedacht ist, in linguistischen
Datenbanken, sogenannte Baumbanken, nach spezifischen sprachlichen
Phänomenen zu suchen. Die Sätze sind von einer syntaktischen Struktur
in Form eines Baumes versehen. Als Abfragesprache wird Monadische Logik
Zweiter Stufe angeboten. Bekanntlich ist hierfür ein Automatenmodell verfügbar
und es ist genau dies, was in MonaSearch genutzt wird: mit Hilfe von Mona,
einem Modell-Checking-Werkzeug, ist es gelungen, die ganze Kraft von MSO für Abfragen
bereit zu stellen. Es wird einen Überblick der theoretischen Hintergründe gegeben,
gefolgt von einer Systemvorführung.



14.7.08, Friederike Sobe: Kryptologische Analyse eines Verfahrens
zur abhörsicheren Eingabe der PIN

Das von Yousofivorgestellte Verfahren zur sicheren Eingabe der PIN soll
verhindern, dass ein sich auf dem Rechner des Benutzers befindendliches Pro-
gramm, welches die Benutzereingabe mit liest, in Kenntnis der geheimen PIN
gelangt. Dies soll verhindert werden, indem der Benutzer bei jeder Eingabe
der PIN, durch anwenden eines Schlüssels in Kombination mit einer von der
Authentifizierungsstelle zufällig erzeugten Permutation, nie die PIN direkt
eingibt. Ein Angreifer soll also nicht in der Lage sein, durch mehrmaliges
Abhören des Eingabevorgangs die PIN zu berechnen, und sich somit erfolg-
reich in den Account einloggen zu können.
Ziel dieser Studienarbeit ist es zu untersuchen, inwiefern das vorgestellte Ver-
fahren diese Art von Angriff verhindern kann. Konkret soll ermittelt werden,
wie oft es möglich ist, den zur Verschleierung der Eingabe genutzten Schlüs-
sel wiederzuverwenden, bevor ein Angreifer mit einer 1%-igen Erfolgswahr-
scheinlichkeit die Challenge, also die Eingabe der PIN, korrekt beantworten
kann.
Es wird angenommen dass der Schlüssel dem Benutzer auf sicherem Wege
übermittelt wurde, und nicht auf dem Computer abgespeichert ist. Wäre dies
nämlich der Fall, so könnte der Virus den Schlüssel ebenfalls ausspionieren
und daraus auf die PIN schließen.


 
Letzte Änderung: 11. Jul. ‘08 | Bei Fragen und Anregungen E-Mail an: fswebadmin
Home WSI Fachschaft Uni-Tübingen Tübingen Externe Links