해싱의 역사
일반 해시 함수는 임의 크기의 데이터를 다음의 데이터에 매핑하는 데 사용되는 특수한 유형의 프로그래밍 함수입니다. 고정 된 크기. 해시 함수는 압박 붕대 대용량 파일을 저장하는 데 필요한 메모리 양을 줄이기 위해 해시 함수의 가장 널리 사용되는 사용 사례는 해시 테이블, 빠른 데이터 조회에 널리 사용됩니다. 해시 함수는 정확히 동일한 두 해시를 감지하여 테이블 또는 데이터베이스 조회 속도를 높이는 데 도움이됩니다..
또한 mp3, PDF 또는 이미지와 같은 방대한 파일에 대한 태그를 축소하여 이러한 다소 큰 파일 형식을 관리 할 수 있도록합니다. 신속한 식별을 위해 해시 함수의 핵심 요구 사항은 고정 길이의 영숫자 문자열 출력.
해시 함수가 시작된 핵심 이유는 콘텐츠를 압축 할 필요가 있었기 때문에 곧 두 번째 이점이 해싱의 필수 요소가되었습니다. 단일 고유 식별자입니다. 이상적으로는 여러 메시지를 해싱 할 때 서로 다른 두 메시지가 동일한 해시를 반환하지 않아야합니다. 동일한 출력 해시를 생성하는 두 개의 서로 다른 해시 메시지를 충돌.
데이터베이스 관리 관점에서 이것은 두 개의 다른 개체가 같은 셀에 저장된다는 것을 의미합니다. 단일 고유 식별자를 정의하려는 경우에는 좋지 않습니다. 해시 함수를 고려하면 무한 입력 (즉, 모든 문자열을 해시 할 수 있음) 충돌이 실제로 발생하는 이유를 정확히 도출 할 수 있습니다. 피하기 어려운.
Pigeonhole 원리
암호화 수학에는 다음과 같은 개념이 있습니다. pigeonhole 원리 이는 (n) 요소를 (m) 공간에 맞추면 엔 > 미디엄, 그런 다음 원칙적으로 두 개 이상의 요소 (n)가 차지하는 공간 (m)이 하나 이상 있습니다..
예를 들어, 5 명의 개인이 사용 가능한 세 개의 코트 큐비 중 하나에서 코트를 확인합니다. pigeonhole 원칙에 따라 저장되는 코트의 수 (n)가 사용 가능한 큐비 (m)보다 많기 때문에 적어도 하나의 큐비가 하나 이상의 코트를 수용 할 수 있습니다..
일반적으로 소프트웨어 엔지니어는 해시 함수에 관심이 있습니다. 무한 도메인 (즉, 가능한 모든 길이의 입력 문자열로 간주 됨) 및 유한 범위. 다시 pigeonhole 원칙에 따라 범위 (n)가 영역 (m)보다 작기 때문에 하나 이상의 충돌이 있어야합니다.. 따라서 효과적인 해시 함수는 충돌 수를 최소화하는 것뿐입니다.이 문제가 잠시 후에 더 명확 해 지겠지만 지금은 해시 기록으로 돌아가 보겠습니다..
해시 함수는 데이터베이스 유지 관리에서 엄격하게 시작되었습니다. & 무엇보다도 속도를 선호하는 관리 요구 사항은 그 유용성이 빠르게 발전했습니다. 개인 정보 보호, 보안을 선호하는 해시 함수의 특수 분기, & 투명성이 곧 현장에 들어갔다. 이 기사의 초점으로 남을 해시 함수의 한 가지 : 암호화 해싱 함수.
암호화 해싱
이름에서 알 수 있듯이 암호화 해싱 기능은 절대적으로 중단없는 메시지를 보존하는 데 유리합니다. 충돌을 최소화하는 것은 다른 해시 함수, 특히 암호화 기능에 대해 좋은 방법이지만 충돌을 최소화하는 것은 요구 사항. 신속한 데이터베이스 또는 테이블 조회 시나리오를위한 유틸리티를 최대화하는 대신 암호화 해싱 함수는 적대적 시나리오를 염두에두고 구축됩니다. 즉, 코드 브레이커 (암호 분석가)가 적극적으로 충돌을 일으키려고 시도하는 시나리오입니다. 이제 표준 해시 함수 표기법을 정의하겠습니다. & 암호화 관점 내에서 해시 함수 원칙 설정.
해시 함수 표기법
일반 암호화 해시 함수에는 압축 할 메시지 또는 해시 (x)의 두 가지 입력이 있습니다. & 해시의 고정 길이 출력을 영숫자 문자로 나타내는 공개 키 (들). 해시 된 결과를 메시지 다이제스트 또는 간단히 다이제스트 (x *)라고합니다. 이것은 다음과 같습니다.
H (s, x) = x *
이전에 표준으로 명명 된 해싱 함수를 사용하여 문자열을 해싱하는 실제 예를 살펴보면서이 표기법을 간단히 살펴 보겠습니다. MD5. MD5를 사용하여 “Hello World!”를 해시하고 싶다고 가정 해 보겠습니다. 끈. 또한 기본적으로 MD5는 항상 128 비트 (0 & 1 ‘s). 이 표기법은 다음과 같습니다.
H (128, x) = ed076287532e86365e841e92bfc50d8c
사실, 계속하면 & 제공하려고 MD5 해시 함수“Hello World!” 똑같은 결과 해시를 볼 수 있습니다.. 대박. 이제 충돌에 대한 표기법을 설정해 보겠습니다. 이전 변수 H, s, x에 추가, & x * 이제 두 번째 메시지 (x ‘)를 소개합니다. 숫자 적으로 두 개의 개별 메시지 (x)를 해싱 할 때 충돌이 발생합니다. & x ‘)는 정확히 동일한 메시지 다이제스트 (x *)를 생성합니다.
H (128, x) = H (128, x ‘)이면 해시 함수 (H)가 x에서 충돌한다고합니다. & 엑스’.
이제 해시 함수 암호화의 현재 특징 표준에 대한 표기법을 설정했습니다. 적이 (컴퓨터로 말하는) 가능한 경우 충돌을 일으킬 수있는 경우, 해시 함수는 더 이상 실질적으로 안전한 것으로 간주되지 않습니다..
다음 시간까지 마무리 생각
마지막 수학적 정의는 해시 함수 실용성에 대한 매혹적인 catch-22가 사는 곳입니다. 압축의 필요성에서 비롯된 해시 함수 & 저장 편의를 위해 표준화 된 균일 데이터를 출력합니다. 즉, a의 의사 난수 문자열을 뱉어냅니다. 고정 길이. 그러나 만들기 위해 완전 충돌 방지 해시 함수, 모든 단일 메시지 (x)는 해시 된 출력을 가져야합니다. 입력과 동일한 길이. 고정 길이의 해시가 없으면이를 편리한 데이터 구조로 사용할 수있는 능력을 잃게되지만 고정 된 길이를 할당하면 해시 함수가 완전히 충돌하지 않게됩니다..
추신 — 일부 스마트 쿠키는 MD5 예제에서 길이 문자열을 반환하는 해시 함수를 표시했음을 알았습니다. 128, 그러나 우리의 “Hello World!” 해시는 32 영숫자 문자열. 다음에 다시 오세요 & 이 차이가 어디서 발생했는지 설명하기 위해 해시 함수에 대해 자세히 살펴 보겠습니다..
