2a. Kryptographische Basistechniken

Algorithmische Zufallserzeugung

(Pseudo-) Zufallsgeneratoern


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.

  1. Bei den »klassischen« Zufallsgeneratoren verlangt man, dass sie übliche statistische Tests bestehen. Beispiele:
  2. Bei den »perfekten« Zufallsgeneratoren verlangt man, dass sich ihr Output durch keinen effizienten Algorithmus von echtem Zufall unterscheiden lässt. Beispiele:


Lineare Kongruenz-Generatoren

Parameter:Modul m ³ 2
Multiplikator a Î [0 .. m-1]
Inkrement b Î [0 .. m-1]
Startwert x0 Î [0 .. m-1]
(Bei der kryptographischen Anwendung wird der Startwert x0 oder aber alle vier Parameter m, a, b, x0 als Schlüssel betrachtet, d. h., geheim gehalten.)

Verfahren

Eine Folge (xi) von Zufallszahlen im ganzzahligen Intervall [0 .. m-1] wird durch folgende Iterationsformel erzeugt:

xi = a × xi-1 + b mod m.

Eigenschaften

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!


Lineare Schieberegister

Parameter:Registerlänge l ³ 2
Rückkopplungsvorschrift I Í [1 .. l]
Startwert (ul-1...u0) Î F2l
(Bei der kryptographischen Anwendung wird der Startwert (u) oder aber alle drei Parameter l, I, (u) als Schlüssel betrachtet, d. h., geheim gehalten.)

Verfahren

Eine Folge (ui) von Zufallsbits wird durch folgende Iterationsformel erzeugt:

[Formel]

[Schieberegister]

Eigenschaften

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!


Kryptographische Sicherheit

Nach einem Satz von YAO sind folgende Eigenschaften eines Zufallsgenerators äquivalent:

  1. Unvorhersagbarkeit: Aus einem Stück der Output-Folge lässt sich kein weiteres Bit der Folge effizient berechnen.
  2. Perfektheit: Es gibt kein effizientes Verfahren, das die Output-Folge von einer Zufallsfolge unterscheiden kann. Insbesondere besteht die Folge jeden effizienten statistischen Test.

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.


Beispiel: Der BBS-Generator

[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
(Bei der kryptographischen Anwendung wird der Startwert x0 als Schlüssel betrachtet, d. h., geheim gehalten.)

Verfahren

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.

Eigenschaften


Der Micali-Schnorr-Generator

[Micali-Schnorr]


Der Rucksack-Generator (Impagliazzo/Naor)

[Impagliazzo/Naor]

Der Rucksack-Generator ist perfekt, wenn das »Rucksack-Problem« (Knapsack Problem, Subset Sum Problem) nicht effizient lösbar ist. Dieses ist NP-vollständig.


Praktisches Beispiel

Konstruktion aus starker Bitblock-Chiffre f (vgl. OFB).

Parameter:Startwert s0,
Schlüsselk.

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.


Vorlesung Datenschutz und Datensicherheit
Autor: Klaus Pommerening, 31. März 1999; letzte Änderung: 11. Juni 2007.
E-Mail an
Pommerening »AT« imbei.uni-mainz.de.