Xesh funktsiyasi nima? Kriptografik xesh funktsiyalari

Shakl 14.4.

Ikki n dan kam tub sonlarning jadvali, stolning o'lchami bosh bo'lishi uchun zarur bo'lganda, hash stolni dinamik ravishda tarqatish uchun ishlatilishi mumkin. Berilgan diapazondagi har qanday ijobiy qiymat uchun ushbu jadvaldan undan 2 martaga kam farq qiluvchi ko'payishni aniqlash uchun foydalanish mumkin.

Butun sonli tugmachalarni qayta ishlashning yana bir varianti multiplikativ va modulli usullarni birlashtirishdir: siz kalitni 0 va 1 oralig'idagi doimiyga ko'paytirishingiz kerak, keyin M. bo'linish modulini bajaring. Boshqacha aytganda, siz funktsiyadan foydalanishingiz kerak. Nazariy jihatdan g'ayritabiiy xatti-harakatlarga olib kelishi mumkin bo'lgan qadriyatlar, M va kalitlarni raqamlash tizimining samarali bazasi o'rtasida bog'liqlik mavjud, ammo agar siz a-ning ixtiyoriy qiymatidan foydalansangiz, haqiqiy dasturda har qanday muammo bo'lmaydi. Ko'pincha f \u003d 0.618033 ... (oltin nisbat) ning qiymati a sifatida tanlanadi.

Ushbu mavzudagi boshqa ko'plab o'zgarishlar o'rganildi, xususan, siljitish va niqobni tanlash kabi samarali mashina ko'rsatmalaridan foydalanib bajarilishi mumkin bo'lgan hash funktsiyalari (bog'lanishlar bo'limiga qarang).

Belgilar jadvalidan foydalanadigan ko'plab dasturlarda kalitlar raqam emas va ular qisqa bo'lishi shart emas; tez-tez bu juda uzun bo'lishi mumkin bo'lgan alfanumerik raqamlardir. Averylongkey kabi so'z uchun hash funktsiyasini qanday hisoblash mumkin?

7 bitli ASCII kodida bu so'z 84 bitli raqamga to'g'ri keladi \\ boshlash (tekislang *) 97 \\ cdot 128 ^ (11) va + 118 \\ cdot 128 ^ (10) + 101 \\ cdot 128 ^ (9) + 114 \\ ^ (3) \\\\ & + 107 \\ cdot 128 ^ (2) + 101 \\ cdot 128 ^ (1) + 121 \\ cdot 128 ^ (0), \\ end (tekislang *),

ko'pgina kompyuterlar bilan odatiy arifmetik funktsiyalarni bajarish uchun juda katta. Va ko'pincha siz uzoqroq tugmachalarni qayta ishlashingiz kerak.

Uzoq tugmachalar uchun modulli hash funktsiyasini hisoblash uchun ular qismlarga bo'laklarga aylantiriladi. Modul funktsiyasining arifmetik xususiyatlaridan foydalanishingiz va Horner algoritmidan foydalanishingiz mumkin (4.9 "Mavhum ma'lumot turlari" bo'limiga qarang). Ushbu usul tugmachalarga mos keladigan raqamlarni yozishning boshqa usuliga asoslangan. Ko'rib chiqilayotgan misol uchun biz quyidagi ifodani yozamiz: \\ boshlamoq (tekislang *) (((((((((((((((97) cdot 128 ^ (11)) 128) (+) 118) \\ cdot 128 ^ (10) + 101)) 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 (tekislang *)

Ya'ni, satrni belgilar kodlashiga mos keladigan o'nlik raqamni chapdan o'ngga qarab ko'rib chiqishda, to'plangan qiymatni 128 ga ko'paytirganda va keyingi belgining kod qiymatini qo'shganda hisoblash mumkin. Uzun simli holatda bu hisoblash usuli oxir-oqibat umuman kompyuterda namoyish etilishi mumkin bo'lganidan kattaroq songa olib keladi. Ammo bu raqam kerak emas, chunki uning M.ga bo'linishidan faqat kichik (kichik) qismi talab qilinadi.Natijani katta to'plangan qiymatni saqlamasdan olish mumkin, chunki hisoblash paytida istalgan vaqtda, siz M ga ko'paygan sonni tashlab yuborishingiz mumkin - har safar ko'paytirsangiz va qo'shsangiz, siz M. bo'linish modulining faqat qolgan qismini saqlashingiz kerak bo'ladi, natijada biz uzoq raqamni hisoblash va keyin bo'linishni amalga oshirish imkoniga ega bo'lgandek bo'lamiz (qarang). mashq 14.10). Ushbu kuzatish uzun simlar uchun modulli xesh funktsiyalarini hisoblash uchun to'g'ridan-to'g'ri arifmetik usulga olib keladi - 14.1 dasturiga qarang. Ushbu dasturda yana bitta, oxirgi hiyla qo'llaniladi: baza 128 o'rniga, u 127 raqamini ishlatadi. Ushbu o'zgarish sababi keyingi paragrafda muhokama qilinadi.

