MD4 편집하기

'''MD4'''(message digest 4)는 입력 [[데이터]]로부터 128[[비트]](bit) 메시지 축약을 만듦으로써 데이터 [[무결성]]을 검증하는데 사용되는 [[해시]] [[알고리즘]]이다. 1990년 미국 [[MIT]]의 교수 [[로날드 리베스트]](Ronald Rivest)가 이전 버전인 [[MD2]]를 32비트 [[컴퓨터]]에서 사용하기 위해 개발했다.

==개요==
MD4는 [[전자서명]], [[응용 프로그램]] 등 정보보호를 목적으로 개발한 해시 알고리즘이다. 프로그램이 위변조 되었는지를 확인하는 무결성 검사에 사용된다. 입력받은 메시지를 128비트로 압축하는 방식이며, 이전 버전으로는 [[MD2]], 이후 버전으로는 [[MD4]]가 있다.<ref name="데이터포털">〈[http://www.dbguide.net/db.db?boardUid=145958&boardConfigUid=9&boardIdx=107 제3장 DBMS_CRYPTO]〉, 《데이터 전문가 지식포털》</ref> 

==특징==
* 임의의 길이로 입력받은 메시지를 512비트 단위로 처리해 128비트로 암호화한다.
* 입력 메시지의 길이 제한이 없다.
* 해시값 길이 : 128 비트
* 패딩 처리 : 메시지 길이를 512 비트 정수배로 만든다

==비교==
* [[MD2]] : MD2는 8비트 [[컴퓨터]]에 최적화되어있는 반면 MD5는 32비트 컴퓨터에 최적화되어있다.

* [[MD5]] : MD4는 3라운드에 걸쳐 처리하지만 MD5는 4라운드에 걸쳐 처리한다. MD4보다 MD5가 더 느리지만 더 안정적이다.

==알고리즘 구현==

알고리즘 구현은 개발자인 [[로날드 리베스트]] 교수가 발표한 성명문에 따른 것이다.<ref>Ronald Rivest, 〈[https://tools.ietf.org/html/rfc1320 The MD4 Message-Digest Algorithm]〉, 1992-04</ref>

첫 번째 단계에 들어가기 전 입력받은 임의의 메시지가 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로 끝낸다.

{{각주}}

==참고자료==
* 〈[http://www.dbguide.net/db.db?boardUid=145958&boardConfigUid=9&boardIdx=107 제3장 DBMS_CRYPTO]〉, 《데이터 전문가 지식포털》
* Margaret Rouse,〈[https://searchsecurity.techtarget.com/definition/MD4 MD4]〉, 《TechTarget》, 2005-09

== 같이 보기 ==
* [[암호 알고리즘]]
* [[합의 알고리즘]]
* [[체인 알고리즘]]
* [[블록체인]]
* [[해시그래프]]
* [[암호화폐]]

{{암호 알고리즘|검토 필요}}