Merkle-Damgård construction
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/01/03 00:38 UTC 版)
「暗号学的ハッシュ関数」の記事における「Merkle-Damgård construction」の解説
暗号学的ハッシュ関数は、任意長のメッセージを固定長の出力に変換しなければならない。したがって、入力を一連の固定長のブロックに分割し、それらに順次一方向性圧縮関数を作用させる。この圧縮関数はハッシュのために特に設計したものでもよいし、ブロック暗号を使って構築したものでもよい。Merkle-Damgård construction で構築されたハッシュ関数は、その圧縮関数と同程度の衝突困難性がある。ハッシュ関数全体で発生する衝突は、圧縮関数での衝突に起因する。最後のブロックには明らかにパディングが必要で、この部分はセキュリティ上重要である。 このような構築法を Merkle-Damgård construction と呼ぶ。SHA-1やMD5などのよく使われているハッシュ関数は、この形式である。 この構築法の本質的欠点として、length-extension 攻撃や generate-and-paste 攻撃に弱く、並列処理できないという点が挙げられる。より新しいハッシュ関数であるSHA-3は全く異なる構築法を採用している。
※この「Merkle-Damgård construction」の解説は、「暗号学的ハッシュ関数」の解説の一部です。
「Merkle-Damgård construction」を含む「暗号学的ハッシュ関数」の記事については、「暗号学的ハッシュ関数」の概要を参照ください。
- Merkle-Damgård constructionのページへのリンク