「数字6桁パスワードのMD5ハッシュ値の総当たり」Scalaは1.70秒だった

パスワード問合せシステムを作る (clojureのreducers) に端を発してにわかに盛り上がっている 数字6桁パスワードのMD5ハッシュ値の総当たり ですが、PHPやPerlでは1秒を切る実装が紹介されているようです。（他の言語もあるかもしれません）
数字6桁パスワードのハッシュ値の総当たり、PHPなら約0.25秒で終わるよ
数字6桁パスワードのハッシュ値の総当たり、Perlでも約0.25秒で終わるよ

kawasima氏は追加の記事（String.formatが遅い理由）で「String.formatが遅い原因」と書かれてますが、JVM上の言語で実際にどの程度なものなのか試してみました。。。Scalaで！

環境

Winodws7 Pro SP1 64bit/Corei7-3770K/JDK 1.7.0_25/Scala 2.10.3

フォーマッタ利用、並列化無し

まずはClojureと同様の処理をScalaで書いてみます。

FindPassword_Single.scala

import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Single_WithFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map("%02x".format(_)).mkString
    }
    (0 to 1000000)
      .find(i => hexdigest("%s$%06d".format(salt, i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}

11.88秒でした。遅いですね。

フォーマッタ利用、並列化有り

Scalaの場合、parメソッドを呼び出すだけでCollectionを容易に並列Collection化できます。

MD5FindPassword_Parallel_WithFormatter.scala

import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Parallel_WithFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map("%02x".format(_)).mkString
    }
    (0 to 1000000)
      .par // 変更点はココだけ
      .find(i => hexdigest("%s$%06d".format(salt, i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}

4.52秒になりました。8コアありますが、さすがに単純に1/8にはなりませんね。

フォーマッタ無し、並列化無し

では、フォーマッタを使わないとどうなるか。

MD5FindPassword_Single_NoFormatter.scala

import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Single_NoFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexformatter(x:Int):String = {
      val h = Integer.toHexString(x)
      "0"*(2 - h.length) + h.toString
    }
    def mkOrigin(x:Int):String = {
      val xs = x.toString
      salt + "$" + "0"*(6 - xs.length) + xs
    }
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map(hexformatter(_)).mkString
    }
    (0 to 1000000)
      .find(i => hexdigest(mkOrigin(i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}

3.10秒でした。Formatterを使った場合に比べて1/4になっています。確かにFormatterはかなり遅いですね。

フォーマッタ無し、並列化有り

最後に、フォーマッタ無しで並列化有りの場合

MD5FindPassword_Parallel_NoFormatter.scala

import java.security.{MessageDigest => MD}
 
object MD5FindPassword_Parallel_NoFormatter {
  def findPassword(salt:String, pw:String):Option[Int]  = {
    def hexformatter(x:Int):String = {
      val h = Integer.toHexString(x)
      "0"*(2 - h.length) + h.toString
    }
    def mkOrigin(x:Int):String = {
      val xs = x.toString
      salt + "$" + "0"*(6 - xs.length) + xs
    }
    def hexdigest(s:String):String = {
      val digester = MD.getInstance("MD5")
      digester.update(s.getBytes)
      digester.digest.toList.map(_&0xff).map(hexformatter(_)).mkString
    }
    (0 to 1000000)
      .par // 変更点はココだけ
      .find(i => hexdigest(mkOrigin(i)) == pw)
 
  }
  def main(args: Array[String]) {
    findPassword(args(0), args(1)) match {
      case Some(f) => printf("match [%06d]%n", f)
      case None    => printf("not match%n")
    }
  }
}

1.70秒まで縮みました

まとめ

パターン	秒
フォーマッタ利用＋並列化無し	11.88
フォーマッタ利用＋並列化有り	4.52
フォーマッタ無し＋並列化無し	3.10
フォーマッタ無し＋並列化有り	1.70

JVM上の言語でも、2秒は切れるようですが、1秒を切ることはできませんでした。
なんだかとても悔しいので、次はCで書いてみます。