Matsui-Algorithmus
Der Suchalgorithmus, der lineare Approximationen von DES von der Theorie zum tatsächlichen Bruch machte.
Mitsuru Matsui stellte 1993 die lineare Kryptoanalyse von DES vor. Die Idee war elegant, doch die besten linearen Approximationen von Hand zu finden, ging schleppend voran. Matsuis Branch-and-Bound-Suche durchmusterte mögliche Charakteristiken systematisch und kappte jeden Zweig, der keine nutzbare Verzerrung mehr erreichen konnte.
Das Ergebnis von 1994 war die erste experimentelle Kryptoanalyse von DES: ein Known-Plaintext-Angriff mit rund 243 Paaren und mehreren Tagen Rechenzeit auf einem Netz von Workstations. DES war seit 1977 Standard; 2001 löste ihn AES ab, und lange trauerte ihm niemand nach.