Analyseverfahren spart Rechenzeit Polynome schneller auf Primitivität prüfen

Ein neues Analyseverfahren ermöglicht es, Polynome bis r=53 in einem Sekundenbruchteil auf Primitivität zu überprüfen.
Ein neues Analyseverfahren ermöglicht es, Polynome bis r=53 sehr schnell auf Primitivität zu überprüfen.

Rückgekoppelte Schieberegister werden für Sicherheitsanwendungen mit einem primitiven Generatorpolynom r-ten Grades implementiert. Ein neues Analyseverfahren ermöglicht es, Polynome bis r=53 in einem Sekundenbruchteil auf Primitivität zu überprüfen – statt in mehr als 30 min.

In der Sicherheitstechnik werden zur Fehlererkennung lineare Block-Codes eingesetzt. Bei einem Block-Code werden die k Informationsbits gefolgt von r Prüfbits als ein Codewort CW der Länge n = k + r übertragen. Es gibt somit 2k Kombinationen von Informationsbits. Zu jeder dieser Kombination gibt es eine eindeutige Zuordnung von r Prüfbits. Damit ergeben sich 2k Codeworte. Wenn der übertragene Block kein Codewort bildet, so wird es als verfälscht erkannt. Ein Block kann insgesamt auf 2n unterschiedliche Weisen verfälscht werden. Wird der  fehlerfreie Fall, der grundsätzlich nicht als fehlerhaft erkannt werden kann und auch keinen Fehler darstellt, von 2k CW abgezogen, so bleiben 2k – 1 Fehlerkombination unerkannt. Die Wahrscheinlichkeit von nicht Erkennen eines Fehlers beträgt somit (2k – 1) / 2n = 2-r – 2-n. Für einen großen Wert n beträgt dann diese Restfehlerwahrscheinlichkeit ≈ 2-r.

Zur Generierung von Prüfbits wird häufig ein r-stufiges rückgekoppeltes Schieberegister (LFSR, linear feedback shift register) eingesetzt. Die Rückkopplungen von einzelnen Registern werden in zwei unterschiedlichen Weisen vorgenommen und ohne äußere Einflüsse durchlaufen beide Ausführungen eine Anzahl von ZL Zuständen, bis der Startwert des Registers wiederkehrt. Die Zykluslänge ZL hängt davon ab, mit welchem Startwert das Schieberegister anläuft. Der Zustand eins bestehend aus r – 1 Nullen und eine eins liefert stets die größte Zykluslänge ZL. Abhängig vom Polynom kann die Zykluslänge den maximalen Wert ZLmax = 2r – 1 erreichen. Der Zustand Null mit r Nullen bleibt unberücksichtigt, da in diesem Fall das Schieberegister sich nicht mehr verändert. Die primitiven Polynome erreichen die maximal mögliche Zykluslänge ZLmax und sind irreduzibel, haben also keinen Teiler [1].

Primitive Polynome haben in der Sicherheitstechnik einen hohen Stellenwert und werden bevorzugt zur Datensicherung eingesetzt. Zur Bestimmung der Primitivität eines Polynoms muss daher die Zykluslänge ZL ermittelt werden. Für großes r (r ≥ 32) müssen dann mehr als 4,2 Milliarden Zustände untersucht werden. Selbst die modernsten Computer brauchen dafür mehr als 30 Minuten. Mit einer neuen Analysemethode lässt sich diese Aufgabe im Bruchteil einer Sekunde erledigen. Die neue Methode lässt sich flexibel einsetzen und erlaubt auch die Analyse von Polynomen mit großem r (r > 64).

Methoden zur Bestimmung der Polynomprimitivität

