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.
Do'stlaringiz bilan baham: |