166
5.
Xesh funksiya ma‘lumotlar strukturasi qoʻllaniladigan
sohalarga
qaysilar kiradi?
Mustaqil ishlash uchun masalalar:
1. C++ tilida xesh jadvallarni hosil qiling.
2. C++da xesh jadvallarning metodlarini qoʻllang
14-§. Xesh funksiya
Xesh funksiyalar
– ixtiyoriy uzunlikdagi kirish ma‘lumotini
chiqishda belgilangan uzunlikdagi xesh qiymatga aylantirib beruvchi bir
tomonlama funksiyalarga aytiladi. Xesh funksiyalar
kriptografiya va
zamonaviy axborot xavfsizligi sohasida ma‘lumotlarni toʻlaligini
tekshirishda foydalaniladi. Elektron toʻlov tizimlari protokollarida ham
istemolchi kartasi ma‘lumotlarini bank-emitentga toʻliq yetkazish uchun
foydalaniladi.
Xesh funksiya
– ixtiyoriy uzunlikdagi M-ma‘lumotni fiksirlangan
uzunlikga siqish yoki ikkilik sanoq sistemasi ifodalangan ma‘lumotlarni
fiksirlangan uzunlikdagi bitlar ko‗rinishidagi
qandaydir kombinatsiyasi
(svertkasi) deb ataluvchi funksiya.
Ta‟rif.
Xesh-funksiya deb, har qanday
h: X
Y
oson
hisoblanuvchi va
M –ma‘lumot uchun h(M) = H fiksirlangan
uzunlikga ega bo‗lgan funksiyaga aytiladi.
Berilgan M-ma‘lumotning h(M) –xesh
qiymatini topish uchun
avvalo ma‘lumot biror «m» -uzunlikdagi bloklarga ajratilib chiqiladi.
Agar M-ma‘lumot uzunligi «m» -ga karrali bo‗lmasa, u holda oxirgi
to‗lmay qolgan blok «m»- uzunlikga olindan kelishib olingan maxsus
usulda biror simvol yoki belgi (masalan ―0‖ yoki ―1‖) bilan to‗ldirilib
chiqiladi. Natijada hosil qilingan M-ma‘lumot bloklariga:
M= { M
1
, M
2
,.......M
n
)
quyidagicha siqishni (svertkani) hisoblash protsedurasi qo‗llaniladi:
H
0
=
,
H
i
= f ( M
i
, H
i-1
) , i =1,2,......n
167
h(M)= H
n
;
bu yerda
-qandaydir fiksirlangan boshlangʻich vektor.
Misol sifatida quyidagi keng tarqalgan:
f ( M
i
, H
i-1
) = E
k
( M
i
H
i-1
) i =1,2,......n
xesh-funksiyani keltirib o‗tish mumkin.
Bu yerda E-simmetrik shifrlash algoritmi (masalan DES, GOST
28147-87, AES –FIPS 197 va hakoza), k- esa shifrlash algoritmi maxfiy
kaliti, H
0
= 0,
- XOR (mod 2 bo‗yicha mos bitlarni qo‗shish) amali.
