2a.4 Einweg-Verschlüsselung(Einweg-Funktionen und Hash-Funktionen) |
Eine Einweg-Funktion ist eine umkehrbare Funktion
f : {Klartexte} ---> {Geheimtexte},wobei
Verfahren [Needham 1967]:
Nachteile:
Verbesserung durch Zusatzmaßnahmen:
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.]
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.
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.
Die Umkehrabbildung (der »induzierten« Abbildung)
alog: <a> ---> Z/sZist ein Isomorphismus und heißt der diskrete Logarithmus in G zur Basis a.
Die Exponentialfunktion ist effizient auswertbar mit dem binären Potenzalgorithmus:
Ist | |
so |
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:
... 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.