A função hash de mão única MD4 foi projetada por Ron Rivest e publicada oficialmente pela primeira vez em outubro de 1990. O algoritmo usa como entrada uma mensagem de comprimento arbitrário e produz uma "impressão digital" ou um "digesto de mensagem" de 128 bits. MD vem de message digest, cuja tradução pode parecer estranha, mas é digesto de mensagem. Um digesto é uma compilação de diretrizes ou uma coleção de decisões, geralmente aplicado como termo jurídico

O MD4 foi criado para ser utilizado em assinaturas digitais onde um texto longo precisa ser "comprimido" de forma segura antes de ser cifrado com uma chave privada (secreta) por um criptossistema de chave pública. Foi projetado para ser bastante rápido em máquinas de 32 bits. Além disso, não necessita de grandes tabelas de substituição e pode ser facilmente programado de forma compacta. O autor colocou o algoritmo no domínio público.

Descrição do algoritmo MD4

A entrada do MD4 é uma mensagem que pode ter qualquer comprimento, ou seja, qualquer mensagem com um número arbitrário de bits. O número de bits, representado por b, é um número inteiro positivo que varia de zero até o infinito. Para obter o digesto da mensagem, seus bits, representados por m₀, m₁, ..., m_{b-1}, onde b = número de bits da mensagem, são submetidos a diversas operações. Este processo é dividido em cinco etapas ou passos.

Passo 1: Adição de bits

A mensagem é "esticada" com a adição de bits até que atinja um comprimento congruente com 448 no módulo 512, ou seja, adiciona-se tantos bits quantos forem necessários para que o comprimento da mensagem seja 448 ou qualquer múltiplo de 512 menos 64 bits (512 - 64 = 448, 1024 - 64 = 960, etc). Esta adição pressupõe a inclusão de no mínimo um bit e, no máximo, de 512 bits.

O primeiro bit que deve ser adicionado logo no final da mensagem original é um bit "1". Todos os outros, necessários para se atingir o comprimento preconizado, são bits "0".

Passo 2: Incluir comprimento

O valor b, que representa o comprimento em bits da mensagem original, deve ser adicionado à mensagem previamente preparada no passo 1 na forma de 64 bits. É pouco provável que o valor de b seja maior do que 2⁶⁴, porém, caso isto ocorra, apenas os 64 bits menos significativos de b serão usados. Estes 64 bits são adicionados como dois words de 32 bits. O word menos significativo é inserido primeiro, seguido do word mais significativo.

Neste ponto, o comprimento da mensagem resultante é 512 ou um dos seus múltiplos. Também é um múltiplo exato de 16 words pois, se um word possui 32 bits, 16 words possuem 16 x 32 = 512 bits. Estes words podem ser representados por M[0, 1, ..., N-1], onde N é um múltiplo de 16.

Passo 3: Inicialização do buffer MD

Um buffer de quatro words é usado para calcular o digesto da mensagem. Os registradores de 32 bits A, B, C e D são inicializados com os seguintes valores hexadecimais:

     word A: 01 23 45 67
     word B: 89 ab cd ef
     word C: fe dc ba 98
     word D: 76 54 32 10

Nestes valores, os bytes mais significativos são colocados após os menos significativos, ou seja

        Hexadecimal                    Binário                       Decimal
        -----------    ---------------------------------------    -------------
     A: 67 45 23 01    0110 0111 0100 0101 0010 0011 0000 0001    1.732.584.193
     B: ef cd ab 89    1110 1111 1100 1101 1010 1011 1000 1001    4.023.233.417
     C: 98 ba dc fe    1001 1000 1011 1010 1101 1100 1111 1110    2.562.383.102
     D: 10 32 54 76    0001 0000 0011 0010 0101 0100 0111 0110      271.733.878