[ Pobierz całość w formacie PDF ]
Algorytmhaszuj¡cyMD5
PodobniejakDES,algorytmhaszuj¡cyMD5zostałopublikowanyprzezR.Rivestabezpodania
argumentów,uzasadniaj¡cychmatematycznie,»emo»eonpełni¢funkcj¦dobrejjednokierunkowej
funkcjiskrótu.Wej±ciemalgorytmujestkomunikat
M
opraktyczniedowolnejdługo±ci,awyj±ciem
128-bitowyskrót,czyliwyci¡gtegokomunikatu.Przetwarzaniekomunikatunaskrótodbywasi¦
w4krokach.Danewka»dymkrokuprzetwarzasi¦w512-bitowychblokach,podzielonychna16
podblokówpo32bity.
•
Krok1
.Wiadomo±¢dopełniasi¦dodatkowymibitamiwtakisposób,byjejdługo±¢byłao
64bitykrótszaodwielokrotno±ci512bitów.Dodatkowebitydodajesi¦nawetwówczas,gdy
warunekpowy»szyjestspełniony,tzn.gdy
K
448(mod512),gdzie
K
oznaczapierwotn¡
długo±¢komunikatu.Wtakiejsytuacjidopełnieniemadługo±¢od1do512bitów.Ustalono,
»euzupełniaj¡cebityrozpoczynajedynka,poktórejnast¦puj¡samezera.
•
Krok2
.Powykonaniuczynno±ci,podanychw1.kroku,douzupełnionegokomunikatudo-
dajesi¦64bity,którereprezentuj¡liczb¦
K
,czylidługo±¢pierwotn¡komunikatu
M
.Je±li
pocz¡tkowadługo±¢komunikatujestwi¦kszaod2
64
,toliczb¦,okre±laj¡c¡pierwotn¡długo±¢
komunikatuobliczasi¦modulo2
64
.Wrezultacietejczynno±ciotrzymasi¦
L
512-bitowych
bloków
Y
0
,Y
1
,,...,Y
L
−
1
,zktórychka»dymo»napodzieli¢na16podbloków32-bitowych,
poniewa»512=16
·
32.
•
Krok3
.Operacje,realizowaneprzezalgorytmMD5,polegaj¡namodyfikacjiwarto±ciczte-
rechzmiennych
A,B,C
i
D
,zapami¦tanychw4rejestrach32-bitowych.Wkroku3.
zmiennymtymnadajesi¦nast¦puj¡cewarto±cipocz¡tkowe,zapisanewkodzieszesnastko-
wym:
A
=
01234567
,
B
=
89abcdef
,
C
=
fedcba98
,
D
=
76543210
.
•
Krok4
.Wtymkrokuu»ywasi¦czterechfunkcjipomocniczych,którychargumentamis¡
trzy32-bitowesłowa,awyj±ciemjednosłowo32-bitowe.S¡tonast¦puj¡cefunkcje:
1
2
F
(
X,Y,Z
)=(
X
and
Y
)or((not
X
)and
Z
)
,
(1)
G
(
X,Y,Z
)=(
X
and
Z
)or(
Y
and(not
Z
))
,
(2)
H
(
X,Y,Z
)=
X
xor
Y
xor
Z,
(3)
I
(
X,Y,Z
)=
Y
xor(
X
or(not
Z
))
.
(4)
Funkcjetedziałaj¡oczywi±cienaodpowiadaj¡cychsobiebitachbloków
X,Y,Z
zgodniez
tablic¡:
xyzFGHI
000 0 0 0 1
001 1 0 1 0
010 0 1 1 0
011 1 0 0 1
100 0 0 1 1
101 0 1 0 1
110 1 1 0 0
111 1 1 1 0
Wtymkrokustosujesi¦równie»64-elementow¡tablic¦
T
[1..64],którejelementyzawieraj¡
podaneni»ejliczbycałkowite,przedstawionewzapisieszesnastkowym:
T[1]=d76aa478T[2]=e8c7b756T[3]=242070dbT[4]=c1bdceee
T[5]=f57c0fafT[6]=4787c62aT[7]=a8304613T[8]=fd469501
T[9]=698098d8T[10]=8b44f7afT[11]=ffff5bb1T[12]=895cd7be
T[13]=6b901122T[14]=fd987193T[15]=a679438eT[16]=49b40821
T[17]=f61e2562T[18]=c040b340T[19]=265e5a51T[20]=e9b6c7aa
T[21]=d62f105dT[22]=02441453T[23]=d8a1e681T[24]=e7d3fbc8
T[25]=21e1cde6T[26]=c33707d6T[27]=f4d50d87T[28]=455a14ed
T[29]=a9e3e905T[30]=fcefa3f8T[31]=676f02d9T[32]=8d2a4c8a
T[33]=fffa3942T[34]=8771f681T[35]=6d9d6122T[36]=fde5380c
T[37]=a4beea44T[38]=4bdecfa9T[39]=f6bb4b60T[40]=bebfbc70
T[41]=289b7ec6T[42]=eaa127faT[43]=d4ef3085T[44]=04881d05
T[45]=d9d4d039T[46]=e6db99e5T[47]=1fa27cf8T[48]=c4ac5665
T[49]=f4292244T[50]=432aff97T[51]=ab9423a7T[52]=fc93a039
T[53]=655b59c3T[54]=8f0ccc92T[55]=ffeff47dT[56]=85845dd1
T[57]=6fa87e4fT[58]=fe2ce6e0T[59]=a3014314T[60]=4e0811a1
T[61]=f7537e82T[62]=bd3af235T[63]=2ad7d2bbT[64]=eb86d391
Warto±cielementówtablicy
T
wyznaczasi¦zwzoru
T
[
i
]=2
32
·|
sin(
i
)
|
=4294967296
·|
sin(
i
)
|
,
gdzieargument
i
podanyjestwradianach.
Niech
M
[0
,
1
,...,N
−
1]oznacza32-bitowesłowauzupełnionegokomunikatu,składaj¡cego
si¦z
L
512-bitowychbloków.Wobectego
N
=16
·
L
,czylika»dyblok
Y
q
składasi¦z16słów
M
[
j
],
j
=0
,
1
,...,
15.Procesprzetwarzaniawtymkrokuobejmujeka»dyblok16-słowowy
Y
q
iprzebieganast¦puj¡co:
3
forq:=0toL-1do
forj:=0to15doX[j]:=M[16*q+j];
{kopiowaniekolejnegosłowadotablicyX}
AA:=A;BB:=B;CC:=C;DD:=D;
{zapami¦taniepocz¡tkowychwarto±cirejestrówABCD}
{Etap1.
Niech[abcdksi]oznaczawykonanieoperacji
a=b+((a+F(b,c,d)+X[k]+T[i])<<<s).
Symbol(B)<<<soznaczasłowo32-bitowe,otrzymaneprzezcykliczne
przesuni¦ciesłowaBosmiejscwlewo,zmiennea,b,cidoznaczaj¡
te»słowa32-bitowe,Fjestfunkcj¡,okre±lon¡wzorem(5.2),T-wspo-
mnian¡wcze±niejtablic¡.Działanie+oznaczadodawaniesłów
32-bitowychbezprzeniesie«(dodawaniemodulo2^32).
Wykona¢16nast¦puj¡cychoperacji:}
[ABCD071][DABC1122][CDAB2173][BCDA3224]
[ABCD475][DABC5126][CDAB6177][BCDA7228]
[ABCD879][DABC91210][CDAB101711][BCDA112212]
[ABCD12713][DABC131214][CDAB141715][BCDA152216]
(Etap2.
Niech[abcdksi]oznaczawykonanieoperacji
a=b+((a+G(b,c,d)+X[k]+T[i])<<<s).
Gjestfunkcj¡,okre±lon¡wzorem(5.3),pozostałeoznaczenia
jakwetapie1.
Wykona¢16nast¦puj¡cychoperacji:}
[ABCD1517][DABC6918][CDAB111419][BCDA02020]
[ABCD5521][DABC10922][CDAB151423][BCDA42024]
[ABCD9525][DABC14926][CDAB31427][BCDA82028]
[ABCD13529][DABC2930][CDAB71431][BCDA122032]
(Etap3.
Niech[abcdksi]oznaczawykonanieoperacji
a=b+((a+H(b,c,d)+X[k]+T[i])<<<s).
Hjestfunkcj¡,okre±lon¡wzorem(5.4),pozostałeoznaczenia
jakwetapie1.
Wykona¢16nast¦puj¡cychoperacji:}
[ABCD5433][DABC81134][CDAB111635][BCDA142336]
[ABCD1437][DABC41138][CDAB71639][BCDA102340]
[ABCD13441][DABC01142][CDAB31643][BCDA62344]
[ABCD9445][DABC121146][CDAB151647][BCDA22348]
(Etap4.
Niech[abcdksi]oznaczawykonanieoperacji
a=b+((a+I(b,c,d)+X[k]+T[i])<<<s).
4
Ijestfunkcj¡,okre±lon¡wzorem(5.5),pozostałeoznaczenia
jakwetapie1.
Wykona¢16nast¦puj¡cychoperacji:}
[ABCD0649][DABC71050][CDAB141551][BCDA52152]
[ABCD12653][DABC31054][CDAB101555][BCDA12156]
[ABCD8657][DABC151058][CDAB61559][BCDA132160]
[ABCD4661][DABC111062][CDAB21563][BCDA92164]
{Obliczenienowejwarto±cirejestrówABCD(dodawaniemodulo2^32):}
A:=AA+A;B:=BB+B;C:=CC+C;D:=DD+D;
{koniecp¦tlij}
{koniecp¦tliq}
Wyj±ciemalgorytmujest128-bitowyskrótkomunikatu
M
,czylizawarto±¢rejestrów
ABCD
.
AlgorytmMD5jestłatwydozrealizowanianaprocesorach32-bitowych,aobliczeniaskrótu
trwaj¡bardzokrótko.Byłonszczegółowozbadanyzpunktuwidzeniaodporno±cinakryptoanaliz¦
iuzyskałbardzodobr¡ocen¦.
[ Pobierz całość w formacie PDF ]