54
ma‘lumotlar uchun xesh qiymatlari shulardan biriga teng bo‗ladigan
boshqa
ma‘lumotni tanlashning murakkabligini bildiradi.
Murakkab deganda, masalani real vaqt davomida
zamonaviy hisoblash
qurilmalaridan foydalanib hal qilish imkoniyati bo‗lmaydigan hisoblash jarayoni
tushuniladi.
Kalitli xesh funksiyalar bir-biriga ishonuvchi tomonlar o‗rtasida ishlatiladi va
ular umumiy maxfiy kalitga ega bo‗ladilar. Odatda bu sharoitda ikkinchi tomon
ma‘lumotni qabul qilib olganligini tan olmaslik yoki uni o‗zgartirish holatidan
axborot-kommunikatsiya tizimini himoya qilish talab qilinmaydi.
Shuning uchun
kalitli xesh funksiyalardan kolliziyalarga bardoshlilik talab qilinmaydi.
Kalitli xesh funksiyalarga ―imitatsiya‖ qilish, ya‘ni bo‗sh kanalda soxta
ma‘lumotni uzatish hamda uzatilayotgan ma‘lumotni soxta ma‘lumotga almashtirish
kabi hujumlar bo‗lishi mumkin.
Hisoblash bardoshliligi xossasidan xesh funksiyada qo‗llanilayotgan kalitni
aniqlash imkoniyati yo‗qligi kelib chiqadi, kalitni bilish esa ixtiyoriy ma‘lumotning
xesh qiymatini hisoblash imkonini beradi. Teskari tasdiq esa o‗rinli emas, chunki
ba‘zi hollarda kalitni
oldindan bilmasdan turib, xesh qiymatni tanlash mumkin.
Masalan, keng tarqalgan, bir qadamli siqish funksiyasi yordamida qurilgan quyidagi
ko‗rinishdagi xesh funksiyani korish mumkin:
bu yerda
– bloklab shifrlash algoritmi.
–ma‘lumotning
qiymatini hisoblash uchun ma‘lumot ketma-ket kelgan
bitli
– bloklar ko‗rinishida ifodalanadi. Agar ma‘lumot uzunligi
blokning uzunligiga karrali bo‗lmasa, oxirgi blok biror maxsus shaklda to‗liq
blokkacha to‗ldiriladi. Xesh qiymatni hisoblash algoritmi quyidagi ko‗rinishda
bo‗ladi:
(2)
Kalitli xesh funksiyalarni qurishning yana bir usuli kalitsiz xesh
funksiyalardan foydalanishdir. Bunda xesh qiymatni hisoblash uchun kalit berilgan
ma‘lumotga qo‗shib yozib qo‗yiladi. Agar kalit berilgan ma‘lumotning boshiga yoki
oxiriga to‗g‗ridan-to‗g‗ri qo‗shib qo‗yilsa, ba‘zi hollarda ma‘lumotni modifikatsiya
qilishga imkin berishi mumkin.
Masalan,
𝑘
kalit ma‘lumotning
boshiga
𝑘
formulaga asosan qo‗shib
qo‗yilgan bo‗lsin. Agar
funksiya (1) formulaga asosan bir qadamli siquvchi
funksiyalar yordamida qurilgan bo‗lsa, u holda
va
𝑘
larning ma‘lum
qiymatlari bo‗yicha biror
qo‗shib yozilgan
ko‗rinishdagi
ixtiyoriy
55
ma‘lumot uchun bu funksiyaning qiymatlarini hisoblash mumkin. Bu xesh
funksiyani hisoblashning iterativligi bilan izohlanadi, chunki
𝑘
qiymatni
topish uchun
𝑘
kalitning qiymatini bilish shart emas,
qiymatning
hisoblangan oraliq qiymatlaridan foydalanish yetarli. Shuning uchun bunday
funksiya modifikatsiyaga bardoshli emas.
Agar kalit ma‘lumotning oxiriga
𝑘
formulaga
asosan
qo‗shilgan bo‗lsa,
funksiya uchun kolliziyani , ya‘ni
bo‗ladigan
juftlikni bilish ixtiyoriy
𝑘
kalit uchun
𝑘
𝑘
qiymatni
hisoblash imkonini beradi. Shuning uchun
ma‘lumotni
modifikatsiya qilish
murakkabligi
𝑂
kattalik bilan emas, balki kolliziyalarni qidirish murakkabligi
bilan taqqoslanadi va
𝑂
bilan
baholanadi, chunki bu holda ―tug‗ulgan kun‖
paradoksiga asoslangan hujum o‗rinli bo‗ladi.
Dostları ilə paylaş: