MD4

위키원
leejia1222 (토론 | 기여)님의 2019년 7월 3일 (수) 17:11 판 (→‎알고리즘 구현)
이동: 둘러보기, 검색

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

개요

MD4는 전자서명, 응용 프로그램 등 정보보호를 목적으로 개발한 해시 알고리즘이다. 프로그램이 위변조 되었는지를 확인하는 무결성 검사에 사용된다. 입력받은 메시지를 128비트로 압축하는 방식이며, 이전 버전으로는 MD2, 이후 버전으로는 MD5가 있다.[1]

특징

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

비교

  • MD2 : MD2는 8비트 컴퓨터에 최적화되어있는 반면 MD5는 32비트 컴퓨터에 최적화되어있다.
  • 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로 끝낸다.

각주

  1. ↑ 〈제3장 DBMS_CRYPTO〉, 《데이터 전문가 지식포털》
  2. ↑ Ronald Rivest, 〈The MD4 Message-Digest Algorithm〉, 1992-04

참고자료

  • 〈제3장 DBMS_CRYPTO〉, 《데이터 전문가 지식포털》
  • Margaret Rouse,〈MD4〉, 《TechTarget》, 2005-09

같이 보기


블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스
채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW)
매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더
추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링
고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘
대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘
제약 만족 문제 국소검색 • 역추적검색 • 제약전파
게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임
위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반
원본 주소 "http://wiki1.kr/index.php?title=MD4&oldid=89729"