MD5

Allikas: Vikipeedia

MD5 (inglisekeelsest Message Digest 5) on levinud räsifunktsioon, mille väljundiks on 128-bitine kontrollsumma (inglise checksum). MD5 kasutusalad krüptograafias on laiad, kuid enamasti kasutatakse seda andmete tervikluse kontrolliks.

Ajalaugu[muuda | muuda lähteteksti]

MD5 lõi 1991. aastal Ronald Rivest, et asendada varasem räsifunktsioon MD4.

1996. aastal leiti viga MD5 disainis. Kuigi tol ajal ei peetud seda saatuslikuks, soovitasid krüptograafid teiste räsifunktsioonide kasutamist, näiteks SHA-1, milles hiljem avastati samuti vigu.[1] 2004. aastal näidati, et MD5 ei ole kollisioonikindel, mis tõttu see ei sobi SSL sertifikaatide ega digiallkirjade loomiseks. Samal aastal leiti MD5s veelgi suuremaid vigu, mis seadis algoritmi turvalisuse küsimärgi alla, kui professor Wangi töörühm kirjeldas, kuidas luua failide paar, millel on sama MD5 kontrollsumma.[2]

Kasutusalad[muuda | muuda lähteteksti]

MD5 on juba pikemat aega olnud laialt kasutusel tarkvaramaailmas, kus seda kasutatakse failide tervikluse kontrollimiseks, sest failide transpordil võib osa failist kaduma minna. Turvalisuse huvides saab võrrelda allalaaditud faili MD5 kontrollsummat originaalse faili kontrollsummaga. Kuna kõige väiksemgi erinevus failis muudab kontrollsummat oluliselt, on see tõhus meetod faili vigasuse kontrollimiseks.

Algoritm[muuda | muuda lähteteksti]

Kujutatud on üks MD5 operatsioon. MD5 koosneb 64st sellisest operatsioonist, mis on võrdselt jaotatud nelja etappi (16 operatsiooni igas etapis). on mittelineaarne funktsioon. Igas etapis kasutatakse natuke erinevat funktsiooni. Mi tähistab 32-bitist osa sisendi sõnumist ja Ki tähistab 32-bitist konstanti, mis on erinev iga operatsiooni jaoks. Rotatsioon vasakule tähistab vasakut biti rotatsiooni võrra ning see on erinev iga operatsiooni jaoks. Liitmine tähistab liitmist, mille tulemusest võetakse modulo 232.

Sõnum jagatakse ära 512-bitisteks tükkideks, millele lisatakse lõppu üksik "1" bitt ning seejärel lisatakse "0" bitte, kuni sõnumi pikkus bittides on 64 bitti vähem kui 512 kordne arv. Ülejäänud 64 bitti täidetakse bitijadaga, mis vastab originaalse sisendi pikkusele baitides.

MD5 põhialgoritm opereerib neljal 32-bitisel registril, mida tähistatakse tähtedega ning millel on kindlad algväärtused. Seejärel kasutatakse igat 512-bitist sõnumi osa, et modifitseerida registrite väärtusi. Ühe sõnumi osa töötlemine jaotakakse ära neljaks sarnaseks etapiks, kus iga etapp koosneb kuueteistkümnest operatsioonist. Igal etapil kasutatakse natuke erinevat funktsiooni operatsioonides. Need funktsioonid on järgnevad:

Välistav disjunktsioon (XOR)

Konjunktsioon (AND)

Disjunktsioon (OR)

Eitus (NOT)

Järgnev pseudokood näitab üht viisi, kuidas implementeerida MD5 algoritm.

//Kõik muutujad on 32-bitised
var int[64] s, K

//s kirjeldab iga etapi jaoks vajalikke bitijada nihete suurusi
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 }

//Konstantide massiiv on defineeritud järgnevate funktsioonide kombinatsioonina:
for i from 0 to 63
    K[i] := floor(232 × abs(sin(i + 1)))
end for
//(Võib ka kasutada juba väljaarvutatud väärtusi):
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 }

//Registrite algväärtused
var int a0 := 0x67452301   //A
var int b0 := 0xefcdab89   //B
var int c0 := 0x98badcfe   //C
var int d0 := 0x10325476   //D

//Lisatakse üksik "1" bitt
append "1" bit to message

//Lisatakse lõppu "0" bitid
append "0" bit until message length in bits ≡ 448 (mod 512)
append original length in bits mod (2 pow 64) to message

//Töötle sõnumit 512-bitiste "tükkidena":
for each 512-bit chunk of message
    break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
//Räsi algväärtus selle "tüki" jaoks:
    var int A := a0
    var int B := b0
    var int C := c0
    var int D := d0
//Põhitsükkel:
    for i from 0 to 63
        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
        dTemp := D
        D := C
        C := B
        B := B + leftrotate((A + F + K[i] + M[g]), s[i])
        A := dTemp
    end for
//Liida selle "tüki" räsi lõpptulemusele:
    a0 := a0 + A
    b0 := b0 + B
    c0 := c0 + C
    d0 := d0 + D
end for

var char digest[16] := a0 append b0 append c0 append d0 //(Väljund on little-endian)

//Rotatsiooni funktsiooni definitsioon
leftrotate (x, c)
    return (x << c) binary or (x >> (32-c));

Näited[muuda | muuda lähteteksti]

MD5 räsi pikkus on alati 128 bitti mistahes suurusega sisendi puhul. Tavaliselt kujutatakse MD5 räsisid 32 kuueteistkümnendsüsteemi numbriga. Järgnevad sisendid on ASCII kujul:

MD5("Kui Arno isaga koolimajja jõudis, olid tunnid juba alanud") =
26aada48a686c4cb16e294ecd4fdaf6c

Isegi väike muudatus muudab räsi täielikult.

MD5("Kui Arno isaga koolimajja jõudis, olid tunnid juba alanud.") =
74b9efe7c90c35e08e84e6c9eca590a9

Ka tühja sisendi jaoks on olemas räsi.

MD5("") = 
d41d8cd98f00b204e9800998ecf8427e

Viited[muuda | muuda lähteteksti]