Linear feedback shift register?

Da war ich auf der Suche für einen LFSR-Implementierung in Python, ich stolperte über dieses Thema. Ich fand jedoch, dass die folgende war ein wenig genauer nach meinen Bedürfnissen:

def lfsr(seed, mask):
    result = seed
    nbits = mask.bit_length()-1
    while True:
        result = (result << 1)
        xor = result >> nbits
        if xor != 0:
            result ^= mask

        yield xor, result

Den oben LFSR-generator ist, basierend auf GF(2^k) Modul Infinitesimalrechnung (GF = Galois-Feld). Dass gerade ein Algebra-Kurs, ich werde das erklären der mathematischen Weg.

Let ' s start, indem, zum Beispiel, GF(2⁴), das entspricht {a₄x⁴ + a₃x³ + a₂x² + a₁x¹ + a₀x⁰ | a₀, a₁, ..., a₄ ∈ Z₂} (um zu klären, Z_n = {0,1,...,n-1} und damit Z₂ = {0,1}, d.h. ein bit). Dies bedeutet, dass diese ist die Menge aller Polynome des vierten Grades, mit allen Faktoren, die entweder vorhanden ist oder nicht, aber da Sie keine vielfachen dieser Faktoren (z.B. es gibt keine 2x^k). x³, x⁴ + x³, 1 und x⁴ + x³ + x² + x + 1 sind Beispiele für Mitglieder dieser Gruppe.

Nehmen wir diesen Satz modulo einem Polynom vierten Grades (D. H., P(x) ∈ GF(2⁴)), z.B. P(x) = x⁴+x¹+x⁰. Diese modulo-operation auf einer Gruppe wird auch als bezeichnet GF(2⁴) /P(x). Für Ihre Referenz, P(x) beschreibt die 'taps' innerhalb der LFSR.

Wir auch ein willkürliches Polynom von Grad 3 oder niedriger (so dass es nicht betroffen ist, indem Sie unsere E-Modul, sonst könnten wir genauso gut führen Sie die modulo-operation direkt auf ihm), z.B. A₀(x) = x⁰. Jetzt alle nachfolgenden Ein_i(x) wird durch Multiplikation mit x: A_i(x) = A_i-1(x) * x mod P(x).

Da wir in einem begrenzten Feld, die modulus-operation kann eine Wirkung haben, aber nur, wenn die resultierende A_i(x) hat mindestens einen Faktor x⁴ (unsere höchste Faktor in P(x)). Beachten Sie, dass, da wir mit zahlen in Z₂, die Durchführung der modulo-operation selbst ist nichts anderes als das bestimmen, ob jedes a_i wird eine 0 oder 1 durch addition der beiden Werte von P(x) und A_i(x) zusammen (also, 0+0=0, 0+1=1, 1+1=0, oder "xoring" diese zwei).

Jedes Polynom kann geschrieben werden als ein Satz von bits, zum Beispiel x⁴+x¹+x⁰ ~ 10011. Die A₀(x) kann angesehen werden als die Samen. Das 'mal x' operation gesehen werden kann, als eine Verschiebung nach Links-Betrieb. Die modulus-operation kann als eine bit-Maskierung Betrieb, mit der Maske als unser P(x).

