21C3 Schedule Release 1.1.7

21st Chaos Communication Congress
Lectures and workshops

Speakers
Picture of Rolf Freitag Rolf Freitag
Schedule
Day 1
Location Saal 2
Start Time 15:00 h
Duration 01:00
INFO
ID 49
Type Lecture
Track Hacking
Language german
FEEDBACK

Zufallszahlengeneratoren

Zufallszahlengeneratoren mit zentralem Grenzwertsatz und Lötkolben

Vorgestellt werden Verfahren und Schaltpläne sowie Hardware zum Erzeugen von Zufallszahlen und zugehörige mathematische Beweise. Im Mittelpunkt stehen Zufallszahlengeneratoren, die auf dem zentralen Grenzwertsatz basieren und sich auch für schnelle Anwendungen wie Rausch-Radar eignen. Einige dieser Generatoren werden auch gezeigt und vorgeführt.

Zufallszahlengeneratoren gibt es zwar viele und in vielen verschiedenen Formen, aber nur die wenigsten können echte, also nicht berechenbare, Zufallszahlen erzeugen, die keine statistischen Auffälligkeiten haben sodass sie meist eine Nachbearbeitung erfordern.

Zudem gab es vor dem hier vorgestellten Verfahren keine schnellen echten Zufallszallengeneratoren ohne statistische Auffälligkeiten, sodass Anwendungen wie Korrelationsmessverfahren mit echten Zufallszahlen nur bei relativ niedrigen Taktfrequenzen von weit weniger als 1 MHz möglich waren.

Mit dem hier vorgestellten Verfahren gibt es weder das Problem der Nachbearbeitung noch der niedrigen Taktfrequenz, weil einfach für jedes Bit einer Zufallszahl viele (>10) primäre Zufallsbits von sehr schnellen echten Zufallsbitgeneratoren modulo 2 addiert werden. Aus dem zentralen Grenzwertsatz folgt nämlich, dass diese Modulo-2-Summe auch bei statistischen Auffälligkeiten der primären Bits bei ausreichend vielen nicht mehr in der Modulo-2-Summe vorhanden sind, d. h. eine Nachbearbeitung ist nicht nötig! Die Modulo-2-Addition wird von einem Paritätsgenerator innerhalb einer Taktperiode durchgeführt und die primären Zufallsbits werden im einfachsten Fall von Invertern mit auf den Eingang geschaltetem Ausgang (=Ring-Oszillator der Länge 1) erzeugt.

Dadurch kann man den Zufallszahlgenerator rein digital aufbauen und komplett in einen IC integrieren. Durch den digitalen Aufbau entfallen auch Probleme wie eine Abschirmung oder Arbeitspunkte die von Temperatur, Alterung, Versorgungsspannung und anäerem abhängen.

Realisiert wurden bisher solche Zufallszahlengeneratoren schon Ende der 90er hot-swap-fähig für den Parallelport, ISA-Bus und PCI-Bus mit Geschwindigkeiten zwischen 1 bis 160 MByte/s.

Diese Zufallszahlengeneratoren können unter anderem für stochastische Resonanz, genetische Algorithmen, Monte-Carlo-Simulationen, Glücksspiele, Surrogatdaten-Methode oder auch zum Erzeugen von PINs, TANs und kryptographischen Schlüsseln verwendet werden.

Sie eignen sich auch für Korrelationsmessverfahren wie Rauschradar, und weil das Amplituden-Spektrum von zufälligen Folgen unabhängiger Bits weißes Rauschen ist (zumind. bis Taktfrequenz/4), können sie auch als Rauschgeneratoren oder sehr breitbandige Störsender verwendet werden.

Neben dem theoretischen Teil gibt es Schaltpläne und einige Zufallszahlengeneratoren mit Beschreibung und auch zum Anfassen.

Ein kleiner Zufallszahlengenerator (rp1) für den Parallelport wird live vorgeführt.