Institut für Theoretische Informatik 

Universität zu Lübeck
Lübecker Hochschultag
    13. November 2003
 
Informationen verstecken - Kryptographie
 
  • Wie können wir vertraulich kommunizieren, so daß kein Unbefugter Kenntnis von der übermittelten Nachricht erhält?
  • Wie kann ich mich zweifelsfrei ausweisen?
  • Wie kann ich feststellen, daß eine Nachricht von einem bestimmten Sender stammt?
  • Wie kann ich nachweisen, daß ein Datensatz mein Eigentum ist?
  • Wie kann ich einen anderen davon überzeugen, daß ich ein Geheimnis kenne, ohne dieses zu verraten?
  • Wie kann ich anonym bleiben und dabei ein Geschäft abwickeln?
  • Wie kann ich an einer Abstimmung teilnehmen, ohne daß ein anderer Information über mein Abstimmungsverhalten erhält?
    •  
    Public Key Systeme
     

    Bei einem Public-Key-System werden zwei verschiedene Schlüssel benötigt. Ein Schlüssel, der öffentlich bekannt ist (public key), dient zur Verschlüsselung einer Nachricht. Der zweite Schlüssel ist nur dem Empfänger bekannt (private key) und wird benötigt, um die Nachricht zu lesen.
    Das RSA-Kryptosystem (benannt nach seinen Erfindern Rivest, Shamir und Adleman - Turing-Award-Preisträger 2003 - entspricht dem Nobelpreis für die Informatik) ist das bekannteste Public-Key-Kryptosystem. Der Algorithmus funktioniert wie folgt:


     

    Alice wählt zwei grosse Primzahlen p, q und berechnet N = p q sowie f = (p-1) (q-1). Dann wählt sie e aus {1,2,...,f} mit ggT(e,f) = 1 und berechnet d mit (d e) mod f = 1.

  • N und e ist Alice? oeffentlicher Schlüssel, den sie allen mitteilen darf.
  • p, q und d ist Alice? privater Schlüssel, sie sind geheim.

    •  

     
     

    Um eine Nachricht an Alice zu senden, unterteilt Bob diese in Blöcke und wandelt jeden Block in eine Zahl m < N um (z.B. mit Hilfe des ASCII-Codes). Er berechnet c = me mod N und übermittelt c an Alice. Zur Dekodierung berechnet Alice m = cd mod N.

    Sicherheit von Kryptosystemen

    Die Sicherheit basiert auf der Schwierigkeit, konkrete Probleme zu lösen. Beim RSA ist dies das Faktorisieren grosser Zahlen (gegeben N, bestimme p und q).

    Beispiel:

  • Für N = 15 erhalten wir 3 und 5.
  • Für N = 39199007823998693533 erhalten wir 4093082899 und 9576890767.
  • Welche Primfaktoren hat N=2630492240413883318777134293253671517529?
    •  


    Sichere Protokolle ohne Schlüssel: No-Key-Protokolle
     

    Bei einem solchen No-Key-Protokoll geht es darum, daß Alice und Bob eine Nachricht vertraulich austauschen, ohne daß vorher ein gemeinsamer Schüssel ausgetauscht wird. Die folgende Idee geht auf A. Shamir zurück.

     
     

     

    Zur Realisierung benutzen wir die diskrete Exponentialfunktion: Sei p eine grosse Primzahl, die Alice und Bob bekannt ist. Alice bestimmt (a, a') mit aa' mod (p-1)=1 und Bob (b, b') mit bb' mod (p-1)=1. Es gilt s(aa') mod p = s(bb') mod p = s für alle s=0, 1, ..., p-1.

    Wir erhalten folgendes Protokoll zum Senden der Nachricht s:

  • Alice sendet an Bob n1=sa.
  • Bob sendet an Alice n2=n1b.
  • Alice sendet an Bob n3=n2a'.
  • Bob berechnet s = n3b' mod p= s(aba'b') mod p.
    •  


    2 Fragen zum Knobeln:

     
    1. Zero-Knowledge:
     
     

    Alice: Ich kenne den geheimen Schlüssel zur Tür T.
    Bob: Beweise es mir!
    Eva: Mir auch!
    Alice: Ich werde es Bob beweisen aber Eva nicht.
    Eva: Dann werde ich Bob nicht mehr aus den Augen lassen.

    Wie kann Alice Bob überzeugen, ohne daß Eva dieses Wissen bekommt. Es ist erlaubt, daß Alice und Bob eine geheime Absprache treffen.

     
     
    2. Private Berechnung:

    Alice, Bob, Eva und Tom wollen ihr Durchschnittsgehalt berechnen, ohne daß einer eine Ahnung von dem Gehalt eines anderen zu bekommt. Das jeweilige Einzelgehalt liegt unter 10.000 Euro monatlich. Wie können sie dies erreichen?

     

     
     


     
     

    Informationen entdecken - Data Mining
     

    In den letzten zwei Jahrzehnten haben wir ein enormes Wachstum der elektronisch verfügbaren Daten zu verzeichnen. Etwa alle 20 Monate verdoppelt sich die Menge der bereitgestellten Daten. Erinnert sei hier nur an das Human-Genome-Projekt, die weltweite Erfassung von Klimadaten, das ständig wachsende World Wide Web (WWW) oder die im Mobilfunk anfallenden Daten.

    Die wichtigste Aufgabe besteht nun darin, daß in den Daten enthaltene Wissen zu extrahieren. Diesen Prozess nennt man Data Mining oder Wissensentdeckung in Datenbasen. So möchte man z.B. wissen:
     

  • Welche Gene bewirken was im Organismus oder welche Veränderungen an Genen sind krankhaft?
  • Welche Veränderungen der Sonnenaktivität beeinflussen das Klima auf der Erde nachhaltig?
  • Welche neuen Publikationen sind im WWW verfügbar, die für meine Forschungen/Entwicklungen bedeutsam sind?
  • Welche Abweichungen vom typischen Kundenverhalten deuten auf einen Betrugsversuch hin?

    •  

     

    Wie die Beispiele zeigen, ist es weiterhin oft wichtig, das in den Daten vorhandene Wissen nicht nur zu entdecken, sondern es auch in einer für Menschen verständlichen Form darzustellen.

    Die Lösung dieser Aufgabe ist als schwierig einzustufen, da die Menge der zu analysierenden Daten oft riesig ist (mehrere Gigabyte), die Daten oft in sehr inhomogener Form vorliegen, oft unvollständig und mit Fehlern behaftet sind und häufig noch relevantes Vorwissen zu integrieren ist. Die Daten müssen somit vorverarbeitet, transformiert, angereichert und vereinheitlicht werden, bevor der eigentliche Wissensentdeckungsprozess beginnen kann. Dann sind geeignete maschinelle Lernverfahren oder statistische Methoden auf die so erhaltenen Daten anzuwenden und abschliessend ist das gefundene Wissen zu evaluieren. Ggf. ist der gesamte Prozess solange zu wiederholen, bis wirklich relevantes Wissen entdeckt wurde.

     
     


    Ein einfaches Beispiel: Wetterdaten

    In Abhängigkeit vom Wetter spielen wir Tennis oder nicht.

    Gegeben ist folgende Tabelle:
     
     
    Vorhersage Temperatur Luftfeuchtigkeit  Windig  Spielen 
    sonnig heiss hoch falsch nein
    sonnig heiss hoch wahr nein
    bewölkt heiss hoch falsch ja
    Regen mild hoch falsch ja
    Regen kühl normal falsch ja
    Regen kühl normal wahr nein
    bewölkt kühl normal wahr ja
    sonnig mild hoch falsch nein
    sonnig kühl normal falsch ja
    Regen mild normal falsch ja
    sonnig mild normal wahr ja
    bewölkt mild hoch wahr ja
    bewölkt heiss normal falsch ja
    Regen mild hoch wahr nein

     
    Ausserdem bekommen wir die Daten für morgen
     
     
    Vorhersage Temperatur Luftfeuchtigkeit  Windig Spielen
    sonnig  kühl hoch wahr ?

    und müssen vorhersagen, ob gespielt wird oder nicht (diese Vorhersage soll natürlich konsistent mit der Tabelle sein). In diesem Fall können wir aus der Tabelle einen Entscheidungsbaum lernen und diesen dann zur Vorhersage nutzen.

     
    Data Mining wird von uns nicht nur intensiv untersucht, sondern auch im Rahmen des Zukunftsinvestitionsprogramms der Bundesregierung im Verbundprojekt DaMiT für die Lehre an Universitäten und für potentielle Anwender aufbereitet.

    Ansprechpartner:
    Prof. Thomas Zeugmann,
    Institut für Theoretische Informatik
    Wallstr. 40
    23560 Lübeck

    Homepage: http://www.tcs.uni-luebeck.de/pages/thomas/index.jhtml

     

    Demos zum downloaden:

    Alle Demos zum downloaden

    Dateien zum downloaden:

    Kryptographie in der Antike (PS-File)  (PDF-File)

    Kryptographie im Mittelalter (PS-File)  (PDF-File)

    Zero-Knowledge-Beweise (PS-File)  (PDF-File)

    Sichere verteilte Daten (PS-File)  (PDF-File)

    Visuelle Kryptographie (PS-File)  (PDF-File)

    Wasserzeichen (PS-File)  (PDF-File)

    Moderne Anwendungen der Kryptographie (PS-File)  (PDF-File)

    IT-Firmen in der Kryptographie (PS-File)  (PDF-File)

    Data Mining (PS-File)  (PDF-File)

    Das Institut (PS-File)  (PDF-File)

    Erstellt 07. November 2003, Claudia Mamat