해시 편집하기

'''해시'''(hash)란 다양한 길이를 가진 [[데이터]]를 고정된 길이를 가진 데이터로 [[매핑]](mapping)한 값이다. 이를 이용해 특정한 배열의 인덱스나 위치나 위치를 입력하고자 하는 데이터의 값을 이용해 저장하거나 찾을 수 있다. 기존에 사용했던 자료 구조들은 탐색이나 삽입에 선형시간이 걸리기도 했던것에 비해, 해시를 이용하면 즉시 저장하거나 찾고자 하는 위치를 참조할 수 있으므로 더욱 빠른 속도로 처리할 수 있다. '''해시값'''이라고도 한다. '해쉬'가 아니라 '해시'가 올바른 표기법이다. 중국어로는 '''하시'''(哈希, 합희, {{발음|hā xī}})라고 한다. 해시는 암호학에 있어서 매우 중요한 요소이며, [[블록체인]](blockchain)을 구현하기 위한 핵심 기술이다.

== 특징 ==

=== 무결성 ===
해시는 특정한 데이터를 이를 상징하는 더 짧은 길이의 데이터로 변환하는 행위를 의미한다. 여기서 상징 데이터는 원래의 데이터가 조금만 달라져도 확연하게 달라지는 특성을 가지고 있어 무결성을 지키는 데에 많은 도움을 준다. 예를 들어 'A'라는 문자열의 해시와 'B'라는 문자열의 해시는 고작 한 알파벳이 다를뿐이지만 해시 결과값은 완전히 다른 문자열이 나오게 된다.<ref name="hash_bitweb">비트웹 편집국장, 〈[http://www.bitweb.co.kr/m/view.php?idx=360 블록체인의 기본, 해시란 무엇인가?]〉, 《비트웹》, 2018-02-12</ref>

=== 보안성 ===
해시는 기본적으로 [[복호화]]가 불가능하다는 특징이 있다. 이는 당연히 입력 데이터 집합이 출력 데이터 집합을 포함하고 있으므로, 특정한 출력 데이터를 토대로 입력 데이터를 찾을수 없기 때문이다. 즉, 동일한 출력 값을 만들어낼 수 있는 입력 값의 가짓수는 수학적으로 무한개라고 볼 수 있다. 만약에 해시 결과 값에 대해서 복호화를 수행할 수 있다면, 이는 압축률이 무한인 압축 알고리즘과도 같다. 해시는 애초에 복호화를 수행할 수 없도록 설계되었으며, 실제로도 해커가 쉽게 복호화를 할 수 없다는 점에서 강한 보안성을 가진다.<ref name="hash_bitweb"></ref>

=== 비둘기집 원리 ===
대부분의 해시 알고리즘들은 항상 고정된 길이의 결과 문자열을 반환한다는 특징을 가지고 있다. 대표적인 해시 알고리즘인 [[MD5]]로 예를 들면, 128비트로 구성된 결과값, 즉 32자리의 16진수 값을 반환한다. 이 문자열의 길이는 변하지 않는다. 한 비트 단위는 0 혹은 1이라는 두 가지 경우의 수를 가진다는 점에서 128비트는 총 <math>2^{128}</math>만큼의 경우의 수를 표현할 수 있다. 이는 약 340 간(<math>10^{36}</math>)에 해당하는 매우 큰 숫자이다. 단순히 무차별 대입으로 해시 결과가 동일한 두 입력 값을 찾기 위해서는 개인용 컴퓨터로는 상당히 많은 시간을 필요로 하게 된다. 하지만 아무리 큰 숫자라고 하더라도 무한은 아니라는 점에서 특정한 두 입력 값의 결과 해시 값이 동일한 경우가 발생할 수 있다. 예를 들어 입력 값의 개수가 <math>2^{128}</math>를 넘어가게 되면 최소한 한 쌍의 입력 값은 그 결과 값이 동일할 것이다. 더 간단히 설명하자면 비둘기가 5마리일때 상자가 4개밖에 존재하지 않는다면 아무리 비둘기를 균등하게 분배해도 최소한 한 상자에는 2마리의 비둘기가 들어가게 된다. 이러한 원리를 비둘기집 원리라고 말한다. 이 원리에 따라 해시에서는 '서로 다른 입력 값의 해시 결과 값이 동일한 문제' 즉, [[해시 충돌]]이 발생할 여지가 있다. <ref name="hash_bitweb"></ref>

=== 해시레이트 ===

[[해시레이트]]란 연산 처리능력을 측정하는 단위로 해시 속도를 의미한다. 일반적으로 해시레이트가 높아져 연산량이 많아질 경우, 더 빠른 채굴이 이루어지기 때문에 채굴 난이도가 높아진다. 초당 해시값 계산 횟수의 총합으로 암호화폐의 연산 작용 과정에서 얻을 수 있는 채굴의 성공 확률과 실제로 채굴에 성공한 시간으로부터 도출되는 이론값이라고도 할 수 있는데, 이는 채굴 간격과 난이도와는 달리 네트워크에서 직접 측정되지는 않는다. 채굴 난이도와 같은 정방향의 값을 가져서 채굴 난이도가 높아진다는 의미는 해시레이트가 저하된다는 것이고, 이는 곧 단위 시간당 생산할 수 있는 채굴량이 줄어든다는 의미이다. 현재 [[비트코인]]의 채굴은 [[제네시스마이닝]]이나 [[해시플레어]]와 같이 대규모 [[하드웨어]], 즉 [[채굴기]]를 보유한 사람들에 의해 이루어지고 있다. 따라서 실제 해시레이트의 증감은 채굴을 실행하기 위한 사람들이 보유한 채굴장비 수의 변화가 반영된다.

== 활용 ==
해시는 [[블록체인]]과 [[IPFS]] 등 다양한 분야에서 활용되고 있다. 보안 분야에서도 널리 사용되는데 이는 해시 함수가 원래의 문장을 복호화할 수 없게 뭉개버린다는 장점과 원문과 해시값 사이에 선형적 관계가 없다는 특성을 지니고 있기 때문이다. 해시 함수의 결과물은 고정된 길이의 숫자이므로, 원래의 정보는 손실되는데, 이러한 특성 때문에 하나의 원 데이터는 하나의 해시값만 가지지만, 하나의 해시값을 만들어 낼 수 있는 원본 데이터는 매우 많아서, 해시값만 가지고는 아무리 용을 써도 이미 뭉개져버린 원문을 복원해해는 것은 불가능하다. 따라서 비밀번호, [[전자서명]], 전자투표, 전자상거래와 같은 민감한 입력의 무결성을 검증할 때 주로 사용된다. 따라서 데이터의 무결성과 직접적인 연관이 있기 때문에 어떤 해시 함수에서 해시 충돌이 일어나기 쉽다는 것은 보안 분야에서는 매우 민감한 문제에 해당한다. <ref name="hash_namuwiki"> 나무위키 - https://namu.wiki/w/%ED%95%B4%EC%8B%9C </ref>

=== 해시함수 ===
해시 함수는 임의의 길이를 갖는 임의의 데이터에 대해 고정된 길이의 데이터로 매핑하는 함수를 말한다. 이러한 해시 함수를 적용하여 나온 고정된 길이의 값을 해시값이라고 한다. 보통 그리 복잡하지 않은 [[알고리즘]]으로 구현되기 때문에, 상대적으로 [[CPU]], [[메모리]] 같은 시스템 자원을 덜 소모하는 특성이 있다. 그리고 해시함수(hash function)는 결정론적으로 작동하기 때문에, 원래의 데이터가 같으면 해시값도 항상 동일하며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 해시 함수도 존재한다. 이러한 특성으로 인해 다양한 목적에 맞게 설계된 해시 함수가 존재하며 자료구조, 캐시, 중복 레코드 검색, 유사 레코드 검색, 에러검출 등 다양한 분야에서 매우 유용하게 사용된다. 하지만 서로 다른 데이터가 동일한 해시값을 가질 수 있기 때문에 [[해시충돌]]이 발생할 수 있다. <ref name="hash_namuwiki"></ref> 대표적인 해시 함수로는 [[MD5]], [[SHA]] 등이 있다.

=== 해시테이블 ===
[[해시 테이블]](hash table)은 키와 값을 매핑해 둔 데이터 구조이다. 해시함수를 이용하여 검색하고자 하는 값을 변환하면 그 값이 저장된 위치를 즉시 알아낼 수 있다. 데이터의 양이 아무리 많아지더라도 원리적으로 해시 변환과 검색에 걸리는 시간은 항상 동일하다. 따라서 방대한 데이터에서 특정한 값을 검색할 때 해시 테이블을 사용하면 검색 시간을 획기적으로 단축할 수 있다. 해시 맵(hash map)은 기존 해시 테이블의 기능을 개선한 신 버전의 해시 테이블이다. 

해시 테이블의 기본 개념은 데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것이다. 따라서 특이하게도 데이터가 입력되지 않은 여유공간이 많아야 제 성능을 발휘할 수가 있다. 

=== 해싱 ===
[[해싱]](hashing)이란 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법을 말한다. 해싱에 사용되는 [[자료구조]]는 [[배열]](array)과 [[연결리스트]](linked list)가 조합된 형태이다. 짧은 해시 키를 사용하여 항목을 찾으면, 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 [[데이터베이스]] 내의 항목들을 색인하고 검색하는데 사용된다. <ref>Vangie Beal, 〈[https://www.webopedia.com/TERM/H/hashing.html hashing]〉, 《웨보피디아》</ref> 해싱은 데이터들을 저장하거나 찾을 때 인덱스(index)라는 또다른 데이터 스트럭쳐를 이용하는 대신, 각 데이터들이 테이블의 어느 영역에 위치할 것인가를 결정해주는 해시함수를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을 수 있도록 해주는 것이다. 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에 걸쳐서 골고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해시함수를 사용하면 곧바로 그 위치를 알아내는 것이 가능하기 때문에 매우 빠른 속도로 데이터를 검색할 수가 있게 된다. <ref>Omnis, 〈[https://omnis.tistory.com/entry/Hashing-%EC%9D%B4%EB%9E%80 Hashing 이란?]〉, 《티스토리》, 2012-04-09</ref>

== 해시 방법 ==
송신자는 메시지의 해시를 생성하여 암호화한 후 메시지 자체를 가지고 송신한다. 그런 다음 수신자는 메시지와 해시를 모두 해독하고, 수신된 메시지에서 또 다른 해시를 생성하고, 두 해시를 비교한다. 동일하다면 메시지가 온전하게 전달되었을 가능성이 매우 높다.

=== 제산법 ===
제산법은 나머지 연산자를 사용하여 테이블 주소를 계산하는 방법이다. 레코드 키 값을 수치 자료로 간주하여 어떤 양의 정수(대개 해시 테이블의 크기)로 나눈 나머지를 홈 주소로 결정하는 간단한 방법이다. 
 예) 버킷주소 = 키 값 % 해시 테이블의 크기
 12 = 512 % 100

=== 제곱법 ===
제곱법은 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용하는 방법이다. 제곱된 결과의 중간 비트는 대게 레코드의 모든 문자에 의존하므로, 레코드를 구성하는 몇 개의 문자가 같을지라도 서로 다른 레코드 키는 다른 홈 주소를 갖게 될 확률이 높다. 홈 주소를 얻기 위해 사용되는 비트 수는 테이블의 크기에 따라 달라지는데, 중간 부분의 자릿수를 n 이라 하면 각 레코드 값들이 가지는 범위인 해시 테이블의 크기는 <math>2^{n}</math>이 된다. 

키 값 제곱 => 해시 테이블 크기에 따라 주소 값 산출
 예) 레코드 키 값이 K=512이고, 해시테이블 크기가 100일때 제곱법에 의한 레코드 주소는
 512제곱 = 262144 =====> 중간 2자리 "21"이 최종 주소값이 됨

