의견.png

해시

위키원
fshiel8165 (토론 | 기여)님의 2019년 7월 23일 (화) 16:03 판
이동: 둘러보기, 검색

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

개요

특징

무결성

해시는 특정한 데이터를 이를 상징하는 더 짧은 길이의 데이터로 변환하는 행위를 의미한다. 여기서 상징 데이터는 원래의 데이터가 조금만 달라져도 확연하게 달라지는 특성을 가지고 있어 무결성을 지키는 데에 많은 도움을 준다. 예를 들어 'A'라는 문자열의 해시와 'B'라는 문자열의 해시는 고작 한 알파벳이 다를뿐이지만 해시 결과값은 완전히 다른 문자열이 나오게 된다.[1]

보안성

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

비둘기집 원리

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

활용

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

해시함수

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

해시테이블

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

해싱

해싱(hashing)이란 해시함수를 사용하여 주어진 값을 변환한 뒤, 해시 테이블에 저장하고 검색하는 기법을 말한다. 해싱에 사용되는 자료구조배열(array)과 연결 리스트(linked list)가 조합된 형태이다. 짧은 해시 키를 사용하여 항목을 찾으면, 원래의 값을 이용하여 찾는 것보다 더 빠르기 때문에, 해싱은 데이터베이스 내의 항목들을 색인하고 검색하는데 사용된다.

해시의 방법

제산법

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

ex) 버킷주소 = 키 값 % 해시 테이블의 크기
12 = 512 % 100

제곱법

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

키 값 제곱 => 해시 테이블 크기에 따라 주소 값 산출

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

숫자 분석법

레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법이다.

ex) 해시 테이블의 크기 = 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)을 취하여, 해시 테이블의 홈 주소로 이용하는 방법으로 두 가지 방법이 사용된다.

3 0 1 2 3 0 1 2 3 2 1 3 3 0
P1 P2 P3 P4 P5

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

기수변환법

기수변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다. 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소 값이 테이블의 크기를 초과할 때는 주소 값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다.

ex) 해시 테이블의 크기 = 100000
십진수로 입력된 키 값(B2538) 10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오.
 
홈 주소 = 4728(레코드의 주소값에서 해시 테이블이 허용하는 하위 4자리를 선택한다)

무작위방법

난수 발생 프로그램을 이용하여 난수를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로, 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위 값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용한다.[3]


해시계산사이트

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

각주

  1. 1.0 1.1 1.2 비트웹 편집국장, 〈블록체인의 기본, 해시란 무엇인가?〉, 《bitweb》, 2018-02-12
  2. 2.0 2.1 나무위키 - https://namu.wiki/w/%ED%95%B4%EC%8B%9C
  3. SLENDER ANKLES, 〈해시(Hash)〉, 《개인 블로그》, 2015-07-01

참고자료

같이 보기


  의견.png 이 해시 문서는 블록체인 기술에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.