Zufallszahlen

Wofür braucht man überhaupt Zufallszahlen? Es gibt recht viele probabilistische Algorithmen, die besser funktinonieren, wenn man „gute“ Zufallszahlen hat. Besonders wichtig sind diese aber auch in der Kryptographie, zum Beispiel zur Generierung von Schlüsseln.

Die Qualität der Zufallszahlen ergibt sich aus der Vorhersehbarkeit des nächsten Werts. Wenn dieser z.B. mit heutigen Mitteln aus bekannten Werten berechnet werden kann oder nur schon dieser berechnete Wert mit höherer Wahrscheinlichkeit zu erwarten ist als bei Gleichverteilung, dann sind die Zufallszahlen nicht mehr optimal. Man kann dann zum Beispiel den „private key“ eines Schlüsselpaars erraten und dadurch die Sicherheit des Verfahrens vermindern.

Nun ist die Frage, ob es wirklichen Zufall in der Natur gibt. Nach heutigen Erkenntnissen glaubt man das und findet als Beispiel den radioakativen Zerfall. Also müßte nur jeder Rechner einen „Radiumkarte“ eingebaut bekommen und schon hätte man überall gute Zuzfallszählengeneratoren zur Verfügung. Doch es gibt einige andere Effekte, die man nutzen kann, z.B. Zenerdioden oder den Luftdruck. Radiowellen aus dem Weltall wären sicher auf den ersten Blick auch gut, aber da diese für jeden empfangbar sind, ist es sehr schwierig, eine Vorhersehbarkeit der Zufallszahlen auszuschließen. Zenerdioden eignen sich wohl auch ganz gut. So kann man recht gute Zufallszahlengeneratoren auf die CPU einbauen: RdRand (en.wikipedia.org) oder rdrand (Intel)

Ist das Thema damit gegessen? Vielleicht, zumindest für viele Anwendungszwecke. Vielleicht traut man dem nicht und braucht dort, wo es wirklich darauf ankommt, noch bessere Verfahren? Auf jeden Fall wird es noch eine Weile dauern, bis man das wirklich verwenden kann. Heute haben das neue Intel-CPUs, wann haben es auch CPUs anderer Hersteller? Wann wird das durch die verschiedenen Betriebssysteme genutzt? Mindestens ein paar Jahre dürfen wir uns noch darauf freuen, daß dieses Feature breit verfügbar ist.

Linux hat einen Zufallszahlengenerator auf OS-Basis, der als /dev/random ansprechbar ist. Dieser nutzt „Zufälligkeiten“ wie Tastatureingaben, Mausbewegungen, vielleicht auch Plattenbewegungen u.s.w. aus. Vielleicht nicht ganz so gut wie rdrand, aber dafür schon lange verfügbar. Vielleicht haben andere Betriebssysteme ähnliche Möglichkeiten.

Wie funktioniert das? Wenn man teilweise zufällige Informationen hat, dann läßt sich das nächste Stück mit einer gewissen Wahrscheinlichkeit vorhersagen. Typisches Beispiel wäre etwa ein Text, der eingegeben wird. Der kann einer abstrakten Sprache angehören, z.B. einer natürlichen Sprache, einer Programmiersprache (mit einer natürlichen Sprache für die Kommentare) oder so etwas. Wenn das einigermaßen fehlerarm eingegeben wird, dann läßt sich ein unvollständiges Wort oft auf nur wenige Arten vervollständigen, so daß von den vielen möglichen Zeichen einige wenige wahrscheinlich sind. Wenn man mal von einem 8-bit-Zeichensatz ausgeht, bringt dieses eine Zeichen vielleicht nur etwa 1 Bit an Information, wenn etwa zwei Vervollständigungen sehr wahrscheinlich sind, statt 8 Bit. Dieses eine Bit wäre idealerweise die Zufälligkeit, also ein Zufallsbit, wenn man es schafft, das herauszudestilieren.

