SHA1 충돌 확률

SHA1 충돌 확률

---

길이가 같은 100 개의 서로 다른 문자열 세트가 주어지면 문자열에 대한 SHA1 다이제스트 충돌이 발생할 가능성을 어떻게 정량화 할 수 있습니까?

---

SHA-1에 의해 생성 된 160 비트 해시 값이 모든 블록의 지문이 고유한지 확인하기에 충분히 큰가요? 균등 분포, n 개의 서로 다른 데이터 블록의 모음 및 b 비트를 생성하는 해시 함수를 갖는 임의 해시 값을 가정하면, 하나 이상의 충돌이 발생할 확률 p는 블록 쌍 수에 다음 확률을 곱한 값으로 제한됩니다. 주어진 쌍이 충돌합니다.

(출처 : http://bitcache.org/faq/hash-collision-probabilities )

---

음, 충돌 확률은 다음과 같습니다.

1 - ((2^160 - 1) / 2^160) * ((2^160 - 2) / 2^160) * ... * ((2^160 - 99) / 2^160)

10 개의 공간에서 2 개의 항목이 충돌 할 확률을 생각해보십시오. 첫 번째 항목은 100 % 확률로 고유합니다. 두 번째는 9/10 확률로 고유합니다. 따라서 둘 다 고유 100% * 90%할 확률은이고 충돌 확률은 다음과 같습니다.

1 - (100% * 90%), or 1 - ((10 - 0) / 10) * ((10 - 1) / 10), or 1 - ((10 - 1) / 10)

가능성은 거의 없습니다. 원격 가능성이 되려면 더 많은 문자열이 있어야합니다.

위키 백과의이 페이지에 있는 표를보십시오 . 128 비트와 256 비트의 행 사이를 보간하면됩니다.

---

이것이 바로 생일 문제입니다 .이 기사는 확률을 매우 쉽게 추정 할 수있는 근사치를 제공합니다. 실제 확률은 매우 매우 낮습니다 . 예를 들어이 질문 을 참조하십시오 .

참고 URL : https://stackoverflow.com/questions/1867191/probability-of-sha1-collisions