In der technisierten und modernen Welt ist es zur Gewohnheit geworden das alles hochgradig deterministisch ist. Für viele Bereiche ist es essenziell das Vorgänge vorbestimmt und deterministisch ablaufen. So sei an dieser Stelle das Beispiel des Automotors erwähnt, der z.B. mit 3000 Umdrehungen/min arbeitet. Dreitausendmal in der Minute läuft exakt die gleiche mechanische Bewegung ab, dreitausendmal in der Minute kommt es zur selben Verkettung von Ursache und Wirkung, die dem mobilen Leben im Automobil Vortrieb verleiht. Ein Abweichen von diesem deterministischen Prozessgefüge könnte fatale Folgen haben.
Und dennoch hat auch der „Nichtdeterminismus“, also der Zufall seine Bedeutung und Notwendigkeit. Ebenso wie technisierte Gesellschaften auf eine Vielzahl deterministischer Prozesse beruht und angewiesen ist, so hängt diese nicht minder von nicht deterministischen Prozessen ab. Im Allgemeinen ist hier von Zufall die Rede, also von einem Ereignis oder Ereignisketten die nicht vorhersagbar also nicht deterministisch sind, für die es keine kausale Erklärung gibt.
Insbesondere in der Informationstechnik kommen Zufallszahlen und die entsprechenden Methoden und Module zu deren Erzeugung häufiger vor als vielleicht auf den ersten Blick vermutet.
Ein guter Grund dafür einige Aspekte der Erzeugung von Zufallszahlen genauer zu betrachten. Insbesondere die hardwarenahe Umsetzung der zu Grunde liegenden Prinzipien in Logikschaltungen wird in dieser Arbeit untersucht. Nach einer kurzen Einführung in die theoretischen Grundlagen verschiedener Schaltungen folgt ein Entwurf mit konsekutivem simuliertem Verhalten, so dass ein Verständnis für die Umsetzung von der Theorie in die Praxis entsteht.
Am Ende steht für den Leser der Zufall nicht mehr für etwas Unklares, unfassbares oder unbegreifliches, sondern als etwas das man messen, quantifizieren und anwenden kann.
Zielsetzung ist hier nicht ein umfassendes Verständnis des Themas, sondern eine pragmatische Einführung für die Anwendung in Informationstechnik und hier insbesondere in den Bereich der hardwarenahen Umsetzung.
Inhaltsverzeichnis
0 Einleitung
1 Zufall… und seine Folgen
1.1 Grundlagen
1.2 Kriterien an Zufallszahlenfolgen
1.2.1 Verteilung von Zufallszahlen
1.2.2 Periodenlänge bei der Erzeugung
1.2.3 Unvorhersehbarkeit
1.2.4 Reproduzierbarkeit
1.2.5 Korrelation
1.2.6 Entropie
1.2.6.1 Allgemeine Betrachtung
1.2.6.2 Entropie physikalischer Phänomene
1.2.6.3 Entropie in der Informationstechnik
1.3 Zufallszahlengeneratoren
1.3.1 Echter Zufallszahlengenerator (TRNG)
1.3.2 Pseudozufallszahlengeneratoren (PRNG)
1.4 Anwenden und verwenden von Zufall
2 Physische (echte) Zufallszahlengeneratoren
2.1 Ausgewählte typische Entropiequellen in der Informationsverarbeitung
2.1.1 Thermisches Rauschen an passiven Komponenten
2.1.2 Rauschen in Halbleitern
2.1.3 Praktische Umsetzung eines auf Rauschen basierenden Zufallszahlengenerators
2.2 Digitale Rauschquellen
3 Pseudozufallszahlengeneratoren
3.1 Kongruenzgeneratoren
3.2 Linear Rückgekoppelte Schieberegister
3.3 Nicht linear Rückgekoppelte Schieberegister
3.4 Maximale Periodenlänge von NLFSR
4 Praktische Implementierung mit logischen Schaltungen
4.1 Einführungsbeispiel: gemischt linearer 4Bit Kongruenzgenerator
4.1.1 Simulation mit Matlab
4.1.2 Betrachtung ausgewählter Kongruenzgeneratoren aus der Praxis
4.1.2.1 RANDU (historisch auf IBM Mainframes zum Einsatz gekommen)
4.1.2.2 Random Funktion im TI-59 von Texas Instruments
4.1.3 Einschränkung bei der Umsetzung in logischen Schaltungen
4.2 Einführungsbeispiel: 4Bit Fibonacci LFSR
4.2.1 Prinzip Aufbau
4.2.2 Simulation mit Matlab
4.2.3 Betrachtung als endlicher deterministischer Automat
4.2.4 Modellierung und Simulation mit Matlab Simulink
4.2.5 Modellierung und Simulation mit Altera (Intel) Quartus II
4.2.6 Darstellung in VHDL
4.3 Einführungsbeispiel 4-Bit NLFSR
4.3.1 Prinzipieller Aufbau
4.3.2 Simulation mit Matlab
4.3.3 Modellierung und Simulation mit Altera (Intel) Quartus II
4.3.4 Darstellung in VHDL
4.4 16 Bit LFSR mit maximaler Periodenlänge
4.4.1 Prinzipieller Aufbau
4.4.2 Simulation mit Matlab
4.4.3 Modellierung und Simulation mit Altera (Intel) Quartus II
4.4.4 Darstellung in VHDL
4.5 16 Bit NLFSR mit maximaler Periodenlänge
4.5.1 Prinzipieller Aufbau
4.5.2 Simulation mit Matlab
4.5.3 Modellierung und Simulation mit Altera (Intel) Quartus II
4.5.4 Darstellung in VHDL
5 Gütebetrachtung von Zufallszahlengeneratoren
5.1 Referenzgenerator
5.2 Vergleich verschiedener PRNGs
5.2.1 Randu
5.2.2 TI-59
5.2.3 16 Bit LFSR
5.2.4 16 Bit NLFSR
Zielsetzung & Themen
Diese Arbeit untersucht die hardwarenahe Umsetzung und Simulation von Pseudozufallszahlengeneratoren in logischen Schaltungen, um ein praktisches Verständnis von der theoretischen Erzeugung des Zufalls in der Informationstechnik zu vermitteln.
- Grundlagen von Zufallszahlenfolgen und Gütekriterien
- Physische versus algorithmische Zufallserzeugung
- Implementierung von linearen (LFSR) und nicht-linearen (NLFSR) rückgekoppelten Schieberegistern
- Simulation und Validierung mittels Matlab und Altera Quartus Prime
- Vergleichende Gütebetrachtung verschiedener Generatortypen
Auszug aus dem Buch
3 Pseudozufallszahlengeneratoren
PRNGs beruhen auf deterministischen Algorithmen und lassen sich daher formal als endliche deterministische Automaten (deterministischer endlicher Automat (DEA) oder deterministic finte state machines (DFM) beschreiben:
A = (, S, , Zstart, F)
Es sei das Eingabealphabet, das Ausgabealphabet, S die Zustandsmenge des Automaten, die Zustandsüberführungsfunktion, die Ausgabefunktion, Zstart S der Startzustand des Automaten und F S der oder die Endzustände des Automaten.
Bei einer binären Kodierung sind für gewöhnlich S=F ergibt sich aufgrund der Periodizität die alle PRNGs aufweisen, d.h. nach Durchlaufen des Zustandsraums des Automaten beginnt der Zyklus von vorne und der Zustandsraum wird erneut immer wieder durchlaufen.
Aus der Eigenschaft „endlich“ ergibt sich, dass die Zustandsmenge beschränkt ist und die logische Implementierung Speicherelemente enthalten muss, die durch eine binäre Kodierung den Zustandsraum abdecken können.
So sind für 24 mögliche Zustände 4 Speicherzellen notwendig um die 16 Zustände abbilden zu können. Dies maximal möglichen Zustände (S) sind jedoch nicht mit der maximalen Periodenlänge (P) eines PRNGs gleichzusetzten, diese ist immer kleiner als die mögliche Zustandsmenge und im Allgemeinen abhängig vom mathematischen Modell welches den Rechenvorschriften zugrunde liegt.
Pmax < |S|max
Die maximal erzielbare Periodenlänge ist hierbei:
Pmax = 2|S|-1
welche im Allgemeinen von der Abbildungsvorschrift und den zugehörigen Rahmenparametern beeinflusst wird. [Vergleiche hierzu 12]
Die Operationen, welche in den Abbildungsvorschriften, bzw. Algorithmen Verwendung finden sind hierbei typischerweise AND und XOR Verknüpfungen durch welche die Rechenoperationen des Algorithmus umgesetzt werden. Darüber hinaus beruht die Arithmetik in den binären Systemen auf das Rechnen im Restklassenringen und hier im konkreten auf dem Rechnen in /2 = {0. 1} (Modulo 2). Dies wiederum impliziert, dass sich die binäre Addition durch eine XOR-Verknüpfung und die binäre Multiplikation durch eine AND Verknüpfung effektiv umsetzen lassen (Operationen ohne Übertrag).
Zusammenfassung der Kapitel
0 Einleitung: Bietet einen Überblick über die Bedeutung des Zufalls in technischen Systemen und umreißt die Zielsetzung der Arbeit.
1 Zufall… und seine Folgen: Definiert die Grundlagen von Zufallszahlenfolgen sowie relevante Gütekriterien wie Verteilung, Periodenlänge und Entropie.
2 Physische (echte) Zufallszahlengeneratoren: Untersucht physikalische Entropiequellen, insbesondere Rauschen, als Grundlage für echte Zufallszahlengeneratoren.
3 Pseudozufallszahlengeneratoren: Behandelt die mathematische Modellierung von PRNGs als endliche deterministische Automaten und führt in die Logik von Schieberegistern ein.
4 Praktische Implementierung mit logischen Schaltungen: Dokumentiert den Entwurf und die Simulation von Kongruenzgeneratoren, LFSR und NLFSR mittels Matlab und Quartus Prime.
5 Gütebetrachtung von Zufallszahlengeneratoren: Vergleicht die statistische Qualität verschiedener Generatortypen anhand von grafischen Auswertungen.
6 Fazit: Fasst die Ergebnisse zusammen und bewertet die Eignung der untersuchten Implementierungen für verschiedene Anwendungsgebiete.
Schlüsselwörter
Zufall, Zufallszahlen, Pseudozufallszahlengeneratoren, PRNG, LFSR, NLFSR, Entropie, Hardware, Logische Schaltungen, Simulation, FPGA, Quartus Prime, Matlab, VHDL, Periodenlänge
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit befasst sich mit der Erzeugung von Zufallszahlen in technischen Systemen, wobei der Schwerpunkt auf der hardwarenahen Implementierung in logischen Schaltungen liegt.
Was sind die zentralen Themenfelder?
Die zentralen Themen umfassen die theoretischen Grundlagen der Zufallserzeugung, den Unterschied zwischen physikalischen und algorithmischen Generatoren sowie die praktische Modellierung und Simulation.
Was ist das primäre Ziel der Arbeit?
Das primäre Ziel ist eine pragmatische Einführung in die hardwarenahe Umsetzung von Pseudozufallszahlengeneratoren, ergänzt durch Simulationen, um ein Verständnis für die Anwendung in der Informationstechnik zu fördern.
Welche wissenschaftliche Methode wird verwendet?
Es werden methodische Ansätze aus der Digitaltechnik, Informatik und Mathematik kombiniert, um Generatoren zu entwerfen, in Matlab und Quartus Prime zu simulieren und deren Güte grafisch zu bewerten.
Was wird im Hauptteil behandelt?
Der Hauptteil widmet sich detailliert der Implementierung verschiedener Generatortypen wie linearen Kongruenzgeneratoren, LFSR und NLFSR, inklusive deren VHDL-Umsetzung.
Welche Schlüsselwörter charakterisieren die Arbeit?
Die Arbeit lässt sich durch Begriffe wie Zufallszahlengeneratoren, LFSR, NLFSR, Hardware-Implementierung, Simulation und Gütebetrachtung charakterisieren.
Warum ist die Wahl des Initialisierungsvektors für Automaten kritisch?
Ein Initialisierungsvektor darf nicht Null sein, da dies beim Modell als endlicher deterministischer Automat nicht zum gewünschten zyklischen Verhalten führt.
Eignen sich die untersuchten Generatoren für kryptographische Zwecke?
Die Arbeit kommt zu dem Schluss, dass einfache Implementierungen von (N)LFSR aufgrund ihrer Neigung zur Strukturbildung für kryptographische Zwecke im Allgemeinen ungeeignet sind.
- Citation du texte
- Andreas Hümmer (Auteur), 2020, Design und Simulation von PRNGs in Logischen Schaltungen, Munich, GRIN Verlag, https://www.grin.com/document/542616