=== 숫자 분석법 ===
레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법이다.
 예) 해시 테이블의 크기 = 1000, 홈 주소: 0~999까지(3자리 필요) 레코드 키 값이 다음의 (a)와 같을 때 숫자 분석법을 이용하여 각 키들에 대한 홈 주소를 결정하시오.
  (레코드 키 값)  (각 키의 홈 주소)
 012 - 452 - 0236 ==> 426
 012 - 153 - 0530 ==> 150
 015 - 342 - 0935 ==> 395
 012 - 752 - 1032 ==> 702
 012 - 852 - 0470 ==> 840
 012 - 543 - 0231 ==> 512
 (1) (a)에서 왼족 3자리는 거의 같으므로 제거
 (2) 왼쪽 5열, 6열, 7열, 9열 역시 동일 숫자가 많이 분포하므로 무시
 (3) 비교적 고른 숫자 분포를 가진 4열, 8열, 10열을 선택하여 주소로 사용

=== 폴딩법 ===
폴딩법은 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더하거나 배타적 논리합(XOR)을 취하여, 해시 테이블의 홈 주소로 이용하는 방법으로 두 가지 방법이 사용된다.

{|class=wikitable width=700
|align=center|3
|align=center|0
|align=center|1
|align=center|2
|align=center|3
|align=center|0
|align=center|1
|align=center|2
|align=center|3
|align=center|2
|align=center|1
|align=center|3
|align=center|3
|align=center|0
|-
|align=center colspan=3|P1
|align=center colspan=3|P2
|align=center colspan=3|P3
|align=center colspan=3|P4
|align=center colspan=2|P5
|}