Den Algorithmus oben dargestellt erzeugt deshalb (ein unendlicher Strom von) gültige vier-bit-LFSR Muster. Zum Beispiel für unsere definiert Ein₀(x) (x⁰) und P(x) (x⁴+x¹+x⁰), können wir definieren die folgende erste Ergebnisse gezeitigt, die in GF(2⁴) (beachten Sie, dass Ein₀ ist nicht nachgegeben, bis am Ende der ersten Runde-Mathematiker in der Regel beginnt mit der Zählung bei "1'):

 i   Ai(x)                   'x⁴'  bit pattern
 0   0x³ + 0x² + 0x¹ + 1x⁰   0     0001        (not yielded)
 1   0x³ + 0x² + 1x¹ + 0x⁰   0     0010
 2   0x³ + 1x² + 0x¹ + 0x⁰   0     0100
 3   1x³ + 0x² + 0x¹ + 0x⁰   0     1000
 4   0x³ + 0x² + 1x¹ + 1x⁰   1     0011        (first time we 'overflow')
 5   0x³ + 1x² + 1x¹ + 0x⁰   0     0110
 6   1x³ + 1x² + 0x¹ + 0x⁰   0     1100
 7   1x³ + 0x² + 1x¹ + 1x⁰   1     1011
 8   0x³ + 1x² + 0x¹ + 1x⁰   1     0101
 9   1x³ + 0x² + 1x¹ + 0x⁰   0     1010
10   0x³ + 1x² + 1x¹ + 1x⁰   1     0111
11   1x³ + 1x² + 1x¹ + 0x⁰   0     1110
12   1x³ + 1x² + 1x¹ + 1x⁰   1     1111
13   1x³ + 1x² + 0x¹ + 1x⁰   1     1101
14   1x³ + 0x² + 0x¹ + 1x⁰   1     1001
15   0x³ + 0x² + 0x¹ + 1x⁰   1     0001        (same as i=0)

Beachten Sie, dass Sie Ihre Maske muss eine '1' an der vierten position, um sicherzustellen, dass Ihre LFSR erzeugt vier-bit-Ergebnisse. Beachten Sie auch, dass eine " 1 " vorhanden sein muss, an der nullten position, um sicherzustellen, dass Ihre bitstream-würde nicht am Ende mit einem 0000 bit-Muster, oder, dass das Letzte bisschen würde unbenutzt (wenn alle bits werden nach Links verschoben ist, würden Sie auch am Ende mit einer null an der position 0. nach einer Schicht).

Nicht alle P(x)'s unbedingt werden Generatoren für GF(2^k) (d.h., nicht alle Masken von k bits generieren, die 2^k-1-1 zahlen). Zum Beispiel x⁴ + x³ + x² + x¹ + x⁰ erzeugt 3 Gruppen von 5 verschiedenen polynomals jeder, oder "3 Zyklen der Periode 5": 0001,0010,0100,1000,1111; 0011,0110,1100,0111,1110; und 0101,1010,1011,1001,1101. Beachten Sie, dass 0000 kann nie generiert werden, und kann Sie nicht erzeugen jede andere Zahl.

In der Regel die Ausgabe eines LFSR ist das bit, das ist 'verschoben', die eine '1' wenn modulus-operation durchgeführt wird, und eine '0' wenn er es nicht ist. LFSR ist mit einer Frist von 2^k-1-1, die auch als pseudo-noise PN oder-LFSR ist, befolgen Sie die Golomb-die Zufälligkeit postuliert, die sagt so viel wie, dass das Ausgabe-bit ist zufällig 'genug'.

Sequenzen von diesen bits haben daher Ihre Nutzung in der Kryptographie, zum Beispiel in der A5/1 und A5/2 mobile encryption standards oder E0 Bluetooth-standard. Sie sind jedoch nicht so sicher, wie man möchte: die Berlekamp-Massey-Algorithmus kann verwendet werden, um reverse-Engineering die charakteristische polynomal (P(x)) des LFSR. Starke Verschlüsselung-standards verwenden daher Nicht-lineare FSR's oder ähnlichen, nicht-lineare Funktionen. Ein Verwandtes Thema sind die S-Boxen bei AES.

Hinweis, dass ich die int.bit_length() operation. Dies wurde nicht umgesetzt, bis Python 2.7.

Wenn Sie würde nur wie eine endliche bit-Muster, die Sie überprüfen könnten, ob der seed gleich das Ergebnis und dann brechen Sie Ihre Schleife.

Können Sie meine LFSR-Methode in einer for-Schleife (z.B. for xor, pattern in lfsr(0b001,0b10011)) oder Sie können wiederholt aufrufen, die .next() Betrieb auf das Ergebnis der Methode, die einen neuen (xor, result)-pair-Mädchen jedes mal.

Machen es wirklich elegante und Pythonic, versuchen Sie, erstellen einen generator an, der yield-ing aufeinanderfolgende Werte aus der LFSR. Auch im Vergleich zu einer Fließkomma - 0.0 ist unnötig und verwirrend.

Einem LFSR ist nur eine von vielen Möglichkeiten zum erstellen von pseudo-Zufallszahlen in Computern. Pseudo-zufällig, denn es zahlen nicht wirklich random - Sie können ganz einfach wiederholen lassen, indem beginnend mit der seed (Startwert) und Verfahren mit der gleichen mathematischen Operationen.

Wenn wir davon ausgehen, dass Saatgut ist eine Liste von ints, anstatt ein string (oder konvertieren, wenn es nicht ist), dann die folgenden sollte das tun, was Sie wollen, mit ein bisschen mehr Eleganz:

def lfsr(seed, taps) :
  while True:
    nxt = sum([ seed[x] for x in taps]) % 2
    yield nxt
    seed = ([nxt] + seed)[:max(taps)+1]

Beispiel :

for x in lfsr([1,0,1,1,1,0,1,0,0],[1,5,6]) :
  print x