Der Mathe­matik hinter Zufalls­zahl­ge­ne­ra­toren auf der Spur

Zufalls­zahlen finden in vielen Bereichen Anwendung. Aber wie werden sie eigentlich erzeugt und sind Zufalls­zah­len­ge­ne­ra­toren sicher?

Heut­zutage gene­rieren Com­puter Zufalls­zahlen für alle mög­lichen Bereiche, von Video­spielen bis hin zu Glücks­spiel oder der Kryp­to­grafie. Zu unter­scheiden ist dabei zwi­schen „echten“ Zufalls­zahlen und Pseu­do­zu­falls­zahlen. Für die Sicherheit der Ver­schlüs­se­lungs­systeme ist dieser Unter­schied wichtig.

Nicht alle Men­schen glauben daran, dass Zufalls­zah­len­ge­ne­ra­toren wirklich zuver­lässig arbeiten. Wir haben uns dafür einmal ange­sehen, wie Zufalls­zahlen über­haupt gene­riert werden und wo genau sie zum Einsatz kommen.

Wo sind Zufalls­zahlen wichtig? 

Bereits seit tau­senden von Jahren nutzt man Zufalls­zahlen oder zufällige Ergeb­nisse. Man denke nur einmal an den klas­si­schen Münzwurf. Das Ergebnis über­lässt man hier dem Zufall. Die Zufalls­zahlen, die in Com­putern zum Einsatz kommen, sind ähnlich. Sie stellen einen Versuch dar, ein zufäl­liges und unvor­her­seh­bares Ergebnis zu erzeugen.

Genutzt werden können Zufalls­zahlen für unter­schied­liche Zwecke. Offen­sichtlich ist zum Bei­spiel die Anwendung bei Glücks­spielen oder zur Erzeugung zufäl­liger Ergeb­nisse bei Com­pu­ter­spielen. Im Bereich der Kryp­to­grafie wie­derum benötigt man Zahlen, welche Angreifer nicht erraten können. Ent­spre­chend können nicht immer wieder die­selben Zahlen genutzt werden. Statt­dessen sollen Zahlen auf eine unvor­her­sehbare Weise gene­riert werden, sodass es Angreifern unmöglich wird, sie zu erraten. Diese Zufalls­zahlen sind bei sicheren Ver­schlüs­se­lungen essen­tiell. Dabei ist es egal, ob man eigene Daten ver­schlüsseln möchte oder auf eine beliebige Web­seite im Internet zugreift.

Inter­essant dabei ist, dass es ein Miss­ver­ständlich darüber gibt, wie zufällig gene­rierte Zah­lungen funk­tio­nieren. Denn eigentlich sind sie alles andere als zufällig, sondern das Ergebnis kom­pli­zierter mathe­ma­ti­scher Algorithmen.

Pseudo-Zufalls­zah­len­ge­ne­ra­toren

In der Regel handelt es sich bei Zufalls­zah­len­ge­ne­ra­toren um eine Software, die keine echten Zufalls­zahlen aus­spuckt. Statt­dessen nutzen diese Zufalls­zah­len­ge­ne­ra­toren Algo­rithmen, welche die Auswahl eines Werts limi­tieren. So nähert man sich der echten Zufäl­ligkeit an. Der Benutzer kann hier den Bereich oder die Ver­teilung fest­legen, aus denen die Zufallszahl gewählt wird. Es kann also zum Bei­spiel ein nied­rigster und höchster Wert fest­gelegt werden. Der Zufalls­zah­len­ge­ne­rator ist dann in der Lage, sofort eine Zahl auszugeben.

Für die meisten Anwen­dungen sind die so erzeugten Zufalls­zahlen aus­rei­chend. Bei sicheren kryp­to­gra­fi­schen Imple­men­tie­rungen sollte man sich aber nicht einfach so auf sie ver­lassen. Hier ist ein besonders sicherer Peudo-Zufalls­zahl­ge­n­ge­ne­rator von Nöten.

Echte Zufalls­zahlen 

