MD4
Из пројекта Википедија
MD4 (Message-Digest algorithm 4) алгоритам је хаш функција, која за улазни текст даје излаз фиксне величине - 128 битова. Мала промјена у улазним подацима резултират ће значајним променама на излазу. MD4 се сматрао сигурним, јер је захтевао огромну количину процесорске снаге да се пронађе улазни низ који за излаз даје неки познати хаш. Другим речима - не постоји начин да се декриптира излаз. Но с временом су му пронађени недостаци, те уместо њега (и верзије MD5) радије користи SHA-1 алгоритам који резултира 160-битним излазом.
Садржај |
[уреди] Настанак алгоритма
Аутор MD4 је професор са МИТ-а Роналд Ривест, такође и аутор алгоритама MD2 и MD5. MD2 је прилагођен извођењу на 8-битним процесорима док су MD4 и MD5 дизајнирани за 32-битне процесоре. MD4 настао је 1990. године и најбржи је међу њима. Показао се непоузданим и зато га је наслиедио MD5 који је врло сличан MD4 али има неке додатне функције које га чине споријим, али зато пуно сигурнијим. На основама MD4 настали су следећи алгоритми: MD5,SHA-1,RIPEMD.
[уреди] Опис алгоритма
Претпоставимо да имамо поруку дужине б бита.
[уреди] Корак 1.
Порука се прошири тако да је њена дужина у битовима плус 64 дељива са 512. Порука се увијек продужује, чак и кад је услов дељивости већ задовољен. То се врши на слиједећи начин : Један бит вриедности "1" додамо на крај поруке, а затим додајемо "0" све док дужина поруке плус 64 бита није дељива са 512. Свеукупно можемо додати најмање један и највише 512 битова.
[уреди] Корак 2.
Дужину оригиналне поруке (тј. поруке пре него штп смо је проширили) б прикажемо са 64 бита и тај број додамо на крај проширене поруке коју смо добили у прошлом кораку. Ако би оригинална порука била дужа од 264 знакова тада се на крај поруке додаје само нижих 64 бита. Битови се додају као две 32-битне речи тако да се прво дода реч која садржи ниже битове, а затим реч која садржи више битове. У овом тренутку дужина поруке је 16 32-битних речи. Означимо сада сваку поједину реч са
M[0 ... N-1]
где је N садржалац 16.
[уреди] Корак 3. Иницијализација МД бaфера
Бафер дужине 4 речи (А, B, C, D) се користи за израчунавање сажетка поруке. A,B,C,D су 32-битни регистри са следећим почетним вредностима заданим хекsадецимално (најмање важан октет је А, најважнији је D).
word A: 01 23 45 67 word B: 89 AB CD EF word C: FE DC AB 98 word D: 76 54 32 10
[уреди] Корак 4. Процесирање поруке у блоковима од 16 речи
Прво дефинишемо три помоћне функције тако да свака користи као улаз 3 речи дужине 32 бита као излаз дају једну реч дужине 32 бита.
F(X,Y,Z) = XY v not(X) Z G(X,Y,Z) = XY v XZ v YZ H(X,Y,Z) = X xor Y xor Z
Функција F се понаша као условна функција: ако X онда Y иначе Z. Функција G се понаша као већинска функција : ако било која 2 улаза x,y или z на некој бит позицији имају '1' онда ће и излаз на тој позицији имати '1'. Функција Х је XOR функција са својствима сличним функцијама F и G.
Након тога извршимо следећи псеудокод :
// procesiraj svaki blok poruke
za i=0 do (N/16-1) čini
// kopiraj blok i u X
za j=0 do 15 čini
X[j] = m[i*16+j]
kraj
// sačuvaj A,B,C,D
AA=A
BB=B
CC=C
DD=D
// 1. KRUG
// označimo sa [abcd k s] operaciju:
// a = (a + F(b,c,d) + X[k]) <<< s
// '<<<s' je rotacija u levo za s bitova
[ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]
[ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19]
[ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19]
[ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]
// 2. krug
// označimo sa [abcd k s] operaciju:
// a = (a + G(b,c,d) + X[k] + 5A827999) <<< s
[ABCD 0 3] [DABC 4 5] [CDAB 8 9] [BCDA 12 13]
[ABCD 1 3] [DABC 5 5] [CDAB 9 9] [BCDA 13 13]
[ABCD 2 3] [DABC 6 5] [CDAB 10 9] [BCDA 14 13]
[ABCD 3 3] [DABC 7 5] [CDAB 11 9] [BCDA 15 13]
// 3. krug
// označimo sa [abcd k s] operaciju:
// a = (a + H(b,c,d) + X[k] + 6ED9EBA1) <<< s
[ABCD 0 3] [DABC 8 9] [CDAB 4 11] [BCDA 12 15]
[ABCD 2 3] [DABC 10 9] [CDAB 6 11] [BCDA 14 15]
[ABCD 1 3] [DABC 9 9] [CDAB 5 11] [BCDA 13 15]
[ABCD 3 3] [DABC 11 9] [CDAB 7 11] [BCDA 15 15]
// na kraju svaki registar uvećamo sa vrijedošću koju je
// imao pre izvršenja ovog bloka programa
A = A + AA
B = B + BB
C = C + CC
D = D + DD
//kraj
[уреди] Пример
Пример примене MD4 алгоритма. Реченицу у ASCII формату "The quick brown fox jumps over the lazy dog" пустићемо кроз MD4 алгоритам и добићемо 128-битни излаз у хексадецималном облику
MD4("The quick brown fox jumps over the lazy dog") = 1bee69a46ba811185c194762abaeae90
Чак и најмања промена тип једног слова у реченици имаће као резултат промену хексадецималног излаза. На пример променићемо d у c:
MD4("The quick brown fox jumps over the lazy cog") = b86e130ce7028da59e672d56ad0113df
Излаз МД4 функције у случају празног стринга биће:
MD4("") = 31d6cfe0d16ae931b73c59d7e0c089c0
