hash은(는) 여기로 연결됩니다.
동음이의어에 대한 내용은 해시(동음이의어) 문서 참고하십시오.| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
[[컴퓨터공학|컴퓨터 과학 & 공학
Computer Science & Engineering
]]- [ 펼치기 · 접기 ]
- ||<tablebgcolor=#fff,#1c1d1f><tablecolor=#373a3c,#ddd><colbgcolor=#0066DC><colcolor=white> 기반 학문 ||수학(해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학(환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학(형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 ||
하드웨어 구성 SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 기술 기계어 · 어셈블리어 · C/C++ · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍 · 해킹 · ROT13 · 일회용 비밀번호 · 사물인터넷 · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 · 하드웨어 가속 연구
및
기타논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 운영 체제 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱 · 링커 · 난해한 프로그래밍 언어} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 디자인 패턴 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) · 버전 (버전 관리 시스템 · Git · GitHub)
1. 개요
Hash function해시 함수 (짧게는 그냥 해시)는 임의의 길이를 갖는 임의의 데이터를 고정된 길이의 데이터로 매핑하는 단방향 함수를 말한다. 쉽게 말해, 아무리 큰 숫자를 넣더라도 정해진 크기의 숫자가 나오는 함수이다. 예를 들면 어떤 숫자를 10으로 나누었을 때 그 나머지를 구하는 함수도 해시 함수이다.[1]
이러한 해시 함수를 적용[2]하여 나온 고정된 길이의 값을 해시값, 해시 코드, 해시섬(sum), 체크섬 등으로 부른다.
해시 함수는 보통 입력의 범위(정의역)보다 출력값의 범위(치역)가 작으므로 서로 다른 입력값에도 동일한 값이 출력되는 경우도 존재한다. 자세한 원리는 비둘기 집의 원리와 생일 문제 참고. 이러한 경우를 '충돌'한다고 한다.
2. 쓰임
이러한 특성에 힘입어 다양한 목적에 맞게 설계된 해시 함수가 존재하며 다음과 같은 다양한 분야에서 매우 유용하게 사용된다.- 자료구조
- 해시 테이블 (또는 해시 맵)
- 해시셋(set)
- 블룸 필터(Bloom filter)
- 캐시
- 중복 레코드 검색
- 유사 레코드 검색
- 유사 부분 문자열 검색
- 기하학적 해시
- 변조 탐지/에러 검출[3]
유명한 해시 알고리즘으로는 Message-Digest Algorithm(MD)[4] 사상을 도입한 MD-N Secure Hash Algorithm(SHA)-N 등이 있다. 이 알고리즘은 암호학적 해시 알고리즘의 요구사항(연산량 포함), 암호학적인 취약점 등에 따라 해시 함수를 개선하여 여러 종류의 함수가 있다.
3. 암호학적 해시 함수
암호학적 해시 함수는 같은 입력값에 대해서는 같은 출력값이 보장되며, 이 출력값은 가능한 한 고른 범위에 균일하게 분포하는 특성이 있다. 특수 목적용으로 해시값을 생성하는 원본과 별도의 값을 입력받아서 같은 입력에 대해 다른 출력값을 가지게 하는 해시 함수도 존재한다.암호학적 해시 함수는 입력값이 조금만 변해도 결과가 크게 달라지는 특성을 갖도록 설계되는데, 이런 성질을 눈사태 효과라고 한다. 일반 해시 함수와 다르게 암호학적 해시 함수는 이러한 특성이 중요한데, 이와 관련해서는 증명가능한 보안(provable security)의 의사난수함수(pseudo random function)을 참고한다. [5]
암호학적 해시 함수를 설계할 때 세 가지 목적을 갖는다.
3.1. 역상 저항성(preimage resistance)
주어진 결과값에 대해 입력값을 계산하기 어려워야 한다.컴퓨터 공학에서의 해시 함수와의 차이점에 대해 쉽게 이해할 수 있는 예이다.
3.2. 제 2 역상 저항성(seconde preimage resisatance)
주어진 입력값에 대해 충돌쌍을 갖는 다른 입력값을 계산하기 어려워야 한다.3.3. 충돌 저항성(collision resistance)
충돌쌍(같은 결과값)을 갖는 두 개의 입력값을 계산하는 것이 어려워야 한다. 제 2 역상 저항성과 유사해 보이지만 암호학적으로 주어진 조건이 다르므로 공격 시나리오가 다르다.GPU를 몇십 개씩 쌓아두고 하나씩 대입해가며 찍는 방식이 브루트 포스, 남들이 일일이 삽질해본 데이터를 참고해서 뚫어보는 것이 레인보우 테이블 전략이다.
4. 해시 테이블(=해시 맵)
해시를 사용하는 자료구조다.배열의 색인(Index)에 해시값을 사용하는 자료 구조로, Associative array ADT(=Map ADT)를 구현하는데 사용한다. 정렬을 하지 않고도 빠른 검색, 빠른 삽입이 가능하다.
해시맵은 여러 성분을 저장하기 위해 배열을 사용하는 접근법은 동일하지만, 여기에 색인 개념이 추가되어 있다. 일단 충분히 큰 공간을 할당받은 다음 해시 함수를 이용하여 고유 색인을 생성한다. 그리고 이 고유 색인과 맞는 위치에 데이터를 저장한다.
예로 설명하면, 0 ~ 10000까지 데이터를 담을 수 있는 배열을 생성하고, '나무위키'란 단어에 해시 함수를 적용하여 2642란 색인이 생성되면 배열 2642번 색인에 '나무위키'를 저장하는 방식이다. 해시 함수는 언제나 동일한 해시 값을 반환하기 때문에 '나무위키'를 입력하면 항상 2642란 색인이 나오므로 굳이 정렬하지 않고도 바로 찾을 수 있게 되는 셈. 단, 이러한 목적으로 사용하는 해시 함수는 해시값을 계산하는 비용이 기존 검색 알고리즘에 비해 훨씬 적고 뛰어나야 한다는 전제 조건이 붙는다. 그렇지 않다면 이러한 방법을 사용하는 의미가 없다.
위에서 언급한 것처럼 해시값이 충돌하는 경우가 발생하여 같은 색인이 만들어질 수도 있다. 예를 들어 나중에 입력된 '위키위키' 단어를 해시 함수에 넣었더니 2642란 색인으로 나온다면 '나무위키'와 동일한 색인을 가지게 되는 문제가 발생한다. 이 경우 보통 사용하는 방법은 두 가지 정도인데, 하나는 배열의 각각의 색인을 연결 리스트[6]로 만들어서 새로 입력이 될 때마다 같은 해시를 가진다 하더라도 색인이 연결리스트로 구현되어 있기 때문에 원하는 데이터의 접근이 가능한 개별 체이닝(Separate Chaining)과 다음에 위치한[7] 색인들 중 비어있는 곳에 넣는 방식인 오픈 어드레싱(Open Addressing) 등이 있다.
- 이하 내용은 도서 <파이썬 알고리즘 인터뷰>가 출처입니다.
해시 테이블의 기본 방식이기도 한 개별 체이닝(Separate Chaining)은 충돌 발생 시 그림과 같이 연결 리스트로 연결(link)하는 방식이다. 충돌이 발생한 윤아와 서현은 윤아의 다음 아이템이 서현인 형태로 서로 연결 리스트로 연결되었다. 이처럼 기본적인 자료구조와 임의로 정한 간단한 알고리즘만 있으면 되므로, 개별 체이닝 방식은 인기가 높다. 원래 해시 테이블 구조의 원형이기도 하며 가장 전통적인 방식으로, 흔히 해시 테이블이라고 하면 바로 이 방식을 말한다.
오픈 어드레싱(Open Addressing) 방식은 충돌 발생 시 그림과 같이 탐사를 통해 빈 공간을 찾아나서는 방식이다. 사실상 무한정 저장할 수 있는 체이닝 방식과 달리, 오픈 어드레싱 방식은 전체 슬롯의 개수 이상은 저장할 수 없다. 충돌이 일어나면 테이블 공간 내에서 탐사(Probing)를 통해 빈 공간을 찾아 해결하며, 이 때문에 개별 체이닝 방식과 달리, 모든 원소가 반드시 자신의 해시값과 일치하는 주소에 저장된다는 보장은 없다. 그림은 가장 간단한 방식인 선형 탐사(Linear Probing) 방식이며 충돌이 발생할 경우 해당 위치부터 순차적으로 탐사를 하나씩 진행한다. 특정 위치가 선점되어 있으면 바로 그 다음 위치를 확인하는 식이다. 이렇게 탐사를 진행하다가 비어 있는 공간을 발견하면 삽입하게 된다. 가장 가까운 다음 빈 위치를 탐사해 새 키를 삽입한다. 그림에서도 윤아 다음에 서현의 해시값이 동일한 2로 충돌이 발생했고, 다음번 빈 위치를 탐색하며 그 다음 위치인 3에 서현이 들어가게 된다. 이처럼 선형 탐사 방식은 구현 방법이 간단하면서도, 의외로 전체적인 성능이 좋은 편이기도 하다.
이렇게 충돌 해결을 한다고 해도 결과적으로 충돌로 인한 성능 저하는 막을 수 없다. 그림과 같이 수용률이 일정량을 넘어서게 되면 저장/조회 성능이 모두 점점 떨어지며 그래서 수용률이 일정량을 넘어가게 되는 경우에는 아예 리스트 자체의 크기를 키운 뒤에 재배열을 하는 방법을 사용한다. 다만, 이 과정 자체가 상당히 비용이 많이 드는 과정이라서 실시간으로 빠르게 처리해야되는 환경에서는 무리가 있을 수 있다. 이럴 때는 큰 리스트를 하나 더 만들어서 적당한 타이밍에 몇 개씩 점진적으로 옮기다가 다 옮기면 기존의 테이블을 없애 확장하는 방식도 있기는 하다. 다만 이 경우에는 메모리를 훨씬 더 많이 사용하게 된다.
또는 해시의 비트수를 늘이는 방법도 있다. 항목 수가 적을 때에는 짧은(적은 비트 수) 해시와 작은 저장공간를 사용하다가 충돌이 잦아지면 비트수를 1비트 늘이고 저장공간도 2배로 늘인다. 그리고 항목을 점진적으로 확장된 공간으로 이전하게 함으로써 충돌을 줄일 수 있다. Consistent hashing 이라고 하며 분산 데이터베이스에서 데이터의 일관성을 유지하기 위해 사용되고 있다.
자료를 기본적으로 정렬하지 않은 상태로 저장하기 때문에 정렬된 순서로 접근하는 것은 비용이 매우 많이 들며 순회를 하는 경우에도 무효한 값들이 많아 실제 데이터의 개수만 순회하는 것보다 더 많은 비용이 들게 된다. 그리고 부하의 임계점을 적으면 50%, 많아봐야 75% 정도로 잡기 때문에 실제 데이터의 양보다 메모리를 많이 쓰게 된다.
각 언어별 해시 테이블의 구현 방식은 다음과 같다.
| 언어 | 방식 |
| C++(GCC libstdc++) | 개별 체이닝 |
| 자바 | 개별 체이닝 |
| C\# (Hashtable)[8] | 오픈 어드레싱 |
| 고(Go) | 개별 체이닝 |
| PHP | 개별 체이닝 |
| 루비 | 오픈 어드레싱 |
| 파이썬 | 오픈 어드레싱 |
5. 보안과 해시
해시는 보안 분야에서도 널리 사용되는데 이는 해시 함수가 원래의 문장을 복호화할 수 없게 뭉개버린다는 장점, 그리고 원문과 해시값 사이에 선형적 관계가 없다는 특성을 지니고 있기 때문이다. 해시 함수의 결과물은 고정된 길이의 숫자이므로, 원래의 정보는 손실된다.[9] 또한 이런 특성 때문에 하나의 원 데이터는 하나의 해시값만 가지지만, 하나의 해시값을 만들어낼 수 있는 원본 데이터는 매우 많다. 그 때문에 해시값만 가지고는 아무리 용을 써도 이미 뭉개진 원문을 복원해내는 것은 불가능하다. 그런 주제에 원본 데이터가 조금만 바뀌어도 해시값은 확확 바뀌기 때문에, 원본 데이터와 다른 입력값이 (예컨대 복사본이나 키보드 입력으로 입력 받은 비밀번호가) 같은지 확인하는 작업을 둘의 해시값을 대신 비교하는 것으로 갈음할 수 있을 것이다.[10] 따라서 비밀번호, 전자서명, 전자투표, 전자상거래와 같은 민감한 입력의 무결성을 검증할 때 사용된다.[11] 또한 파일의 무결성을 검증할 때에도 사용한다. 파일을 배포할 때 해시값을 같이 배포하고, 파일의 해시값이 배포된 해시값과 같으면 파일이 변조되지 않았다는 것을 확인할 수 있다. 소프트웨어의 코드서명이나 인터넷에서 다운로드한 파일을 검증하는 데 쓰인다. 따라서 어떤 해시 함수에서 해시 충돌이 일어나기 쉽다는 것은 보안 분야에서는 매우 민감한 문제에 해당한다. 데이터의 무결성과 직접적인 연관이 있기 때문이다.현재까지 개발된 거의 모든 해시 함수는 해시 충돌의 문제가 확인된 상태이다. SHA-1와 길이만 늘어날 뿐, 알고리즘이 SHA-1와 똑같은 SHA-256, SHA-512는 해시 충돌의 가능성이 이론적으로 제시되었다. 2014년 기준으로 문제가 없는 해시 표준으로는 SHA-3가 유일하다. 다만 여기서 이론적으로 제시되었다는 것은 지구 전체의 연산 처리 능력을 기준으로 계산적 가능성을 따지는 것이다. 순수한 무차별 대입(Brute Force)보다 몇 천 배 정도 적은 계산 횟수로 복호화할 수 있으면 학계에서는 대체로 '깼다'라고 취급한다. 그런데 예컨대 SHA-1 해시를 무차별 대입으로 깨려면 2160번의 계산을 해야 하는데, 여기서 1,000배 빨라졌다고 해 봤자 2150번의 계산이 필요하다.[12] 즉 현실적인 의미로는, SHA-1이나 SHA-2족의 해시가 불안하다고 여기기엔 다소 무리가 있다. 다만 2017년을 기점으로는 SHA-1은 실질적인 의미로도 깨졌다고 봐야할듯.
5.1. 채굴기의 보안 위협
SHA 해독에 그래픽카드보다 96,000배의 연산력을 보이는 ASIC, FPGA 등을 이용한 비트코인 채굴기가 개발되면서 해시 함수의 보안력이 급격히 떨어졌다.당장 현재의 상황을 보면, 라데온 R9 290X 8대를 크로스파이어해서 사용한다고 해도 1.12GH/s 정도의 해시레이트가 나오는데, 1,100달러(126만 원) 정도 하는 ASIC 채굴기인 Antminer S9를 사용하면 13,500GH/s가 나온다. 그래픽카드보다 성능이 약 9만 6천 배나 더 낫다는 것이다.
6. 해시 함수의 종류
- MD5
- SHA
- SHA-1
- SHA-256, SHA-512
- SHA-3
- CRC
- CRC32 - [13]
- Tiger
- Argon2
- Bcrypt
- Scrypt
- Snefru
- Ripemd
- Haval
- Gost
- Joaat
- FNV
- Whirlpool
- PBKDF2
- Blake3
7. 해시 산출 툴
- 파일 해시값 산출[14]
- certutil - 윈도우 내장 해시값 출력 프로그램 #
- PowerShell - 'Get-FileHash' 명령어 설명서
- md5sum, sha256sum 등 - 리눅스 자체 해시값 출력 명령어 #
- shasum - 맥 cli에서 사용.
- HashCalc
- HashTab
8. 관련 문서
[1] 왜냐하면 나머지는 0부터 9까지로 제한되어있기 때문.[2] 해싱(hashing)[3] 오픈소스 프로그램을 다운받을 때 md5sum, sha1sum, sha256sum 등으로 bacc82b32fe8b8b45c9225f129196943 과 같은 이상한 문자열을 같이 표기해 놓은 것을 볼 수 있다. 그 문자열이 이 목적으로 사용되는 해시값이다.[4] MD5가 대표적.[5] 사실 모든 암호학적 함수는 이런 성질을 요구한다.[6] 트리를 사용하기도 한다. Java8의 해시맵은 Red-Black 트리를 이용하여 체이닝(Chaining) 한다.[7] 꼭 +1번째를 말하는 것은 아니다. 현재 색인이 2642일때 다음이 2643이 될 수도 있고 2650이 될 수도 있다. 보통은 규칙적으로 넣는 편으로 1, 2, 3, ...처럼 +1 하는 방식인 선형 탐색법(Linear Probing), 1, 2(=1+1), 6(=2+4), 15(=6+9), ...처럼 n의 제곱을 더하는 방식인 2차 탐색법(Quadratic Probing), 추가적인 해시값으로 다음 위치를 결정하는 2중 해싱(Double Hashing) 등이 있다.[8] 해시 맵(Dictionary)의 경우 개별 체이닝 방식이다.[9] 예컨대 1GB짜리 데이터도 SHA-1 해시 함수에 넣으면 고작 40자리의 16진수 해시값으로 변환된다.[10] 여기까지 읽었으면 알겠지만 물론 해시값이 같다고 두 비교하는 내용이 같다는 보장은 없다. 그럼에도 불구하고 이 비교 방식이 유효한 이유는 악의적인 조작을 통해 해시값까지 똑같이 만드는 것이 (현재 연산 기술로는 유의미한 시간 내에) 사실 상 불가능하기 때문이다. 이는 위의 저항성들을 통해 보장받는다.[11] 그런 이유로 서버에서는 비밀번호 원본이 아닌 해시값을 저장해야 한다. (법적으로 강제된 사항이다.) 만에 하나 서버가 털렸을 때 비밀번호 원본은 유출되지 않는 편이 훨씬 더 낫기 때문이다. 어차피 해시값으로만 비교하는 거면 해시값이 유출되는 것도 똑같이 심각한 문제이지 않냐고 할 수 있을텐데, 이 문제를 해결하기 위해 비밀번호의 해시값을 계산할 때 무작위로 생성된 솔트(salt) 배열을 비밀번호에 덧붙인 다음, 이 늘어난 문자열의 해시값을 구하고 솔트와 같이 서버에 저장하는 방식을 쓸 수 있다. 물론 비교는 저장된 솔트를 이용해서 똑같이 구한 해시값으로 하면 된다. 이러면 해시값이 유출되더라도 솔트만 바꿔 다시 구한 해시값을 쓰면 그만이거니와, 어차피 다른 사이트들에는 (다른 사이트들이 모두 보안 수칙을 잘 적용했다는 가정 하에) 다른 솔트 값으로 구한 해시값이 저장되어 있을테니, 유출된 해시값으로 할 수 있는 게 없어진다.[12] 감이 안 온다면 현대 슈퍼컴퓨터들이 250~260 수준의 연산능력을 지니는데 이를 이용해서 계산하려면 햇수만으로 해(1020)단위 이상의 시간이 필요하다.[13] 8바이트(32비트)이며, 속도가 빠른 편에 속하는 알고리즘이라 정확도보다는 처리량과 속도가 중요한 프로그램에서 사용한다.[14] 산출된 해시섬을 통해서 파일 위변조 확인, 중복파일 검사 등에 활용할 수 있다.