Mein Programm (avr-gcc) soll eine Sequenz pseudozufälliger Werte vorwärts und rückwärts generieren/durchlaufen. Dazu zwei Fragen: 1. Lässt sich ein LFSR umkehren (ich vermute: ja)? 2. Gibt es bei PRNG (z.B. LFSR) eine Funktion, um den Zufallswert einer bestimmten Iteration direkt zu erhalten? Dagegen spricht https://de.wikipedia.org/wiki/Pseudozufall > Generell definiert man in der Berechenbarkeitstheorie als pseudozufällig, was durch effiziente Algorithmen nicht vorhergesagt werden kann. Pseudozufälligkeit ist aber immer noch berechenbar (man kann sie effizient erzeugen), nur nicht vorhersagbar. Aber evtl. trifft das ja nicht auf LFSR zu. Bei bekannter Anzahl von Werten könnte man alternativ ja den Zustand vorbereiten und dann als seed für den umgekehrten Algorithmus nutzen, richtig? Weitere Wikipedia-Artikel: https://de.wikipedia.org/wiki/Zufallszahlengenerator#Pseudozufallszahlengenerator https://de.wikipedia.org/wiki/Linear_rückgekoppeltes_Schieberegister
Dazu erzeugt man sich z.B. 1000 Zufallszahlen in einem Array. Diese kann man beliebig durchlaufen.
Danke, aber du hast damit leider keine meiner Fragen beantwortet :-(
Interessante Fragen, die Antworten kenne ich leider nicht. Aber ich kann noch zwei weitere Fragen stellen: - Wie kriege ich aus einer Pseudozufallszahlenfolge das generierende Polynom raus, also das LFSR? - Wie kriege ich für ein LFSR raus, ob es eine 'maximum length sequence' erzeugt. So viele interessante Themen, so wenig Zeit. Cheers Detlef
Adam schrieb: > 1. Lässt sich ein LFSR umkehren (ich vermute: ja)? Nein. > 2. Gibt es bei PRNG (z.B. LFSR) eine Funktion, um den Zufallswert einer > bestimmten Iteration direkt zu erhalten? Nein. Aber man kann natürlich eine Funktion bauen, die einen Parameter bekommt (0 ... 65535 oder so), und ihn mit einem Startwert (z.B. diesmal 5623) verrechnet, so daß die Ergebniszahlen wild hin und her springen. Jedesmal, wenn man einen anderen Parameter verwendet, kommt eine andere Zahl raus, aber jedesmal, wenn man denselben Parameter reinsteckt, kommt, beim gleichen Startwert, dieselbe Zahl raus. Eine einfache vorgefertigte Funktion dafür wäre MD5 (berechnet gleich einen Haufen Ergebniswerte auf ein Mal). Man muss etwas auspassen, wenn man den Zahlenbereich einschränken will, daß die Ergebnisse gleichverteilt bleiben. Die Sache mit dem Startwert ist ja auch per PRNG bekannt. ein Programm läuft mit gl4ichen Startwert immerg leich ab (deterministisch) und man braucht andere Startwerte für andere Zufallsfolgen.
Detlef _. schrieb: > - Wie kriege ich aus einer Pseudozufallszahlenfolge das generierende > Polynom raus, also das LFSR? https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm Umkehrung evtl. doch für Fibonacci LFSR ? https://crypto.stackexchange.com/questions/29066/reverse-output-of-general-fibonacci-lfsr
Michael B. schrieb: > man kann natürlich eine Funktion bauen Gute Idee. Evtl. reicht schon eine LFSR-Funktion mit dem Index der Sequenz als "seed" (keine Ahnung, wie es dann mit der Gleichverteilung aussieht, aber ist für meinen Zweck nicht kritisch)?
Adam schrieb: > Detlef _. schrieb: >> - Wie kriege ich aus einer Pseudozufallszahlenfolge das generierende >> Polynom raus, also das LFSR? > > https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm > > Dann ist die Antwort auf Deine erste Frage doch klar: Du steckst die umgekehrte Folge in den Berlekamp/Massey Algorithmus und bekommst das Polynom. math rulez! Cheers Detlef
Kleiner Test:
1 | #!python3
|
2 | #coding=utf-8
|
3 | |
4 | def xorshift(seed=None): |
5 | if seed is not None: |
6 | xorshift.bits = seed |
7 | xorshift.bits ^= xorshift.bits << 13 |
8 | xorshift.bits ^= xorshift.bits >> 17 |
9 | xorshift.bits ^= xorshift.bits << 5 |
10 | return xorshift.bits & 0xFF |
11 | |
12 | xorshift.bits = 1; # "static" function attribute |
13 | |
14 | output = "{:2}\t{:3}" |
15 | |
16 | print("forward") |
17 | for i in range(0, 32, 1): |
18 | print( output.format(i, xorshift(i)) ) |
19 | |
20 | print() |
21 | print("backward") |
22 | for i in range(31, -1, -1): |
23 | print( output.format(i, xorshift(i)) ) |
Detlef _. schrieb: > Du steckst die > umgekehrte Folge in den Berlekamp/Massey Algorithmus und bekommst das > Polynom. Stimmt, auch 'ne Idee. Bin leider nicht im Thema drin, daher werde ich es zunächst mit einer "Würfelfunktion" mit Parameter versuchen (siehe letzter Post).
Detlef _. schrieb: > Interessante Fragen, die Antworten kenne ich leider nicht. > > Aber ich kann noch zwei weitere Fragen stellen: > > - Wie kriege ich aus einer Pseudozufallszahlenfolge das generierende > Polynom raus, also das LFSR? > > - Wie kriege ich für ein LFSR raus, ob es eine 'maximum length sequence' > erzeugt. > > So viele interessante Themen, so wenig Zeit. > > Cheers > Detlef Ob es eine Maximum Length Sequence ist, kann man anhand des Polynoms sagen. Die Polynome, die eine MLS erzeugen, haben bestimmte spezielle Eigenschaften, und man kann dann beweisen, dass man damit eine MLS erhält. Ich hatte da mal eine Vorlesung drüber, bei Interesse kann ich die Unterlagen hervorkramen.
Tobias P. schrieb: > Ob es eine Maximum Length Sequence ist, kann man anhand des Polynoms > sagen. Die Polynome, die eine MLS erzeugen, haben bestimmte spezielle > Eigenschaften, und man kann dann beweisen, dass man damit eine MLS > erhält. Ich hatte da mal eine Vorlesung drüber, bei Interesse kann ich > die Unterlagen hervorkramen. Hallo Tobias, schön von Dir zu hören, wir hatten das Thema mal früher diskutiert: Beitrag "Hadamard Transformation" Ja, ich weiß, dass man anhand des Polynoms entscheiden kann, ob das eine MLS gibt oder, ich kann das leider aber immer noch nicht ;/ Ich hatte damals verschiedene 2^17-1 lange Folgen gesucht und auch alle 7170 oder so erzeugenden Polynome durch ne Woche Rechner laufenlassen gefunden. Auch die Rückrechnung des Polynoms aus der Folge (Berlekamp/Massey Algorithmus) habe ich noch nicht so verstanden, dass ich ihn implementieren könnte. Es gibt imer was zu tun. math rulez! Cheers Detlef
Detlef _. schrieb: > schön von Dir zu hören, wir hatten das Thema mal früher diskutiert: > > Beitrag "Hadamard Transformation" > > Ja, ich weiß, dass man anhand des Polynoms entscheiden kann, ob das eine > MLS gibt oder, ich kann das leider aber immer noch nicht ;/ Stimmt, an diese Diskussion habe ich gar nicht mehr gedacht :-) damals konnte ich das auch nicht (entscheiden, ob ein Polynom eine MLS ergibt). Habe aber mittlerweile durch den Dienst am Vaterland einiges über Kryptographie gelernt und hatte dort ein paar Vorlesungen zu dem Thema, auch MLS und diese Polynome wurden behandelt. Im Moment kann ich es auch grade nicht mehr sagen, was genau die Eigenschaft war, aber in den Vorlesungsunterlagen ist es definitiv beschrieben. Ich schaue übers Wochenende mal, das Zeug müsste irgendwo noch rum liegen. > Es gibt imer was zu tun. > math rulez! *dito!*
Adam schrieb: > 1. Lässt sich ein LFSR umkehren (ich vermute: ja)? was meinst du mit umkehren? Etwa op man das rückkoppelte Schieberegister auch in die entgegngesetzte Richtung schieben lassen kann? Denk mal nach! Kann man sagen wenn ein XOR bspw eine 1 ausgibt rückschliessen an welchen Eingang welcher Wert anliegt? Kann man das bei einer '0' am Ausgang? Oder stellst Du die Frage ob man zwei LFSR konstruieren kann die die gleiche Sequenz nur in entgegengesetzter Reihenfolge ausgeben? > 2. Gibt es bei PRNG (z.B. LFSR) eine Funktion, um den Zufallswert einer > bestimmten Iteration direkt zu erhalten? Was meinst du mit direkt? Meinst du eher "schneller" als durch Durchlaufen lassen der Iterationen? So ein LSFR lässt sich leicht in einem FPGA nachbilden, der dann mit 300 MegaIterationen pro sekunde läuft. also ein 32bit LSFR in 13 Sekunden wegnudelt.
Ich denke, die Intention des TO ist, die ausdrückliche Iteration des LSFR einzusparen indem er direkt aus einem alten Wert rechnet. BBS ist so ein Algorithmus, der das kann.
1.) zu jedem nicht reduzierbaren Polynom eines LFSRs exitiert ein inverses Polynom mit gleichen Eigenschaften wie das nicht inverse Polynom 2.) kennt man das LFSR Polynom und dessen Seed so kann man auf einfache Art und Weise das inverse Polynom und dessen Seed berechnen 3.) die Sequenz der erzeugten Bits beider LFSR ist dann zueinander gespiegelt, ebenso der Inhalt der LFSR Register 4.) LFSR mit maximaler Länge benutzen immer nicht reduzierbare Polynome (das ist wie eine Primzahl in N aber eben bei LFSRs stattdessen in GF(2^x)) 5.) nicht reduzierbare Polynome kann man direkt berechnen, man muß sie also nicht per Brute Force erzeugen. Dazu muß man in GF(2^x) ein gegebenes Polynom faktorisieren und die sich daraus ergebenden Teilpolynome überprüfen. Wie bei natürlichen Zahlen faktorisiert man diese in Primzahlen und kann so die Eigenschaften der zusammengesetzten Zahlen ermitteln. So geht dies auch mit Zahlen in Galois Feldern. 6.) bei bekanntem Polynom eines LFSRs und einer unvollständigen Folge an Ausgabebits kann man die nächsten Bits berechnen. Das, und der Fakt das LFSR meistens sehr kleine Polynome verwenden, ist der Grund warum LFSRs in der Kryptographie als unsicher einzustufen sind. Man kann sie also knacken und das benutzte Polynom aus eine gegebenen Folge von Ausgabebits berechnen. 7.) im FHT Thread findest du meinen Source in dem du auch die par Zeilen Source finden kannst die aus einem Polynom+Seed das passende inverse Polynom+Seed direkt berechnet. Essentiell: Bitreichenfolge des Polynoms invertieren und dabei gleich den Seed für das inverse Polynom berechnen, ist nur eine kleine Schleife im Source. Gruß Hagen PS: weil oben der BBS=Blum Blum Shub RNG angesprochen wurde. Dieser ist der einzige als mathematisch sicher beweisbare PRNG. Kennt man dessen Parameter, also auch die im allgemeinen geheimen Parameter, kann man mathematisch auf direktem Wege: 1.) das Bit mit Index X berechnen 2.) den internen Status des BBS vor- und zurück"spulen", also den Ausgabestrom der PRNG Bits überpringen um +- X Datenbits. 3.) demzufolge den Ausgabestrom auch rückwärts ablaufen lassen
Georg B. schrieb: > Ich denke, die Intention des TO ist, die ausdrückliche Iteration des > LSFR einzusparen indem er direkt aus einem alten Wert rechnet. BBS ist > so ein Algorithmus, der das kann. Natürlich geht auch dies: man benötigt nur das benutzte LFSR Polynom und den aktuellen Seed und schwups berechnet man das nächste Datenbit. Also exakt das was man sowieso macht wenn man mit einem LFSR die Zufallsbits erzeugen würde. Da man aus einem gegebenen Polynom+Seed das inverse Polynom+Seed berechnen kann, kann man also auch ab dieser Bitposition in die Gegenrichtung die vorherigen Datenbits berechnen. Gruß Hagen
Danken kann ich auch, verstehen bislang nur ein Bruchteil :-)
Beitrag #5020826 wurde vom Autor gelöscht.
Hallo,
bist Du's, Hagen RE ? Bei dem alten thread warst Du auch beteiligt,
schon damals war ich leider nicht in der Lage gewesen Dir zu folgen :/ .
Habe mich mal bisschen gebildet und C-Routinen gebastelt, die mit
Galoisfeldern rechnen, siehe file. Ich kann in Galoisfeldern jetzt
addieren, multiplizieren und dividieren. Inverse Polynome über modulo
Polynomen kann ich auch berechnen, alles schick.
Jetzt war Deine Aussage:
>>>>>>
1.) zu jedem nicht reduzierbaren Polynom eines LFSRs exitiert ein
inverses Polynom mit gleichen Eigenschaften wie das nicht inverse
Polynom
<<<<<<<
Ein inverses Polynom p^-1 zum Polynom p hat die Eigenschaft
(p^-1 * p) modulo m = 1 , mit einem Modulopolynom m. Wenn p das LFSR
Polynom ist, was ist den dann m? Das irreduzible Polynom x^2+x liefert
für 3Bit eine MLS der Länge 7, dito das Polynom x^2+1. Die beiden Folgen
sind 'rückwärts', das was der TO will, also nehme ich an dass die
Polynome invers zueinander sind, aber mit welchem Modulopolynom, man
will ja in GF(2^3) bleiben?
Fragen über Fragen.
Als nächstes plane ich Berlekamp/Massey und Test, ob ein Polynom
irreduzibel ist, so Zeit vorhanden.
Cheers
Detlef
PS: Die C source dient zur Ansicht und meiner Bildung, die ist weder
fehlersicher noch richtig noch schön noch effizient.
Ähm, vielleicht liegts an meiner verfälschenden Wortwahl: ich meinte nicht inverses Polynom sondern invertiertes Polynom. Du verstehst wahrscheinlich unter "invers" das Modulare Inverse zum Polynom, das meinte ich natürlich nicht. Wenn ich am WE wieder zu Hause bin schaue ich mal nach meinen alten GF() Sourcen um nicht reduzierbare Polynome zu berechnen, bin allerdings im Umzugsstreß :( Gruß hagen
Liebe Freunde der linearen Algebra (es sind wenige, wie die mageren Downloadzahlen zeigen), anbei der Berlekamp-Massey Algorithmus für Bitfelder. Damit ist Frage 1 des lange verschollenen TO beantwortet. Wenn man bei einem 4-er 'Linear feedback shift Register' den letzten und den vorletzten anzapft kommt eine 'Maximum length sequence' raus. Wenn man die 'umdreht' und in den Berlekamp-Massey schickt sagt der, dass man den letzten und den ersten anzapfen soll um diese Folge zu erhalten. Wieso das das 'inverse Polynom' ist enzieht sich meiner schwachen Kenntnis. Als nächstes werde ich ich rausfinden, wie man prüft ob ein Polynom 'irreducible' ist, also eine MLS liefert. Großer Spaß. math rulez ! stay tuned ! Cheers Detlef
Hallo, anbei ein Programm, das für ein linear feedback shift register der maximalen TAP Anzahl 64 alle primitiven Polynome berechnet, die eine maximum length sequence liefern. War nen schwieriger hack, Geschichte dazu siehe hier: www.matheplanet.de/matheplanet/nuke/html/viewtopic.php?topic=230404&post _id=1677816 Jetzt rechne ich allerdings für 17 taps alle 7710 Polynome in 13sec, hatte ich schon mal 3 Wochen Rechenzeit für benötigt. War ein grosser Spaß, ich poste das in der Hoffnung, dass das irgendjemenden interessieren könnte. Rückfragen willkommen. math rulez! Cheers Detlef
Ach so, die Ursprungsfrage lautete ja, wie man die MLS umdreht. Die Antwort kenne ich jetzt als Beifang: Für ein z.B. 4-Tap LFSR lautet das Polynom p^4+b3*p^3+b2*p^2+b1*p^1+1 Das Polynom ist also normiert und der Koeffizient von p^0 ist immer 1 (ansonsten wäre das Polynom durch p teilbar). Die umgedrehte MLS kriegt man mit dem Polynom p^(4-4)+b3*p^(4-3)+b2*p^(4-2)+b1*p^(4-1)+1*p^(4-0), also die Koeffizienten quasi spiegeln. Anbei ein richtigeres Programm. Cheers Detlef
Die zweite Frage des TO lautete >>>>>>> 2. Gibt es bei PRNG (z.B. LFSR) eine Funktion, um den Zufallswert einer bestimmten Iteration direkt zu erhalten? <<<<<<< Ja, die gibt es. Beispiel seien 5 taps, primitives Polynom ist p(x)=x^5+x^2+1, ein Galois LFSR, dh. das höchste Bit wird unten wieder reingeschoben und xored in die zweitunterste Stufe, siehe https://de.wikipedia.org/wiki/Linear_r%C3%BCckgekoppeltes_Schieberegister Dann lautet die Folge beginnend bei #1=00010: #2=00100, #3=01000, #4=10000, #5=00101, #6=01010 #23 lautet 01111, es kommt also aus dem LFSR eine 0 nach der 23. Iteration raus. Das entspricht dem Ausdruch x^23 mod p(x). x^23 ist mit 'square and multiply' schnell zu berechnen, siehe gal_exp in der source: x^23 =(((x^2)^2*x)^2*x)^2*x https://de.wikipedia.org/wiki/Bin%C3%A4re_Exponentiation. So kriegt man mit O(log n) mit n als Bitlänge des Schieberegisters eine beliebige Iteration 'direkt' (mit O(log n) Laufzeit) raus, das geht schnell. Cheers Detlef
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.