ハッシュ関数

ハッシュ関数

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

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

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

ネットの話題: ハッシュ関数

人気

新着