Java: ハッシュ関数

Takami Torao Java 11 #CRC #SHA
  • このエントリーをはてなブックマークに追加

概要

ハッシュ関数 (hash function)、または Java ではメッセージダイジェスト (message digest) と呼ばれる機能は、ある任意の大きさのバイナリデータから固定長のバイナリを生成するためのアルゴリズムである。データ破損を検出するチェックサム (checksum) と似ているが、以下のような特徴を持つ。

  • 同一のバイナリからは同一のハッシュ値を算出するが、1bit でも異なれば全く違うハッシュ値となる。
  • バイナリの大きさにかかわらず、算出されるハッシュ値は小さな固定長 (一般的に数十バイト) である。
  • ハッシュ値から元のバイナリを推測・復元することが極めて困難である。

以下は SHA-256 を使用して "hello, world" のバイナリ表現をハッシュ化する Scala の実装例である。

import java.security.MessageDigest

// binary to retrieve hash
val binary = "hello, world".getBytes()

val md = MessageDigest.getInstance("SHA-256")
md.update(binary)
val hash = md.digest()

hash.map(x => f"$x%02X").mkString  // 09CA7E4EAA6E8AE9C7D261167129184883644D07DFBA7CBFBC4C8A2E08360D5B

また、ファイルのような大きなデータのハッシュを算出するには、その先頭から読み込んだ部分的なデータで update() で更新してゆけば良い。

def digest(in:InputStream, md:MessageDigest, buffer:Array[Byte] = new Array(1024)):Array[Byte] = {
  val len = in.read(buffer)
  if(len < 0) md.digest() else {
    md.update(buffer, 0, len)
    digest(in, md)
  }
}

結果として算出されるハッシュ値は、元のデータがどれだけ大きくても SHA-256 アルゴリズムによって 32 バイトに固定されている。またハッシュ値 09CA7E4... から元の "hello, world" を復元することは極めて困難である。

Java 11 でサポートされているアルゴリズム名とハッシュ値のサイズ、おおよその実行コストは以下の通りである。CRC32 はチェックサムのためのアルゴリズムだが比較のために同様の処理を行った。

512.0kB のデータに対するハッシュ関数 300 回実行時の平均算出時間
アルゴリズム 算出時間 [msec] ハッシュサイズ [B]
CRC32 0.17 4
MD2 161.23 16
MD5 3.59 16
SHA 5.43 20
SHA-224 5.08 28
SHA-256 5.05 32
SHA-384 3.21 48
SHA-512 3.49 64
SHA-512/224 3.15 28
SHA-512/256 2.82 32
SHA3-224 9.66 28
SHA3-256 11.77 32
SHA3-384 12.02 48
SHA3-512 18.00 64
java version "11.0.2"
OpenJDK Runtime Environment (build 11.0.2+9)
OpenJDK 64-Bit Server VM (build 11.0.2+9, mixed mode)

SHA は一般に SHA1、SHA-224SHA-512 は SHA2 と呼ばれるアルゴリズムである。MD2, MD5, SHA1 は既に強衝突するケースが見つかっておりセキュリティが求められる設計では使用してはならない。ただし、繰り返しハッシュ関数を適用するストレッチングハッシュチェイン (hash chain) といった手法においてはその限りではない。

64bit 演算を使用する SHA-512 は、64bit 環境下では一般的に 32bit 演算を使用する SHA-256 よりも高速である2。SHA-512/224, SHA-512/256 はそれぞれ SHA-512 の結果を 224bit, 256bit に切り詰めたものである。

参照