, so dass 
ebenfalls eine ungerade Primzahl ist. (Dieses ist nicht trivial!) Weiter werden zwei primitive Elemente 
gewählt, mit 
. Der Wert 
mit 
bleibt geheim, die anderen Daten sind öffentlich.
ist definiert als
| Hashverfahren | Extension von Hashfunktionen |
Diese Hashfunktion beruht auf dem Diskreten Logarithmus Problem.
, so dass ebenfalls eine ungerade Primzahl ist. (Dieses ist nicht trivial!) Weiter werden zwei primitive Elemente gewählt, mit . Der Wert mit bleibt geheim, die anderen Daten sind öffentlich. ist definiert als
Für diese Hashfunktion ist es vermutlich schwer, Kollisionen zu finden, wie der folgende Satz zeigt.
Satz 14
Wenn eine Kollision für die Chaum-van Heigst-Pfitzmann Hashfunktion 
gegeben ist, dann ist der diskrete Logarithmus 
effizient berechenbar.
Beweis Gegeben ist eine Kollision, also zwei Paare 
mit
. Aus 
und 
prim folgt 
. Entsprechend den möglichen Werten von 
unterscheiden wir vier Fälle.
Fall 1: Sei 
. Dann existiert das Inverse 
und es folgt
zu bestimmen, in diesem Fall also mit dem erweiterten Euklidischen Algorithmus lösen (Bestimmung von 
).
Fall 2: Sei 
. Mit 
und 
ungerade ergibt sich 
. Damit existiert das Inverse 
und es folgt
, da 
erzeugendes Element in 
ist, 
und die Gleichung 
genau zwei Lösungen hat. Es ergibt sich:
in 
kann dann leicht die richtige Lösung ermittelt werden.
Fall 3: Sei 
und damit 
für ein 
. Mit 
folgt aber 
, also ist 
nicht möglich.
Fall 4: Für 
folgt 
. Mit 
ergibt sich 
, also 
, da 
primitiv ist. Nach Annahme war jedoch 
.