Zufallszahlen aus der Webcam

Ein Generator für kryptografisch sichere Zufallszahlen ist entweder langsam oder teuer. Nicht so die RandCam: Mit nur 10 Euro für die Hardware sind Sie dabei, die Software kostet nix — und trotzdem sind erstaunlich hohe Erzeugungsraten von mehr als 100 KByte pro Sekunde drin.

Auf der Suche nach einem besonders guten und gleichzeitig hübsch anzusehenden Generator ist SGI vor einigen Jahren das LavaRand-Projekt eingefallen: Eine Webcam filmte das Wabern der Wachs-Blobs in Lava-Lampen. Aus jedem aufgenommenen Bild erzeugte eine Software 140 Zufallsbytes. Das Projekt wurde um die Jahrtausendwende eingestellt und einer der Schöpfer, Landon Curt Noll, führte es eigenverantwortlich in Gestalt von LavaRnd fort. Statt Lava-Lampen setzt Noll ausschließlich auf eine einfache Webcam als Zufallsquelle. Der Zufall stammt aus dem elektronischen Rauschen, das der Bildsensor produziert.

Aus einem Bild entstehen so n × 20 Bytes Zufallszahlen. Der Wert für n ergibt sich aus einem Koeffizienten, der umso höher ausfallen darf, je größer die im Bildrauschen vermutete Entropie ist. Standardmäßig verwendet die LavaRnd-Software n = 17. Bei 25 Bildern pro Sekunde ergibt sich eine Zufallszahlenrate von 17 × 20 × 25 = 8500 Bytes pro Sekunde.

Ziemlich wenig. Deshalb reifte die Idee, das Verfahren weiter auszureizen und einen Zufallszahlengenerator zu entwickeln, der auf eine deutlich höhere Rate kommt. Das Ergebnis: Die Randcam. Die zugrundeliegende Software randcam verwendet zur Entropiesammlung allerdings nicht wie Nolls Lavarnd den Helligkeitskanal (Y-Kanal) der Webcam-Bilder, sondern die Differenz aus allen drei Farbkanälen (RGB) zweier Bilder. Die Differenzbildung schaltet alles Unveränderliche (lies: Nichtrauschen) aus; übrig bleibt das Rauschen. Der Algorithmus zur Bildung von Zufallszahlen aus dem Datenwust jedes Differenzbildes fügt die Bytes in der ersten Stufe im Reißverschlussverfahren zu n Blöcken neu zusammen. Daraus berechnet er n MD5-Hashes à 16 Bytes.

Den Wert von n ermittelt randcam aus der Entropie für jedes Differenzbild nach der Formel n = (E · s · α / h)1/2 neu, wobei E für die Entropie in Bits pro Bit, s für die Anzahl der im Bild enthaltenen Bytes und h für die Größe des Hash (in Bytes) steht. Die Variable α gibt einen Koeffizienten an, der sicherheitshalber im Bereich zwischen 0,1 und 1 liegt, prinzipiell aber auch deutlich über 10 liegen kann. Voreingestellt ist 2,5. Höhere Werte führen zu höheren Datenraten — aber auch gegebenenfalls schlechteren Ergebnissen bei den statistischen Tests. Die Zufallszahlen aus dem Rauschen der Test-Webcams (Logitech QuickCam Pro 5000, Logitech QuickCam Express und Philip ToUCam 740 Pro) hielten in unseren Versuchen selbst bei einem α von 30 noch den meisten statistischen Tests stand — was zu einer Zufallszahlenrate von bis zu 200 KByte/s führte.

Wer nun glaubt, die Entropie durch eine Verlängerung der Belichtungszeit erhöhen zu können und damit die Zufallszahlenerzeugungsrate zu steigern, sägt an dem Ast, auf dem er sitzt: Die Anzahl der Bilder pro Sekunde geht mit längerer Belichtungszeit nämlich in den Keller — und mit ihr die Datenrate, weil die Entropie durch "Verdunkelungsmaßnahmen" kaum steigt. Um das Rauschen ohne Verlängerung der Belichtungszeit zu verstärken, empfiehlt es sich, die elektrische Verstärkung auf Maximum zu drehen. Diese Option bietet jedoch nicht jeder Webcam-Treiber an.

Zur Ansteuerung der Webcam setzt die Software auf die frei erhältliche Bibliothek OpenCV. Dank OpenCV lässt sich randcam plattformübergreifend einsetzen. Unter Windows funktioniert sie problemlos mit jeder Webcam, für die es einen Windows-Treiber gibt. Linux ist trotz breiter Webcam-Unterstützung durch Video4Linux etwas zickiger. Hinweise zur Installation von OpenCV bietet die Projekt-Homepage.

Installation

RandCam benötigt aktuelle C++-Laufzeitbibliotheken. Unter Linux sind sie typischerweise gleich dabei, Windows-Nutzer müssen sie gegebenenfalls in Gestalt des Microsoft Visual C++ 2008 SP1 Redistributable Package nachinstallieren:

Zur Ansteuerung der Webcam verwendet RandCam die Bibliothek OpenCV. Die Datei OpenCV_1.1pre1a.exe ist an beliebiger Stelle zu installieren, zum Beispiel nach C:\Programme\OpenCV. Das Verzeichnis C:\Programme\OpenCV\bin ist dem Systempfad hinzuzufügen. Unter Windows ist dazu die Umgebungsvariable PATH anzupassen (Arbeitsplatz/Eigenschaften/Erweitert/Umgebungsvariablen/Systemvariablen).

Die RandCam-Software ist im Download-Archiv der Random-Tools enthalten. Entpacken Sie das Archiv in ein beliebiges Verzeichnis, öffnen Sie eine Kommandozeile/Eingabeaufforderung und wechseln Sie in das betreffende Verzeichnis.

Los gehts …

Das Verhalten von randcam lässt sich über einige Kommandozeilenparameter festlegen. Der Schalter --cam bestimmt, welche Kamera randcam verwenden soll. Momentan unterstützt OpenCV nur zwei gleichzeitig angeschlossene Kameras, die Zählung beginnt bei 0. Der Schalter --alpha bestimmt den Koeffizienten für die Datenrate. Der Aufruf von

randcam --cam=1 --alpha=2.5

wählt demnach die zweite Webcam und einen Koeffizienten von 2,5. Weitere Kommandozeilenparameter listet der Aufruf von randcam --help auf.

Die RandCam liefert bei geringen Datenraten (je nach Lichtverhältnissen und dem Wert für α zwischen 4 und 200 KByte/s) Zufallszahlen, die alle gängigen statistischen Tests bestehen. Billige Webcams mit 0,3 Megapixel (640×480 Bildpunkte) bekommt man schon für 10 Euro.

Zur Verbesserung des ästhetischen Eindrucks (und gleichzeitig geringfügiger Steigerung der Entropie) kann man wie beim Lavarand genannten Urahn ein paar Lava-Lampen vor die Kamera stellen — muss dann aber auch mit hohen Stromkosten und einem schlechten ökologischen Gewissen leben. (ol)

Letzte Änderung: $Date: 2009/02/05 14:10:44 $

nach oben