Siegenthaler bound verständlich erklärt: Unterschied zwischen den Versionen

Aus NOBAQ
Zur Navigation springenZur Suche springen
Zeile 18: Zeile 18:
 
<math>n - m \leq d</math>
 
<math>n - m \leq d</math>
  
Im Kern besagt dieser Sachverhalt, dass die Nichtlinearität einer booleschen Funktion durch die ''correlation immunity'' begrenzt ist und umgekehrt. Bei der Implementation einer Streamcipher durch nichtlineare Kombinationen aus LFSRs muss man also einen Kompromiss zwischen der ''correlation immunity'' und dem Grad der Linearität eingehen.
+
Im Kern besagt dieser Sachverhalt, dass die Nichtlinearität einer booleschen Funktion durch die ''correlation immunity'' begrenzt ist und umgekehrt. Bei der Implementation einer Streamcipher durch nichtlineare Kombinationen aus LFSRs muss man also einen Kompromiss zwischen der ''correlation immunity'' und dem Grad der Linearität eingehen. Die Grenze ist auch abhängig von der Anzahl der Parameter n.
  
 
Intuitiv ist der Sachverhalt auch einfach nachvollziehbar: Die Wahrheitstabelle von XOR gibt genau 2 Werte mit 0 aus und 2 mit 1, der Output ist also gleichverteilt. Seien <math>X_1</math> und <math>X_2</math> zwei zufällige Binärfolgen (niedrige Autokorrelation), dann ergibt
 
Intuitiv ist der Sachverhalt auch einfach nachvollziehbar: Die Wahrheitstabelle von XOR gibt genau 2 Werte mit 0 aus und 2 mit 1, der Output ist also gleichverteilt. Seien <math>X_1</math> und <math>X_2</math> zwei zufällige Binärfolgen (niedrige Autokorrelation), dann ergibt
Zeile 31: Zeile 31:
  
 
so ergibt die Verknüpfung von <math>Y</math> und einem Plaintext zu einem Ciphertext eine hohe Korrelation zwischen Ciphertext und Plaintext, da der Ciphertext mit einer höheren Wahrscheinlichkeit 0 als 1 wird. AND ist eine nichtlineare Funktion und kann als Multiplikation modulo 2 betrachtet werden.
 
so ergibt die Verknüpfung von <math>Y</math> und einem Plaintext zu einem Ciphertext eine hohe Korrelation zwischen Ciphertext und Plaintext, da der Ciphertext mit einer höheren Wahrscheinlichkeit 0 als 1 wird. AND ist eine nichtlineare Funktion und kann als Multiplikation modulo 2 betrachtet werden.
 +
 +
== Correlation immunity ==
 +
 +
Die ''correlation immunity'' <math>m</math> ist ein Maß dafür, wie resistent eine boolesche Funktion gegen Korrelationsattacken ist, d.h. ob und wieviel Information man aus der Ausgabe einer Funktion über deren Argumente ziehen kann. Nach dem Beispiel oben ist <math>m</math> für eine XOR-Funktion hoch und für eine AND-Funktion niedrig.
 +
 +
Eine notwendige Bedingung für correlation immunity ist die Gleichverteilung der Ausgabe einer Funktion. ------------------

Version vom 10. Juni 2008, 12:37 Uhr

Bei Streamciphers in der Kryptographie ist es sehr wichtig, einen Keystream zu erstellen, der möglichst wenige Rückschlüsse auf den verschlüsselten Plaintext zulässt. Da eine Streamcipher eine Erweiterung der Vernam-Cipher ist, wird dabei der Plaintext einfach mit dem Ciphertext addiert (modulo 2):

Damit die Cipher sicher ist, soll der Keystream KS ein paar nette Eigenschaften haben:

  • Der Keystream soll wie Rauschen aussehen, das bedeutet die Autokorrelation soll sehr niedrig sein
  • Die lineare Komplexität der Folge soll möglichst hoch sein, damit die Folge eine möglichst hohe Periode hat
  • Die Folge soll von nicht-linearen Funktionen erzeugt werden (d.h. von keinem (reinen) LFSR) oder zumindest von einer Kombination aus nichtlinearen Funktionen, da für jede lineare Kombination aus LFSRs mit Berlekamp-Massey in eine alternative Darstellung als LFSR gefunden werden kann die höchstens so hoch ist, wie die LFSRs zusammen.

Siegenthaler hat 1984 gezeigt dass diese Anforderungen zum Teil im Widerspruch stehen. Da ich nach langem Suchen keine schöne Erklärung zum Siegenthaler bound, der correlation immunity und dem nonlinear order gefunden habe, versuche ich hier selbst eine verständliche Erklärung.

Siegenthaler bound

Der Siegenthaler Bound ist definiert mit:

If has inputs and is -th order correlation immune, then the nonlinear order of is at most . Mathematisch:

Im Kern besagt dieser Sachverhalt, dass die Nichtlinearität einer booleschen Funktion durch die correlation immunity begrenzt ist und umgekehrt. Bei der Implementation einer Streamcipher durch nichtlineare Kombinationen aus LFSRs muss man also einen Kompromiss zwischen der correlation immunity und dem Grad der Linearität eingehen. Die Grenze ist auch abhängig von der Anzahl der Parameter n.

Intuitiv ist der Sachverhalt auch einfach nachvollziehbar: Die Wahrheitstabelle von XOR gibt genau 2 Werte mit 0 aus und 2 mit 1, der Output ist also gleichverteilt. Seien und zwei zufällige Binärfolgen (niedrige Autokorrelation), dann ergibt

ebenfalls wieder eine zufällige Folge. Verknüpft man nun einen Plaintext mit , so gibt es keine Korrelation zwischen dem resultierendem Ciphertext und dem Plaintext, da der Output der XOR Funktion gleichverteilt ist. XOR ist eine lineare Funktion.

Anders verhält es sich mit der AND Funktion: Das Ergebnis ist mit einer Wahrscheinlichkeit von 0 und nur mit der Wahrscheinlichkeit von 1. Sei nun

so ergibt die Verknüpfung von und einem Plaintext zu einem Ciphertext eine hohe Korrelation zwischen Ciphertext und Plaintext, da der Ciphertext mit einer höheren Wahrscheinlichkeit 0 als 1 wird. AND ist eine nichtlineare Funktion und kann als Multiplikation modulo 2 betrachtet werden.

Correlation immunity

Die correlation immunity ist ein Maß dafür, wie resistent eine boolesche Funktion gegen Korrelationsattacken ist, d.h. ob und wieviel Information man aus der Ausgabe einer Funktion über deren Argumente ziehen kann. Nach dem Beispiel oben ist für eine XOR-Funktion hoch und für eine AND-Funktion niedrig.

Eine notwendige Bedingung für correlation immunity ist die Gleichverteilung der Ausgabe einer Funktion. ------------------