Hatena Blog Tags

ハッシュ関数

(サイエンス)
はっしゅかんすう

原文から固定長の文字列を生成する関数。「要約関数」とも呼ばれる。
生成した値は、「ハッシュ値」「メッセージダイジェスト」という。
一般に一様性と衝突耐性(強衝突耐性と弱衝突耐性)が求められる。
(参照→ハッシュ, SHA-1, MD5)

数学的な定義

[N]:=\{0,1,...,N-1\} (N \in \mathcal{N})とする。

  1. H:[N] \rightarrow [M]\,\,(N>M)
  2. H(x)が効率良く計算出来る(入力長\log Nに対して)
  3. x\in [N]が与えられた時にH(x) = H(y)なるy \not= xを発見することが難しい(弱衝突耐性)
  4. H(x) = H(y)を満たすx \not= yなる組(x,y)を発見することが難しい(強衝突耐性)
  5. H(x)を与えられた時にxを逆算することが難しい(入力長\log Mに対して)
  • 1,2を満たすものをハッシュ関数という。
  • 1,2,3を満たすものを弱衝突耐性ハッシュ関数という。
  • 1,2,4を満たすものを強衝突耐性ハッシュ関数という。
  • 1,2,5を満たすものを一方向性ハッシュ関数(非可逆ハッシュ関数)という。

*リスト:リスト::数学関連

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。

ネットで話題

もっと見る

関連ブログ