3 Amaliy ish Mavzu: md5 xeshlash algoritmi

3 - Amaliy ish 

Mavzu: MD5 xeshlash algoritmi 

Kriptografiyada, xesh funksiya deb ixtiyoriy uzunlikdagi (bitlar yoki baytlar 

birliklarida)  ma’lumotni  biror  fiksirlangan  (belgilangan)  uzunlikdagi  (bitlar  yoki 

baytlar  birliklariga)  qiymatga  o’tkazib  beruvchi  funksiyaga  aytiladi.  Xesh 

funksiyalardan  amalda  statistik  tajribalar  o’tkazishda,  mantiqiy  qurilmalarni 

tekshirishda,  ma’lumotlar  bazasida  tez  qidirib  topish  algoritmlarini  yaratishda  va 

ma’lumotlar bazasidagi ma’lumotlarning butunligini tekshirishda foydalaniladi.  

Kriptografiyada  xesh  funksiyalardan  quyidagi  muammolarni  hal  qilishda 

foydalaniladi: 

- ma’lumotni uzatishda yoki saqlashda uning to’laligini nazorat qilish uchun; 

- ma’lumotning manbaini autentifikasiya qilish uchun. 

Ma’lumotlarni uzatishda yoki saqlashda ularning to’laligini nazoratlashda har 

bir ma’lumotning xesh qiymati (bu xesh qiymat  ma’lumotni autentifikasiya qilish 

kodi  yoki  “imitoqo’yish”-ma’lumot  bloklari  bilan  bog’liq  bo’lgan  qo’shimcha 

kiritilgan belgi deyiladi) hisoblaniladi va bu qiymat ma’lumot bilan birga saqlaniladi 

yoki  uzatiladi.  Ma’lumotni  qabul  qilgan  foydalanuvchi  ma’lumotning  xesh 

qiymatini hisoblaydi va uning xesh qiymati bilan solishtiradi. Agar taqqoslashda bu 

qiymatlar mos kelmasa, ma’lumot butunligi buzilganligini anglatadi.  

“Imitoqo’yish”lar  hosil  qilish  uchun  foydalaniladigan  xesh  funksiyalar 

nazorat yig’indisidan farqli ravishda ma’lumotni saqlash va uzatishda ro’y beradigan 

tasodifiy xatolarni aniqlabgina qolmasdan, raqib tomonidan qilingan aktiv hujumlar 

to’g’risida ham ogohlantiradi. Buzg’unchi xesh qiymatni osonlik bilan o’zi hisoblab 

topa  olmasligi  va  muvaffaqiyatli  imitasiya  qilishi  yoki  ma’lumotni  o’zgartira 

olmasligi uchun xesh funksiya buzg’unchiga ma’lum bo’lmagan maxfiy kalitga ega 

bo’lishi kerak. Bu maxfiy kalit faqatgina ma’lumotni uzatuvchi va qabul qiluvchi 

tomonlarga  ma’lum  bo’lishi  kerak.  Bunday  xususiyatga  ega  xesh  funksiyalarga 

kalitli xesh funksiyalar deyiladi.  

Kalitli  xesh  funksiyalar  yordamida  hosil  qilinadigan  “imitoqo’yish”lar 

imitasiya (impersonation) turidagi hujumlarda qalbaki ma’lumotlarni hosil qilishga 

(fabrication)  va  “o’zgartirish”  (substitution)  turidagi  hujumlarda  uzatiladigan 

ma’lumotni modifikasiya (modification) qilishga yo’l qo’ymaslikda foydalaniladi.  

Ma’lumot  manbaining  autentifikasiyalash  masalasi  axborot-kommunikasiya 

tizimlarining bir-biriga ishonmaydigan ikki tomoni orasida ma’lumot almashinuvida 

yuzaga keladi. Bu masalani hal qilishda ikkala tomon ham biladigan maxfiy kalitdan 

foydalanib bo’lmaydi. Bu holatda ma’lumotning manbaini autentifikasiya qilishga 

imkon  beradigan  elektron  raqamli  imzo  sxemasi  qo’llaniladi.  Bunda  odatda 

foydalanuvchining maxfiy kalitiga asoslangan imzo qo’yishdan oldin xatolik kodini 

aniqlovchi  xesh  funksiya  yordamida  ma’lumot  siqiladi.  Bu  holda  xesh  funksiya 

maxfiy  kalitga  ega bo’lmaydi  hamda  u  fiksirlangan bo’lishi  va  hammaga  ma’lum 

bo’lishi  mumkin.  Unga  qo’yilgan  asosiy  talab  imzolangan  hujjatni  o’zgartirish 

hamda  bir  xil  xesh  qiymatga  ega  bo’lgan  ikkita  har  xil  ma’lumotni  tanlash 

imkoniyati yo’qligining kafolatidir. Agar bir xil xesh qiymatga ega bo’lgan ikkita 

har xil ma’lumot mavjud bo’lsa, bu ma’lumotlar jufti kolliziya hosil qiladi deyiladi.  

