1,2,3~nとインクリメントされていく数値文字列をMD5でハッシュ化していった際に、

最初にコリジョンが発生するnは何でしょうか?

また同様にSHA1の場合についてもご存知であればお教えください。

回答の条件
  • 1人2回まで
  • 登録:
  • 終了:2008/03/21 11:00:02
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。

回答3件)

id:felix33jp No.1

回答回数484ベストアンサー獲得回数3

id:FnuLnu

関係ないです。

2008/03/17 13:17:07
id:KUROX No.2

回答回数3542ベストアンサー獲得回数140

id:FnuLnu

違います。

具体的なnを求めています。

そして、それには泥臭い作業が必要なので、

既にそれをした事のある人はいないか、

或いはしようとする人がいないか、

という質問です。

2008/03/19 01:28:00
id:iww No.3

回答回数101ベストアンサー獲得回数10

ポイント26pt

bashでスクリプト書いてみたです。

#!/bin/sh

HOGE=/tmp/hoge.txt

n=1
:>$HOGE

while [ $n -ne 0 ]; do
    set `echo $n | md5sum`
    grep $1 $HOGE
    if [ $? -eq 0 ]; then
        echo $n
        exit
    fi
    echo $1:$n >> $HOGE
    n=$(($n+1))
done

これはhoge.txtにどんどんhash値を追記しながらn=1から順に

既知のhashが見つかるまでループして検査します。

でもbashだと0xffffffffの次は0になるのでそこで打ち切りです。

もっと調べたいときは、足し算のところでbc使うようにするか

もっと大きい数字の扱える言語で試すといいと思います。

id:FnuLnu

ありがとうございます。

bashではなくMySQL+何かを使う予定ですが、

土日にでも私も走らせて見ます。

2008/03/21 10:57:08
  • id:pahoo
    ご参考まで。
    MD5 Collision Generator
    http://www.stachliu.com/files/md5coll.c
  • id:FnuLnu
    >>md5coll.c
    たぶん私が意図している用途では使えないと思います。

    自前でレインボーテーブルを生成して検証するのも有りなんですが、
    最悪のケース(2^128+1)を考えると気が重たいので。
  • id:tsukasa57
    やってみたんだけど、すぐには見つからないと思う。
    md5 を大量に生成するのはそれほど難しくないけど、md5 が重複しているかどうかを調べるのが遅いのでかなり大変。
  • id:tsukasa57
    とりあえず 100000 までの中には無かった。しかし、どうやれば高速化できるかわからなかったので処理時間が 20 分もかかった。ぶんまわすのではめんどくさすぎるかもしれません。
  • id:tsukasa57
    iww さんの方法では、たぶん、遅すぎて、求めるまで時間がすごいかかります。数日レベルかそれ以上で...。この質問は簡単そうに見えるけれども実は難しいことが分かりました。
  • id:FnuLnu
    レインボーテーブルを生成するためのライブラリも、
    どこかしらに転がっているでしょうから、
    それを流用するのが一番手っ取り早いかもしれません。

    私はストレージにMySQLを使い、
    重複チェックはユニーク制約にやってもらう予定です。
    MySQLのパフォーマンスチューニングに関して得るものもありそうなので。
  • id:tatsumi-da
    rubyでわたしもやってみました。

    2^23-1までは衝突しませんでした。
    それ以上ではメモリエラーでできませんでしたが。
    ソース
    >|ruby|
    require 'digest/md5'
    ary = Array.new
    for n in 0..32
    for i in (2**n)..(2**(n+1)-1)
    ary[i-1]=Digest::MD5.hexdigest(i.to_s)
    end
    puts n.to_s + ":" + (2**(n+1)-1).to_s + ":" + ary.uniq.size.to_s
    end
    ||<

この質問への反応(ブックマークコメント)

トラックバック

  • FnuLnuの日記 2008-03-15 18:45:16
    回答受付中。 http://q.hatena.ne.jp/1205459729 なんでこんな質問をしたのかというと、 ある案件のある申込番号で、 元々はあるテーブルのサロゲートキーをそのまま使っていたんですが、 ユーザ
  • 数値文字列に対するMD5のコリジョン 回答受付中。 http://q.hatena.ne.jp/1205459729 なんでこんな質問をしたのかというと、 ある案件のある申込番号で、 元々はあるテーブルのサロゲートキーをそ
「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

回答リクエストを送信したユーザーはいません