Siegenthaler bound verständlich erklärt: Unterschied zwischen den Versionen
Niki (Diskussion | Beiträge) |
Niki (Diskussion | Beiträge) |
||
| Zeile 6: | Zeile 6: | ||
* Der Keystream soll wie Rauschen aussehen, das bedeutet die Autokorrelation soll sehr niedrig sein | * Der Keystream soll wie Rauschen aussehen, das bedeutet die Autokorrelation soll sehr niedrig sein | ||
* Die lineare Komplexität <math>\mathcal{L}</math> der Folge soll möglichst hoch sein, damit die Folge eine möglichst hohe Periode hat | * Die lineare Komplexität <math>\mathcal{L}</math> 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) [http://de.wikipedia.org/wiki/LFSR LFSR]) oder zumindest von einer Kombination aus nichtlinearen Funktionen, da für jede | + | * Die Folge soll von nicht-linearen Funktionen erzeugt werden (d.h. von keinem (reinen) [http://de.wikipedia.org/wiki/LFSR LFSR]) oder zumindest von einer Kombination aus nichtlinearen Funktionen, da für jede lineare Kombination aus LFSRs mit [http://de.wikipedia.org/wiki/Berlekamp-Massey-Algorithmus Berlekamp-Massey] in <math>O(n^p)</math> eine alternative Darstellung als LFSR gefunden werden kann die höchstens so hoch ist, wie die LFSRs zusammen. |
| − | Siegenthaler hat 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 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 <math>f</math> has <math>n</math> inputs and <math>f</math> is <math>m</math>-th order correlation immune, then the nonlinear order of <math>f</math> is at most <math>n-m</math>: | ||
| + | |||
| + | <math>n-m \seq d</math> | ||
Version vom 10. Juni 2008, 11:46 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 :
Fehler beim Parsen (Unbekannte Funktion „\seq“): {\displaystyle n-m \seq d}
