좋은 해시 함수란 무엇입니까?

StackOverflow https://stackoverflow.com/questions/34595

문제

좋은 해시 함수란 무엇입니까?대학 시절 데이터 구조 강좌에서 해시 함수와 응용을 많이 보았지만 좋은 해시 함수를 만드는 것이 꽤 어렵다는 것을 대부분 깨달았습니다.충돌을 피하기 위한 경험에 따르면 교수님은 다음과 같이 말씀하셨습니다.

function Hash(key)
  return key mod PrimeNumber
end

(mod는 C 및 유사한 언어의 % 연산자입니다)

소수는 해시 테이블의 크기가 됩니다.충돌을 피하고 빠른 기능을 제공하는 다소 좋은 기능이라는 것을 알지만 어떻게 더 나은 기능을 만들 수 있습니까?숫자 키에 비해 문자열 키에 대한 더 나은 해시 함수가 있습니까?

도움이 되었습니까?

해결책

기본적으로 모든 종류의 데이터에 대해 "일반적인" 해시 테이블 조회를 수행하는 데 사용되는 Paul Hsieh의 이 테이블은 내가 사용해 본 것 중 최고입니다.

http://www.azillionmonkeys.com/qed/hash.html

암호화 보안이나 기타 고급 기능에 관심이 있다면 YMMV를 선택하세요.해시 테이블 조회를 위한 범용 해시 함수를 원한다면 이것이 바로 여러분이 찾고 있는 것입니다.

다른 팁

범용 해시에는 "좋은 해시 함수"라는 것이 없습니다(ed.예, "유니버설 해싱"과 같은 것이 있다는 것을 알고 있지만 이는 제가 의미하는 바가 아닙니다.)상황에 따라 다양한 기준에 따라 해시의 품질이 결정됩니다.이미 두 사람이 SHA를 언급했습니다.이것은 암호화 해시이며 아마도 의미하는 해시 테이블에는 전혀 좋지 않습니다.

해시 테이블에는 요구 사항이 매우 다릅니다.그러나 여전히 좋은 해시 함수를 보편적으로 찾는 것은 어렵습니다. 왜냐하면 다양한 데이터 유형이 해시될 수 있는 다양한 정보를 노출하기 때문입니다.원칙적으로 고려하는 것이 좋습니다. 모두 한 유형이 동일하게 보유하는 정보입니다.이는 항상 쉬운 일도 아니고 가능한 일도 아닙니다.통계(및 그에 따른 충돌)의 이유로 문제 공간에 걸쳐 좋은 확산을 생성하는 것도 중요합니다.가능한 모든 개체.즉, 100에서 1050 사이의 숫자를 해싱할 때 객체의 최대 90%에 대해 이 숫자가 0이 되기 때문에 가장 중요한 숫자가 해시에서 큰 역할을 하도록 하는 것은 좋지 않습니다.마지막 세 자리 숫자로 해시를 결정하는 것이 훨씬 더 중요합니다.

마찬가지로, 문자열을 해싱할 때 모든 문자를 고려하는 것이 중요합니다. 단, 모든 문자열의 처음 세 문자가 동일하다는 것이 미리 알려진 경우는 예외입니다.이것을 고려하는 것은 낭비입니다.

이것은 실제로 Knuth가 말한 내용을 읽어 보라고 조언하는 사례 중 하나입니다. 컴퓨터 프로그래밍의 예술, 권.삼.또 다른 좋은 책은 Julienne Walker의 책입니다. 해싱의 기술.

해싱 함수에는 두 가지 주요 목적이 있습니다.

  • 데이터 포인트를 n 비트로 균일하게 분산시킵니다.
  • 입력 데이터를 안전하게 식별합니다.

해시를 어떤 용도로 사용하는지 모르고 해시를 추천하는 것은 불가능합니다.

프로그램에서 해시 테이블을 만드는 것이라면 알고리즘이 얼마나 되돌릴 수 있는지 또는 해킹 가능한지 걱정할 필요가 없습니다.SHA-1 또는 AES는 이를 위해 전혀 필요하지 않습니다. FNV의 변형.FNV는 귀하가 언급한 단순한 프라임 모드보다 더 나은 분산(따라서 충돌 감소)을 달성하며 다양한 입력 크기에 더 잘 적응합니다.

공개 정보(예: 비밀번호 또는 문서 해싱)를 숨기고 인증하기 위해 해시를 사용하는 경우 공개 조사를 통해 검증된 주요 해싱 알고리즘 중 하나를 사용해야 합니다. 해시 함수 라운지 시작하기 좋은 곳입니다.

