위키원
MD4
MD4(message digest 4)는 입력 데이터로부터 128비트(bit) 메시지 축약을 만듦으로써 데이터 무결성을 검증하는데 사용되는 해시 알고리즘이다. 1990년 미국 MIT의 교수 로날드 리베스트(Ronald Rivest)가 이전 버전인 MD2를 32비트 컴퓨터에서 사용하기 위해 개발했다.
개요
MD4는 전자서명, 응용 프로그램 등 정보보호를 목적으로 개발한 해시 알고리즘이다. 프로그램이 위변조 되었는지를 확인하는 무결성 검사에 사용된다. 입력받은 메시지를 128비트로 압축하는 방식이며, 이전 버전으로는 MD2, 이후 버전으로는 MD5가 있다.[1]
특징
- 임의의 길이로 입력받은 메시지를 512비트 단위로 처리해 128비트로 암호화한다.
- 입력 메시지의 길이 제한이 없다.
- 해시값 길이 : 128 비트
- 패딩 처리 : 메시지 길이를 512 비트 정수배로 만든다
비교
- MD5 : MD4는 3라운드에 걸쳐 처리하지만 MD5는 4라운드에 걸쳐 처리한다. MD4보다 MD5가 더 느리지만 더 안정적이다.
알고리즘 구현
알고리즘 구현은 개발자인 로날드 리베스트 교수가 발표한 성명문에 따른 것이다.[2]
첫 번째 단계에 들어가기 전 입력받은 임의의 메시지가 b비트라고 가정한다. b는 0일 수 있다.
m_0 m_1 ... m_{b-1}
- Step1 : Append Padding Bits
- 입력받은 메시지의 길이가 512비트의 배수가 되게 패딩해야 하지만, 첫 번째 단계에서는 512비트의 배수보다 64비트 모자라게(-64bit) 패딩해야 한다. 이때 마이너스 한 64비트는 패딩 전 원래의 서명문 길이를 의미한다. 1비트를 1개 추가하고 0비트를 추가해 최소 1비트와 최대 512비트를 추가한다.
- Step2 : Append Length
- Step1에서 제외시켰던 64비트를 채워준다. 패딩 전 원래의 서명문 길이를 64비트로 표시하여 붙여준다. 이때 메시지의 길이가 2^64보다 클 경우, 낮은 64비트만 사용된다. 패딩이 완료되었다면 완료된 메시지를 16word단위로 M[0,,,,,,N-1]에 할당시킨다. 이때 M은 워드 단위를 의미하고, N은 16의 배수가 된다.
- Step3 : Initialize MD Buffer
- 메시지 다이제스트를 계산하기 위해 4단어의 버퍼(A, B, C, D)를 사용하는데, 각각 32비트 레지스터이며 MD4는 Little-endian 방식을 사용하길 규정하기 때문에 low-order bytes를 따른다.
word A: 01 23 45 67 word B: 89 ab cd ef word C: fe dc ba 98 word D: 76 54 32 10
- Step4 : Process Message in 16-Word Blocks
- 3개의 32비트 단어를 입력해 32비트 워드로 생산하는 3개의 보조 기능을 정의한다.
F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XY v XZ v YZ H(X,Y,Z) = X xor Y xor Z
- 각 비트 위치는 'X가 되면 Y가 Z가 된다는 F 조건을 따른다. XY와 not(X)Z는 동일한 비트 위치에 1비트가 위치하지 않을 것이므로 F함수는 v 대신 +를 사용해 정의할 수 있다. 각 비트 위치의 G는 다수결 함수이고, X,Y,Z 중 두 개가 켜져 있으면 G는 해당 위치에 1비트가 있고 그렇지 않다면 0비트가 있다. 주의해야 할 점은 X, Y, Z의 비트가 독립함수라면 F(X,Y,Z)와 G(X,Y,Z)도 독립함수라는 것이다. H함수는 비트 단위 XOR연산(bit-wise XOR) 또는 패리티 연산을 수행하는 함수이다. 의사코드(Pseudo Code)는 다음과 같다.
Process each 16-word block. */ For i = 0 to N/16-1 do
/* Copy block i into X. */ For j = 0 to 15 do Set X[j] to M[i*16+j]. end /* of loop on j */
/* Save A as AA, B as BB, C as CC, and D as DD. */ AA = A BB = B CC = C DD = D
/* Round 1. */ /* Let [abcd k s] denote the operation a = (a + F(b,c,d) + X[k]) <<< s. */ /* Do the following 16 operations. */ [ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19] [ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19] [ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19] [ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]
/* Round 2. */ /* Let [abcd k s] denote the operation a = (a + G(b,c,d) + X[k] + 5A827999) <<< s. */
/* Do the following 16 operations. */ [ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13] [ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13] [ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13] [ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13]
/* Round 3. */ /* Let [abcd k s] denote the operation a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s. */ /* Do the following 16 operations. */ [ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15] [ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15] [ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15] [ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]
/* Then perform the following additions. (That is, increment each of the four registers by the value it had before this block was started.) */ A = A + AA B = B + BB C = C + CC D = D + DD end /* of loop on i */
- Step5 : Output
- 생성된 메시지 다이제스트 A, B, C, D를 연결해 준다. A의 low-order byte로 시작해 D의 high-order byte로 끝낸다.
각주
- ↑ 〈제3장 DBMS_CRYPTO〉, 《데이터 전문가 지식포털》
- ↑ Ronald Rivest, 〈The MD4 Message-Digest Algorithm〉, 1992-04
참고자료
- 〈제3장 DBMS_CRYPTO〉, 《데이터 전문가 지식포털》
- Margaret Rouse,〈MD4〉, 《TechTarget》, 2005-09
같이 보기
