Ich suche einen Algorithmus, um Zufallszahlen (32 Bit) zu erzeugen. Ich
kenne diese linearen Kongruenzgeneratoren mit XOR. Allerdings möchte ich
die Zufallszahlen nicht rekursiv erzeugen. Ich habe eine natürliche Zahl
n (32 Bit), die in jedem Schritt um 1 erhöht wird und auf Basis dieser
Zahl soll die Zufallszahl berechnet werden. Ich bin jetzt nicht sicher,
ob diese XOR-Methode trotzdem funktioniert, d.h. wie zufällig die Zahlen
dann sind...
Aber vielleicht hat ja jemand eine bessere Idee.
Bernd schrieb:> XOR-Methode
Das müsste auf ein rückgekoppeltes Schieberegister rauslaufen.
So weit bekannt, sind die Nachkommastellen von Pi zufällig. Wenn du die
berechnen kannst und an einer halbwegs zufälligen Stelle einsteigst,
hast du quasi perfekte Zufallszahlen.
Das was du möchtest sind wohl Counter Based Random Number Generators
(http://www.deshawresearch.com/resources_random123.html). Eigentlich
sind die für parallele Architekturen wie Grafikkarten gedacht aber
sollten auch auf Mikrocontrollern laufen. Ich hab die Philox Variante
selbst mal als CUDA Variante Implementiert (uint2 sind zwei unsigned
int, unsigned int ist 32 Bit groß):
Einen einfachen Hash-Algorithmus nehmen, n (+ optional Salt) hashen und
am Ende einfach die überflüssigen Bits verwerfen.
Arbeitet natürlich ohne Abhängigkeit vom vorherigen Zustand, d.h.
gleiche Eingabe ergibt gleiche Ausgabe.
Bernd schrieb:> Genau so soll es sein. So einen einfachen Hash-Algorithmus suche ich.> Möglichst ressourcenschonend, es ist für einen ATTiny.
Ohne die Anwendung (kryptographie o.ä.) zu kennen kann man da schlecht
Tipps geben.
Bernd schrieb:> es ist für einen ATTiny.
Das wird schwierig. Ich bin jetzt erstmal von ARM ausgegangen weil von
32 Bit die Rede war. Was ist denn überhaupt Ziel des Ganzen? Warum muss
das ganze von einem Zähler abhängen? Bei linearen Kongruenzgeneratoren
ist der Zustand des Zufallszahlengenerators üblicherweise auch nur ein
32 Bit Wert. Ob man nun diesen Wert oder den Zähler hat sollte doch egal
sein?
Edit: Der ATTiny hat übrigens auch keine Instruction für Multiplikation,
eine 32 Bit Multiplikation ist daher wohl alles andere als schnell.
Die XOR-Methode (rückgekoppeltes Schieberegister) braucht nur Shift und
eben XOR. Das klappt auch, aber ist eigentlich nicht dafür gedacht, mit
einem Zähler gefüttert zu werden. Ich will möglichst "guten" Zufall
(sofern das einen Sinn ergibt) bei möglichst wenig
Ressourcenverbrauch...
Vielleicht ist das auch schon das Optimum.
Bernd schrieb:> Die XOR-Methode (rückgekoppeltes Schieberegister) braucht nur Shift und> eben XOR. Das klappt auch, aber ist eigentlich nicht dafür gedacht, mit> einem Zähler gefüttert zu werden. Ich will möglichst "guten" Zufall> (sofern das einen Sinn ergibt) bei möglichst wenig> Ressourcenverbrauch...> Vielleicht ist das auch schon das Optimum.
Dann suchst du aber ein Optimum das andere nicht beurteilen können.
Was heißt denn möglichst wenig Resourcen? Es soll auf nen Attiny laufen,
ok?
Es soll möglichst "gut" sein. -> Wird schon um einiges schwieriger. Es
gibt nicht so viele Klassen von Zufallszahlen(Im Endeffekt 4: RNGS
(Nichtkryptographische und Kryptographische), Entropy harvester und
Quanten RNGS).
So wie du hier das alles beschreibst, suchst du etwas aus der ersten
Klasse, also Nichtkryptographische RNGs. Sowas nutzt man aber eigentlich
wirklich ernsthaft nur zum Testen, wenn man sowas wie Zufall will. Für
eine tatsächliche Anwendung ist das eher nicht zu empfehlen.
Aber das hängt jetzt wieder von deinem Einsatzzweck ab. Wenn du den
schilderst, könnte man dir evtl. auch weiterhelfen!
Letztendlich kann man erst einmal (fast) jeden kryptographischen
Algorithmus für dieses Unterfangen nehmen, da eine wichtige Eigenschaft
dieser Algorithmen ist, dass das berechnete Ergebnis zufällig
"aussieht". Das bedeutet im Umkehrschluss natürlich nicht, dass jeder
dieser Algorithmen auch einen kryptographisch sicheren
Zufallszahlengenerator darstellt.
Die Frage ist nun, was du genau haben willst. Soll jede Eingabe die
gleiche Zufallszahl zur Folge haben oder willst du, dass die gesamte
Sequenz deterministisch ist, aber die gleiche Eingabe nicht immer die
gleiche Zufallszahl liefert?
Generell könntest du dir mal XTEA anschauen, das ist eine sehr kompakte
Chiffre mit 64 Bit Blocklänge die ohne Division oder Multiplikation
auskommt. Allerdings muss die Verschlüsselung mehrere Zyklen
durchlaufen, damit die Ausgabe genügend zufällig aussieht. Der
empfohlene Wert (für Verschlüsselung) sind 32 Iterationen, das kann man
aber noch reduzieren wenn die Performance damit nicht ausreicht.
Ich habe mal eine Beispielimplementierung angehängt.
Ausgabe
Jörg W. schrieb:> Was spricht dagegen, die normale rand()-Geschichte aus der> avr-libc zu nehmen?
Die Anforderung, daß die einzelnen Glieder der Zufallsfolge direkt
berechenbar sein sollen und nicht aus dem Startwert Schritt für Schritt
iteriert. Wozu auch immer das gut sein soll, das verrät der OP ja nicht.
Nop schrieb:> Die Anforderung, daß die einzelnen Glieder der Zufallsfolge direkt> berechenbar sein sollen und nicht aus dem Startwert Schritt für Schritt> iteriert. Wozu auch immer das gut sein soll, das verrät der OP ja nicht.
Solche Funktionen sind interessant für Chiffrierverfahren, weil man
damit einen beliebig großen, nicht interessierenden Datenblock bei der
Entschlüsselung in konstanter Zeit überspringen kann. Dafür genügt es
nicht, die Zufallszahlen sequentiell zu erzeugen (wie etwa mit rand()),
sondern man muss für beliebiges n die n-te Zufallszahl der Sequenz
ermitteln können. Das geht bspw. mit dem von Daniel H. vorgeschlagenen
RNG des XTEA-Verfahrens.
Das scheint aber nicht der Beweggrund des TE zu sein, denn
Bernd schrieb:> Ich habe eine natürliche Zahl n (32 Bit), die in jedem Schritt um 1> erhöht wird und auf Basis dieser Zahl soll die Zufallszahl berechnet> werden.
Wenn n wirklich in jedem Schritt um 1 erhöht wird und keine Sprünge
macht, tut es eine sequentielle Zufallszahlengenerierung genauso gut.
Vielleicht geht es dem TE ja darum, die gleiche Zufallszahlensequenz ein
zweites Mal zu generieren. Dies ist auch mit den Funktionen aus der Libc
möglich, indem zu Beginn jeder Sequenz mit srand() jeweils der gleiche
Startwert gesetzt wird.
Pseudozufallsfolgen mit maximaler Laenge erzeugt man am Besten mit einem
rueckgekoppelten Schieberegister. Die Koeffizienten kann man in einer
Appnote von Xilink (ich glaub XAPP 110) abschauen. Der Vorteil von
solchen irreduziblen LFSR, linear feedback shift register, ist dass jede
Zahl, ausser Null in der Periode genau (!) einmal pro Periode vorkommt.
Dh man erhaelt genau 2^N -1 Zahlen.
Irreduzible bedeutet, es gibt kein kuerzeren Zyklen. Das kann passieren,
wenn man nicht die optimalen Koeffizienten verwendet.
Yalu X. schrieb:> Vielleicht geht es dem TE ja darum, die gleiche Zufallszahlensequenz ein> zweites Mal zu generieren.
Vielleicht moechte er auch fuer verschiedene Geraete ein
unterschiedliches Zufallsverhalten erzwingen. Bspw. Geraet Eins mit
Startwert 1, Geraet Zwei mit Startwert 1000. Bei nicht zaehlbasierten
Startwerten bestuende die Gefahr, dass das eine Geraet nach wenigen
Iterationen auf den Startwert des anderen Geraets faellt.
Also Bernd, was ist der Zweck des ganzen? Wenns nur drum geht beim
naechsten Start nicht die gleiche Reihe zu haben, kannst du ja den
letzten Zufallswert als neuen Startwert abspeichern.
Sapperlot W. schrieb:> Pseudozufallsfolgen mit maximaler Laenge erzeugt man am Besten mit einem> rueckgekoppelten Schieberegister. [...] Der Vorteil von solchen> irreduziblen LFSR, linear feedback shift register, ist dass jede> Zahl, ausser Null in der Periode genau (!) einmal pro Periode vorkommt.
Ob das (pseudo)zufällig ist, liegt im Auge des Betrachters: Wenn ich den
Wert 5 erhalte, weiß ich genau, dass die nächsten ca. 2^n Werte
garantiert keine 5 sind. Dito für jeden anderen Wert.
> Dh man erhaelt genau 2^N -1 Zahlen.
Falls das für den TO taugt, kann man auch folgendes machen:
Man betrachtet die multiplikative Gruppe F* des endlichen Körpers F mit
2^n Elementen, diese hat 2^n-1 Elemente (die 0 ist nicht dabei). F* ist
zyklisch, hat also einen Erzeuger A.
LFSR-ähnliche Pseudozufallszahlen kann man also folgendermaßen erhalten:
1) Wähle einen zyklischen Erzeuger A von F*.
2) Wähle irgend einen Wert W (SEED) aus F*
3) Berechne W = W * A
4) Gib W als Pseudozufallszahl aus
5) Goto 3)
Die m-te Zufallszahl berechnet sich also gemäß W(m) = W(0) * A^m wobei
W(0) = SEED. Der Vorteil ist nun, dass A^m einfach berechnet werden
kann, wie alle anderen Operationen in F auch.
Übrigens geht das nicht nur in Charakteristik 2 sondern für jeden
endlichen Körper, d.h. man kann auch 3^n, 5^n, 7^n ... verwenden. In
Charakteristik 2 sind die Berechnungen allerdings besonders einfach.
Addition ist zum Beispiel einfach nur ein XOR, Multiplikation mit X
(wenn man F als Polynomring in X auffasst) ein 1-Bit Shift nach links.
Udo schrieb:> Codebeispiel?
Wer interessiert sich schon für sowas Profanes? :o)
Beitrag "Miniprojekt: Lagerfeuer-LED (ATtiny25)"
In lagerfeuer.zip!parith-15.c ist GF(2^15) für einen ATtiny25
implementiert, allerings nur die Multiplikation. Also das, was zur
Berechnung der "nächsten" P-Zufallszahl gebraucht wird und Schritt 3)
von oben entspricht.
Zur Darstellung dient ein 16-Bit unsigned, und auch GF(2^16) geht mit
minimalen Anpassungen.
Die Multiplikation ist ungefähr so aufwändig wie 2 n-Bit Zahlen händisch
und mod 2^n zu multiplizieren, d.h. O(n²) wo O ein Landau-Symbol ist.
Exponentiation mit einer m-Bit Zahl hat also Komplexität O(m·n²), wobei
für ein Element g aus GF(2^n)* offenbar gilt g^m = g^(m mod (2^n - 1)).
Wenn es also notwendig sein sollte, mit großem m zu potenzieren (m
wesentlich größer als 2^n), dann kann man zunächst den Exponenten in den
Bereich [0 ... 2^n - 1) bringen.
Negative Exponenten werden relisiert qua g^m = (g^(-1))^(-m) d.h.
zunächst wird das (multiplikativ) Inverse von g berechnet, was wiederum
mit dem erweiterten Euklidischen Algorithmus bewerkstelligt werden kann.
Hier der wesentliche Teil:
Bernd schrieb:> Ich bin jetzt nicht sicher, ob diese XOR-Methode trotzdem funktioniert,> d.h. wie zufällig die Zahlen dann sind...> Aber vielleicht hat ja jemand eine bessere Idee.
Das kommt drauf an, was du mit "zufällig" meinst.
Die Folge, die aus einem Schieberegister mit rückgekoppelnden XORs
herauskommt, ist genau festgelegt. Mit dem Startwert legst du fest, wo
in der Folge deine Sequenz startet. Deshalb laufen die Dinger auch unter
PR(B)N Generatoren (Pseudo Random (Binary) Number Generator). Bei
richtiger Wahl der Rückkopplungseingänge werden alle 2^32 - 1 erlaubten
Zustände im Lauf von einem Zyklus genau einmal angenommen. Dein
Systemgedächnis von dem Prozess dahinter muss so kurz sein, dass es die
periodizität nicht merkt.
Wenn du den einen, verbotenen Zustand als Startwert lädst, läuft der
Generator nicht.
Bernd schrieb:> Die XOR-Methode (rückgekoppeltes Schieberegister) braucht nur Shift und> eben XOR. Das klappt auch, aber ist eigentlich nicht dafür gedacht, mit> einem Zähler gefüttert zu werden.
Wie ich oben bereits schrieb, kann man diese Operation als
Multiplikation in einem endlichen Körper auffassen. Das Problem ist
lediglich, dass wenn man es nicht mit "Bit", "Register", "Shift" und
"XOR" beschreibt, läuft alles schreiend weg :-/
Aber selbst in der zur Bitschubserei verballhornten Version haben immer
noch Termini wie "irreduzibel", "Polynom" und "Kongruenz" überlebt, was
noch ganz klar die algebraischen Wurzeln erkennen lässt.
> Ich will möglichst "guten" Zufall (sofern das einen Sinn ergibt) bei> möglichst wenig Ressourcenverbrauch...
Wenn es 32-Bit auf ATtiny sein soll, könntest du 64-Bit Arithmetik
verwenden um eine gute[tm] Zufälligkeit zu erreichen. Eine
Multiplikation in GF(2^64) ist grob geschätzt genauso teuer wie zwei
uint64_t ohne MUL zu multiplizieren.
Um die Sequenz ab Position P loslaufen zu lassen, braucht es O(log(P))
solcher Multiplikationen; ist also ein recht zeitaufwändiges Unterfangen
auf einem ATtiny.
Eine n-Bit Multiplikation brauch 2n Shifts und n XORs, dazu geschätzt
rund 10-20 Instruktionen Geraffel, und das alles n mal. Für eine 64-Bit
Mul bist du also bei mindestens 3·64²/8 ~ 1600 Ticks. Wenn dir 32-Bit
Arithmetik reicht, sind es immerhin noch 400 Ticks.
Natürlich kannst du auch ein LFSR direkt verwenden und P mal
multiplizieren, was dann Zeit O(P) kostet anstatt O(log(P)). Vorteil
ist dann, dass ein Faktor bekannt ist und die Mul-Schleife effektiv
entrollt werden kann. Dazu wird der Faktor (zyklischer Erzeuger) so
"gewählt", dass er nur wenige Bits hat, was die Anzahl der XORs
erduziert. Und ein Teil der Shifts fällt ebenfalls weg. Ist also
durchaus zu überlegen, hängt natürlich auch mir der Größe von P ab ob
sich das rechnet.
Ich kann dir erklären was du machen musst, aber implementieren tu ich es
nicht — und dass reine Implementation nicht unbedingt weiterhilft, zeigt
ja bereits, dass LFSR-Code schon überall[tm] verfügbar ist...
Kommt ja auch darauf an wie oft und wie schnell er die Zufallszahlen
braucht. Einen rauschenden ADC Pin als Offset hat mir immer schon gute
und in nicht reproduzierbares Muster gebracht ;-) In Verbindung mit CBRN
dennoch reproduzierbar - aber halt der Counter ist Random und folgt
keinerlei Muster. Denn bei einem fortlaufenden 32Bit ergibt sich alle
4.294.967.295 Schritte das selbe Muster - ich weiß - ist ne lange Zeit -
aber es ergibt sich.
DraconiX schrieb:> Einen rauschenden ADC Pin
Du musst dann aber auch sicherstellen, dass er wirklich rauscht.
Wenn dir in einer sicherheitsrelevanten Anwendung ein Intruder das
Rauschen dadurch wegbügeln kann, dass er ein starkes externes
elektrisches Feld einwirken lässt und daher deine „Zufallszahl“
vorhersagbar wird, hast du nichts gewonnen.
