スマートフォン用の表示で見る

ハッシュ関数

サイエンス

ハッシュ関数

はっしゅかんすう

原文から固定長の文字列を生成する関数。「要約関数」とも呼ばれる。

生成した値は、「ハッシュ値」「メッセージダイジェスト」という。

一般に一様性と衝突耐性(強衝突耐性と弱衝突耐性)が求められる。

(参照→ハッシュ, 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に対して)

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