Willekeurigheidsextractor
Een functie die een klonterige, deels voorspelbare entropiebron indikt tot minder bits die vrijwel perfect uniform zijn.
Ruwe bronnen, zoals diodenruis, klokjitter of een Diffie-Hellman-gedeelde waarde, bevatten vaak ruim voldoende entropie, maar in de verkeerde vorm: sommige waarden komen vaker voor dan andere. De oudste extractor is die van John von Neumann uit 1951: lees bits in paren, geef 0 bij ‘01’, 1 bij ‘10’ en gooi de rest weg. Dat herstelt een onzuivere munt, maar geen munt waarvan de worpen onderling samenhangen.
De algemene theorie rust op het leftover hash lemma (Impagliazzo, Levin en Luby, 1989): een willekeurig gekozen universele hashfunctie levert vrijwel uniforme uitvoer, mits de bron genoeg min-entropie heeft. In de praktijk is dit waarom HKDF twee fasen heeft. Extract is een extractor die een ongelijkmatig gedeeld geheim omzet in een uniforme sleutel; Expand rekt die vervolgens uit tot zoveel sleutels als nodig.