MD5와 같은 해시 함수는 어떻게 고유합니까?
MD5에 약간의 충돌이 있다는 것을 알고 있지만 이것은 해싱 함수에 대한 높은 수준의 질문에 가깝습니다.
MD5가 임의의 문자열을 32 자리 16 진수 값으로 해시하면 Pigeonhole 원리 에 따라 고유 한 32 자리 16 진수 값보다 고유 한 임의 문자열이 더 많기 때문에 고유 할 수 없습니다.
고유성을 보장 할 수는 없지만 32 자리 16 진수 값 (16 ^ 32)에는 약 3.402823669209387e + 38 개의 다른 값이 있습니다. 즉, 알고리즘 뒤에있는 수학이 좋은 분포를 제공한다고 가정하면 중복이있을 확률이 놀랍도록 적습니다. 사용 방법을 생각할 때 복제가 가능하다는 점을 명심해야합니다. MD5는 일반적으로 변경된 사항 (즉, 체크섬)을 확인하는 데 사용됩니다. 무언가를 수정하여 동일한 MD5 체크섬을 생성 할 가능성은 매우 희박합니다.
편집 : (최근 뉴스 제공 : SHA1 해시) 위의 답변은 여전히 유지하지만 MD5 해시가 조작에 대한 모든 종류의 보안 검사 역할을 할 것으로 기 대해서는 안됩니다. SHA-1 해시는 충돌 할 가능성이 2 ^ 32 배 (40 억 이상) 적으며 입력을 변환하여 동일한 값을 생성 할 수 있음이 입증되었습니다. (이것은 꽤 오래 전에 MD5에 대해 시연되었습니다). 아무도 악의적으로 동일한 해시 값을 생성하기 위해 무언가를 수정하지 않았는지 확인하려는 경우 요즘 SHA-2에서 확실한 보증을 받아야합니다.
반면에 보안 검사 컨텍스트가 아닌 경우 MD5는 여전히 유용합니다.
SHA-2 해시가 계산하기에 충분히 저렴하므로 어쨌든 사용해야한다고 주장 할 수 있습니다.
당신은 절대적으로 정확합니다. 그러나 해시는 "고유 한"것이 아니라 "충분히 고유 한 것"에 관한 것입니다.
다른 사람들이 지적했듯이 MD5와 같은 해시 함수의 목표는 두 개체가 원래 무엇인지 (암호) 모르거나 전체를 비교 (큰 파일)하지 않고도 두 개체가 동일한 지 쉽게 확인할 수있는 방법을 제공하는 것입니다.
객체 O와 해시 h O 가 있다고 가정합니다 . 다른 객체를 얻고 P그것이와 같은지 확인하려고합니다 O. 이 암호가 될 수도 있고, 당신이 다운로드 한 파일 (이 경우, 당신은하지 않습니다 O아니라 그것의 해시 시간 O 와 함께 제공된 P가능성이 높습니다). 먼저 Ph P 를 얻기 위해 해시 합니다 .
이제 두 가지 가능성이 있습니다.
- h O 와 h P 는 다릅니다. 이것은 그 뜻한다
O과P동일한 값을 산출해야 2 값 / 개체 동일한 해시를 사용하기 때문에, 상이하다. 해시는 결정적입니다. 거짓 음성이 없습니다. h O 와 h P 는 동일합니다. 언급했듯이 Pigeonhole Principle로 인해 이것은 다른 객체가 동일한 값으로 해시되었음을 의미 할 수 있으며 추가 조치를 취해야 할 수도 있습니다.
ㅏ. 가능성의 수가 너무 많기 때문에 해시 함수에 대한 믿음이 있다면 "글쎄요, 충돌 가능성이 1/2 128 (이상적인 경우) 였으므로
O= 이라고 가정 할 수 있습니다P. 예를 들어 문자의 길이와 복잡도를 제한하는 경우 암호입니다. 이것이 암호 자체가 아니라 데이터베이스에 저장된 암호의 해시를 보는 이유입니다. b. 해시가 동일하게 나왔다고해서 객체를 의미하지는 않는다고 결정할 수 있습니다. 동일, 그리고 직접 비교 할O과를P. 당신은 위양성이있을 수 있습니다.
따라서 거짓 긍정 일치가있을 수 있지만 거짓 부정은 없습니다. 응용 프로그램 및 개체가 항상 같거나 항상 다를 것으로 예상하는지 여부에 따라 해싱은 불필요한 단계가 될 수 있습니다.
암호화 단방향 해시 함수는 본질적으로 Injective가 아닙니다 . 해시 함수 측면에서 "고유"라는 것은 의미가 없습니다. 이러한 함수는 다른 속성으로 측정되며, 이는 주어진 해시의 사전 이미지를 생성하기 어렵게하여 강도에 영향을줍니다. 예를 들어, 사전 이미지에서 단일 비트를 변경하여 영향을받는 이미지 비트 수에 관심을 가질 수 있습니다. 우리는 무차별 대입 공격 (주어진 해시 이미지에 대한 프라이 이미지 찾기)을 수행하는 것이 얼마나 어려운지 관심을 가질 수 있습니다. 충돌을 찾는 것이 얼마나 어려운지 관심을 가질 수 있습니다 . 생일 공격에 사용할 동일한 해시 이미지를 가진 두 개의 사전 이미지를 찾습니다 .
이 값이 더 이상 결과 해시보다 해시 될 경우 충돌을 얻을 가능성이 있지만, 충돌 횟수는 대부분의 목적을 위해 충분히 낮은 여전히 (있다 2 (128) 이 임의의 문자열의 기회가 생산 있도록 가능한 해시 총 동일한 해시는 이론적으로 10 분의 1에 가깝습니다 38 ).
MD5는 주로 무결성 검사를 수행하기 위해 만들어 졌으므로 최소한의 변경 사항에 매우 민감합니다. 입력을 약간 수정하면 출력이 크게 달라집니다. 이것이 해시 값만으로는 암호를 추측하기 어려운 이유입니다.
해시 자체는 되돌릴 수 없지만 순수한 무차별 대입으로 가능한 입력 값을 찾을 수 있습니다. 이것이 MD5를 사용하여 암호 해시를 저장하는 경우 항상 솔트를 추가해야하는 이유입니다. 입력 문자열에 솔트를 포함하면 일치하는 입력 문자열에 정확히 동일한 솔트를 포함해야 동일한 결과를 얻을 수 있습니다. 그렇지 않으면 출력과 일치하는 원시 입력 문자열이 자동화 된 솔팅 후에 일치하지 않기 때문입니다 (즉, 반전 된 MD5 해시는 솔트 처리되지 않을 가능성이 높으므로 MD5를 "반전"하여 로그인하는 데 사용할 수 없습니다. 원래 해시를 생성 한 문자열).
따라서 해시는 고유하지 않지만 인증 메커니즘은 충분히 고유하게 만들 수 있습니다 (솔팅 대신 암호 제한에 대한 다소 그럴듯한 인수 중 하나입니다. 동일한 해시를 생성하는 문자열 집합에는 아마도 많은 문자열이 포함될 것입니다. 암호 제한을 따르지 않기 때문에 무차별 대입으로 해시를 되 돌리는 것이 더 어렵습니다. 그럼에도 불구하고 소금은 여전히 좋은 생각입니다).
해시가 클수록 동일한 입력 세트에 대해 가능한 해시 세트가 더 많으므로 중복 가능성이 낮아 지지만 처리 능력이 충분히 향상되어 무차별 대입 MD5를 사소하게 만들 때까지는 여전히 대부분의 목적에 적합한 선택입니다.
(해시 함수 일요일 인 것 같습니다.)
암호화 해시 함수는 매우 낮은 복제율을 갖도록 설계되었습니다. 명백한 이유 때문에 비율은 절대 0이 될 수 없습니다.
위키 백과 페이지 정보입니다.
Mike (및 기본적으로 다른 모든 사람)가 말했듯이 완벽하지는 않지만 작업을 수행하며 충돌 성능은 실제로 알고리즘에 따라 다릅니다 (실제로는 꽤 좋습니다).
진짜 흥미로운 것은 파일이나 데이터를 자동으로 조작하여 다른 데이터로 동일한 해시를 유지하는 것입니다.이 데모를 참조하십시오.
다른 사람들이 대답했듯이 해시 함수는 정의상 고유 값을 반환하지 않을 수 있습니다. 무한한 수의 입력에 대해 고정 된 수의 해시가 있기 때문입니다. 핵심 품질은 충돌을 예측할 수 없다는 것 입니다.
즉, 쉽게 되돌릴 수 없습니다. 따라서 동일한 해시 결과 ( "충돌")를 생성하는 고유 한 입력이 많을 수 있지만 그중 두 개를 찾는 것은 계산적으로 실행 불가능합니다.
참조 URL : https://stackoverflow.com/questions/2444321/how-are-hash-functions-like-md5-unique
'UFO ET IT' 카테고리의 다른 글
| Ruby에서 float의 표시 정밀도 설정 (0) | 2021.01.05 |
|---|---|
| 선호도에서 인 텐트에 추가 항목을 넣는 방법이 있습니까? (0) | 2021.01.05 |
| Scala에서 더 나은 문자열 포맷팅 (0) | 2021.01.05 |
| 관계형 대수로 MAX를 어떻게 찾을 수 있습니까? (0) | 2021.01.05 |
| 인터넷 연결 상태 변경에 대한 Android 이벤트 (0) | 2021.01.05 |