Idee

Eine Einweg-Funktion ist eine umkehrbare Funktion

f: {Klartexte} ® {Geheimtexte},

• f »leicht« zu berechnen,
• f^-1 »schwer« zu berechnen ist.

Analogien/ Bildliche Vorstellung

• Suche im Telefonbuch (Nummer ® Name).
• Lösen von Gleichungssystemen.
• Tube ausdrücken.
• Fleischwolf.

Kryptographische Bedeutung

• Jeder kann verschlüsseln (mit f).
• Es ist kein Schlüssel nötig..
• Niemand kann entschlüsseln (mit f^-1).
• Anfällig für Angriff mit gewähltem Klartext (Probeverschlüsselung und Wörterbuchattacke).

Ein Konstruktionsprinzip

Gegeben sei ein Blockverschlüsselungssystem

F = {f_k | k in K} mit K Teilmenge von M = F₂^l,

Gewählt wird eine feste (bekannte) Nachricht m₀ (z. B. der Nullstring).

Dann ist durch

c = f(m) : = f_m(m₀)

Klassische Anwendung dieses Konstruktionsprinzips: Speicherung von Passwörtern unter UNIX [Needham 1967].

Achtung: Bitstrom-Verschlüsselung ist hierfür nicht geeignet! Denn ist c = m XOR m₀, so m = c XOR m₀.

Passwort-Verschlüsselung in UNIX

Verfahren:

1. Passwörter werden einweg-verschlüsselt abgespeichert (nach einem modifizierten DES).
2. Bei Anmeldung wird durch Probeverschlüsselung abgeglichen.

Nachteile:

• Anfällig gegen Probeverschlüsselung als Angriff, insbesondere gegen Wörterbuchattacken und Fischzüge (crack).
• Abhören von Passwörtern usw.

Behebung durch Zusatzmaßnahmen:

• »Salt« - c = f_m(m₀, x) mit zufälligem x (12 bit). Abgespeichert wird (c, x).
  • Fischzug wesentlich erschwert.
  • Probeverschlüsselung für einzelne Passwörter nicht erschwert.
  • Abhören nicht erschwert.
• Shadow-Datei (nicht-kryptographische Zusatzmaßnahme).

Typische Einweg-Funktion

Exponentiation in endlichen Körpern (Einweg-Eigenschaft - wie auch sonst - mathematisch unbewiesen):

F_p, p Primzahl, sei der endliche Körper mit p Elementen. Die multiplikative Gruppe F_p^× ist zyklisch. Sei a ein erzeugendes Element dieser Gruppe, eine »Primitivwurzel« modulo p. (Eine solche kann man probabilistisch effizient finden.)

Dann ist die Exponentialfunktion

E_a: {0, ..., p-2} ® F_p^×, c = E_a(m) = a^m mod p

Ist

so

Die Umkehrfunktion von E_a, der »diskrete Logarithmus modulo p zur Basis a«, ist vermutlich nicht effizient auswertbar.

Die Rabin-Funktion

... ist ein weiteres wichtiges praktikables Beispiel:

Sei m eine Blum-Zahl, also ein Produkt zweier (großer) Primzahlen p und q, beide kongruent 3 mod 4. Die Rabin-Funktion ist einfach die Quadrat-Funktion

s: (Z/nZ)^× ® (Z/nZ)^×, s(x) = x² mod m.

Die Berechnung der Umkehrfunktion s^-1, also das Quadratwurzelziehen mod m, ist äquivalent zur Primzerlegung von m, also vermutlich nicht effizient ausführbar.