AとBの2つの異なるメッセージ（サイズが重要な場合は、おそらく20〜80文字のテキスト）が与えられた場合、AのMD5ダイジェストがBのMD5ダイジェストと同じであり、AのSHA1ダイジェストが同じである確率はどれくらいですか。 BのSHA1ダイジェストと同じですか？あれは：
(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))
悪意のない意図、つまり、衝突を見つける目的でメッセージが選択されていないことを前提としています。これが自然に起こる確率を知りたいだけです。
「天文学的に低い」可能性は低いと思いますが、どうやって確認すればいいのかわかりません。
詳細：可能なメッセージのプールのサイズは制限されていますが、大きいです（数億）。誕生日のパラドックスの状況はまさに私が心配していることです。
ランダムな文字列に対してMD5およびSHA-1ハッシュの範囲で均一に広がると仮定し（そうではありません）、文字列のプールについてではなく2つの文字列についてのみ話していると仮定します（したがって、誕生日のパラドックスを回避します） -タイプの複雑さ）：
MD5ハッシュは128ビット幅で、SHA-1は160です。上記の仮定では、2つの文字列AとBは、両方のハッシュが衝突した場合にPと衝突する可能性があります。それで
P(both collide) = P(MD5 collides) * P(SHA-1 collides)
と
P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)
それで
P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87
繰り返しますが、文字列のプールがあり、プールとの衝突の確率を決定しようとしている場合、あなたは誕生日のパラドックスの領域にあり、ここで計算したこの確率は適用されません。それとハッシュは、本来あるべきほど均一ではありません。実際には、衝突率ははるかに高くなりますが、それでも小さいでしょう。
編集
誕生日のパラドックスの状況を扱っているので、誕生日のパラドックスの解決策と同じロジックを適用します。1つのハッシュ関数の観点から見てみましょう。
N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)
2 ^ 29（約5億3000万）のような偶数のハッシュがあるとしましょう。
P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)
要するに、私はこの数を計算することさえ考えたくありません。どうやって見積もってもいいのかわからない。少なくとも、死ぬことなく巨大な階乗を処理できる任意精度の計算機が必要です。
確率は、の場合はほぼ0から始まり、の場合N = 1 or 2は1に達する曲線に従うことに注意してください。これN >= 2^288は、誕生日のパラドックスのWikipediaページにあるものと同様の形状です。
誕生日のパラドックスはP = .5いつになりますかN = 23。つまり、NがSの6％の場合、衝突の確率は50％です。それがスケーリングする場合（そうなるかどうかはわかりません）、次の場合に衝突の確率は50％になることを意味します。 2 ^ 288ハッシュの6％。2 ^ 288の6％は約2^284です。N（数億）の値はそれに近いものではありません。あなたのSと比べるとほとんど意味がないので、心配することはないと思います。衝突の可能性はほとんどありません。
ウェルボグの投稿への補遺：
スターリングの近似を使用することにより、任意精度の算術を使用せずに、大きな階乗の比率を計算できます。
n！≈sqrt（2πn）*（n / e）n
したがって、（S！）/（S ^ N *（S-N）！）≈sqrt（2πS）/ sqrt（2π（SN））*（S / e）S /（（SN）/ e）SN / S N
= sqrt（S /（SN））*（S /（SN））SN * e -N
= sqrt（1 +α）*（1 +α）SN * e -Nここで、α= N /（SN）は小さいです。
近似（1 + a / n）nx≈exは、n→∞として成り立ちます（または少なくとも非常に大きくなります）
**つまり、これは（1+（N /（SN）））SN≈eN for SN>>Nを意味します。
だから私はそれを期待します
（S！）/（S ^ N *（S --N）！）≈sqrt（1 + N /（SN））* e N * e -N = sqrt（1 + N /（SN））for SN >> N...。
これが1より大きいことを除いて...したがって、近似の1つは十分ではありません。：p
（**警告：N / Sは小さくする必要があります：N = 22、S = 365の場合、これは2倍ずれています）
メッセージサイズが制限されていない場合、可能なメッセージの数は無限であり、ハッシュの可能性も限られているため、確率は100％漸近的に近づきます。
（注：質問に編集すると、これは関連性が低くなります）
一般に、N個の要素をランダムに選択すると、衝突の確率よりも予想される衝突の数を計算する方が簡単です。予想される衝突の数は衝突の確率よりも小さくすることはできないため、適切な上限として頻繁に使用できます。
pは、ランダムに選択された2つの要素が衝突する確率であると想定し ます。N個のランダムな要素を選択すると、N *（N-1）/ 2の要素のペアが存在するため、予想される衝突の数は次のようになります。
p * N *（N-1）/2。
たとえば、MD5とSHA1の両方の衝突の確率がp = 2-288であると仮定すると、 2 100個の要素をランダムに選択した後でも、約2-89回の衝突しか期待できません。
別の例：2つの30のランダム要素を選択し、MD5のみを計算する場合。2つのMD5ハッシュ間の衝突がp= 2-128であると仮定すると、これにより、衝突の数として予想される数は2-59になります。したがって、MD5ハッシュが2つの入力に対して衝突する確率でさえ、すでに非常に小さいです。
間違った確率を使用しているため、選択した答えは正しくありません。私は今日のかなりの部分をこれを調査することに費やしました（その答えへのコメントで私の思考プロセスを見ることができます）、そして実際の答えは次のとおりだと信じています（あなたが話しているものよりわずかに大きいメッセージの誕生日攻撃の場合） ：
2 ^ -61 * 2 ^ -18 = 2^79に1回の衝突。
そして、それは、これらの確率を乗算するだけでよい場合です（私はそれがわかりません）。
これは、今日のスーパーコンピューターで実行可能です（数か月未満で毎年減少します）。
これは、（誕生日のパラドックスを意味のあるものにするために）十分に大きなメッセージのプールに基づいていることに注意してください。これはあなたが心配しているとあなたが言ったシナリオでもあります。
ここで、別の状況は、特定のメッセージのハッシュのペア（SHA1とMD5）の衝突を見つけることです。これにより、bdayのパラドックス領域から抜け出し、桁違いに困難になります。それが2^（-61 * 2）* 2 ^（-18 * 2）なのか、それとも他の何かなのかわかりません。誰かがそれが何であるかを知っているならば、この答えにコメントを投稿してください（非常にありがたいです！）。
今あなたは尋ねます：
AとBの2つの異なるメッセージが与えられた場合（サイズが重要な場合は、おそらく20〜80文字のテキスト）
はい、サイズは重要です。2 ^ -18の図へのリンクをクリックすると、値が2つの入力ブロックのものであることがわかります。MD5では、入力ブロックは512バイトです。20〜80文字のテキストはそれには小さすぎ、単一ブロックの値は2^41です。
したがって、その量のデータに対して、2 ^ -61（私は思う）* 2 ^ -41 = 2^-102を取得します。
したがって、そのサイズの場合は安全と思われます（リンクには、SHA256の現在のビットコインハッシュレートの2倍の数値が含まれています：46626.93TH /秒）。