Man unter­teilt die von Com­putern erzeugten Zufalls­zah­len­ge­ne­ra­toren für gewöhnlich in zwei Arten. Neben den beschrie­benen Pseudo-Zufalls­zahlen gibt es dann die „echten“ Zufalls­zahlen. Um eine „echte“ Zufallszahl zu gene­rieren, wird am Com­puter eine Art phy­si­ka­li­sches Phä­nomen gemessen. Dieses findet außerhalb der Maschine statt, also etwa den radio­ak­tiven Zerfall eines Atoms, den wir noch aus dem Schul­un­ter­richt kennen. Hier legt die Quan­ten­theorie fest, dass es keine Gewissheit darüber gibt, wann genau der Zerfall ein­treten wird. Es handelt sich also eigentlich um eine reine Zufallszahl des Uni­versums. Es lässt sich nicht genau vor­her­sagen, wann der Zeit­punkt ein­tritt – einen Zufallswert kann man also nicht kennen.

Ver­ein­facht aus­ge­drückt heißt das, dass ein echter Zufalls­zahl­ge­ne­rator kryp­to­gra­fisch sicher ist und phy­si­ka­lische Eigen­schaften wie ther­mische oder atmo­sphä­rische Bedin­gungen berück­sichtigt. Hierbei können auch Mess­fehler berück­sichtigt werden. Auch phy­si­ka­lische Ver­fahren wie der Wür­felwurf gehören dazu. Ein wei­teres Bei­spiel findet sich im Alltag: Der Com­puter könnte erfassen, wann auf der Tas­tatur getippt wird. Sammelt er genug Daten, kann das als Grundlage zur Erzeugung einer echten Zufallszahl genutzt werden. So ergibt sich eine Entropie-Quelle, die zur Gene­rierung echter Zufalls­zahlen ver­wendet werden kann.

Schauen wir uns ein wei­teres Bei­spiel an: Ent­wickler soll die Arbeit erleichtert werden, indem bei Intel-Chips Zufalls­zah­len­ge­ne­ra­toren inte­griert werden, die sichere Zufalls­zahlen gene­rieren können. Das Ganze nennt sich RdRand. Der Chip nutzt eine Entro­pie­quelle, die auf dem Pro­zessor angelegt ist, und stellt der Software zufällige Zahlen bereit, wenn diese sie anfordert.

Kri­tiker sagen, dass es sich hierbei um eine Art schwarzes Loch handelt, da wir nicht wissen, was genau im Inneren pas­siert. Gibt es zum Bei­spiel eine „Hin­tertür“, dann könnte die Regierung in der Lage sein, Ver­schlüs­se­lungen zu knacken.

Alles in allem ist zu beachten, dass es keine echten Zufalls­zah­len­ge­ne­ra­toren gibt. Sie erzeugen bloß Zahlen, welche für Nor­mal­sterb­liche zufällig wirken.

Vor- und Nach­teile von Zufallszahlengeneratoren 

Zufalls­zah­len­ge­ne­ra­toren, auf RNGs genannt, bieten für ver­schiedene Systeme ein hohes Maß an Sicherheit. Dabei sind Pseudo-Zufalls­zah­len­ge­ne­ra­toren ein­facher zu imple­men­tieren und können im Ver­gleich zu den echten Zufalls­zahlen zügiger gene­riert werden. Ist der Aus­gangs­punkt bekannt, dann ist eine Repro­duktion der bestehenden Sequenz möglich.

Doch wo es Vor­teile gibt, da lassen auch Nach­teile nicht lange auf sich warten: Die echten Zufalls­zah­len­ge­ne­ra­toren sind sehr teuer in der Imple­men­tierung. Nutzt man einen linearen kon­gru­enten Gene­rator, dann hängen die erzeugten Zufalls­zahlen zudem von der Bit­po­sition ab. Das wie­derum heißt, dass die oberen Bits zufäl­liger sind als die unteren.

Mit all diesen Infor­ma­tionen stehen wir noch recht am Anfang, denn hinter Zufalls­zah­len­ge­ne­ra­toren steckt kom­plexe Mathe­matik, die je nach Umfang und Anwen­dungs­gebiet nicht leicht zu begreifen ist. Wer sich mit den Grund­lagen aus­ein­an­der­setzt, merkt aber schnell, dass sie in vielen ver­schie­denen Bereichen zum Einsatz kommen. Für viele Anwen­dungen genügen ein­fache RNGs, doch Experten stehen auch immer wieder vor neuen Her­aus­for­de­rungen, wenn es darum geht, besonders sichere Systeme zu ent­wi­ckeln, die vor Hacker-Angriffen mög­lichst geschützt sein müssen.