| '''이론 컴퓨터 과학 {{{#!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 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6
MD5("The quick brown fox jumps over the lazy dog.") = e4d909c290d0fb1ca068ffaddf22cbd0
Message-Digest algorithm 5
임의의 길이의 값을 입력받아서 128비트 길이의 해시값을 출력하는 알고리즘이다. 1991년 설계되었다.
MD5는 단방향 암호화이기 때문에 출력값에서 입력값을 복원하는 것은 일반적으로 불가능하다. 같은 입력값이면 항상 같은 출력값이 나오고, 서로 다른 입력값에서 같은 출력값이 나올 확률은 극히 낮다(0은 아니며 발생할 수 있다.).
흔히 패스워드 암호화에 많이 사용되는데, 패스워드를 MD5로 해시해서 나온 값을 저장해 두는 것이다. 이렇게 하면 운영자나, 데이터를 무단으로 뜯어본 자도 이 값만 봐서는 본래의 값 자체는 알 수 없게 된다. 비밀번호를 정확하게 입력했다면 같은 해시값이 튀어나오므로, 본래의 키라는 것을 확인할 수는 있는 것이다. 하지만 MD5는 속도가 너무 빠르기때문에 salt같은 수단을 붙이더라도 무차별 대입이나 사전 공격에 너무 취약하다. 비밀번호 해시 함수는 bcrypt나 scrypt같은 비밀번호 해시 용도로 설계된 함수를 쓰자.
단방향 암호화이기 때문에 MD5 해시값에서 원래의 데이터를 찾아내는것은 불가능하며(원문을 해시 계산 과정에서 비트 단위로 박살내버린다), 크래커들은 "같은 MD5를 갖는 문자열", 즉 "충돌"(Collision)을 찾아내는 데 주력한다. 어쨌든 MD5값이 같으면 같은 문자열이라고 판단하기 때문이며 이는 모든 단방향 암호화에 통용되는 기법이다.[2]
2004년에 높은 유사성을 보이는(하지만 엄연히 다른) 128바이트 파일 두 개의 해시값 충돌이 발견되었다. 이는 알고리즘 자체의 엄청난 결함이다. 논문에 따르면 IBM P690 머신에서 충돌을 생성하는 데 한 시간밖에 걸리지 않았다고 한다.
2006년에는 더욱 빠른 알고리즘이 개발되어 논문에 따르면 노트북 한 대의 연산 능력 (Intel Pentium, 1.6 GHz)으로 1분 만에 충돌을 찾아낼 수 있다고 한다.
심지어는 다른 결과가 나오는 프로그램이 같은 MD5 값을 가질 수도 있다.
다만 고속 연산이 가능하고(정수 연산 및 비트시프트로 모든게 해결된다.) 임의로 변경된 패턴에 대해서는 충돌 가능성이 충분히 낮기 때문에, 현재는 주로 네트워크로 전송된 큰 파일의 무결성을 확인하는데 주로 사용된다. 대표적인 예시가 지정된 파일을 MD5 해시 알고리즘으로 체크섬(check sum) 값을 계산하는 리눅스의 'md5sum' 명령어이다. 이는 대용량 파일이 전송 도중에 손실 없이 잘 다운로드 되었는지 확인하고자 할 때 내가 받은 파일의 md5 체크섬을 계산하여, 원본 파일의 체크섬과 비교해서 동일성을 검증하는 방식이다. 보안용도로 쓸 때는 꼭 salt[3]를 붙여서 쓰는 게 안전하지만 다른 알고리즘을 권장한다.
특히, 앞에서 언급된 네트워크에서는 OSI 7계층 중 2계층에 속하게되는 장비인 Switch, 3계층에 속하게되는 Router는 장비 간의 상호인증체계로 활용된다. (Cisco IOS 기준)
고지라 시리즈의 신작인 고질라: 싱귤러 포인트에서 중요한 소재로 등장하는데, MD5의 단방향성에 주목해 답을 얻기 위해서는 답이 필요하다는 명제, 즉 닭과 달걀의 패러독스, 타임 패러독스를 설명하기 위해 쓰였다.
2. 관련 항목
[1] 보다시피 마침표의 유무라는 매우 작은 변화에도 전혀 다른 값이 나온다. 대소문자도 구분한다. 앞이 소문자인
MD5("the quick brown fox jumps over the lazy dog")은 77add1d5f41223d5582fca736a5cb335이다.[2] 1234나 love 등의 간단한 숫자나 단어만 써서 암호를 만들지 말라는 이유는 여기서도 통용된다. 이런 간단한 암호는 해커들이 가지고 있는 해시값 사전에도 있을 확률이 거의 100%이기 때문이다.[3] 입력된 값에 임의의 값을 붙인다든지, 암호화 한 값에 또다른 값을 붙여서 암호화 한다든지... 이름이 왜 Salt냐면 음식에 소금을 뿌리듯 입력된 값에 무작위로 소금을 뿌리듯 임의의 값을 뿌리기 때문이다.