松井のアルゴリズム

松井充は1993年にDESへの線形解読法を発表した。発想は優雅だったが、最良の線形近似を手作業で探すのは遅々として進まなかった。松井の分枝限定探索は候補となる特性を体系的に調べ、有用なバイアスに到達できない枝をすべて刈り込んだ。

1994年の成果は、DESに対する最初の実験的な暗号解読となった。約2⁴³組の既知平文を必要とし、ワークステーションのネットワークで数日を要する攻撃である。DESは1977年から標準であり続けた。2001年にAESが取って代わったが、DESの退場を惜しむ者はすぐにいなくなった。