Algorithmisch kann man nur deterministische Folgen erzeugen. Dennoch lässt sich der Zufall algorithmisch approximieren.
Pseudozufallsfolgen (-zahlen, -bits) sind algorithmisch erzeugte Folgen (Zahlen, Bits), die sich von zufälligen Folgen (Zahlen, Bits) nach bestimmten Kriterien nicht unterscheiden lassen.
Ein Algorithmus, der Pseudozufallsfolgen (-zahlen, -bits) erzeugt, heißt Zufallsgenerator.
Parameter: | Modul | m ³ 2 |
---|---|---|
Multiplikator | a Î [0 .. m-1] | |
Inkrement | b Î [0 .. m-1] | |
Startwert | x0 Î [0 .. m-1] |
Eine Folge (xi) von Zufallszahlen im ganzzahligen Intervall [0 .. m-1] wird durch folgende Iterationsformel erzeugt:
xi = a × xi-1 + b mod m.
Bei geschickter Wahl der Parameter hat die Folge eine Periode » m und ist durch statistische Tests praktisch nicht von einer gleichverteilten Zufallsfolge zu unterscheiden.
Mit zahlentheoretischen Methoden ist aber leicht eine Kryptoanalyse möglich: Aus einem kurzen bekannten Stück der Folge lässt sich der weitere Folgenverlauf vorhersagen, auch wenn die Parameter sämtlich unbekannt sind. Ein Programm dazu gibt's hier.
===> Pseudozufallszahlen aus einem linearen Kongruenz-Generator sind kryptographisch nicht sicher!
Parameter: | Registerlänge | l ³ 2 |
---|---|---|
Rückkopplungsvorschrift | I Í [1 .. l] | |
Startwert | (ul-1...u0) Î F2l |
Eine Folge (ui) von Zufallsbits wird durch folgende Iterationsformel erzeugt:
Bei geschickter Wahl der Parameter hat die Folge eine Periode » 2l und ist durch statistische Tests praktisch nicht von einer gleichverteilten Zufallsfolge zu unterscheiden. (Als »Pseudorauschen« in der E-Technik beliebt.)
Mit linearer Algebra über dem endlichen Körper F2 ist aber leicht eine Kryptoanalyse möglich: Aus einem kurzen bekannten Stück der Folge lässt sich der weitere Folgenverlauf vorhersagen, auch wenn die Parameter sämtlich unbekannt sind.
===> Pseudozufallsbits aus einem linearen Schieberegister sind kryptographisch nicht sicher!
Nach einem Satz von YAO sind folgende Eigenschaften eines Zufallsgenerators äquivalent:
Solche Zufallsgeneratoren werden kryptographisch sicher genannt; sie sind also geeignet, um eine sichere Bitstrom-Verschlüsselung durchzuführen. Leider ist ihre Existenz unbewiesen - sie hängt vom ungelösten Grundproblem der Komplexitätstheorie ab: Wie beweist man, dass ein Problem nicht effizient lösbar ist?
Mathematische Behandlung im Kapitel Perfekte Zufallsgeneratoren der Kryptologie-Vorlesung.
Im folgenden werden drei Zufallsgeneratoren vorgestellt, die vermutlich perfekt sind - unter der Annahme, dass bestimmte zahlentheoretische Probleme nicht effizient lösbar sind.
[Leonore Blum, Manuel Blum, Michael Shub (Bilder)]
Eine Blum-Zahl m ist (wie beim RSA-Verfahren) ein Produkt zweier (großer) Primzahlen p und q, wobei hier noch p und q kongruent 3 mod 4 sein sollen.
Parameter: | Modul | m (Blum-Zahl) |
---|---|---|
Startwert | x0 |
Eine Folge (bi) von Zufallsbits wird durch folgende Iterationsformel erzeugt:
xi = xi-12 mod m;
ausgegeben wird aber nur das letzte Bit bi = xi mod 2.
Der Rucksack-Generator ist perfekt, wenn das »Rucksack-Problem« (Knapsack Problem, Subset Sum Problem) nicht effizient lösbar ist. Dieses ist NP-vollständig.
Konstruktion aus starker Bitblock-Chiffre f (vgl. OFB).
Parameter: | Startwert | s0, |
Schlüssel | k. |
Bei der kryptographischen Anwendung werden der Startwert s0 und der Schlüssel k geheim gehalten.
Verfahren:
si := f (si-1, k).
Kryptoanalyse: Vorhersage nur, wenn k bekannt; entspricht Angriff mit bekanntem Klartext.