이중폴딩 ==> P1+P2+P3+P4+P5 = 301+230+123+213+30 = 897이 홈주소가 된다.<br>
경계폴딩 ==> P1+P2(역)+P3+P4(역)+P5 = 301+032+123+312+30 = 798이 홈주소가 된다.

=== 기수변환법 ===
기수변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다. 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소 값이 테이블의 크기를 초과할 때는 주소 값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다.
 예) 해시 테이블의 크기 = 100000
 십진수로 입력된 키 값(132548) 10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오.
 <math>(1*16^{5})+(3*16^{4})+(2*16^{3})+(5*16^{2})+(4*16^{1})+(8*16^{0}) </math> <br> <math> = 1048576+196608+8192+1280+64+8=(1254728)_{10}</math>
 홈 주소 = 4728(레코드의 주소값에서 해시 테이블이 허용하는 하위 4자리를 선택한다)

=== 무작위 방법 ===
난수 발생 프로그램을 이용하여 난수를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로, 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위 값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용한다.<ref>SLENDER ANKLES, 〈[https://slenderankle.tistory.com/160 해시(Hash)]〉, 《티스토리》, 2015-07-01</ref>

== 해시계산 사이트 ==
해시값을 자동으로 계산해서 알려주는 사이트로 [[깃허브]]의 [[온라인툴즈]]가 있다. 온라인툴즈<!--온라인 툴즈-->(Online Tools)는 알려진 거의 모든 [[해시함수]]를 사용하여, 실시간으로 해시값을 계산해 주는 깃허브의 [[웹페이지]]이다.

== 해시라는 단어가 포함된 회사명 ==
{{로고블록100
|해시넷||해시드||해시캐시||에듀해시||헤데라 해시그래프|헤데라<br>해시그래프|해시가드||해시캐피탈||해시플레어||나이스해시|<!--|맥스해시|-->|희망해시|<!--|해시래빗|-->|해시쉐어|<!--|해시시티|-->|해시팟||해시피시||해시허브||}}

회사명에 '해시'(hash)라는 단어를 사용한 사례는 다음과 같다.
* '''[[해시넷]]'''(Hashnet) : 한국의 블록체인 및 암호화폐 정보 포털 사이트를 운영하는 회사이다. 오프라인 밋업과 콘퍼런스도 진행하고 있다.
* '''[[해시드]]'''(Hashed) : 한국의 블록체인 및 암호화폐 전문 투자업체이다. 한국 1위의 [[크립토펀드]]이다.
* '''[[해시캐시]]'''(Hashcash) : 1997년 [[아담 백]](Adam Back)이 스팸메일과 서비스 거부(DoS) 공격을 제한하기 위해 사용한 [[작업증명]](PoW) 시스템이다. 
* '''[[에듀해시]]'''(Eduhash) : 교육 분야에 블록체인 기술을 적용한 회사이다.
* '''[[헤데라 해시그래프]]'''(Hedera Hashgraph) : 해시그래프 기반의 플랫폼을 만드는 미국의 개발 회사이다.
* '''[[해시가드]]'''(Hashgard) : 블록체인 기반의 자산관리 서비스를 위한 중국의 암호화폐 프로젝트이다.
* '''[[해시캐피탈]]'''(Hash Capital) : 블록체인 투자를 전문적으로 진행하는 중국의 투자업체이다.
* '''[[해시플레어]]'''(HashFlare) : 영국 스코틀랜드에 있는 클라우드 마이닝 채굴 회사이다.
* '''[[나이스해시]]'''(Nicehash) : 동유럽의 슬로베니아에 있는 마이닝풀이다.
* '''[[맥스해시]]'''(Maxhash) : 다중 암호화폐 마이닝풀이다. 채굴장은 미국과 유럽에 있다.
* '''[[지해시아이오]]'''(GHash.io) : 네덜란드에 있는 비트코인 채굴 풀이다.
* '''[[희망해시]]'''(Hopehash) : 전 세계 여러 나라에 채굴장을 마련하여 클라우드 마이닝 서비스를 제공하는 한국의 채굴업체이다.
* '''[[해시래빗]]'''(HashRabbit) : 미국 캘리포니아 주에 있는 암호화폐 채굴업체이다.
* '''[[해시볼트]]'''(Hashvault) : [[크립토노트]](CryptoNote) 기반의 마이닝풀이다.
* '''[[해시쉐어]]'''(Hashshare) : [[마스터노드]]에 [[비트코인]] 채굴 시스템을 결합한 암호화폐 프로젝트이다.
* '''[[해시시티]]'''(Hashcity) : [[조지아]]의 [[트빌리시]]에 있는 다중 암호화폐 채굴 [[마이닝풀]]이다.
* '''[[해시쿼크]]'''(Hashquark) : 중국의 채굴업체이다.
* '''[[해시팟]]'''(Hash Pot) : 중앙아시아의 저렴한 전기요금을 이용한 비트코인 [[채굴]] 서비스를 위한 한국의 암호화폐 프로젝트이다.
* '''[[해시허브]]'''(HashHub) : 일본 도쿄에 본사를 둔 블록체인 스튜디오이다. 대표이사는 준야 히라노(Junya Hirano)이다.

{{각주}}

== 참고자료 ==
* 비트웹 편집국장, 〈[http://www.bitweb.co.kr/m/view.php?idx=360 블록체인의 기본, 해시란 무엇인가?]〉, 《비트웹》, 2018-02-12
* 나무위키 - https://namu.wiki/w/%ED%95%B4%EC%8B%9C 
* SLENDER ANKLES, 〈[https://slenderankle.tistory.com/160 해시(Hash)]〉, 《티스토리》, 2015-07-01
* Omnis, 〈[https://omnis.tistory.com/entry/Hashing-%EC%9D%B4%EB%9E%80 Hashing 이란?]〉, 《티스토리》, 2012-04-09
* Vangie Beal, 〈[https://www.webopedia.com/TERM/H/hashing.html hashing]〉, 《웨보피디아》
* 디센터유니버시티 보스코인, 〈[https://www.sedaily.com/NewsView/1S3E902IZ4 (디센터 용어사전③)해시함수, 해킹이 가능한 듯 불가능…무량대수만큼 시도해야]〉, 《서울경제》, 2018-08-17

== 같이 보기 ==
* [[블록체인]]
* [[IPFS]]

{{블록체인 기술|검토 필요}}
{{암호 알고리즘}}
{{데이터}}

[[분류:블록체인]]
[[분류:알고리즘]]
[[분류:암호학]]