YUqorida  keltirilganlarga  asoslanib,  quyidagi  ta’rif  kiritiladi.  M  orqali 

elementlari ma’lumotlardan iborat bo’lgan to’plam belgilanadi. Odatda ma’lumotlar 

biror  alfavitning,  ko’pincha  ikkilik  sanoq  sistemasi  simvollari  ketma-ketligidan 

iborat bo’ladi.  

Xesh  funksiya  deb,  ixtiyoriy  uzunlikdagi  M  ma’lumotni  fiksirlangan 

uzunlikdagi h(M)=H qiymatga akslantib beruvchi, oson hisoblanadigan bir tomonli 

funksiyaga aytiladi. 

Xesh qiymat: “xesh qiymat”, “svertka”, “daydjest”, “barmoq izlari” deb ham 

ataladi. 

Xesh funksiyaga nisbatan quyidagi talablar qo’yiladi:  

1.Ixtiyoriy uzunlikdagi matn uchun qo’llab bo’lishlik. 

2.CHiqishda belgilangan uzunlikdagi qiymatni berishlik. 

3.Ixtiyoriy berilgan x bo’yicha h(x) oson hisoblanishlik. 

4.Ixtiyoriy berilgan H bo’yicha h (x)= N tenglikdan x ni hisoblab topib 

bo’lmaslik. (Bir tomonlilik xususiyati) 

5.Olingan  x  va  y≠x  matnlar  uchun  h(x)≠  h(y)  munosabat  o’rinli 

bo’lishi. (Kolliziyaga bardoshlilik xususiyati).  

Kalitli  xesh  funksiyalardan  foydalanishda  ularga  quyidagi  asosiy  talablar 

qo’yiladi:  

- fabrikasiyaning imkoniyati yo’qligi;  

- modifikasiyaning imkoniyati yo’qligi.  

Birinchi talabga ko’ra, xesh qiymat berilganda unga mos bo’lgan ma’lumotni 

tanlashning  murakkab  bo’lishini  bildiradi.  Ikkinchi  talab  esa,  ma’lumot  va  uning 

xesh qiymati berilganda, xesh qiymati shunga teng bo’ladigan boshqa ma’lumotni 

tanlash murakkab bo’lishini anglatadi.  

MD 5 xesh funksiyasi. 

MD 5 xesh funksiyasi algoritmi Massachuses texnologiya instituti professori 

Ronal’d  Rivest  tomonidan  1992  yilda  ishlab  chiqilgan.  Bu  algoritmda  kiruvchi 

ma’lumot uzunligi ixtiyoriy bo’lib, xesh qiymat  zunligi 128 bit bo’ladi. MD 5 xesh 

funksiyasi algoritmida kiruvchi ma’lumot 512 bitlik bloklarga ajratilib, ular 16 ta 32 

bitlik qism bloklarga ajratiladi va bular ustida amallar bajariladi. 

Faraz qilaylik, bizga uzunligi b bit bo’lgan, bu erda b – ixtiyoriy nomanfiy 

butun son, ma’lumot berilgan bo’lsin va bu ma’lumotning bitlari  

m0 m1 … m(b-1) 

tartibda yozilgan bo’lsin. 

Xesh qiymatni hisoblash uchun quyidagi beshta bosqich bajariladi:  

1-bosqich. To’ldirish bitlarini qo’shish 

Berilgan ma’lumot uzunligi 512 modul bo’yicha 448 bilan taqqoslanadigan 

(ma’lumot  uzunligi 



  448  mod  512)  qilib  to’ldiriladi,  ya’ni,  kengaytirilgan 

ma’lumotning  uzunligi  unga  eng  yaqin  bo’lgan  512ga  karrali  bo’lgan  sondan  64 

bitga kichik bo’lishi kerak. To’ldirish hamma vaqt, hattoki ma’lumot uzunligi 512 

modul  bo’yicha  448  bilan  taqqoslanadigan  bo’lsa  ham  bajariladi.  To’ldirish 

quyidagi  tartibda  amalga  oshiriladi:  ma’lumotga  1  ga  teng  bo’lgan  bitta  bit 

qo’shiladi, qolgan bitlar esa 0 lar bilan to’ldiriladi. SHuning uchun qo’shilgan bitlar 

soni 1 dan 512 tagacha bo’ladi.  

2- bosqich. Ma’lumotning uzunligini qo’shish 

1-bosqichning  natijasiga  berilgan  ma’lumot  uzunligining  64  bitlik  qiymati 

qo’shiladi. Agar ma’lumotning uzunligi 

2

64

 bitdan katta bo’lsa, bu uzunlik mod 

2

64

 

bo’yicha  olinib  qo’shiladi.  SHunday  qilib,  birinchi  ikkita  bosqich  bajarilgandan 

keyin  uzunligi  512  bitga  karrali  bo’lgan  ma’lumot  olinadi,  ya’ni  kengaytirilgan 

ma’lumot  uzunligi  16  ta  32  bitlik  so’zdan  iborat  blok  uzunligiga  karrali  bo’ladi. 