Horner (Horner) usuli yordamida modulli xeshlash bilan bir xil narxda xesh funktsiyalarini hisoblashning ko'p usullari mavjud (har bir belgi uchun bitta yoki ikkita arifmetik amallar). Tasodifiy kalitlar uchun ushbu usullar deyarli bir-biridan farq qilmaydi, ammo haqiqiy kalitlar kamdan-kam hollarda tasodifiydir. Kichkina narxga haqiqiy kalitlarni tasodifiy ko'rish qobiliyati tasodifiy xeshlash algoritmlarini ko'rib chiqishga olib keladi, chunki biz kalitlarning taqsimlanishidan qat'i nazar, tasodifiy jadval indekslarini yaratadigan hash funktsiyalariga muhtojmiz. Tasodifiylashtirishni tashkil qilish qiyin emas, chunki modulli hashing ta'rifiga so'zma-so'z rioya qilish shart emas - faqat M dan kichik bo'lmagan butun sonni hisoblashda kalitning barcha raqamlari ishlatilishi kerak.

M \u003d 96 va a \u003d 128 (yuqorida),

M \u003d 97 va a \u003d 128 (markazda) va

M \u003d 96 va a \u003d 127 (pastki)

Birinchi holda notekis taqsimlash bu harflarning notekis ishlatilishi va jadvalning kattaligi ham, omil ham 32 ga ko'payganligi sababli notekislikni saqlashning natijasidir. Boshqa ikkita misol tasodifiy ko'rinadi, chunki stol kattaligi va omil - bu nusxa raqamlari.

14.1-dastur buni amalga oshirishning bitta usulini ko'rsatadi: 2-quvvat o'rniga oddiy bazadan va ASCII-ning mag'lubiyatiga mos keladigan butun sondan foydalanish. Shaklda 14.5 rasm. 14.5-rasmda ushbu o'zgarish odatiy simli tugmalar uchun taqsimlashni qanday yaxshilaganligi ko'rsatilgan. Nazariy jihatdan, 14.1 dasturi tomonidan yaratilgan xash qiymatlari jadval jadvallari uchun 127 ga teng bo'lgan yomon natijalar berishi mumkin (garchi amalda bu deyarli ko'rinmas bo'lishi mumkin); Tasodifiy algoritmni yaratish uchun multiplikatorning qiymatini tasodifiy tanlash mumkin. Keyinchalik samaraliroq usul - bu hisoblashda koeffitsientlarning tasodifiy qiymatlari va kalitning har bir raqami uchun turli xil tasodifiy qiymatlardan foydalanish. Ushbu yondashuv universal hashing deb nomlangan tasodifiy algoritmni taqdim etadi.

Nazariy jihatdan ideal universal hash funktsiyasi - bu M o'lchamidagi jadvalda ikkita turli xil kalitlarning to'qnashuvi ehtimoli to'liq 1 / M bo'lgan funktsiya. 14.1 dasturida a koeffitsienti sifatida foydalanish qat'iy belgilangan qiymat emas, balki tasodifiy turli xil qiymatlar ketma-ketligi modulli xeshni universal xesh funktsiyasiga o'zgartirishi isbotlanishi mumkin. Biroq, kalitdagi har bir belgi uchun yangi tasodifiy raqamni yaratish qiymati odatda qabul qilinishi mumkin emas. Amalda, 14.1 dasturida ko'rsatilgan murosaga har bir kalit belgisi uchun turli xil tasodifiy raqamlar qatorini saqlash bilan emas, balki oddiy soxta tasodifiy tartib yaratish orqali koeffitsientlarni o'zgartirish orqali erishish mumkin.

Xulosa qilish uchun: mavhum belgilar jadvalini amalga oshirish uchun xeshdan foydalanish uchun avval siz M-jadval jadvalidan kichikroq manfiy bo'lmagan butun sonlarga kalitlarni joylashtiradigan xesh-operatsiyani kiritish uchun mavhum tipli interfeysni kengaytirish kerak.

Ushbu maqolaning bir qismi sifatida sizga aytaman xesh nimanima uchun kerak, qaerda va qanday ishlatilganligi, shuningdek, eng mashhur misollar.

Axborot texnologiyalari sohasidagi ko'plab vazifalar ma'lumotlar hajmi uchun juda muhimdir. Masalan, agar siz har biringiz uchun 1 KB hajmdagi ikkita faylni va bir-biringizdan 10 GB hajmdagi ikkita faylni taqqoslashingiz kerak bo'lsa, unda bu mutlaqo boshqa vaqt. Shu sababli, qisqa va sig'imli qiymatlar bilan ishlashga imkon beradigan algoritmlar juda mashhur deb hisoblanadi.

Ushbu texnologiyalardan biri ko'p muammolarni hal qilishda o'zining amaliy dasturini topgan Hashing. Ammo, menimcha, oddiy foydalanuvchi sifatida u qanday hayvon ekanligi va u nimaga tegishli ekanligi hali ham aniq emas. Shuning uchun, bundan keyin hammasini sodda so'zlar bilan tushuntirishga harakat qilaman.

Izoh: Material oddiy foydalanuvchilar uchun mo'ljallangan va ko'pgina texnik jihatlarni o'z ichiga olmaydi, ammo asosiy tanishish uchun bu etarli emas.

Xesh yoki xesh nima?

Shartlardan boshlayman.