2a. Kryptographische Basistechniken

Umwandlungstricks für kryptographische Basisfunktionen


Folgende Aussagen über die Existenz von kryptographischen Basisfunktionen sind im komplexitätstheoretischen Sinne im wesentlichen äquivalent:

  1. Es gibt eine starke symmetrische Chiffre,
  2. Es gibt eine Einweg-Funktion.
  3. Es gibt eine Hash-Funktion.
  4. Es gibt einen perfekten Zufallsgenerator.
und implizieren
  1. P ungleich NP.
[Im streng mathematischen Sinne stimmt das so nicht ganz, siehe den entsprechenden Abschnitt der Kryptologie-Vorlesung.]

Aus A folgt D: wurde eben gezeigt.

Von D nach A kommt man z. B. durch die Bitstrom-Verschlüsselung.

Von A nach C kommt man, wie unter »Hash-Funktionen« erwähnt, durch Cipher Block Chaining (CBC) (wobei die Kollisionsfreiheit evtl. nur mit Zusatzbedingungen erfüllbar ist).

Von C nach B braucht man nur die Hash-Funktion auf Zeichenketten der Länge des Hash-Wertes einzuschränken. (Hier ist eigentlich eine genauere Betrachtung nötig, wenn man die Bijektivität der Einweg-Funktion haben will.)

Von B nach A (MDC = Message Digest Cryptography, z. B. nach E. Backus) kommt man etwa (im Ansatz) so:

F(a, k) = f(a) XOR f(k).
Ist nämlich der Klartext a zum Geheimtext c = F(a, k) bekannt, so ist f(k) = c XOR f(a) bekannt, die Bestimmung von k also auf die Umkehrung von f reduziert.

Aus D folgt E ist ein Satz von Yao.

[Äquivalenz]

Moral


Vorlesung Datenschutz und Datensicherheit
Autoren: Klaus Pommerening, Marita Sergl, 31. März 1999; letzte Änderung: 7. Juli 2004.
E-Mail an
Pommerening »AT« imbei.uni-mainz.de.