In vielen kryptografischen Verfahren benötigen Sie Zufallswerte. Bei der One-Time-Pad-Verschlüsselung etwa verwenden Sie als Schlüssel eine Folge von echten Zufallsbits. Bei der Diffie-Hellman-Schlüsselvereinbarung erzeugen beide Kommunikationspartner jeweils eine zufällige Zahl. Zur Erzeugung der Schlüssel für das RSA-Verfahren benötigen Sie zwei zufällig gewählte Primzahlen. Es gibt viele weitere Beispiele.
Zufallsbits werden vom Computer im Allgemeinen algorithmisch erzeugt. Daher handelt es sich streng genommen nicht um echte Zufallsbits, sondern um sogenannte Pseudozufallsbits. Echte Zufallsbits haben die Eigenschaft, dass es wie beim Münzwurf nicht vorhersagbar ist, ob als nächstes eine 0 oder eine 1 fällt. Bei Pseudozufallsbits lässt sich das nächste Bit dagegen vorhersagen, wenn der Algorithmus und dessen Parameter bekannt sind.
Der Einfachheit halber ist im Folgenden meist von Zufallsbits die Rede, auch wenn es eigentlich Pseudozufallsbits sind.
In vielen Anwendungen außerhalb der Kryptografie spielt es keine Rolle, ob sich das jeweils nächste Bit vorhersagen lässt oder nicht. Es kommt nur darauf an, dass die Folge der Bits aussieht wie eine echte Zufallsbitfolge.
Eine klassische Methode zur Erzeugung von Zufallsbits ist die Verwendung eines linear rückgekoppelten Schieberegisters (Linear Feedback Shift Register – LFSR). Solchermaßen erzeugte Zufallsbits sind allerdings kryptografisch unsicher.
Kryptografisch sichere Zufallsbits haben ähnlich wie echte Zufallsbits die Eigenschaft, dass sich auch in Kenntnis von beliebig vielen vorherigen Bits das nächste Bit nicht effizient vorhersagen lässt.
Mit den Verfahren von Blum-Micali und Blum-Blum-Shub erzeugen Sie in einfacher Weise kryptografisch sichere Zufallsbits.
Eine andere Methode ist die Verwendung einer kryptografischen Hashfunktion h. Sie beginnen mit einem Startwert x0 und berechnen fortlaufend
xi = h(xi-1)
für i = 1, 2, ... .
Wenn allerdings ein Angreifer von einem dieser Werte xi Kenntnis erlangt, kann er alle weiteren Hashwerte xi+1, xi+2, ... berechnen – das ist schlecht. Daher lassen Sie nur wenige Bits von xi als erzeugte Zufallsbits nach außen dringen.
Mithilfe einer starken Verschlüsselungsfunktion E wie beispielsweise dem AES-Verfahren verschlüsseln Sie fortlaufend einen Zählerstand:
ti = E(z + i)
mit i = 0, 1, ... . Hierbei ist z der anfängliche Zählerstand.
Die erzeugte Folge der ti ist pseudozufällig.
Bei den Betriebsarten Counter-Modus (Counter Mode - CTR) und Galois-Counter-Modus (Galois Counter Mode - GCM) für die Block-Verschlüsselung wird dies eingesetzt. Sie addieren die Folge der ti ähnlich wie beim One-Time-Pad zur Folge mi der Klartextblöcke, um so die Geheimtextblöcke ci zu erhalten:
ci = mi ⊕ ti
Alles was Sie machen, um eine Folge von Pseudozufallsbits zu erzeugen, kann auch ein Angreifer machen. Er kann somit dieselbe Folge von Pseudozufallsbits erzeugen – wenn er den Startwert kennt, den Sie verwendet haben. Oder aber auch, wenn er den Startwert nur richtig errät.
Deshalb kommt der Wahl des Startwerts eine immense Bedeutung zu. Er darf nicht zu erraten sein. Er darf auch nicht durch Ausprobieren aller Möglichkeiten zu ermitteln sein. Angenommen, Sie nehmen die aktuelle sekundengenaue Uhrzeit als Startwert. Die kann ein Angreifer ja nicht kennen, glauben Sie. Aber wenn der Angreifer diese Zeit auf einen Monat eingrenzen kann, dann muss er nur alle 2,6 MIllionen Möglichkeiten durchprobieren – so viele Sekunden hat ein Monat. Mithilfe eines Computers ist dies schnell getan ...
Es kommt also darauf an, die Anzahl der Möglichkeiten möglichst groß und möglichst unvorhersehbar zu machen. Am besten nutzen Sie die Funktionen, die das Betriebssystem zur Verfügung stellt, oder darauf aufbauend, entsprechende Funktionen in Programmiersprachen. In Python dient hierzu das Modul secrets.