Mirzo ulug’bek nomidagi

Kalitli xesh funksiyalar va ularning xossalari

Kalitli xesh funksiyalarni qo‘llashda ularga quyidagi asosiy talablar qo‘yiladi:

• 
  fabrikatsiya imkoniyatining mavjud emasligi;
  
• 
  modifikatsiyaning imkoniyati yo‘qligi.
  

Birinchi talab xesh qiymat berilganda unga mos bo‘lgan ma’lumotni tanlashning murakkab bo‘lishini bildiradi. Ikkinchi talab ma’lumot va uning xesh qiymati berilganda, xesh qiymati shunga teng bo‘ladigan boshqa ma’lumotni tanlash murakkab bo‘lishini bildiradi.
Ba’zan, bu ikkita xossani bitta kuchliroq xossaga – hisoblash bardoshliligi
xossasiga birlashtiriladi. Bu talab xesh qiymatlari ma’lum bo‘lgan berilgan

х₁ , х₂ ,…, х_l 
ma’lumotlar uchun xesh qiymatlari shulardan biriga teng bo‘ladigan

^boshqa х,
х  х_i ,


i  1, l
ma’lumotni tanlashning murakkabligini bildiradi.

Murakkab deganda, masalani real vaqt davomida zamonaviy hisoblash qurilmalaridan foydalanib hal qilish imkoniyati bo‘lmaydigan hisoblash murakkabligi 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 qalbaki ma’lumotni uzatish hamda uzatilayotgan ma’lumotni qalbaki 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 imkoniyatini beradi. Teskari tasdiq esa o‘rinli emas, chunki ba’zi bir hollarda kalitni oldindan bilmasdan turib, xesh qiymatni tanlash mumkin.
Misol uchun, keng tarqalgan, bir qadamli siqish funksiyasi yordamida qurilgan quyidagi ko‘rinishdagi xesh funksiyani ko‘rish mumkin:

k k
f (x, H )  E (x  H ) ^,



k
^{bu erda} E <sup>–bloklab shifrlash algoritmi.


M -ma’lumotning</sup> h(M ) ^{qiymatini hisoblash uchun ma’lumot ketma-ket}

kelgan m bitli
M₁ , M ₂ ,…, M _N
-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:

H₀  0,
H_i  E_k (M_i  H_i1 ),
h(M )  H_N .


i  1,…, N,

(6.1)

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 imkon berishi mumkin.

Masalan, k kalit ma’lumotning boshiga