暗号アルゴリズムMISTY

MISTYの安全性

ブロック暗号アルゴリズムに対しては、3つの強力な暗号解読法があり、
MISTYはそれらに対して充分な安全性を保持しています。

暗号化鍵の全数探索法

100万ドルのDES解読装置が提案(Wiener 1993)

差分解読法(Biham, Shamir 1990 [4])

DESに対する暗号化鍵の全数探索法より高速な最初の解読法

線形解読法(Matsui 1993 [5])

DESの解読に初めて成功した計算機実験 [6]

Against exhaustive key search

MISTYの暗号化鍵の長さは128 ビットで、これは暗号化鍵の全数探索法に対して充分な安全性を保持する長さです。

表 1. 1年以内に暗号アルゴリズムを解読するために必要な計算機性能[3]
暗号化鍵の長さ 1995年 2000年 2005年
56ビット $64000 $16000 $2000
64ビット $16M $4.1M $510000
128ビット $3.0 x1026 $7.5 x1025 $9.4 x1024

Against differential cryptanalysis

差分解読法はDES型の暗号に適用される選択平文攻撃で、1990年BihamとShamirにより提案されました[4]。この解読法は、暗号化鍵の全数探索法より高速な初めての解読法です。

MISTYは、差分解読法に対して証明可能な安全性を保持しています。

表2は、2つの指標「差分特性確率」と「平均差分確率」を利用してDESとMISTYの差分解読法に対する強度を示しています[7]。

表 2. 差分解読法に対する暗号強度
アルゴリズム 差分特性確率 平均差分確率
DES 2-62 [8] 未知
MISTY 2-140 以下[1] 2-56 以下[1]

差分特性確率は、差分解読法に対する暗号強度を概略で表しています。差分解読法に対して、強い暗号は小さい差分特性確率をもつ必要があります。表2は、MISTYの差分特性確率がDESよりずっと小さいことを示しています。

平均差分確率は、差分解読法に対する暗号強度を厳密に表しています。強い暗号は小さい平均差分確率をもつ必要があります。表2は、MISTYの平均差分確率が充分小さいのに対して、DESの平均差分確率は未知であることを示しています。

平均差分確率は概略で差分特性確率の集合ですので、最大の差分特性確率が低い場合でも、差分解読法に対して、強いとは言えません。MISTYは、最大平均差分確率が充分小さい(この性質は証明可能安全性と呼ばれます[7])、最初の現実的な暗号です。


Against linear cryptanalysis

線形解読法は、DES型の暗号に適用される既知平文攻撃で、1993年当社の松井により提案されました[5]。線形解読法は最も強力な解読で、私共は計算機によるDESの解読実験に初めて成功しました[6]。

MISTYは、線形解読法に対する証明可能な安全性を保持しています。

表3は、 2つの指標「線形特性確率」と「平均線形確率」を利用してDESとMISTYの線形解読法に対する強度を示しています[9] 。

表 3. 線形解読法に対する暗号強度
アルゴリズム 線形特性確率 平均線形確率
DES 1.5x2-24 [8] 未知
MISTY 1.0x2-71 以下[1] 1.0x2-28 以下[1]

線形特性確率は、線形解読法に対する暗号強度を概略で表しています。線形解読法に対して強い暗号は小さい線形特性確率をもつ必要があります。表3は、MISTYの線形特性確率がDESよりずっと小さいことを示しています。

平均線形確率は、線形解読法に対する暗号強度を厳密に表しています。線形解読法に対して強い暗号は、小さい平均線形確率をもつ必要があります。表3は、MISTYの平均線形確率が充分小さいのに対して、DESの平均線形確率が知られていないことを示しています。

平均線形確率は概略で線形特性確率の集合ですので、最大の線形特性確率が低い場合でも、線形解読法に対して、強いとは言えません。MISTYは、最大平均線形確率が充分小さい(この性質は証明可能安全性と呼ばれます[9])、最初の現実的な暗号です。

参考文献

このページを共有

研究開発・技術
カテゴリ内情報