« 2007年06月03日 | メイン | 2007年06月05日 »
2007年06月04日
PDFと署名(37) — ハッシュ・アルゴリズムの進化
前回、ハッシュ・アルゴリズムについて、少し取り上げました、ここで、ハッシュ・アルゴリズムの種類と脆弱性について調べてみます。
以前に、公開鍵暗号方式の説明をしたときは、詳しい仕組みやアルゴリズムまで踏み込むのはあまり関係ないのかな、と考えて、ハッシュ・アルゴリズムについては説明を省略してしまいました。
2007年04月05日PDFと署名(4) — 公開鍵暗号方式を署名に使う
ハッシュ・アルゴリズム（ハッシュ関数）については、こちらをご覧ください。
ハッシュ関数
文書をハッシュ・アルゴリズムに入力し、出力されたデータをハッシュ値と言います。または、ダイジェスト値と呼ぶこともありますし、電子政府のWebページでは、フィンガー・プリントと呼んでいます。
電子署名では文書を丸ごと秘密鍵で暗号化するのではなく、文書のハッシュ値を計算し、そのハッシュ値を秘密鍵で暗号化します。そして、(1)オリジナル文書、(2)ハッシュ値を暗号化したデータ、そして(3)公開鍵を相手に渡します。受け取った相手は、暗号化されたデータの暗号を解いて求めた（オリジナル文書の）ハッシュ値と、受け取った文書から改めて計算したハッシュ値を比較して、その両者が一致すれば、受けとった文書が改竄されていないこと、そして、公開鍵とペアになる秘密鍵の所有者が暗号化したことを認めることになります。
4月5日の図を、上の説明に合わせて書き直しますと、次のようになります。
ハッシュ・アルゴリズムの真髄は、(1)ハッシュ値はオリジナルに比べて非常に小さいこと、(2)入力されたデータが少しでも違っていればハッシュ値が異なること、(3)異なるオリジナルデータからは同じハッシュ値にならない（衝突が起きない）ということになります。
但し、この(1)～(3)を全部達成するのは不可能なことは明らかです。仮に元の文書が、1万文字（2バイト／文字）とすると2万バイトになります。2万バイトの情報の改竄パターンは、意味のある情報になるかどうかを別にすると、最大で2の8万乗-1だけあります。ハッシュ値を128バイトとしますと、ハッシュ値で表現できるパターンは2の(128×8）乗です。ですので1ハッシュ値あたり大体2の78乗回の衝突が起きるはずです。しかし、衝突が起きる確率は極めて小さい（2の78乗÷2の8万乗）のです。
このようにハッシュ・アルゴリズムで計算したハッシュ値は衝突が不可避なわけです。しかし、ハッシュ値が同じになる（衝突が起きる）ような改竄方法を短時間で計算できてしまうと問題になります。
これに関連して、最近は、暗号の専門家の会議で、ハッシュ・アルゴリズムの脆弱性がいろいろと報告されています。
MD5を含む各種ハッシュアルゴリズムに欠陥か
暗号アルゴリズムに重大な欠陥発見の報告相次ぐ
SSLやPGPで使われているSHA-1アルゴリズムにセキュリティ欠陥――専門家が指摘
これに対しては、「 CRYPTREC暗号技術監視委員会事務局 」から、次のような公告も出ています。
ハッシュ関数SHA-1及びRIPEMD-160の安全性について
現在のところ、電子署名ではSHA-1を使っていることが多いのでSHA-256 以上に移行するのは難しいのですが、タイムスタンプのような新しい技術では、新しい技術を採用するのが比較的簡単、ということで日本の商用タイムスタンプ局は、ハッシュ・アルゴリスムとしてSHA-512を採用しているようです。
投票をお願いいたします