6.1.3. Traditional Pseudo-random Sequences (Traditionelle Pseudo-Zufallssequenzen)

6.1.3. Traditional Pseudo-random Sequences (Traditionelle Pseudo-Zufallssequenzen)

Dieser Abschnitt behandelt traditionelle Quellen deterministischer oder "Pseudo-Zufalls"-Zahlen. Diese beginnen typischerweise mit einer "Seed"-Größe und verwenden einfache numerische oder logische Operationen, um eine Sequenz von Werten zu erzeugen. Beachten Sie, dass keine der in diesem Abschnitt diskutierten Techniken für kryptographische Verwendung geeignet ist. Sie werden zur allgemeinen Information präsentiert.

[KNUTH] hat eine klassische Darstellung über Pseudo-Zufallszahlen. Anwendungen, die er erwähnt, sind Simulationen von Naturphänomenen, Stichprobenziehung, numerische Analyse, Testen von Computerprogrammen, Entscheidungsfindung und Spiele. Keine davon hat die gleichen Eigenschaften wie die Arten von Sicherheitsverwendungen, über die wir sprechen. Nur bei den letzten beiden könnte es einen Gegner geben, der versucht, die Zufallsgröße zu finden. In diesen Fällen hat der Gegner jedoch normalerweise nur eine einzige Chance, einen erratenen Wert zu verwenden. Beim Erraten von Passwörtern oder beim Versuch, ein Verschlüsselungsschema zu brechen, hat der Gegner normalerweise viele, vielleicht unbegrenzte Chancen, den korrekten Wert zu erraten. Manchmal kann der Gegner die zu brechende Nachricht speichern und sie wiederholt angreifen. Es wird auch angenommen, dass Gegner von einem Computer unterstützt werden.

Zum Testen der "Zufälligkeit" von Zahlen schlägt Knuth eine Vielzahl von Maßnahmen vor, einschließlich statistischer und spektraler. Diese Tests überprüfen Dinge wie Autokorrelation zwischen verschiedenen Teilen einer "zufälligen" Sequenz oder Verteilung ihrer Werte. Aber diese Tests könnten von einer konstanten gespeicherten Zufallssequenz erfüllt werden, wie der "zufälligen" Sequenz, die in den CRC Standard Mathematical Tables gedruckt ist [CRC]. Trotz Erfüllung aller von Knuth vorgeschlagenen Tests ist diese Sequenz für kryptographische Verwendung ungeeignet, da angenommen werden muss, dass Gegner Kopien aller häufig veröffentlichten "zufälligen" Sequenzen haben und in der Lage sind, die Quelle zu erkennen und zukünftige Werte vorherzusagen.

Eine typische Pseudo-Zufallszahlengenerierungstechnik ist der lineare Kongruenz-Pseudo-Zufallszahlengenerator. Diese Technik verwendet modulare Arithmetik, bei der der Wert mit der Nummer N+1 aus dem Wert mit der Nummer N berechnet wird durch

V    = ( V  * a + b )(Mod c)
 N+1      N

Die obige Technik hat eine starke Beziehung zu linearen Schieberegister-Pseudo-Zufallszahlengeneratoren, die kryptographisch gut verstanden sind [SHIFT*]. In solchen Generatoren werden Bits an einem Ende eines Schieberegisters als Exklusiv-Oder (binäre Summe ohne Übertrag) von Bits aus ausgewählten festen Abgriffen in das Register eingeführt. Betrachten Sie zum Beispiel das Folgende:

  +----+     +----+     +----+                      +----+
  | B  | <-- | B  | <-- | B  | <--  . . . . . . <-- | B  | <-+
  |  0 |     |  1 |     |  2 |                      |  n |   |
  +----+     +----+     +----+                      +----+   |
    |                     |            |                     |
    |                     |            V                  +-----+
    |                     V            +----------------> |     |
    V                     +-----------------------------> | XOR |
    +---------------------------------------------------> |     |
                                                          +-----+

   V    = ( ( V  * 2 ) + B  XOR  B ... )(Mod 2^n)
    N+1         N         0       2

Die Qualität traditioneller Pseudo-Zufallszahlengenerator-Algorithmen wird durch statistische Tests an solchen Sequenzen gemessen. Sorgfältig gewählte Werte a, b, c und anfängliches V oder sorgfältig gewählte Platzierung des Schieberegister-Abgriffs im obigen einfachen Prozess können exzellente Statistiken erzeugen.

Diese Sequenzen können in Simulationen (Monte-Carlo-Experimenten) ausreichend sein, solange die Sequenz orthogonal zur Struktur des zu erforschenden Raums ist. Selbst dort können subtile Muster Probleme verursachen. Solche Sequenzen sind jedoch eindeutig schlecht für die Verwendung in Sicherheitsanwendungen. Sie sind vollständig vorhersagbar, wenn der Anfangszustand bekannt ist. Abhängig von der Form des Pseudo-Zufallszahlengenerators kann die Sequenz aus der Beobachtung eines kurzen Teils der Sequenz bestimmbar sein [SCHNEIER, STERN]. Zum Beispiel kann man mit den obigen Generatoren V(n+1) bestimmen, wenn man Kenntnis von V(n) hat. Tatsächlich wurde gezeigt, dass mit diesen Techniken, selbst wenn nur ein Bit der Pseudo-Zufallswerte freigegeben wird, der Seed aus kurzen Sequenzen bestimmt werden kann.

Nicht nur wurden lineare Kongruenz-Generatoren gebrochen, sondern Techniken sind jetzt bekannt, um alle polynomialen Kongruenz-Generatoren zu brechen [KRAWCZYK].