Kriptografik xesh funksiyasi. Xesh nima va u nima uchun

Guruch. 14.3.
Ushbu jadvalning har bir satrida quyidagilar keltirilgan: 3 harfli so'z, bu so'zning sakkizlik va o'nlik yozuvlarda 21 bitli ASCII ko'rinishi va 64 va 31 jadval o'lchamlari uchun standart modulli xesh funktsiyalari (eng o'ngdagi ikkita ustun). 64-jadvalning o'lchami istalmagan natijalarga olib keladi, chunki xesh qiymatini olish uchun kalitning faqat o'ngdagi eng ko'p bitlari ishlatiladi va oddiy til so'zlaridagi harflar notekis taqsimlanadi. Misol uchun, y harfi bilan tugaydigan barcha so'zlarning xesh qiymati 57 ga teng. Aksincha, 31 ning oddiy qiymati yarmidan ko'p bo'lgan jadvalda kamroq to'qnashuvlarga olib keladi.
Modulli xeshlashni amalga oshirish juda oson, faqat jadval o'lchami tub son bo'lishi kerak. Ba'zi ilovalar uchun siz kichik ma'lum tub sonlar bilan kifoyalanishingiz yoki kerakli jadval hajmiga yaqin bo'lgan ma'lum tub sonlar ro'yxatiga qarashingiz mumkin. Masalan, 2 t - 1 ga teng sonlar tub bo'lganda t = 2, 3, 5, 7, 13, 17, 19 va 31(va t ning boshqa qiymatlari uchun< 31 ): это известные простые числа Мерсенна. Чтобы динамически распределить таблицу нужного размера, нужно вычислить простое число, близкое к этому значению. Такое вычисление нетривиально (хотя для этого и существует остроумный алгоритм, который будет рассмотрен в части 5), поэтому на практике обычно используют таблицу заранее вычисленных значений (см. рис. 14.4). Использование модульного хеширования - не единственная причина, по которой размер таблицы стоит сделать простым числом; еще одна причина рассматривается в разделе 14.4.