Nun ist es bei eingegebenen Texten etwas schwieriger. Wenn das bekannte Texte sind, etwa weil es abgeschrieben wird, oder wenn es ein ehemaliger Minister schreibt, sogar kopiert wird, dann besteht die Zufälligkeit nur noch in der Auswahl der passenden Texte, aber auch bei selbstgeschriebenen Texten schränkt der Kontext ein, was passen würde und was wahrscheinlich ist. Hinzu kommt das Wissen des Schreibers, dessen „Fingerabdruck“, der sich auch in den verfaßten Texten (oder Programmen oder was auch immer geschrieben wird) ausdrückt. Vielleicht ist das Wissen eines Menschen groß genug, um für viele Jahre oder sogar ein Leben lang Texte zu produzieren, die genug Zufälligkeit enthalten, aber wenn keine neue Information durch Kommunikation einfließt, ist das doch zu hinterfragen. Aber viele von uns arbeiten in Bürotätigkeiten, die in irgendeiner Form überwiegend darin bestehen, zu kommunizieren oder doch zumindest etwas einzugeben oder zu schreiben. Vielleicht gibt es dabei gänzlich unkreative Tätigkeiten, wo man etwas ausfüllen muß und genau eine Lösung richtig ist. Aber alle auch nur teilweise kreativen Tätigkeiten produzieren Information, die ohne diese nicht da war und würden sich somit als Basis für die Zufallszahlengenerierung grundsätzlich eignen.

Wir brauchen vielleicht den Kontakt zu unseren Mitmenschen, um neue Ideen zu entwickeln. Und nun fließt die aufgenommene Information natürlich wieder ein. Deshalb ist die Zufälligkeit der geschriebenen Textinhalte nicht leicht abzuschätzen und sie sinkt vielleicht um eine Größenordnung, wenn man verschiedene der hier angesprochenen Aspekte zu fassen bekommt oder ignoriert, weil man sie für nicht fassbar hält. Nun kann man die Texte aber verlustfrei komprimieren. Wenn man viel darüber weiß, was wirklich die reine Information (oder der Zufallsgehalt) ist, auf eine Größe, die knapp über diesem Informationgehalt liegt. Nun kann man auch geschickte „Hash-Codes“ verwenden, die aus den Texten Bytesquenzen generieren, die etwas kleiner sind, als der Informationsgehalt. Wenn das gut gemacht wird, ist das ein brauchbarer Zufallszahlengenerator, der aber für kryptographische Anwendungen sofort einiges an Wert verliert, wenn man aus der Kommunikation der Person nach dem Verfassen des Textes oder gar aus der direkten Verwendung des Textes Rückschlüsse auf diesen ziehen kann.

Wenn der Text öffentlich oder teilweise öffentlich zugänglich wird, zum Beispiel auf einer Webseite erscheint, wie der Text, der hier gerade geschrieben wird, dann besteht die Zufälligkeit nur noch in der Auswahl des Textes von den Milliarden Webseiten, die es gibt, was aber nur noch maximal ein paar Dutzend Bits sind. Und wer will schon eine kreative Tätigkeit nur für die Zufallszahlengeneration ausüben, ohne daß die eigentlichen Ergebnisse dieser Tätigkeit sinnvoll verwendet werden? Und wer will das gar noch bezahlen?

Die Zeitabstände zwischen den Tastatureingaben sind sicher auch so etwas wie ein Fingerabdruck, was individuell den Schreiber erkennen ließe, aber die Zufälligkeit dieser Zeiten läßt sich viel besser nutzen, weil wir das nicht verwenden, um Information zu transportieren. Ich werde mich also auch nicht erinnern, welche Zeitabstände ich zwischen den Zeichen hatte, außer daß der Schreibrhythmus natürlich beim nächsten Mal ähnlich (aber nicht identisch) sein wird. Und die Zeitabstände sind auch nicht auf dieser Webseite nachlesbar.

Share Button

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.


*