SHA1 충돌 가능성

Question

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

Answer 1

SHA-1에 의해 생성 된 160 비트 해시 값은 모든 블록의 지문이 고유 할 수있을 정도로 충분히 큰가요? 균일 분포가있는 임의의 해시 값, n 서로 다른 데이터 블록의 모음 및 b 비트를 생성하는 해시 함수를 가정하면, 하나 이상의 충돌이있을 확률 P는 블록 쌍의 수에 의해 구속됩니다. 주어진 쌍이 충돌합니다.

(원천 : http://bitcache.org/faq/hash-collision-probabilities)

Answer 2

충돌 가능성은 다음과 같습니다.

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)

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

테이블을 살펴보십시오 Wikipedia 의이 페이지; 128 비트와 256 비트로 행 사이를 보간하십시오.

Answer 3

그게 생일 문제 -이 기사는 확률을 쉽게 추정 할 수있는 좋은 근사치를 제공합니다. 실제 확률은 매우 매우 낮습니다. 이 질문 예를 들어.