Hash funkce MD5 (Message Digest 5)

MD5 (akronym anglického Message Digest) představuje tradiční hash algoritmus, který je dnes již postupně vytlačován modernějšími nástroji. Jeho výhoda je jednoduchost, nevýhoda je nízká bezpečnost (může být zlomen pomocí hrubé síly). Algoritmus představil Ron Rivest v roce 1991.

Princip

Algoritmus nejdříve provede úpravu vstupu do požadovaného formátu, následuje jeho zpracování.

Předzpracování

1. Na konec zprávy se přidá bit s hodnotou true (logická 1). Zpráva se dále rozdělí tak, aby byla rozdělena do bloků o velikosti 512 bitů (a to až na poslední blok, který má velikost 448 bitů).

2. Na konec zprávy se doplňují nuly tak, aby poslední blok měl velikost 448 bitů (pokud zpráva v posledním bloku přesahuje 448 bitů, přidá se logicky další blok).

3. V posledním bloku se do posledních 64 bitů zapíše velikost zprávy mod 2⁶⁴.

Vlastní algoritmus

Vlastní algoritmus se skládá z kroků, které jsou ilustrativně zobrazeny na obrázku výše. Celý algoritmus generování hash hodnoty je popsán v pseudokódu níže. V rámci algoritmu se pracuje s hodnotami zapsanými v little-endian:

//Využíváme 32 unsigned int typy (tj. integer bez znaménka)
var int[64] s, K
var int i

//s specifikuje posun (bitový) pro danou rundu
s[ 0..15] := { 7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22 }
s[16..31] := { 5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20 }
s[32..47] := { 4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23 }
s[48..63] := { 6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21 }

//Definujeme pole k, vstup funkce sinus je v radianech, abs značí absolutní hodnotu, floor je zaokrouhlení směrem dolu
for i from 0 to 63
    K[i] := floor(232 × abs(sin(i + 1)))
end for
//Ekvivalentně se může využít tabulka s předvypočtenými hodnotami:
K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be }
K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa }
K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

//Výchozí hodnoty proměnných A, B, C, D:
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

//První část předzpracování, přidání bitu s hodnotou 1 za vstup
přidej bit s hodnotou "1" bit na konec zprávy
// Vstup je považován za řetězec bitů, kde první bit je MSB prvního bajtu (logika little-endian)

//Druhá část předzpracování, doplnění nul do správného počtu (448 bitů pro poslední část)
přidej bity s hodnotou nula "0" na konec zprávy, dokud velikost zprávy v bitech mod 512 není rovna 448 (tj. velikost posledního bloku musí být 448 bitů)
posledních 64 bitů přepiš údajem o velikosti zprávy mod 2^64

//Zpracování 512 bitových bloků zprávy:
for each 512-bitový blok do:
    rozděl blok do šestnácti 32 bitových slov v poli M[j]
    //Inicializace vstupů
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
    //Hlavní smyčka funkce
    for i from 0 to 63
        var int F, g
        if 0 ≤ i ≤ 15 then
            F := (B and C) or ((not B) and D)
            g := i
        else if 16 ≤ i ≤ 31
            F := (D and B) or ((not D) and C)
            g := (5×i + 1) mod 16
        else if 32 ≤ i ≤ 47
            F := B xor C xor D
            g := (3×i + 5) mod 16
        else if 48 ≤ i ≤ 63
            F := C xor (B or (not D))
            g := (7×i) mod 16
        //Zde pozor na způsob přirazování!
        F := F + A + K[i] + M[g]
        A := D
        D := C
        C := B
        B := B + leftrotate(F, s[i]) //leftrotate značí rotaci doleva o s[i] bitů
    end for
    //Přidáváme blok do výsledku
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

//Tvorba výsledné hashe, append značí přidávání bitů ve formátu little-endian
var char digest[16] := a0 append b0 append c0 append d0

//funkce leftrotate je definována jako:
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));