[JoGu]

Kryptologie

Einschub: Linearitätsmaße für BOOLEsche Abbildungen

a7Hzq .#5r<
kÜ\as TâÆK$
ûj(Ö2 ñw%h:
Úk{4R f~`z8
¤˜Æ+Ô „&¢Dø

  1. Die algebraische Normalform BOOLEscher Funktionen [PDF]
  2. WALSH-Transformation und krumme Funktionen [PDF]
  3. Approximation durch lineare Relationen [PDF]
  4. Approximation durch lineare Strukturen [PDF]
  5. Optimierung der Nichtlinearität [PDF]

Dieses Kapitel gibt es auch am Stück als PDF-Datei +


In der Kryptologie dienen BOOLEsche Funktionen und Abbildungen als Grundbausteine für die Konstruktion von Bitblock- und Bitstrom-Chiffren. Ein wichtiges Kriterium dabei ist die Nichtlinearität: Verschlüsselungsfunktionen (z. B. die S-Boxen, die als »atomare« Bausteine von Bitblock-Chiffren verwendet werden) und Bit-Generatoren (z. B. Kombinationen von linearen Schieberegistern) sollen »möglichst wenig linear« sein. Aber was heißt das?

In den letzten Jahren wurden dafür verschiedene Maße eingeführt, die sich bei der Aufdeckung versteckter Linearität ergänzen. Ist eine BOOLEsche Abbildung bezüglich eines solchen Maßes zu nahe an der Linearität, so eröffnen sich Angriffsmöglichkeiten auf die Verschlüsselungssysteme, in denen sie verwendet wird. Die bekanntesten Beispiele dafür sind die lineare und die differenzielle Kryptoanalyse.

Das wichtigste mathematische Werkzeug, um Linearitätsmaße elegant und einheitlich behandeln zu können, ist die WALSH-Transformation, ein Spezialfall der diskreten FOURIER-Transformation. Viele der Beweise aus der Literatur reduzieren sich dadurch auf wenige Zeilen, und die Berechnung der Linearitätsmaße wird sehr effizient möglich. Diese Abschnitte enthalten die systematische und geschlossene Darstellung dieser Theorie, die man auch »FOURIER-Analyse BOOLEscher Abbildungen« nennen könnte, angereichert mit vielen Beispielen.


Autor: Klaus Pommerening, 30. Mai 2000; letzte Änderung: 4. Juli 2008.