Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Shakl 14.2.

O'ng tarafdagi uchta ustun chap tomonda ko'rsatilgan 16 bitli tugmachalarni quyidagi funktsiyalardan foydalanib yutish natijasini ko'rsatadi:

v% 97 (chapda)

v% 100 (markazda) va

(int) (a * v)% 100 (o'ngda),

bu erda a \u003d .618033. Ushbu funktsiyalar uchun jadval o'lchamlari mos ravishda 97, 100 va 100 bo'lib, qiymatlar tasodifiy ko'rinadi (chunki tugmalar tasodifiydir). Ikkinchi funktsiya (v% 100) faqat ikkita tugmachaning o'ng raqamlaridan foydalanadi va shuning uchun tasodifiy bo'lmagan tugmachalar uchun u yomon ishlashi mumkin.

Modulli hashing, shuningdek, suzuvchi nuqta tugmachalariga ham tegishli. Agar kalitlar kichik diapazonga tegishli bo'lsa, siz ularni 0 va 1, 2 w oralig'idagi raqamlarga w-bit sonlarini olish uchun o'lchashingiz mumkin va modulli hash funktsiyasidan foydalanishingiz mumkin. Yana bir variant - modulli hash funktsiyasining operandasi sifatida (agar mavjud bo'lsa) ikkilik kalitlarning vakili sifatida foydalanish.

Modulli xeshlash barcha holatlarda, kalitlarni tashkil etuvchi bitlarga kirish imkoniyati mavjud bo'lganda, ular mashinalar so'zi bilan ifodalangan butun sonlar, mashina so'zida keltirilgan belgilar ketma-ketligi yoki boshqa mumkin bo'lgan variantlardan qat'iy nazar foydalaniladi. Mashina so'ziga kiritilgan tasodifiy belgilar ketma-ketligi tasodifiy butun sonlar bilan bir xil emas, chunki kodlashda hamma bitlardan foydalanilmaydi. Ammo bu ikkala turni (va har qanday boshqa turdagi mashina so'ziga sig'adigan kodlangan) kichkina jadvalda tasodifiy indekslarga o'xshash qilish mumkin.

Modulli xeshlar uchun asosiy raqamni tanlashning asosiy sababi M hash jadvali sifatida sek. 14.3. 7-bitli kodlash bilan belgilar haqidagi ma'lumotlarning ushbu misolida, kalit bazasi bo'lgan raqam sifatida izohlanadi - kalitdagi har bir belgi uchun bitta raqam. Endi so'z 1816567 raqamiga mos keladi, uni ham shunday yozish mumkin

chunki ASCII kodida n, o va w belgilari 1568 \u003d 110, 1578 \u003d 111 va 1678 \u003d 119 raqamlariga mos keladi. Ushbu turdagi kalit uchun M \u003d 64 jadval o'lchamini tanlash muvaffaqiyatsiz tugadi, chunki 64 (yoki 128) ga ko'paytiriladigan x qiymatlarga qo'shish x mod 64 qiymatini o'zgartirmaydi - har qanday kalit uchun, hash funktsiyasining qiymati bu kalitning oxirgi 6 raqamining qiymati. Albatta, yaxshi hash funktsiyasi tugmachaning barcha raqamlarini, ayniqsa belgilar tugmachalarini hisobga olishi kerak. Shunga o'xshash vaziyatlar M darajasining 2-faktorini o'z ichiga olganda yuzaga kelishi mumkin. Buning oldini olishning eng oson yo'li M kabi bosh tanlamoqdir.