Das in Europa weitverbreitete Konzept beruht auf der Polynom-Division und wird als Galois-LFSR (G-LFSR) bezeichnet. Hierzu wird der zu übermittelnde Datenblock durch das Generator-Polynom r-ten Grades, das als G-LFSR implementiert wird, geteilt. Nachdem der Datenblock durch das Schieberegister geschoben wurde, ist die Teilung vollzogen und ein Rest des Teilungsergebnisses bleibt im Schieberegister zurück. Dieser Rest dient als Prüfbits und wird in der Literatur als FCS „Frequency Check Sum“ bezeichnet. Häufig wird der Inhalt des Schieberegisters nach Einschieben des kompletten Datenblocks im Schieberegister (Rest der Division) auch als Signatur des Datenblocks bezeichnet. In der Praxis werden die r Nullen an die k Informationsbits angehängt und der Datenblock der Länge n = k + r wird in das G-LFSR eingeschoben. Dies wird auch als lange Division bezeichnet. Nach n Takten steht der Rest der Division – n-bit-Datenblock (k Informationsbits gefolgt von r Nullen) geteilt durch das Generatorpolynom – im Schieberegister. Wird die, so gewonnene Signatur der langen Division zum Datenblock der Länge n addiert, entsteht ein Codewort. Die Signatur des Codewortes ist dann erwartungsgemäß Null. Wenn die Signatur eines übertragenen Datenblocks Null ist, so ist die übertragene Information entweder fehlerfrei oder die Verfälschung stellt wieder ein Codewort dar. Bei dieser Betrachtungsweise handelt es sich um die Bildung eines echten Rests und sie lässt sich mathematisch exakt beschreiben.

Bei dem nächsten völlig gleichwertigen Verfahren, das als Fibonacci-LFSR (F-LFSR) bezeichnet wird, werden auch die Daten durch das Generator-Polynom r-ten Grades, das als F-LFSR implementiert wird, in das Schieberegister eingeschoben. Im Gegensatz zu einer langen Division werden hier nur die k Informationsbits in das F-LFSR eingeschoben. Nach k Takten steht dann die Signatur des Datenblocks (Nutzinformation) im Schieberegister. Bei F-LFSR handelt es sich um eine Abbildung von einem Datenblock der Länge k auf r bit. Da hier nun keine Division mit Restbildung im eigentlichen Sinne stattfindet, kann die r-bit-Signatur auch nicht zum Datenblock aufaddiert werden, um daraus ein Codewort zu gewinnen. Stattdessen wird diese r-bit-Signatur in einer eindeutigen Weise auf einem anderen r-bit-Tupel abgebildet. Die Abbildungsvorschrift wird im Absatz „Eigenschaften von LFSR“ erläutert. Die manipulierte r-bit-Signatur wird dann konventionsgerecht der k-bit-Nutzinformation vorangestellt. Die Signatur des so gewonnenen Datenblocks der Länge n = r + k bit besteht erwartungsgemäß aus r Nullen und bildet ein Codewort.

Beide Verfahren, G-LFSR und F-LFSR, sind vollkommen zueinander kompatibel. Obwohl ein und dasselbe Generatorpolynom, wie im nächsten Absatz beschrieben, mit zwei physikalisch gänzlich unterschiedlichen LFSR-Implementierungen zum Einsatz kommt, bleiben jedoch die Grundmerkmale, wie z.B. Anzahl der Zyklen und ihre Länge, bei beiden Verfahren stets identisch. Die  Unterschiede sind struktureller Natur. Beispielsweise liefern beide LFSR für das Generatorpolynom 4-ten Grades „1dh“ (binär: 11101) drei Zyklen – zwei Zyklen mit einer Länge von sieben und ein Zyklus mit der Länge eins. Der Verlauf der Zustände ist jedoch bei beiden Verfahren gänzlich unterschiedlich, wie es aus Bild 1 entnommen werden kann. Bemerkenswert ist, dass bei der G-LFSR-Implementierung der Zustand „11“ (binär: 1011) auf sich abbildet, dagegen bei der F-LFSR der Zustand „15“ (binär: 1111) auf sich abbildet.

Ausführungsvarianten

Ein Polynom r-ten Grades wird allgemein durch die Gleichung (1) beschrieben und besteht aus der Summenbildung von maximal r + 1 Glieder, gi xi mit i = 0 bis r.

 

g subscript r times x to the power of r plus g subscript r minus 1 end subscript times x to the power of r minus 1 end exponent plus horizontal ellipsis plus g subscript 1 times x to the power of 1 plus g subscript 0 times x to the power of 0 equals 0 space space space space space left parenthesis 1 right parenthesis
m i t colon space g subscript r equals g subscript 0 equals 1

 

