MD5(Message-Digest Algorithm 5)는 임의 길이의 데이터를 받아 128비트 고정 길이의 해시 값을 생성하는 대표적인 암호학적 해시 함수입니다. MD5는 메시지 다이제스트를 계산하기 위해 다음과 같은 5단계 과정을 거칩니다.
1단계 – 패딩 비트 추가(Append Padding Bits)
메시지의 총 비트 길이가 512 모듈로 448(length ≡ 448 mod 512)과 일치하도록 패딩 비트를 덧붙입니다. 여기서 중요한 점은, 메시지 길이가 이미 조건을 만족하고 있더라도 이 패딩 작업은 반드시 수행된다는 것입니다.
448 + 64 = 512이므로, 패딩 후 메시지 길이는 항상 512의 정수배보다 64비트 짧은 길이가 됩니다.
2단계 – 길이 정보 추가(Append Length)
원본 메시지 M의 비트 길이(패딩 비트가 삽입되기 전 기준)를 나타내는 64비트 값을 1단계의 결과 뒤에 추가합니다. 만약 원본 메시지의 길이가 264 = 18,446,744,073,709,551,616보다 크다면, 길이 값의 하위 64비트(low-order bits)만 사용합니다.
즉, 이 필드에는 원본 메시지 길이를 264로 나눈 나머지(modulo) 값이 저장됩니다. 이 64비트는 두 개의 32비트 워드로 구성되며, 낮은 자릿수 워드(least significant word)부터 순서대로 추가됩니다.
1단계와 2단계가 완료되면 최종 메시지의 비트 길이는 512비트의 정수배가 됩니다.
3단계 – MD 버퍼 초기화(Initialize MD Buffer)
MD5 해시 알고리즘의 중간 및 최종 결과를 저장하기 위해 128비트 버퍼가 사용됩니다. 이 버퍼는 네 개의 32비트 워드(A, B, C, D)로 구성되어 있으며, 각 워드는 하나의 32비트 레지스터입니다.
이 네 개의 레지스터는 다음과 같은 16진수 값으로 초기화되며, 낮은 자릿수 바이트(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
4단계 – 512비트 블록 처리(Process Message in 512-bit Blocks)
메시지는 512비트(16워드) 단위의 블록으로 나누어 처리되며, 이 과정에서 압축 함수(compression function)가 사용됩니다. 압축 함수는 총 네 번의 라운드(round)로 구성되어 있습니다.
각 라운드는 현재 처리 중인 512비트 블록(Yq)과 128비트 버퍼 값 ABCD를 입력으로 받아, 버퍼의 내용을 갱신(update)합니다.
또한 각 라운드에서는 세 개의 32비트 워드를 입력받아 하나의 32비트 워드를 출력하는 네 개의 보조 함수(auxiliary functions)가 사용됩니다.
F (X, Y, Z) = XY ∨ NOT(X) Z
G (X, Y, Z) = XZ ∨ Y NOT(Z)
H (X, Y, Z) = X ⊕ Y ⊕ Z
I (X, Y, Z) = Y ⊕ (X ∨ NOT(Z))
여기서 각 비트 위치를 기준으로 볼 때, 함수 F는 조건문처럼 동작합니다. 즉, X이면 Y를 선택하고, 그렇지 않으면 Z를 선택하는 방식입니다. F는 OR 연산(v) 대신 + 연산으로도 표현할 수 있는데, 그 이유는 XY와 NOT(X)Z가 동일한 비트 위치에서 동시에 1을 가질 수 없기 때문입니다.
5단계 – 결과 출력(Output)
모든 처리가 끝나면 A, B, C, D 네 개의 워드가 순서대로 연결되어 최종 출력을 생성합니다. 메시지를 구성하는 전체 t개의 512비트 블록이 순차적으로 처리된 후, 마지막 라운드의 출력값이 곧 128비트 해시 결과, 즉 메시지 다이제스트(message digest)가 됩니다.
이렇게 생성된 128비트 다이제스트는 원본 데이터의 무결성 검증 등에 활용될 수 있습니다. 다만 MD5는 충돌(collision) 취약점이 발견된 이후 보안 목적으로는 권장되지 않으며, 현재는 SHA-256 같은 더 강력한 해시 알고리즘 사용이 권고됩니다.