Zufallszahlen

Aus der Mikrocontroller.net Artikelsammlung, mit Beiträgen verschiedener Autoren (siehe Versionsgeschichte)
Wechseln zu: Navigation, Suche

Oft wird im Forum die Frage gestellt, wie man denn auf einem Mikrocontroller Zufallszahlen erzeugen kann. Diese Seite soll nur einen groben Überblick über das Thema Zufallszahlen bieten, und vor allem deutlich machen, dass es schwieriger ist als es auf den ersten Blick scheint.

Pseudozufallszahlen

Mit verschiedenen Algorithmen lassen sich Zahlenfolgen erzeugen, die zufällig aussehen. Wichtig ist dabei: Die Zahlen erwecken nur den Anschein, zufällig zu sein, sind es aber nicht. Wenn man das Programm 100 mal startet, dann entsteht 100 mal die gleiche Zahlenfolge, das heißt z. B. der MP3-Player spielt im Random-Modus die Lieder immer in der gleichen Reihenfolge ab. Um das zu verhindern, kann man den Generator mit einer echt zufälligen Zahl initialisieren. Das ändert jedoch nichts daran, dass die erzeugte Folge immer die selbe ist - sie fängt nur immer an einer anderen Stelle an. Bei Generatoren mit genügend langer Periodendauer stellt das für viele Anwendungen kein Problem dar; man muss sich aber darüber im Klaren sein, dass die Folge nicht zufällig ist, sondern von jedem, der den Algorithmus und den Startwert kennt (etwa weil er ihn durch Ausprobieren bestimmt hat), reproduziert werden kann.

Probleme bei der Generierung von Zufallszahlen

Computer sind deterministische Maschinen und Pseudozufallszahlen werden durch streng deterministische Algorithmen erzeugt, sie sind also nicht zufällig. Sie haben allerdings die wichtigsten Eigenschaften von echten Zufallszahlen (Unvorhersehbarkeit, Gleichverteilung, jedoch nicht Unabhängigkeit, da in der Regel die folgende Zahl aus der aktuellen berechnet wird).

Generiert werden immer nur Zahlen aus einem begrenzten Intervall (z. B. Doppelworte zwischen 0 bis [math]\displaystyle{ 2^{32}-1 }[/math] oder Fließkommazahlen zwischen 0 bis 1). Da jede Zufallszahl [math]\displaystyle{ z_i }[/math] zu einer bestimmten Zahl [math]\displaystyle{ z_{i+1} }[/math] führt, der Wertebereich jedoch begrenzt ist, ist jeder Zufallszahlengenerator periodisch; eine weitere Forderung ist somit eine große Periodenlänge.

Pseudozufallsgeneratoren

TODO: LCG, usw.

Siehe u. a. A Survey of Pseudo Random Number Generators By Jeffrey Walton.

Echte Zufallszahlen

"Echter" Zufall bedeutet, dass eine Zufallszahl von niemandem vorhergesagt werden kann, weil sie durch nicht deterministische physikalische Prozesse erzeugt wird. Ein Beispiel ist thermisches Rauschen, aber auch aus dem Verkehr in einem Netzwerk oder den Eingaben eines Benutzers auf der Tastatur kann man Daten gewinnen, die einen gewissen Anteil an echtem Zufall enthalten.

Wozu echten Zufall?

Für kyptographische Anwendungen benötigt man echten Zufall. Ein Beispiel: Wir möchten einen Schlüssel erzeugen, um damit Daten zu verschlüsseln. Wie der Schlüssel danach zum Empfänger kommt, damit dieser die Daten damit wieder entschlüsseln kann, sei mal dahingestellt. Der Verschlüsselungsalgorithmus, den wir anwenden möchten, benötigt einen 128 Bit langen Schlüssel. Da es so umständlich ist, auf dem Controller echten Zufall zu erhalten, könnte man jetzt auf die Idee kommen, nur z. B. 16 zufällige Bits einzulesen, z. B. aus dem Rauschen des AD-Wandlers, und dann mit einem sehr guten (siehe oben) Pseudozufallszahlengenerator den 128 Bit langen Schlüssel zu erzeugen. Der Zufallszahlengenerator ist so gut, dass die 128 Bit für jeden Beobachter nicht von Zufall unterscheidbar sind. Wo ist nun das Problem? Entscheidend für die Sicherheit des Schlüssels ist, wie viele verschiedene Schlüssel es aus Sicht des Angreifers überhaupt geben kann. In diesem Fall verwenden wir 16 Zufallsbits, womit es nur 2^16 = 65536 Schlüssel gibt, was sehr viel weniger sind als bei einem echt zufällig erzeugten Schlüssel mit 128 Zufallsbits (2^128 = 340282366920938463463374607431768211456). Wenn der Angreifer den für die Schlüsselerzeugung verwendeten Algorithmus kennt (wovon man ausgehen muss), dann hat er also leichtes Spiel.

Wie gewinnt man echte Zufallszahlen?

Bei Mikrocontrolleranwendungen bieten sich folgende Quellen für mehr oder weniger guten, echten Zufall an:

  • Abstände zwischen Tastendrücken oder anderen externen Ereignissen (mit hoher Auflösung messen, untere Bits verwenden)
  • Rückkopplung über einen IO-Port
  • Rauschen eines ADC (unteres Bit verwenden)
  • Rauscheffekt einer Z-Diode

Das alleinige Rauschen eines ADC ist meist unzureichend, wegen des Empfangs äusserer Frequenzen und einer nicht genügend grossen Aussteuerung. Besser ist eine Rauschschaltung, die wie angegeben, eine Diode benutzt, deren Rauschen verstärkt und den AC-Anteil auf einen ADC gibt, was zu einem besseren Spektrum führt.

Um die statistische Verteilung dieser Zahlen weiter zu verbessern oder aus vielen "ein bisschen" zufälligen Bits wenige mit guter Qualität zu gewinnen, bieten sich Hash-Funktionen und die Kombination mit einem Pseudozufallszahlen-Generator an.

Hardwareprojekte:

Beiträge im Forum

Projekte, die einen Zufallsgenerator verwenden

Weblinks

Abgerufen von „https://www.mikrocontroller.net/index.php?title=Zufallszahlen&oldid=104674“