Walsh-Hadamard-Transformation
Eine schnelle Transformation, die die Korrelation mit allen linearen Funktionen auf einmal berechnet – das Arbeitspferd großer Teile der linearen Kryptanalyse.
Eine boolesche Funktion mit n Eingängen liegt als Vektor aus 2n Werten vor. Die Transformation liefert einen Vektor gleicher Größe, in dem jeder Eintrag angibt, wie stark die Funktion mit einer bestimmten linearen Funktion korreliert. Naiv gerechnet kostet das 22n Operationen. Die schnelle Variante, die einer FFT ähnelt, schafft es in n·2n.
Der Name geht auf Jacques Hadamard und Joseph Walsh zurück, die sich im späten 19. und frühen 20. Jahrhundert mit orthogonalen Systemen beschäftigten. In der S-Box-Analyse ist sie das Alltagswerkzeug, um die stärksten linearen Approximationen zu finden. Wer die Rechnung einmal ohne sie durchgeführt hat, weiß genau, warum es sie gibt.