Da hier mit den binären Daten operiert wird, können die Koeffizienten gi die Werte 0 oder 1 annehmen. Die Koeffizienten gr und g0 haben per Definition die Wertigkeit 1, die restlichen Koeffizienten sind polynomspezifisch. Die einzige Gemeinsamkeit der Implementierungen G-LFSR und F-LFSR besteht aus der Rückkopplung des r-ten-Registers auf den Eingang des ersten Registers und ist in den nachfolgenden Abbildungen rot markiert. Diese Rückkopplung ist obligatorisch. Das rückgekoppelte Signal wird grundsätzlich über ein Exklusiv-Oder-Gatter verknüpft und weiter gereicht. Jedem rückgekoppelten Signal werden zwei Koeffizienten gj und gk-1 zugeordnet, wobei der Ausgang SRj auf den Eingang SRk rückgekoppelt wird. Die Rückkopplung ist nur dann wirksam, wenn sowohl gj als auch gk-1 die Wertigkeit 1 haben.

Bei der G-LFSR-Implementierung wird grundsätzlich das r-te Schieberegister selektiv mit dem Eingang des i-ten Schieberegisters verknüpft, falls der Koeffizient gi-1 0 ist. Die Zuordnungskoeffizienten-Paare tragen die Bezeichnung gr, gi-1 mit i = 2 bis r (gr = gi-1 =1); das Koeffizienten-Paar gr, g0 ist obligatorisch. Bild 2 zeigt eine G-LFSR-Implementierung für das Polynom 19h. Falls ein Koeffizient gi Null ist, wird die Rückkopplung mit einem Pfeil mit unterbrochener Linie dargestellt. Dies deutet auf eine fehlende Rückkopplung hin. Bei einer F-LFSR-Implementierung wird dagegen der Ausgang des i-ten Schieberegisters mit dem Eingang des ersten Schieberegisters verknüpft, falls der Koeffizient gi 0 ist. Die Zuordnungskoeffizienten-Paare tragen die Bezeichnung gi, g0 mit i = 1 bis r–1 (gi = g0 = 1); das Koeffizienten-Paar gr, g0 ist obligatorisch. Eine F-LFSR-Implementierung für das Polynom 19h ist in Bild 3 dargestellt.

Bereits bei dieser anfänglichen Betrachtung werden die zwei Vorzüge der F-LFSR-Implementierung deutlich. Anhand von Bild 2 lässt sich feststellen, dass zur Realisierung von G-LFSR das Schieberegister am Eingang mit einem XOR-Gatter erweitert werden muss. Ein Schieberegister wird in der Elektronik sehr häufig eingesetzt und dem entsprechend wird es vom Chiphersteller auf die benötigte Chipfläche optimiert. Die Integration eines zusätzlichen Gatters am Eingang erhöht den Aufwand, zumal nicht alle Registerstufen es benötigen. Bei der Implementierung von F-LFSR ist der Einsatz von dem vielfach bewährten, auf minimale Chip-Fläche optimierten und wirtschaftlich günstigeren Schieberegisters möglich. Lediglich wird am Eingang dafür dann ein XOR-Gatter mit mehrfachen Eingängen benötigt. Für eine F-LFSR-Implementierung wird nur einmal ein XOR-Gatter benötigt, wogegen eine G-LFSR-Implementierung mehrere XOR-Gatter erfordert. Selbst wenn die erforderlichen XOR-Gatter außerhalb der Schieberegisterkette implementiert werden, wie es bei G-LFSR-Implementierungen üblich ist, ergibt sich ein Vorteil bei der F-LFSR-Implementierung.

 

Der zweite Vorteil der F-LFSR-Implementierung besteht darin, dass sich der Folgezustand des Schieberegisters relativ leicht bestimmen lässt. Hierzu werden die r bit des aktuellen Zustands um ein bit nach links verschoben und dem LSB wird der Wert 1 oder 0 zugewiesen. Ist die Anzahl der rückgekoppelten Bits plus das aktuelle Datenbit mit der Wertigkeit 1 eine ungerade Zahl, so hat das LSB den Wert 1. Mit ein wenig Übung ist es sogar möglich, den Verlauf des Schieberegisters, im Kopf zu berechnen. Bei G-LFSR muss leider jedes Bit extra bestimmt werden.

Konvention

