3. Lineares Schieberegister mit Rückkopplung:

Schieberegister mit Rückkopplung werden zur Erzeugung von Pseudozufallszahlen verwendet. In der Literatur, insbesondere auch in [1] sind vielseitige Varianten von rückgekoppelten Schieberegisterfolgen zu finden. Im folgenden soll ein rückgekoppeltes Schieberegister vorgestellt werden, das sich einfach in C++ implementieren läßt.

Die Arbeitsweise des dargestellten Schieberegister kann folgendermaßen beschrieben werden:

• Immer wenn ein Pseudozufallsbit benötigt wird, selektiert man das niederwertigste Bit des Schieberegisters b₁, das zum Ausgabebit wird.
• Das so gewonnene Ausgabebit wird mit einem Maskenwort (das gleich viele Bits wie das Schieberegister hat) UND verknüpft.
• Das Ergebnis dieser UND Verknüpfung wird mit den einzelnen Bits des Schieberegisters XOR verknüpft. (wenn das Ausgabebit 1 ist, werden die Maskenbits auf die XOR-Verknüpfung durchgeschaltet, ist das Ausgabebit 0, werden die Maskenbits ausgeblendet.)
• Das Ergebnis dieser XOR-Verknüpfung wird wieder in die Schieberegisterbits eingespeichert.
• Nach Ausführung dieser Rückkopplungsfunktion werden alle Bits des Schieberegisters um eine Stelle nach rechts geschoben. Das höchstwertige Bit erhält den Wert des Ausgabebits.

Schieberegister mit Rückkopplungsfunktion

Das in Schieberegister läßt sich auch folgendermaßen beschreiben:

Bemerkungen:

• Das Maskenbit m₁ ist, wie aus der Formelaufstellung ersichtlich, belanglos. Das Ergebnis bleibt das gleiche, ob m₁ 0 ist oder 1.
• Wenn alle Bits des Schieberegisters b₁ bis einschließlich b_n den Wert 0 haben, sind alle folgenden Werte des Schieberegisters ebenfalls 0.
• Hat das Schieberegister n Bits, so können maximal 2n-1 von Null verschiedene Zustände auftreten, die periodisch durchlaufen werden.
• Die Anzahl der Zustände werden durch die Maskenbits m₂ bis m_n bestimmt.

Die Bedeutung des Maskenwortes:

Sind sehr viele Bits des Maskenwortes 0, und nur wenige 1, so spricht man von einer "dünn besetzten" Rückkopplungsfunktion. Entsprechend der Literatur [1] sind "dicht besetzte" Rückkopplungsfunktionen kryptographisch schwerer zu knacken als "dünn besetzte". Dies läßt sich ansatzweise folgendermaßen erklären: Wenn alle Maskenbits den Wert 0 haben, werden die Bits im Schieberegister im Ring geschoben. Damit können im Schieberegister maximal n-1 verschiedene Zustände auftreten. Das heißt nach nur wenigen Durchläufen läßt sich ohne Kenntnis der Rückkopplungsfunktion auf das folgende Pseudozufallsbit schließen. Je "dicht besetzter" die Rückkopplungsfunktion desto stärker werden die einzelnen Bits bei jedem Durchlauf "verwürfelt". Diese Aussage ist allerdings mit Vorsicht zu genießen, es gibt auch durchaus "dicht besetzte" Rückkopplungsmasken, die eine nur geringe Periode aufweisen. Als besonders kritisch erweisen sich (nach entsprechenden Tests mit dem folgenden C-Programm) gleichmäßige Masken z.B. (001001001...).

Die in der folgenden Tabelle aufgeführten Rückkopplungskoeffizienten erzielen für ein 32Bit Schieberegister eine maximale Periode:

(25,5,4,2) (28,6,3,2)

(31,7,5,2)

(32,7,5,3,2)

3.1 Softwareimplementierung des linearen Schieberegisters mit Rückkopplung in C++

Hier wird nur aus Gründen der grafischen Darstellbarkeit auf eine Erzeugung von Zufallszahlen, die größer als 255 sind, verzichtet. Selbstverständlich ist es möglich, und wird auch in der Praxis so gehandhabt, daß Zufallszahlen mit einer Bitlänge bis zu 32Bit erzeugt werden.

// Name: LRSR.cpp (linear feedback shift register)
// Aufgabe: Implementierung eines linearen Schieberegisters mit Rückkopplung.
// Damit die erzeugten Pseudozufallsbits ausgewertet werden können, werden aus
// den Ausgabebits Zahlen zwischen 0 und 255 erzeugt.
// Ersteller: Cornelia Weiß

#include <iostream.h>
#include <conio.h>
#include <stdio.h>

/** Variable zur Darstellung eines Schieberegisters, Vorbelgung mit 1 **/
unsigned long ShiftRegister = 1;
/** Konstante, die die Maskenbits enthält **/
unsigned long mask = 0x80000057;

/** Funktion, die als Rückgabe das Ausgabebit liefert.
Das Ausgabebit kann 0 oder 1 sein. Funktion führt die Rückkopplungsfunktion
aus, und schiebt die Variable ShiftRegister um eine Stelle nach rechts **/

int modify_lfsr(void)
{
/* Wenn Bit 1 gesetzt ist, wird das ShiftRegister mit der vordefinierten Maske
XOR verknüft, danach wird das gesamte Schieberegister um eine Stelle nach
rechts geschoben. Mit der folgenden ODER-Verknüpfung wird das höchstwertige
Bit auf 1 gesetzt.*/

  if(ShiftRegister & 0x00000001)
  {
    /** XOR-Verknüpfung , Rechtsschieben, höchstwertiges Bit auf 1 setzen **/
    ShiftRegister = (ShiftRegister ^ mask) >> 1 | 0x80000000;
    /** Niederwertigstes Bit war eins, siehe if-Bedingung, deshalb return 1 **/
    return 1;
  }

/* Wenn Bit1 nicht gesetzt ist, wird das ShiftRegister lediglich um eine
Stelle nach rechts geschoben. Siehe vorhergehende Beschreibung:
Maskenbits werden ausgeblendet */
  else
  {
    /** Um eine Stelle nach rechts schieben **/
    ShiftRegister >>= 1;
    return 0;
  }
}


void main()
{
/** Um eine Zahl zwischen 0 und 255 zu erzeugen werden 8 Pseudozufallsbits
benötigt **/
  int bit1,bit2,bit3,bit4,bit5,bit6,bit7,bit8;
/** Variable für Pseudozufallszahl */
  unsigned long ax;
/** Variable für Anzahl der zu erzeugenden Pseudozufallszahlen **/
  unsigned long a;
/** Einlesen der Anzahl **/
  cout<<"Anzahl: "
  cin>>a;

  while(a-->0)
  {
/* Erzeugung der Bits für eine Pseudozufallszahl zwischen 0 und 255 */
    bit1 = modify_lfsr();
    bit2 = modify_lfsr();
    bit3 = modify_lfsr();
    bit4 = modify_lfsr();
    bit5 = modify_lfsr();
    bit6 = modify_lfsr();
    bit7 = modify_lfsr();
    bit8 = modify_lfsr();

/** Aufaddierung der Bitwertigkeiten **/
    ax = bit1 + bit2 * 2 + bit3 * 4 + bit4 * 8 + bit5 * 16 + bit6 * 32
 + bit7 * 64 + bit8 * 128;
    cout<<ax;
  }
}