Hash 함수 특징 질문

Question

안녕하세요, 해시에 대해 공부하다 몇가지 질문이 있어 이렇게 남기게 되었습니다.해시 함수의 특징 중 해시 충돌이라는 치명적인 단점에도 사용하는 이유는?1. 적은 리소스로 많은 데이터를 효율적으로 관리가 가능하다.2. 예를 들어 하드디스크나 클라우드에 존재하는 무한의 데이터들은 유한한 개수의 해시 값으로 매핑하여 작은 크기의 캐시메모리로도 프로세스 관리가 가능하다.라는 부분이 있는데, 제가 알기론 데이터의 양이 버킷의 사이즈 80%를 넘어가면 매우 비효율적이라고 알고 있습니다. 여기서 적은 리소스로 많은 데이터를 효율적으로 처리할 수 있다고 말하는건 80% 사이즈를 넘지 않을때의 경우인가요?또한 버킷 사이즈를 어떻게 측정하고 해시 테이블을 만드는지 궁금합니다.마지막으로 해시 함수의 특징 중 충돌저항성이라고 있는데, 만약 해시 함수의 충돌이 발생한다면 이 해시 함수는 해시 함수로 역할을 잃는것인가요? (해시 함수라고 말할 수 없는것인가?)

Hide_D · Answer

(1)해시맵에서 버킷의 사이즈 80%를 넘어가면, 버킷의 크기를 2배로 키우면 됩니다. 예를 들자면 해시맵을 생성할 때 첫번째에는 해시값의 첫 8비트를 키로 삼아 256개짜리 배열[버킷]을 만들어서 관리하고, 크기가 차면 그 다음엔 첫 10비트짜리를 키로 삼아 1024개짜리 배열을 만들어서 관리하는거죠.적절한 해시를 사용할 경우엔 버킷이 어지간해선 겹치지 않으니 반복해나가면 됩니다. (2) 해시값의 범위보다 원본 데이터는 당연히 그보다 더 큰 영역이니, 충돌 자체는 발생할 수 있습니다.해시에 따라 다르지만 암호학적으로 안전한 SHA256의 경우 2^256개고, 이정도면 어지간해선 해시 충돌이 일어나지 않겠지만, 그래도 어쩌다 하나는 있을 수 있겠죠. SHA256기준으로 birthday paradox에 의해서 데이터가 2^128개가 넘어가면 '무조건 충돌'이 있다고 보고 설계해야하구요.해결책은 보통 두가지인데, 충돌이 발생하지 않을 정도로 충분한 해시를 쓰거나(SHA512를 적용한다면 2^256개의 데이터까지 버틸 수 있겠죠), 해시값으로 1차 비교하고 원본으로 비교한다거나 하는거죠. 충돌저항성은 다른 이야기로, 공격자가 같은 해시값을 가진 다른 데이터 쌍을 의도적으로 만들어 낼 수 없도록 한다는 이야기입니다. 암호학적인 용도 외에 해시맵에서는 같은 해시값을 의도적으로 만들어낼 수 없고, 해시 결과는 무작위이니, 버킷을 단순한 알고리즘에 따라 늘려나가는 것으로도 충분히 효율적(O(1))이다! 라는 증명에 쓰이죠. (이제보니 블록체인 카테고리였군요!)블록체인에서는 역상저항성과 충돌저항성 두가지를 동시에 활용하는데, 원본 데이터와 다른 데이터이지만 같은 해시값을 갖도록 의도적으로 만들어 낼 수 없다는 데에 활용합니다. 우연히 해시값이 같을 순 있겠지만, 그런 경우에는 데이터의 원본이 올바른 형태가 아니거나, 진짜로 데이터가 너무 많이 쌓여서(2^128개?) 다른 해시를 쓰기 시작해야하는 경우죠.

yeori · Answer

해시값 충돌은 단점이라기보다는 현상입니다.얼음이 녹으면 물이 되는 것처럼요

Alan-cho · Answer

&#64;Hide_D 자세한 설명 정말 감사합니다. &#64;yeori자연스러운 현상이라는 거네요! 감사합니다.

Hash 함수 특징 질문

3개의 답변

Q&A 목록