이것은 좋은 예이자 왜 결코 쓰고 싶지 않은지에 대한 예입니다.이는 컴퓨터 공학의 천재이자 순수한 ​​부두교인 Fowler / Noll / Vo(FNV) 해시입니다.

unsigned fnv_hash_1a_32 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned h = 0x811c9dc5;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x01000193;

   return h;
}

unsigned long long fnv_hash_1a_64 ( void *key, int len ) {
    unsigned char *p = key;
    unsigned long long h = 0xcbf29ce484222325ULL;
    int i;

    for ( i = 0; i < len; i++ )
      h = ( h ^ p[i] ) * 0x100000001b3ULL;

   return h;
}

편집하다:

  • Landon Curt Noll은 다음을 권장합니다. 그의 사이트 원래 FVN-1 알고리즘에 대한 FVN-1A 알고리즘:향상된 알고리즘은 해시의 마지막 바이트를 더 잘 분산시킵니다.그에 따라 알고리즘을 조정했습니다.

경험상 주요 규칙은 직접 굴리지 않는 것입니다.예를 들어 SHA-1 또는 이와 유사한 것 등 철저하게 테스트된 것을 사용해 보십시오.

좋은 해시 함수에는 다음과 같은 속성이 있습니다.

  1. 메시지의 해시가 주어지면 공격자가 해시가 동일한 다른 메시지를 찾는 것은 계산상 불가능합니다.

  2. 한 쌍의 메시지 m'과 m이 주어지면 h(m) = h(m')이 되는 두 개를 찾는 것이 계산적으로 불가능합니다.

두 가지 경우는 ~ 아니다 똑같다.첫 번째 경우에는 충돌을 찾으려는 기존 해시가 있습니다.두 번째 경우에는 다음을 찾으려고 합니다. 어느 충돌하는 두 개의 메시지.두 번째 작업은 생일 "역설"로 인해 훨씬 ​​더 쉽습니다.

성능이 그다지 큰 문제가 되지 않는 경우에는 항상 보안 해시 기능을 사용해야 합니다.해시에서 충돌을 강제하여 수행할 수 있는 매우 영리한 공격이 있습니다.처음부터 강력한 것을 사용한다면 이러한 것들로부터 자신을 보호할 수 있을 것입니다.

새로운 디자인에는 MD5 또는 SHA-1을 사용하지 마세요.나를 포함한 대부분의 암호해독자들은 그것들이 깨졌다고 생각할 것입니다.이 두 설계의 주요 약점은 위에서 설명한 두 번째 속성이 이러한 구성에 적용되지 않는다는 것입니다.공격자가 m과 m'이라는 두 개의 메시지를 생성할 수 있고 두 메시지 모두 동일한 값으로 해시되면 이러한 메시지를 사용자에게 사용할 수 있습니다.SHA-1 및 MD5도 메시지 확장 공격에 취약하므로 주의하지 않으면 애플리케이션이 치명적으로 약화될 수 있습니다.

Whirpool과 같은 보다 현대적인 해시가 더 나은 선택입니다.이는 이러한 메시지 확장 공격을 겪지 않으며 AES가 다양한 공격에 대한 보안을 입증하기 위해 사용하는 것과 동일한 수학을 사용합니다.

도움이 되었기를 바랍니다!

여기서 말하는 것은 충돌 저항력이 있는 것을 사용하고 싶다는 것입니다.SHA-2를 사용해 보세요.또는 Miyaguchi-Preenel 모드의 AES와 같은 단방향 압축 기능(이전에는 시도한 적이 없음)에서 (좋은) 블록 암호를 사용해 보십시오.문제는 다음을 수행해야 한다는 것입니다.

1) IV가 있습니다.Khinchin 상수의 분수 부분 중 처음 256비트나 이와 유사한 것을 사용해 보십시오.2) 패딩 방식을 가지고 있습니다.쉬운.MD5 또는 SHA-3(Keccak['ket-chak'로 발음)]과 같은 해시에서 배로우합니다.보안에 관심이 없다면(몇몇 사람들이 이렇게 말함), FNV나 Bob Jenkins의 lookup2를 살펴보세요(실제로 저는 lookup2를 추천하는 첫 번째 사람입니다). 또한 MurmurHash를 사용해 보세요. 빠릅니다(다음을 확인하세요:.16cpb).

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top