Siegenthaler bound

Für die Konstruktion einer Stromchiffre in der Kryptographie wird eine pseudozufällige Bitfolge benötigt, die in der Regel mit dem Plaintext XOR verknüpft wird:

$CT = PT \oplus KS$

Damit die Chiffre sicher ist, soll der Keystream wie Rauschen aussehen, d.h. die Autokorrelation soll sehr niedrig sein, damit es zu keiner Korrelation zwischen dem Plaintext und dem Ciphertext kommt.

Zum Herstellen dieser Bitfolge verwendet man gewöhnlich LFSR. Normale LFSR sind aber linear und erzeugen so einen Bitstrom der relativ einfach rückberechnet werden kann. Zur Verbesserung kombiniert man mehrere LFSR mit nichtlinearen Funktionen. Siegenthaler hat 1984 gezeigt, dass sich dadurch die Korrelationsimmunität einer Folge verschlechtert:

Sei f eine boolesche Funktion mit n Argumenten und sei f zur Ordnung m korrelations immun, so ist die lineare Ordnung der Funktion nach oben begrenzt mit:

$n - m \leq d$

Bei der Implementation einer Stromchiffre durch nichtlineare Kombinationen aus LFSR muss man also einen Kompromiss zwischen der Korrelationsimmunität und dem Grad der Linearität eingehen.

Referenzen

• T. Siegenthaler: Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications. In: IEEE Transactions on Information Theory. 30, Nr. 5, September 1984, S. 776–780. doi:10.1109/TIT.1984.1056949.

Weblinks

• Siegenthalerbound verständlich erklärt