Lehekülje MD5 lähteteksti vaatamine

{{Ajakohasta|kuu=detsember|aasta=2017}}
{{Lisa materjali}}
'''MD5''' (ingliskeelsest nimest '''Message Digest 5''') on levinud [[räsifunktsioon]], mille väljundiks on 128-[[bitt|bitine]] [[kontrollsumma]] (ingl. ''checksum''). MD5 kasutusala [[krüptograafia]]s on lai, enamasti kasutatakse seda andmete [[terviklus]]e kontrolliks.

[[Software Engineering Institute]] peab MD5-d "krüptograafiliselt murtuks ja edasiseks kasutuseks ebasobivaks".<ref name="ded" /> Tähelepanuväärne näide MD5 nõrgast turvalisusest on 2012. aastal levinud pahavara [[Flame (pahavara)|Flame]].

==Ajalugu==
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.<ref name="YBEXT" />

2004. aastal näidati, et MD5 ei ole [[Kollisioonikindlus|kollisioonikindel]], mis tõttu see ei sobi [[Transpordikihi turbeprotokoll|SSL sertifikaatide]] ega [[Digitaalne allkirjastamine|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 failipaar, millel on sama MD5 kontrollsumma.<ref name="7R1Xl" />

==Kasutusalad==
MD5 on juba pikemat aega olnud laialt kasutusel tarkvaramaailmas failide tervikluse kontrollimiseks, sest failide transpordil võib osa failist kaduma minna.

==Algoritm==
[[Pilt:MD5 algorithm.svg|pisi|300px|Kujutatud on üks MD5 operatsioon. MD5 koosneb 64st sellisest operatsioonist, mis on võrdselt jaotatud nelja etappi (16 operatsiooni igas etapis). <math>F</math> on mittelineaarne funktsioon. Igas etapis kasutatakse natuke erinevat funktsiooni. ''M<sub>i</sub>'' tähistab 32-bitist osa sisendi sõnumist ja ''K<sub>i</sub>'' tähistab 32-bitist konstanti, mis on erinev iga operatsiooni jaoks. [[Pilt:lll.png|Rotatsioon vasakule]]<sub><math>s</math></sub> tähistab vasakut biti rotatsiooni <math>s</math> võrra ning see on erinev iga operatsiooni jaoks. [[Pilt:Boxplus.png|Liitmine]] tähistab liitmist, mille tulemusest võetakse modulo 2<sup>32</sup>.]]
Sõnum jagatakse 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 <math>A, B, C, D</math> 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:
:<math>\begin{align}
F(B,C,D) &= (B\wedge{C}) \vee (\neg{B} \wedge{D}) \\
G(B,C,D) &= (B\wedge{D}) \vee (C \wedge \neg{D}) \\
H(B,C,D) &= B \oplus C \oplus D \\
I(B,C,D) &= C \oplus (B \vee \neg{D})
\end{align}
</math>

<math>\oplus</math> – [[Välistav disjunktsioon]] (XOR)

<math>\wedge</math> – [[Konjunktsioon]] (AND)

<math>\vee</math> – [[Disjunktsioon]] (OR)

<math>\neg</math> – [[Eitus]] (NOT)

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

 <span style="color:green;">//''Kõik muutujad on 32-bitised''</span>
 '''var''' ''int''[64] s, K
 
 <span style="color:green;">//''s kirjeldab iga etapi jaoks vajalikke bitijada nihete suurusi''</span>
 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 }
 
 <span style="color:green;">//''Konstantide massiiv on defineeritud järgnevate funktsioonide kombinatsioonina:''</span>
 '''for''' i '''from''' 0 '''to''' 63
     K[i] := floor(2<sup>32</sup> × abs(sin(i + 1)))
 '''end for'''
 <span style="color:green;">//''(Võib ka kasutada juba väljaarvutatud väärtusi):''</span>
 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 }
 
 <span style="color:green;">//''Registrite algväärtused''</span>
 '''var''' ''int'' a0 := 0x67452301   <span style="color:green;">//A</span>
 '''var''' ''int'' b0 := 0xefcdab89   <span style="color:green;">//B</span>
 '''var''' ''int'' c0 := 0x98badcfe   <span style="color:green;">//C</span>
 '''var''' ''int'' d0 := 0x10325476   <span style="color:green;">//D</span>
 
 <span style="color:green;">//''Lisatakse üksik "1" bitt''</span>
 '''append''' "1" bit '''to''' message</span><span style="color:green;"></span>
 
 <span style="color:green;">//''Lisatakse lõppu "0" bitid''</span>
 '''append''' "0" bit '''until''' message length in bits ≡ 448 (mod 512)
 '''append''' original length in bits '''mod''' (2 '''pow''' 64) '''to''' message</span>
 
 <span style="color:green;">//''Töötle sõnumit 512-bitiste "tükkidena":''</span>
 '''for each''' ''512-bit'' chunk '''of''' message
     break chunk into sixteen 32-bit words M[j], 0 ≤ j ≤ 15
 <span style="color:green;">//''Räsi algväärtus selle "tüki" jaoks:''</span>
     '''var''' ''int'' A := a0
     '''var''' ''int'' B := b0
     '''var''' ''int'' C := c0
     '''var''' ''int'' D := d0
 <span style="color:green;">//''Põhitsükkel:''</span>
     '''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'''
 <span style="color:green;">//''Liida selle "tüki" räsi lõpptulemusele:''</span>
     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 <span style="color:green;">//''(Väljund on little-endian)''</span>
 
 <span style="color:green;">//''Rotatsiooni funktsiooni definitsioon''</span>
 '''leftrotate''' (x, c)
     '''return''' (x << c) '''binary or''' (x >> (32-c));

==Näited==
MD5 räsi pikkus on olenemata sisendi suurusest 128 bitti. 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==
{{viited|allikad=
<ref name="YBEXT">{{Netiviide |pealkiri=Arhiivikoopia |url=https://www.ria.ee/public/PKI/kruptograafiliste_algoritmide_elutsukli_uuring_II.pdf |vaadatud=2016-01-28 |arhiivimisaeg=2016-04-26 |arhiivimisurl=https://web.archive.org/web/20160426200703/https://www.ria.ee/public/PKI/kruptograafiliste_algoritmide_elutsukli_uuring_II.pdf |url-olek=ei tööta }}</ref>
<ref name="7R1Xl">http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf</ref>
<ref name="ded">https://www.kb.cert.org/vuls/id/836068</ref>
}}

[[Kategooria:Algoritmid]]
[[Kategooria:Krüptograafia]]