Hallo,
welchen sind hat das Zusammenschalten mehrerer Linear Feed Back Shift
Register. Ich habe hier ein Blockschaltbild vor mir wo drei LFSRs mit
unterschiedlichen Polynomen parallel betrieben werden. Aus jedem werden
willkürlich zwei Ausgangsbits genommen und zu einem 6 bit Ausgangswort
zusammengefügt. Hat das einen besonderen Sinn. Erhöht sich somit die
maximale Zykluslänge ? Leider lässt der Author (Semesterarbeit) den Sinn
und Zweck dieses Vorgehens völlig unbeleuchtet.
Gruss, Matze
Hallo,
man nimmt in der Regel nur ein Bit eines LFSR um damit
Pseudo-Zufallszahlen zu erzeugen, denn andernfalls wird - zusätzlich zu
der eigentlichen Periodenlänge des LFSR - ein periodisches Signal
kleinerer Länge generiert.
Bin selbst kein Experte auf dem Gebiet, habe aber vor kurzem einen
einfachen Rauschgenerator benötigt, mir hat die englische Wikipedia
weitergeholfen:
http://en.wikipedia.org/wiki/LFSR -> Xilinx-Link
Vielleicht hatte der Schreiber der Semesterarbeit nur einen sehr kleinen
CPLD und wollte Logik sparen, aber besser dürften 6 parallele LFSR sein.
Bei allen kann das gleiche Polynom verwendet werden, allerdings mit
unterschiedlichen preload-Werten.
Falls Rauschen als Störquelle erzeugt wird, lohnt es sich ein Histogramm
für die Verteilung und eine FFT (keine unerwünschten Perioden)
aufzustellen.
> Hat das einen besonderen Sinn.
Ich tippe auf Hokus-Pokus ;-)
Mit einem z.B. 16 Bit breiten LFSR kann ich maximal 65535 verschiedene
Zufallszahlen erzeugen. Ich kann mir keine Konstellation vorstellen, in
der die Aufteilung der Zahlen auf z.B. 2x8 Bit eine bessere
Zufallsreihenfolge bringen könnte. 16 Bit bleiben 16 Bit.
> wo drei LFSRs mit unterschiedlichen Polynomen parallel betrieben werden.> Aus jedem werden willkürlich zwei Ausgangsbits genommen und zu> einem 6 bit Ausgangswort zusammengefügt.
Wenn also jedes der drei LFSR 16 Bit breit wäre, würde ich von einem 48
Bit LFSR, aus dem willkürlich 6 Bit herausgeschnitten werden, gleich
gute Ergebnisse erwarten.
Ich frage mal nach, auch wenn es ein altes Thema ist:
Lothar M. schrieb:> Wenn also jedes der drei LFSR 16 Bit breit wäre, würde ich von einem 48> Bit LFSR, aus dem willkürlich 6 Bit herausgeschnitten werden, gleich> gute Ergebnisse erwarten.
Hätte das 48er LFSR nicht ein bessere Güte die mit der 2er-Potenz geht?
Das müsste doch gleich erheblich besser sein, um mehrere Bits zu
gewinnen.
Wäre die Frage, wie man sie gewinnen könnte.
Dann versuche ich mich mal an einer plausiblen Erklärung.
Solche Konstrukte findet man oft in der Kryptographie,
https://de.wikipedia.org/wiki/Stromverschl%C3%BCsselung
um eine ausreichend hohe Periodenlänge zu erzielen.
Das geht mit einem einzelnen, sehr langen LFSR nicht so gut, weil es
"gute" und "schlechte" Polynome (Rückführungskombinationen) gibt, die zu
ermitteln, einen beträchtlichen Aufwand macht. Also nutzt man lieber
mehrere, kürzere LFSR, mir erwiesen gutem Polynom.
ok, das ist nachvollziehbar. Habe ich auch schon mitbekommen, dass sie
verschiedene Autoren schwer tun, für ihre Polynome statistisch bewiesene
Angaben zur Qualität zu machen.
Für mich wäre es entscheidend, dass ich mehrere Bits erhalte, die
unabhängi von einander sind und deren Zusammenführung nicht die Qualität
des Rauschens reduziert.
Es geht dabei vermutlich um kryptografische Sicherheit. Ein LFSR ist
deterministisch. Kennt man das Polynom und den momentanen Zustand, kann
man alle Folgezustände berechnen. Kombiniert man hingegen Teilergebnisse
aus mehreren verschiedenen LFSR, dann geht das nicht mehr so einfach,
weil man aus dem Gesamtergebnis nicht mehr auf den aktuellen Zustand
jedes der LFSR zurückrechnen kann, jedenfalls nicht mit nur einem
Sample. Ein Angreifer braucht dann schon genaue Kenntnis der
Architektur, um den Folgezsutand zu berechnen.
Besser wäre es, einen richtig guten PRNG zu verwenden (z.B. einen
Mersenne-Twister) und eine sichere Hashfunktion nachzuschalten. Aber der
Hardwareaufwand dafür ist natürlich massiv größer.
Vancouver schrieb:> Besser wäre es, einen richtig guten PRNG zu verwenden (z.B. einen> Mersenne-Twister)
Ja, wobei ein solcher Twister geht im FPGA erstaunlich einfach - mit
entsprechenden Frequenzen - (BTDT). Weitere "Rüttel-und
Schüttelmethoden" wären Marsaglia etc.
Man muss sich aber immer fragen, wie sicher die Methode jeweils ist,
wenn jemand aus der Entwicklertruppe ausscheidet oder ein Angreifer
sonst wie dazu kommt, zu wissen, wie ein Algo funktioniert. Es ist im
Sinne der Sicherheit daher oft zweckmäßiger eine einfache Codierung mit
Verfahren zu wählen, die man dem Prinzip nach erraten kann, die aber von
einem oder mehreren Schlüsseln abhängig sind, die man regelmäßig
wechselt. Damit sind Klassifizierungen und das Einrichten von
Sicherheitshierarchien sehr einfach möglich.
Es ist nur eben etwas mehr Rundherumaufwand nötig wie das geschützte
Übertragen von Schlüsseln, deren Änderungen und deren Löschungen.
Eine andere Frage ist, wie man ein Signal so aufbereitet, dass es sicher
decodiert werden kann, als Rauschen aber im normalen Datenstrom gar
nicht auftaucht, also gar nicht bekannt ist, dass ein System etwas von
sich gibt.
Auch da gibt es Methoden mit / ohne LSFR.
Markus W. schrieb:> Für mich wäre es entscheidend, dass ich mehrere Bits erhalte
Das Einfachste sind wohl mehrere unabhängige Generatoren, jedenfalls im
FPGA. Das ist zumindest die kleinste Lösung. Da ein einzelner Generator
ein (fast) gleichverteiltes Spektrum (weißes Rauschen) erzeugt, sind die
Ergebnisse auch "weiss", wenn die Generatoren wirklich unabhängig sind.
Das sind sie allerdings nicht perfekt, wenn derselbe FPGA Takt verwendet
wird. Auch nicht, wenn man ihnen einen Teiltakt verpasst.
Kommt eben darauf an, welche Qualität man möchte. Ich habe das damals
einfach so gemacht, dass ich das Rauschen, das entstand, gemessen habe
und einen Korrektur-EQ drübergestülpt habe.
