DES暗号の仕組み(Feistel構造とラウンド関数fについて)


昔々、あるところにNBSというアメリカのお偉い機関で採用された暗号技術がありました…。

というわけでDESという前のアメリカ標準の暗号技術の紹介です。

DESについて

1977年にNBSで作られた56bit鍵を使用したブロック鍵暗号です。ブロック長は64bitで、56bitの鍵から48bitのサブ鍵を16個作成し、16回のラウンド処理を行います。

構造はFeistel構造。仕組みもかなりシンプルなもので、割と高速に動作します。ただシンプルである分、高速に解析を行うことができてしまい、今では弱い暗号として使われていません。

この暗号の利点

DESはFeistel構造を使用しているため、暗号も復号も同一のコードで行うことができます。また、ラウンド関数fも不可逆なもので問題ないため、非常にシンプル。なおかつそこまで複雑に考えて作らなくても割と簡単にできちゃう。

欠点

非常にシンプルな構造だったために、ブルートフォース攻撃で1日もかからず復号されてしまいます。今のコンピュータなら家庭用パソコンでも解けてしまうんじゃないでしょうか。

Feistel構造

この構造の特徴は、暗号も復号も同一コードでできるというわけです。

暗号時は平文と鍵を、復号時は暗号文と鍵をつっこめば、それぞれ暗号文・平文が出てきます。

img_0185

流れとしては、入力されたものを[左]と[右]に分けます。あとは[右]と[サブ鍵]をラウンド関数に入れて、その[出力]と[左]をXORします。その後、暗号化された左と右を入れ替えて終了です。

結論として、[左]と[右]が [右]と[暗号化された左]になって出てきます。これを16回繰り返すことにより、全体で8回暗号化されたことになります。

ラウンド関数fの構造

img_0186

 

こちらも非常にシンプル。入力を拡大置換→XOR→縮小換字→終了。って感じです。

ここでの特徴…ってわけでもないですが、頻度分析を防ぐ方法として置換えや換字をする時は複数単位で行うといいらしいです。ここでは32bitを48bitに拡大して置換えしています。また、縮小化する時は6bitを4bitにしています。こうすることで頻度の偏りを抑えることができるのです。

攻撃手段

暗号技術での一般的な攻撃の耐性は以下の通りです。

  • ブルートフォース攻撃←弱い
  • 頻度分析←安全
  • ショートカット法←有用な手段あり

といった感じです。つまり、現代では弱い暗号技術と言えちゃいますね。

ブルートフォース攻撃については15年前の時点で1日かかっていなかったと思います。現代なら家庭用コンピュータでもすぐに解析できちゃうのではないでしょうか。

単純に鍵長が56bitなので、2の56乗のパターンで解析することができます。

ショートカット法は2つ編み出されています。

差分解析法 特定の条件に当てはまる時のみ2の47乗で解析できる選択平文攻撃
線形解決法 条件なしで2の47乗で解析できる任意平文攻撃

詳しい話は割愛しますが、仕組み的には暗号化を無効化させてしまうことが可能だったという感じらしいです。

DES関連の他の暗号技術

DESをちょっと改造したものにDES-2とDES-3があります。

これは非常に単純な考えで、鍵を2つ使ったもの、鍵を3つ使ったもので、単純に鍵長が2倍3倍になります。

また、コードもDES-3用に作り、

  • DES-2の時は鍵1→鍵2→鍵1の順で暗号化。
  • DES-3の時は鍵1→鍵2→鍵3の順で暗号化。
  • 普通のDESの時は鍵1→鍵1→鍵1順で暗号化。

とさせればいいだけです。つまり互換性があるというわけですね。

ただこれには問題があり、単純に処理時間が2倍3倍になります。また、鍵長が長くなることになり管理しづらくなります。(といっても短い方ですが)

結局は過去の暗号技術

もう解析にかかる時間がすごい短くなっている時点でダメな暗号技術なんですけどね。現在の米国ではこのDESにかわってAESというものに取って代わられています。

 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">