Warum benötigen Blockchiffren eine nichtlineare Komponente (wie eine S-Box)?

  • Warum werden "nichtlineare Funktionen" als Bestandteil vieler gängiger Blockchiffren benötigt (z. B. die S-Box in DES oder 3DES)?

    Wie wird die Verschlüsselung sicherer?

    Die einzige Intuition, die ich habe, ist, dass eine nicht lineare Funktion viele Wurzeln (Lösungen) haben kann. Z.B. Wenn der Angreifer $ y $ für die Ermittlung des $ x $ kennt, kann es für ein nicht lineares $ y = F (x) $ viele Optionen geben, die $ y = F (x) $ erfüllen. Daher addiert sich die Komplexität am Ende des Angreifers wenn er versucht, von verschlüsseltem Text zu reinem Text zurückzukehren (zurück zu gehen).

    Alle Referenzen oder detailliertes Material sind willkommen.

    06 June 2012
    cmcculloh
2 answers
  • Wenn eine Blockverschlüsselung in Bezug auf ein Feld linear ist, ist es bei einigen bekannten Klartext-Geheimtext-Paaren möglich, den Schlüssel mithilfe eines einfachen Gaussian elimination . Dies widerspricht eindeutig den Sicherheitseigenschaften, die man von einer sicheren Blockchiffre erwartet.

    07 June 2012
    cryptopathe
  • Hier ist die Perspektive der Kryptografietheorie.

    Wir möchten, dass Blockchiffristen pseudozufällige Permutationen (PRPs). PRPs sind ein wünschenswertes Modellierungsziel, da eine Blockverschlüsselung unter einem gegebenen Schlüssel eine Permutation der Eingabe ist und ein PRP einfach eine zufällige Sammlung von Permutationen ist. Der Schlüssel der Blockchiffre kann nie besser Permutationen erzeugen als eine zufällige Stichprobe davon, aber wir möchten, dass er so nahe wie möglich ist. Eine erkennbare Abweichung vom PRP-ähnlichen Verhalten wird als Schwachstelle in einer Blockverschlüsselung angesehen.

    Um eine Blockverschlüsselung mit einem PRP zu vergleichen, verwenden wir das CPA-Modell, bei dem ein Angreifer eine Blackbox abfragt mit Klartext und erhält die entsprechende permutierte Ausgabe. Sie versuchen zu ermitteln, ob die Blackbox die Chiffretextausgabe auswählt, indem sie eine zufällige Permutation oder die angegebene Blockverschlüsselung mit einem unbekannten Schlüssel auf den Klartext anwenden. Wenn sie richtig raten, gewinnen sie das Spiel. Wenn sie das Spiel mit einer Wahrscheinlichkeit von mehr als 50% gewinnen können, haben sie die Blockchiffre gebrochen. (Siehe diese Notizen , Seiten 1 - 8, insbesondere 7, für ein Bild und genauere Definition dieses Modells.)

    Ein Angreifer kann eine Blockverschlüsselung von einem PRP unterscheiden, wenn die Blockverschlüsselung lineare Eigenschaften aufweist. Sie können diese linearen Eigenschaften lernen und dann die Blackbox mit Klartexten abfragen, die bestimmte Eigenschaften im verschlüsselten Text erzeugen sollen. Wenn die Blackbox für mehr als 50% der Eingabeabfragen mit einem Chiffretext antwortet, der mit den erwarteten Eigenschaften übereinstimmt, vermutet der Angreifer, dass die Blackbox die Blockchiffre enthält, da eine zufällige Permutation diese linearen Eigenschaften mit einer Wahrscheinlichkeit von nur 50% berücksichtigt. (Andernfalls vermuten sie, dass die Blackbox eine zufällige Permutation verwendet.) Dann gewinnt der Angreifer das Unterscheidungsspiel.

    Natürlich, wenn Sie nach einem praktischen Grund suchen, t

    07 June 2012
    B-Con