共通鍵暗号は歴史も古く、強度に関する研究は数多く行われている。 イスラエルのＢｉｈａｍとＳｈａｍｉｒによる差分解読法、 松井（三菱電機）による線型解読法などが有名なところである。 これらの解読法は多くの共通鍵暗号系に適用でき、 現在共通鍵暗号の強度評価の尺度になっている。
一方、数多くの共通鍵暗号を統一した尺度で強度評価することは、 多くの面から望まれているが、現実には行われていない。
この研究は、創造的ソフトウエア育成事業の一つ「秘密鍵暗号の強度評価ソフトウエア」として行われた。 発注先は三菱電機。
本プロジェクトでは、現在使用されている幾つかの６４ビット共通鍵暗号の強度を、統一された尺度で評価する。
評価基準として、前述の差分解読法と線型解読法を用いるが、その他にも幾つかの尺度がある。 用いた尺度は以下の通り。
- 差分特性確率
- 線型特性確率
- 平均差分確率
- 平均線型確率
- 閉構造探索
- Ｐｕｒｉｔｙ構造検索
- 乱数列評価
- ０１等類度性
- 系列検定
- 衝突検定
また、評価の対象として選ばれた共通鍵暗号は、以下の通り。
- ＤＥＳ（米国標準）
- ＦＥＡＬ（ＮＴＴ）
- Ｍｕｌｔｉ−２（日立製作所）
- ＬＯＫＩ
- ＩＤＥＡ
- ＭＢＡＬ（ローレルインテリジェントシステムズ）
- ＭＩＳＴＹ（三菱電機）
上記の尺度により各共通鍵暗号の性質がグラフで明示されるソフトウェアが完成した。 （ただし１部の共通鍵暗号は特許権・著作権の制限から、発注先企業の内部で実験されたのみで、納入されていない。） 特に、差分特性・線型特性は暗号の強度が直感的に見とれるので、有益なソフトウェアとなった。
この研究は、「暗号強度評価に関わる調査研究」の一部として行われた。三菱電機と横浜国立大学松本勉助教授の共同プロジェクト。
本プロジェクトでは、共通鍵暗号であるＤＥＳ（Data Encryption Algorithm）を対象として、「平文とその平文が暗号化された後の暗号文の1つのペアが与えられている条件の元、暗号化に用いられた鍵をもとめる」場合に、必要な装置規模と実行時間によって暗号の強度を評価する方法の１つであるタイムメモリードレードオフ（ＴＭＴＯ）解読法を研究調査した。 現在最も使用されているＤＥＳの強度は、実世界に直接影響するだけに、詳しく調べる必要がある。
ＴＭＴＯ法の処理は，事前処理と解読の２つの異なる処理に大別することができる。
事前処理は、暗号化される前の平文が、あらかじめ与えられているとして、探索表と呼ばれる特定の法則に基づいた表の作成を行なう処理である。 この探索表は2次元の表であり、後述の変形暗号化という処理を用いて作成される。 事前処理では、この探索表を多数作成し、この探索表の一部を１次元の表として格納する。
解読は、事前処理において作成した探索ベクトルを使用し、入手した暗号文を作成した鍵を探索する処理である。 この探索は各探索ベクトルと暗号文のペアを用いて行なわれ、表を用いた検索と検証という２つの作業からなる。
研究の結果、事前処理で、２＾５７回の変形暗号化と５１２ギガバイトの表の格納を行なえば、鍵の探索に成功する確率は下限値で８０%程度となることが判った。 この装置をハードウェア実装した場合は、１月程度の事前処理と１時間程度の解読作業で、ＤＥＳの解読に８０％の確率で成功する。