[JoGu]

Kryptologie

III.6 Kryptographische Basisfunktionen und ihre Äquivalenz
a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

  1. Einweg-Funktionen [PDF-Datei].
  2. Hash-Funktionen [PDF-Datei].
  3. Umwandlungstricks [PDF-Datei].
  4. Physikalische Komplexität [PDF-Datei].
  5. TURING-Maschinen [PDF-Datei].
  6. Die Klasse NP [PDF-Datei].

Und der ganze Abschnitt am Stück als PDF-Datei.

Für Anwendungen der Kryptographie im praktischen Leben - also für die Konstruktion kryptographischer Protokolle - werden die folgenden Basisfunktionen benötigt:

  1. Symmetrische Chiffren:
    1. Bitblock-Chiffren,
    2. Bitstrom-Chiffren.
  2. Asymmetrische Chiffren.
  3. Schlüsselfreie Chiffren:
    1. Einweg-Funktionen,
    2. Hash-Funktionen.
  4. Zufall:
    1. Physikalische Zufallsgeneratoren,
    2. (Algorithmische) Pseudozufallsgeneratoren.
  5. Steganographie.
Es wird sich zeigen, dass die Existenz der meisten davon - nämlich 1a, 1b, 3a, 3b, 4b in geeigneten Varianten - zueinander äquivalent und mindestens so schwer wie das Grundproblem der theoretischen Informatik P ?=? NP - und damit bisher unbewiesen - ist.

Dieser Abschnitt ist weitgehend mathematisch unpräzise, Komplexitätsaussagen werden noch naiv formuliert und meist nur mit heuristischen Argumenten unterlegt. Der Ansatz zur Formalisierung mittels TURING-Maschinen wird skizziert. Er ist allerdings für die Kryptologie nicht ausreichend. Die mathematisch strenge Version von Komplexitätsaussagen für kryptologische Verfahren folgt im nächsten Abschnitt.

Autor: Klaus Pommerening, 29. Oktober 2000; letzte Änderung: 6. Januar 2009.