2a. Kryptographische Basistechniken

2a.4 Einweg-Verschlüsselung

(Einweg-Funktionen und Hash-Funktionen)

[One-Way]

Idee

Eine Einweg-Funktion ist eine umkehrbare Funktion

f : {Klartexte} ---> {Geheimtexte},
wobei Die Definition lässt sich komplexitätstheoretisch präzisieren, der mathematische Existenzbeweis für Einweg-Funktionen ist aber offen.
[Wenn Einweg-Funktionen existieren, dann ist P ungleich NP.]

Analogien/ Bildliche Vorstellung

Kryptographische Bedeutung


Anwendung 1: Passwort-Verschlüsselung in UNIX

Verfahren [Needham 1967]:

  1. Passwörter werden einweg-verschlüsselt abgespeichert (nach einem modifizierten DES, s. u.).
  2. Bei Anmeldung wird durch Probeverschlüsselung abgeglichen.
[In NT ff. wird ein analoges Verfahren, aber mit einer anderen Einweg-Funktion eingesetzt.]

Nachteile:

Verbesserung durch Zusatzmaßnahmen:


Anwendung 2: Pseudonymisierung

Ziel: Die Daten einer Person sollen mit anderswo abgelegten Daten derselbem Person zusammengeführt werden, ohne dass jemand die zur Person gehörenden Identitätsdaten sehen oder ermitteln kann.

Lösung: Einwegverschlüsselung eines eindeutigen Identifikators.

[Andere Modelle der Pseudonymisierung folgen später.]

[Andere Anwendungen von Einweg-Funktionen folgen.]


Beispiel 1: Konstruktionaus Blockchiffre

Gegeben sei eine Blockchiffre

F = {fk | k in K} mit K Teilmenge von M = F2l,
die sicher vor Angriff mit bekanntem Klartext ist (z. B. DES oder AES) - also eine starke Blockchiffre.

Gewählt wird eine feste (bekannte) Nachricht m0 (z. B. der Bitstring aus lauter Nullen).

Dann ist durch

c = f (m) : = fm(m0)
eine Einweg-Funktion f definiert.

[Beweis: Die Bestimmung von m ist ein Angriff mit bekanntem Klartext auf F.]

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

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


Beispiel 2: Die diskrete Exponentialfunktion

Sei G Gruppe (multiplikativ geschrieben), a ein Element von G der Ordnung s (£ ¥).

Die Exponentialfunktion in G zur Basis a,

expa : Z ---> G, x ---> ax,
ist Gruppenhomomorphismus der Periode s.

[Exp und Log]

Die Umkehrabbildung (der »induzierten« Abbildung)

alog: <a> ---> Z/sZ
ist ein Isomorphismus und heißt der diskrete Logarithmus in G zur Basis a.

Die Exponentialfunktion ist effizient auswertbar mit dem binären Potenzalgorithmus:

Ist [Formel]
so [Formel]

Exponentiation und Logarithmus in endlichen Körpern:

Fp, p Primzahl, sei der endliche Körper mit p Elementen. Die multiplikative Gruppe Fp× ist zyklisch und hat die Ordnung p-1. Sei a ein erzeugendes Element dieser Gruppe, eine »Primitivwurzel« modulo p.

(Eine solche kann man »probabilistisch effizient« finden.)

Dann ist

alog: Fp× ---> Z/(p-1)Z = {0, ..., p-2}
der diskrete Logarithmus modulo p zur Basis a.

Der diskrete Logarithmus modulo p ist vermutlich nicht effizient berechenbar. Anders ausgedrückt:

Die Exponentialfunktion expa modulo p ist (für eine Primitivwurzel a) eine Einwegfunktion.
Dies ist die Diskreter-Logarithmus-Vermutung.

Die praktischen Sicherheitsschranken haben die gleiche Größe wie die für die Faktorisierung:


Beispiel 3: 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/mZ)× ---> (Z/mZ)×, s(x) = x2 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.


Vorlesung Datenschutz und Datensicherheit
Autor: Klaus Pommerening, 31. März 1999; letzte Änderung: 23. Mai 2007.
E-Mail an
Pommerening »AT« imbei.uni-mainz.de.