ハッシュ関数

ハッシュ関数

形式化数学研究室

宮島啓一

ハッシュ関数とは？

「長いメッセージを短くする関数」

のことである。一般に、

と表す。ここで、 はメッセージで ある。

例えば、ハッシュ関数が

「 10 ビットのメッセージを 3 ビットに短縮す る」 とする。

「 1101111011 」

ハッシュ関 数

「 111 」 この部分がもっと長い！

逆向きに「元に戻 す」ことは考えな くてよい

メッセージ

ハッシュ値

ハッシュの特徴

今回の特集は、

暗号化技術がテ ーマです。

ハッシュ関数

acbd18db4cc2f85cedef654fccc4a4d8

①

ハッシュ値から 元のメッセージ を推測できない

元のメッセージの長さに関 わらず、ハッシュ値の長さ は一定

今回の特集は、

暗号化技術がテ ーマですよ。

ハッシュ関数

d3b07f84d11fedec49eaf6238ad5ff00

②

同じハッシュ値になるメッセー ジを導くのが困難

ソフトウェ ア

ソフトウェア

ハッシュ関 数

ハッシュ値 ミラーサイト

ソフトウェ ア

ハッシュ値 オリジナルサイト

比較 ユーザ

ハッシュ関 数

ソフトウェアの改ざん検 出！

・ミーラーサイトで入手したソ フトウェアから得られたハッシ ュ値と、オリジナルサイトで公 開しているハッシュ値を比較

・通信負荷の分散のため、ミ ラーサイトからソフトウェア を入手（ソフトウェアを配布するサ ーバは負荷軽減のため複数の サイトの助けを借りることが よくある。）

～ハッシュ値の利用例～

（ソフトウェアの改ざん検出の場

合）

～ハッシュ値の衝突による問題点～

（デジタル署名の場合）

契約書 A

（原本）

同じハッシュ値を出 力

契約書 B

（偽造）

契約書 A

（原本）

悪用！

署名

署名 圧縮版

圧縮版

署名部分のみを偽造 文書へ貼り付け！

ハッシュ関数によって圧 縮

契約書 B

（偽造）

破棄！

ハッシュ関数によって圧 縮

～ハッシュ関数の脆弱性～

・バースデーパラドックスの理論によると

、ハッシュ関数 SHA-1 の場合、約回の計算 を行えば、同じハッシュ値を発生するメッ セージの組みを少なくとも一つ作り出せる

。

•  

～ハッシュ関数の脆弱性～

・

SHA-1 に対する攻撃法が 2005 年に発表される。

2 ⁸⁰

2 ⁶⁹

危険性が 2048 倍増加！！

現在に至るまで多くの企業や公的機関が SHA- 1 を利用した証明書等を受け入れないように する事を表明

•  

・米国国立標準技術研究所（ NIST ）は合衆 国政府組織に対し、 2010 年までに SHA-2 に 移行するように要請。

・ SHA-2 は構造が SHA-1 に似ているが、そ の有効な攻撃法は未だ報告されていない。

SHA-1 SHA-2

移行！

～ハッシュ関数の脆弱

性～

ご清聴ありがとうございました

参考文献

・現代暗号の基礎数理

・現代暗号への招待

・暗号技術入門

・数理的技法による情報セキュリティー