md5 hash collision

어떤 해쉬 알고리즘이라도 비둘기 집의원리에 의해 해쉬 테이블에서 가능한 모든 키의 숫자는 테이블 인덱스의 개수보다 많으므로 충돌은 불가피하다합니다.

아래 예제 소스를 통해 알아보죠.

'''
Created on 2012. 9. 7.

@author: Administrator
'''
import base64
import md5
str1 = base64.b64decode("pmTquIkEwqxIQ0EOCmNCVBZgbIFELdaNQARYPrj7f4lVrTQGCfSzAoPkiIMlcUFaCFEl6PfNyZ/ZHb3ygDc8W5eevbQOKm4XpiNXJNHfQbRGc/mW8WJK3RApMWfQCbGPdad/eTDZXOsC6K26eshVXO10yt1fyZNtsZtK2DXMZ+M=")
str2 = base64.b64decode("pmTquIkEwqxIQ0EOCmNCVBZgbAFELdaNQARYPrj7f4lVrTQGCfSzAoPkiIMl8UFaCFEl6PfNyZ/ZHb1ygDc8W5eevbQOKm4XpiNXJNHfQbRGc/kW8WJK3RApMWfQCbGPdad/eTDZXOsC6K26ekhVXO10yt1fyZNtsZtKWDXMZ+M=")
print md5.new(string1).hexdigest()
print md5.new(string2).hexdigest()
print str1 == str2

출력결과

2ba3be5aa541006b62370111282d19f5
2ba3be5aa541006b62370111282d19f5
False

위 md5encode 결과는 위와 같이 같지만 두 문자열은 결코 같지않습니다. 여기서 해쉬충돌이 일어나네요

-참고 URL-

http://www.phpschool.com/gnuboard4/bbs/board.php?bo_table=tipntech&wr_id=39021

http://tit99hds.egloos.com/2489324

http://ko.wikipedia.org/wiki/%EB%B9%84%EB%91%98%EA%B8%B0%EC%A7%91_%EC%9B%90%EB%A6%AC