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.
Hmm, ne zufällig einsteigen kann ich nicht. Ich muss bei Position n starten. Möchte aber nicht 1..n berechnen müssen... (Mikrocontroller)
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ß):
1 | uint2 philox2x32(uint2 counter, unsigned int key) |
2 | {
|
3 | const unsigned int m = 0xD256D193; |
4 | unsigned int r = counter.x; |
5 | unsigned int l = counter.y; |
6 | for(int i = 0; i < 10; i++) |
7 | {
|
8 | unsigned int l_old = l; |
9 | l = r * m; |
10 | r = __umulhi(r, m) ^ key ^ l_old; |
11 | key += 0x9E3779B9; |
12 | }
|
13 | return make_uint2(r, l); |
14 | }
|
Das einzige Problem könnte __umulhi sein was es scheinbar auf dem ARM nicht als Instruction gibt, kann man aber nachbauen. Edit: OK, scheint es doch eine Instruction zu geben (http://infocenter.arm.com/help/topic/com.arm.doc.dui0553a/BABIJGJB.html)
:
Bearbeitet durch User
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.
Genau so soll es sein. So einen einfachen Hash-Algorithmus suche ich. Möglichst ressourcenschonend, es ist für einen ATTiny.
https://www.amazon.de/Kryptografie-Protokolle-Infrastrukturen-Klaus-Schmeh/dp/3898646025 Hier findest Du Antworten zu Deiner Frage, viele Algorithmen, aber auch Hinweise, wie Du diese sinnvoll nutzt, gerade eben auch zu Deinem Zweck.
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.
:
Bearbeitet durch User
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.
Was ist denn jetzt der Sinn dieses Zählers, oder warum meinst du diesen zu brauchen?
:
Bearbeitet durch User
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
1 | 0x00000000 = 0xB08F3363 |
2 | 0x00000001 = 0x35998608 |
3 | 0x00000002 = 0xF0AD5803 |
4 | 0x00000003 = 0x4DD48E59 |
5 | 0x00000004 = 0x0035DFD5 |
6 | 0x00000005 = 0xB3D8C784 |
7 | 0x00000006 = 0x8C1CCC20 |
8 | 0x00000007 = 0x1E0719B6 |
9 | 0x00000008 = 0x1CB4DC1F |
10 | 0x00000009 = 0x6945C52A |
Was spricht dagegen, die normale rand()-Geschichte aus der avr-libc zu nehmen?
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.
:
Bearbeitet durch User
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:
1 | /* POLY erzeugt GF(2^15) = GF(2)[x] */
|
2 | /* POLY = 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15 */
|
3 | #define POLY 0xe125
|
4 | #define DEGREE 15
|
5 | |
6 | /* ROOT ist ein zyklischer Erzeuger von GF(2^15)^* */
|
7 | /* ROOT = x^9 + x^13 */
|
8 | #define ROOT 0x2200
|
9 | |
10 | typedef unsigned short poly; |
11 | |
12 | static poly seed = ROOT; |
13 | |
14 | #define MASK(b) \
|
15 | (((poly) 1) << (b))
|
16 | |
17 | /**
|
18 | * Arithmetik in GF(2)[x] / p(x)*GF(2)[x]
|
19 | * Berechnet c = a*b mod p
|
20 | */
|
21 | poly pprod (poly a, poly b) |
22 | {
|
23 | const poly mask = MASK (DEGREE); |
24 | poly c = 0; |
25 | |
26 | do
|
27 | {
|
28 | // Ist Bit i in b gesetzt?
|
29 | if (b & 1) |
30 | c ^= a; // dann c = c + a * x^i |
31 | |
32 | a <<= 1; // a = a*x |
33 | if (a & mask) // a = a mod p |
34 | a ^= POLY; |
35 | |
36 | b >>= 1; |
37 | } while (b); |
38 | |
39 | return c; |
40 | }
|
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...
Es gibt keine "echten" Zufälle, wurde alles beim Urknall gestartet.
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.
Beitrag #4966689 wurde von einem Moderator gelöscht.
Beitrag #4966692 wurde vom Autor gelöscht.
Beitrag #4966707 wurde von einem Moderator gelöscht.
Beitrag #4966714 wurde vom Autor gelöscht.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.