Der Umgang mit LFSR ist gewöhnungsbedürftig und erfordert ein hohes Maß an Disziplin vom Anwender. Nachfolgend wird die Konvention zusammengefasst, die akribisch genau eingehalten werden muss. Bei Nichteinhaltung der Konvention, auch bei der geringsten Abweichung, entsteht ein Chaos.

Für beide Verfahren (G-LFSR und F-LFSR) gemeinsam:

  1. Anordnung von Schieberegister: MSB steht links und LSB rechts.
  2. Schieberichtung: Geschoben wird von rechts nach links.
  3. Die Schieberegister werden von rechts nach links, beginnend mit eins, in aufsteigender Reihenfolge bezeichnet.
  4. Ein Spaltenvektor mit r bit, wobei das MSB des Schieberegisters oben und das LSB des Schieberegisters unten steht, stellt den Zustand des Schieberegisters zu einem beliebigen Zeitpunkt t dar.

    Z left parenthesis t right parenthesis equals space left square bracket S R subscript r left parenthesis t right parenthesis comma space S R subscript r minus 1 end subscript left parenthesis t right parenthesis comma space S R subscript r minus 2 end subscript left parenthesis t right parenthesis comma space horizontal ellipsis comma space S R subscript 2 left parenthesis t right parenthesis comma space S R subscript 1 left parenthesis t right parenthesis right square bracket to the power of T space space space space space left parenthesis 2 right parenthesis
     
  5. Mit einer r x r-Matrix Tm kann der nächste Zustand des Schieberegisters bestimmt werden.

    Z left parenthesis t plus 1 right parenthesis equals T m times Z left parenthesis t right parenthesis space space space space space left parenthesis 3 right parenthesis
     
  6. Die Matrix Tm wird als Transformationsmatrix bezeichnet und ist für die Varianten G-LFSR und F-LFSR unterschiedlich.

G-LFSR-spezifische Konvention:

  1. Schieben der Daten: MSB wird zuerst geschoben.
  2. Ein Zeilenvektor mit r bit stellt die Rückkopplung Rk dar. Rk besteht aus der binären Darstellung des Polynoms ohne MSB, z.B. für das Polynom dh (binär: 1101) ist Rk = [101].
  3. Die Transformationsmatrix Tm-G wird aus einer (r – 1) x (r – 1) Einheitsmatrix  E(r – 1) und der Rückkopplung bestimmt.

    T m minus G equals left enclose table row blank row cell R subscript k superscript T end cell row blank end table end enclose space left enclose right enclose table row cell 2 cross times 2 end cell row E row cell table row 0 0 end table end cell end table end enclose equals end enclose left enclose right enclose table row 1 1 0 row 0 0 1 row 1 0 0 end table end enclose space space space space space left parenthesis 4 right parenthesis end enclose
f ü r space d a s space P o l y n o m space d h   
     
  4. Zur Codewortbildung werden die r Nullen an das Datum angehängt und die Signatur gebildet. Die so gewonnene Signatur der langen Division wird zu dem mit r Nullen erweiterten Datum auf addiert oder an das Datum selbst angehängt.

F-LFSR-spezifische Konvention:

  1. Schiebung der Daten: LSB wird zuerst geschoben.
  2. Ein Zeilenvektor mit r bit stellt die Rückkopplung Rk dar. Rk besteht aus der binären Darstellung des Polynoms ohne LSB, z. B. für das Polynom dh = 1101 ist Rk = [1 1 0].
  3. Die Transformationsmatrix Tm-F wird aus einer (r – 1) x (r – 1) Einheitsmatrix E(r – 1) und der Rückkopplung bestimmt.

    T m minus F equals open vertical bar table row cell fraction numerator table row 0 cell 2 cross times 2 end cell row 0 E end table over denominator R subscript k end fraction end cell end table close vertical bar space equals open vertical bar table row 0 1 0 row 0 0 1 row 1 1 0 end table close vertical bar space space space space space left parenthesis 5 right parenthesis
f ü r space d a s space P o l y n o m space d h

          
  4. Zur Codewortbildung wird die Signatur des Datums (Nutzinformation) gebildet. Anschließend wird die Signatur des Datums einer Manipulation unterworfen, um daraus die tatsächliche Signatur zu bilden. Diese wird dann dem Datum vorangestellt. Die Manipulationsvorschrift wird im nächsten Absatz erläutert.