Guruch. 14.4.
2 n dan kichik bo'lgan eng katta tub sonlar jadvali  , jadval o'lchami tub son bo'lishini xohlasangiz, xesh-jadvalni dinamik ravishda ajratish uchun ishlatilishi mumkin. Qoplangan diapazondagi har qanday ijobiy qiymat uchun ushbu jadvaldan 2 martadan kam farqli tub sonni aniqlash uchun foydalanish mumkin.
Butun sonli kalitlarni boshqarishning yana bir usuli - multiplikativ va modulli usullarni birlashtirish: siz kalitni 0 dan 1 gacha bo'lgan doimiyga ko'paytirishingiz kerak, so'ngra M bo'linish modulini bajarishingiz kerak. Boshqacha qilib aytganda, siz funktsiyadan foydalanishingiz kerak. M qiymatlari va kalitning samarali radikali o'rtasida nazariy jihatdan anomal xatti-harakatlarga olib kelishi mumkin bo'lgan bog'liqlik mavjud, ammo agar siz a ning ixtiyoriy qiymatidan foydalansangiz, haqiqiy dasturda deyarli hech qanday muammo bo'lmaydi. Ko'pincha ph = 0,618033 ... (oltin nisbat) qiymati a sifatida tanlanadi.
Ushbu mavzu bo'yicha ko'plab boshqa o'zgarishlar, xususan, siljish va maskalangan ta'kidlash kabi samarali mashina ko'rsatmalari bilan amalga oshirilishi mumkin bo'lgan hash funktsiyalari o'rganildi (havolalar bo'limiga qarang).
Belgilar jadvallaridan foydalanadigan ko'pgina ilovalarda kalitlar raqamlar emas va qisqa bo'lishi shart emas; ko'pincha ular juda uzun bo'lishi mumkin bo'lgan harf-raqamli satrlardir. Xo'sh, averylongkey kabi so'z uchun hash funktsiyasini qanday hisoblash mumkin?
7 bitli ASCII kodida bu so'z 84 bitli raqamga mos keladi \ begin (align *) 97 \ cdot 128 ^ (11) & + 118 \ cdot 128 ^ (10) + 101 \ cdot 128 ^ (9) + 114 \ cdot 128 ^ (8) + 121 \ cdot 128 ^ (7) \\ & + 108 \ cdot 128 ^ (6) + 111 \ cdot 128 ^ (5) + 110 \ cdot 128 ^ (4) + 103 \ cdot 128 ^ (3) \\ & + 107 \ cdot 128 ^ (2) + 101 \ cdot 128 ^ (1) + 121 \ cdot 128 ^ (0), \ end (hizalang *),
Bu ko'pchilik kompyuterlarda oddiy arifmetik funktsiyalarni bajarish uchun juda katta. Va ko'pincha siz uzoqroq kalitlarni boshqarishingiz kerak bo'ladi.
Uzun tugmalar uchun modulli xesh funktsiyasini hisoblash uchun ular bo'laklarga bo'linadi. Siz modul funksiyasining arifmetik xususiyatlaridan foydalanishingiz va Horner algoritmidan foydalanishingiz mumkin (4.9 “Mavhum ma’lumotlar turlari” bo‘limiga qarang). Bu usul kalitlarga mos keladigan raqamlarni yozishning boshqa usuliga asoslangan. Ushbu misol uchun quyidagi ifodani yozing: \ begin (align *) (((((((((97 \ cdot 128 ^ (11)) & + 118) \ cdot 128 ^ (10) + 101) \ cdot 128 ^) (9) + 114) \ cdot 128 ^ (8) + 121) \ cdot 128 ^ (7) \\ & + 108) \ cdot 128 ^ (6) + 111) \ cdot 128 ^ (5) + 110) \ cdot 128 ^ (4) + 103) \ cdot 128 ^ (3) \\ & + 107) \ cdot 128 ^ (2) + 101) \ cdot 128 ^ (1) + 121. \ end (hizalash *)
Ya'ni, satrning belgilar kodlashiga mos keladigan o'nlik sonni chapdan o'ngga qarab, to'plangan qiymatni 128 ga ko'paytirish va keyingi belgining kod qiymatini qo'shish orqali hisoblash mumkin. Uzoq satr bo'lsa, bu hisoblash usuli oxir-oqibat kompyuter tasavvur qilganidan kattaroq raqamga olib keladi. Biroq, bu raqam kerak emas, chunki uni M ga bo'lish uchun faqat (kichik) qoldiq talab qilinadi. Natijani hatto katta to'plangan qiymatni saqlamasdan ham olish mumkin, chunki hisoblashda istalgan vaqtda siz M ning ko'paytmasini tashlab qo'yishingiz mumkin - har safar ko'paytirish va qo'shishni amalga oshirganingizda, faqat M bo'linish modulining qolgan qismini saqlashingiz kerak. Natija xuddi biz hisoblash imkoniga ega bo'lgandek bo'ladi. uzun raqam va keyin bo'linish amalga oshirish (qarang. Mashq 14.10). Ushbu kuzatish uzoq satrlar uchun modulli xesh-funktsiyalarni hisoblashning to'g'ridan-to'g'ri arifmetik usuliga olib keladi - 14.1-dasturga qarang. Bu dastur bitta yakuniy hiyla ishlatadi: 128 ta asos o'rniga 127 tub sonini ishlatadi. Ushbu o'zgarish sababi keyingi paragrafda muhokama qilinadi.
Xesh-funksiyalarni Horner usuli (kalitdagi har bir belgi uchun bir yoki ikkita arifmetik amal) yordamida modulli xeshlash bilan bir xil narxda hisoblashning ko'plab usullari mavjud. Tasodifiy kalitlar uchun bu usullar deyarli bir xil, ammo haqiqiy kalitlar kamdan-kam hollarda tasodifiy bo'ladi. Haqiqiy kalitlarni arzon narxlarda tasodifiylashtirish qobiliyati tasodifiy xesh algoritmlarini ko'rib chiqishga olib keladi, chunki bizga kalit taqsimotidan qat'i nazar, jadvalda tasodifiy indekslarni yaratadigan hash funktsiyalari kerak. Tasodifiylashtirish oson, chunki modulli xeshlash taʼrifiga tom maʼnoda amal qilish shart emas – M dan kichik butun sonni hisoblash uchun kalitning barcha raqamlaridan foydalanish kifoya.