MD5
위키백과 ― 우리 모두의 백과사전.
암호학에서 MD5(Message-Digest algorithm 5)는 128비트 해시를 제공하는 많이 사용되는 암호화 해시 함수이다. RFC 1321로 지정되어 있으며 많은 프로그램 및 파일의 무결성 검사에 사용된다.
1991년 로널드 라이베스트가 처음 고안했다. 예전의 MD4를 대체하기 위해 나왔다. 1996년 MD5의 설계상 결함이 발견되었다. 매우 치명적인 결함은 아니었지만, 암호학자들은 SHA-1 같은 다른 알고리즘을 사용할 것을 권장하기 시작했다. 2004년에는 더욱 심한 암호화 결함[1]이 발견되었고 2006년에는 노트북 컴퓨터 한 대의 계산 능력으로 1 분 내에 해시 충돌을 찾을 정도로 빠른 알고리즘이 발표[2] 되기도 하였다. 사람들은 MD5 알고리즘을 보안 관련 용도로 쓰는 것을 다분히 권장하고 있지 않다.
[편집] 알고리즘
MD5는 임의의 길이의 메시지(variable-length message)를 입력받아, 128bit 짜리 고정 길이의 출력값을 낸다. 입력 메시지는 512-bit짜리 블록들로 쪼개진다; 메시지를 우선 패딩하어 512로 나누어 떨어질 수 있는 길이가 되게 한다. 패딩은 다음과 같이 한다: 우선 첫 단일 비트, 1을 메시지 끝부분에 추가한다. 512의 배수의 길이보다 64 bit가 적은 곳까지 0으로 채운다. 나머지 64 bit는 최초의(오리지날) 메시지의 길이를 나타내는 64-bit 짜리 정수(integer)값으로 채워진다.
메인 MD5 알고리즘은 A,B,C,D라고 이름이 붙은 32-bit 짜리 워드 네 개로 이루어진 하나의 128-bit 스테이트(state)에 대해 동작한다. A,B,C,D는 소정의 상수값으로 초기화된다. 메인 MD5 알고리즘은 각각의 512-bit 짜리 입력 메시지 블록에 대해 차례로 동작한다. 각 512-bit 짜리 입력 메시지 블록을 처리하고 나면 128-bit 스테이트(state)의 값이 변하게 된다.
하나의 메시지 블록을 처리하는 것은 4 단계로 나뉜다. 한 단계를 "라운드"(round)라고 부른다; 각 라운드는 비선형 함수 F, 모듈라 덧셈, 레프트 로테이션(left rotation)에 기반한 16개의 동일 연산(similar operations)으로 이루어져 있다. 오른쪽 "그림 1"은 한 라운드에서 이루어지는 한 연산(operation)을 묘사하고 있다.
함수 F에는 4가지가 있다; 각 라운드마다 각각 다른 F가 쓰인다:
는 각각 XOR, 논리곱, 논리합 그리고 NOT 연산을 의미한다.
[편집] 슈도코드
MD5 알고리즘의 슈도코드는 다음과 같다:
//Note: All variables are unsigned 32 bits and wrap modulo 2^32 when calculating var int[64] r, k //r specifies the per-round shift amounts r[ 0..15] := {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22} r[16..31] := {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20} r[32..47] := {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23} r[48..63] := {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21} //Use binary integer part of the sines of integers as constants: for i from 0 to 63 k[i] := floor(abs(sin(i + 1)) × (2 pow 32)) //Initialize variables: var int h0 := 0x67452301 var int h1 := 0xEFCDAB89 var int h2 := 0x98BADCFE var int h3 := 0x10325476 //Pre-processing: append "1" bit to message append "0" bits until message length in bits ≡ 448 (mod 512) append bit (bit, not byte) length of unpadded message as 64-bit little-endian integer to message //Process the message in successive 512-bit chunks: for each 512-bit chunk of message break chunk into sixteen 32-bit little-endian words w[i], 0 ≤ i ≤ 15 //Initialize hash value for this chunk: var int a := h0 var int b := h1 var int c := h2 var int d := h3 //Main loop: for i from 0 to 63 if 0 ≤ i ≤ 15 then f := (b and c) or ((not b) and d) g := i else if 16 ≤ i ≤ 31 f := (d and b) or ((not d) and c) g := (5×i + 1) mod 16 else if 32 ≤ i ≤ 47 f := b xor c xor d g := (3×i + 5) mod 16 else if 48 ≤ i ≤ 63 f := c xor (b or (not d)) g := (7×i) mod 16 temp := d d := c c := b b := b + leftrotate((a + f + k[i] + w[g]) , r[i]) a := temp //Add this chunk's hash to result so far: h0 := h0 + a h1 := h1 + b h2 := h2 + c h3 := h3 + d var int digest := h0 append h1 append h2 append h3 //(expressed as little-endian)
//leftrotate function definition
leftrotate (x, c)
return (x << c) or (x >> (32-c));
주석: RFC 1321에 나온 공식 말고 다음과 같은 공식이 쓰일 수 있다. 다음과 같은 공식을 쓰면 퍼포먼스가 향상될 수 있다. (어셈블리 언어가 사용될 때 유용하다 - 다른 언어가 쓰일 경우에는 대개 컴파일러가 위의 코드를 최적화 해준다.):
(0 ≤ i ≤ 15): f := d xor (b and (c xor d)) (16 ≤ i ≤ 31): f := c xor (d and (b xor c))
![]() |
이 문서는 암호학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다. |