Natijada hosil qilingan ma’lumotning so’zlarini M[0, ..., N-1] orqali belgilaymiz, u 

holda N soni 16 ga karrali bo’ladi. SHunday qilib, N=L



16 bo’ladi.  

Ushbu ikkita bosqichni quyidagicha tasvirlash mumkin:  

 

3- bosqich. Xesh qiymat uchun bufer inisializasiya qilish. 

Xesh  funksiyaning  oraliq  va  oxirgi  natijalarini  saqlash  uchun  128  bitlik 

buferdan foydalaniladi. Bu buferni to’rtta 32 bitlik A, B, C, D registrlar ko’rinishida 

tasvirlash mumkin. Bu registrlarga 16 lik sanoq sistemasida quyidagi boshlang’ich 

qiymatlar beriladi:  

A=0x01234567  

B=0x89ABCDEF  

C=0xFEDCBA98 

D=0x76543210 

4- bosqich. Ma’lumotni 512 bitlik bloklarga ajratib qayta ishlash. 

Argumenti va qiymati 32 bitlik so’z bo’ladigan to’rtta yordamchi funksiyani 

aniqlaymiz:  

F(X,Y,Z) = (X 



 Y) 



 ( 



 X 



 Z)  

G(X,Y,Z) = (X 



 Z) 



 (Y 



 



 Z)  

H(X,Y,Z) = X 



 Y 



 Z  

I(X,Y,Z) = Y 



 (X 



 



 Z) 

Bu  erda  bitlar  bo’yicha  mantiqiy  AND,  OR,  NOT,  XOR  amallari  mos 

ravishda 



 , 



 , 



 , 



 belgilari bilan ifodalangan.  

Bu  bosqichda  sinus  funksiyasi  asosida  64  ta  so’zdan  qurilgan  T[1,…,64] 

jadvaldan  foydalaniladi.  T[i]=[4294967296



abs(sin(i))]  bo’lib,  jadvalning  i–

elementini  ifodalaydi.  Bu  erda  [q]  ifoda  q  sonning  butun  qismini  bildiradi,  i  esa 

radianlarda ifodalangan.  

Ushbu bosqichda quyidagi amallar bajariladi:  

/* Har bir 16 so’zlik blok qayta ishlanadi. */  

for I = 0 to N/16 – 1 do  

/* i- blok X ga yozib olinadi. */  

For j = 0 to 15 do  

X[j] = M[i*16 + j] 

/*  A  ning  qiymati  AA  ga, B  ning  qiymati  BB  ga, C  ning  qiymati  CC  ga, D  ning 

qiymati DD ga yozib olinadi. */  

AA = A  

 

BB = B  

 

CC = C  

 

DD = D  

/* 1 -qadam. */  

/* [abcd k s i] ifoda quyidagi amalni bildiradi:  

a = b + ((a+ F(b,c,d) +X[k] +T[i]) <<< s). */ 

/* Quyidagi 16 ta amal bajariladi. */ 

[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] 

[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] 

[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] 

[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] 

/* 2-qadam. */ 

/* [abcd k s i] ifoda quyidagi amalni bildiradi: 

a = b+ ((a + H(b,c,d) +X[k] +T[i]) <<< s). */ 

/* Quyidagi 16 ta amal bajariladi.*/ 

[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] 

[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] 

[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] 

[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] 

/* 3-qadam. */ 

/* [abcd k s i] ifoda quyidagi amalni bildiradi: 

a = b + ((a + H(b,c,d)+ X[k] + T[i]) <<< s). */ 

/* Quyidagi 16 ta amal bajariladi.*/ 

[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]  

[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]  

[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] 

[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]  

/* 4-qadam. */  

/* [abcd k s i] ifoda quyidagi amalni bildiradi:  

a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */  

/* Quyidagi 16 ta amal bajariladi. */  

[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]  

[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]  

[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]  

[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]  

/* Quyidagi qo’shish amali bajariladi. */  

A = A + AA  

B = B + BB   

C = C + CC   

D = D + DD  

end /* I bo’yicha sikl */ 

 

5- bosqich. Natija. 

Ma’lumotning xesh qiymati A, B, C, D registrlardagi qiymatlarni birlashtirish 

natijasida hosil qilinadi. 

 

Foydalanilgan adabiyotlar 

1. 

Akbarov  D.E.  Axborot  xavfsizligini  ta’minlashning  kriptografik 

usullari va ularning qo’llanilishi. Toshkent, 2008 – 394 bet. 

2. 

G’aniev  S.  K.,  Karimov  M.  M.,  Tashev  K.  A.  Axborot  xavfsizligi. 

Axborot-kommunikasiya  tizimlar  xavfsizligi.  Oliy  o’quv  yurt  talabalari  uchun 

mo’ljallangan. “Aloqachi”, 2008.  

3. 

SHnayer  B.  Prikladnaya  kriptografiya  (Applied  Cryptography),  2-e 

izdanie. 1996 g.