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#Pseudozufallszahlengeneratorhttps://de.wikipedia.org/wiki/Linear_rückgekoppeltes_Schieberegister
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.
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)?
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
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
