Mustaqil ishi mavzu: Ma’lumotlarni xeshlash argoritmlari

Xeshlash(ba'zan "hashing", ingliz xeshlash) - deterministik algoritm yordamida ixtiyoriy uzunlikdagi kirish ma'lumotlar massivini belgilangan uzunlikdagi chiqish bit qatoriga aylantirish. Bunday transformatsiyalar ham deyiladi hash funktsiyalari yoki konvolyutsiya funktsiyalari, va ularning natijalari deyiladi hash, hash kodi yoki xabar xulosasi(inglizcha) xabar dayjesti). Agar ikkita satrda turli xil xesh kodlari bo'lsa, satrlar boshqacha bo'lishi kafolatlanadi; agar ular bir xil bo'lsa, satrlar bir xil bo'lishi mumkin.
Xeshlash assotsiativ massivlarni yaratish, bir qator ma'lumotlar to'plamida dublikatlarni qidirish, ma'lumotlar to'plamlari uchun etarlicha noyob identifikatorlarni yaratish, saqlash yoki uzatish paytida tasodifiy yoki qasddan xatolarni aniqlash uchun nazorat yig'indisi, xavfsizlik tizimlarida parollarni saqlash uchun ishlatiladi (bu holda kirish parollar joylashgan xotira maydoniga , parolni o'zi tiklashga imkon bermaydi), elektron imzoni yaratishda (amalda, ko'pincha imzolangan xabarning o'zi emas, balki uning xesh tasviri).
Umumiy holatda, xesh funktsiyasi qiymatlari soni kirish massiv parametrlaridan kamroq bo'lganligi sababli manba ma'lumotlari va xesh-kod o'rtasida birma-bir yozishmalar mavjud emas; Turli xil tarkibga ega ko'plab massivlar mavjud, lekin bir xil xesh kodlarini beradi - to'qnashuvlar. To'qnashuvlar ehtimoli xesh funktsiyalarining sifatini baholashda muhim rol o'ynaydi.
Turli xil xususiyatlarga ega (bit chuqurligi, hisoblash murakkabligi, kriptografik quvvat va boshqalar) ko'plab xeshlash algoritmlari mavjud. U yoki bu xesh-funktsiyani tanlash hal qilinayotgan muammoning o'ziga xos xususiyatlari bilan belgilanadi. Xesh-funksiyalarning eng oddiy misollari checksum yoki CRC hisoblanadi.
Katta fayllarni qidirish bilan bog'liq birinchi jiddiy ish Uesli Petersonning maqolasi edi. V. Uesli Peterson ) 1957 yil IBM tadqiqot va ishlanmalar jurnalida, unda u ochiq manzilni aniqlagan va shuningdek, o'chirishda ishlashning pasayishiga ishora qilgan. Olti yil o'tgach, Verner Buxgoltsning ishi nashr etildi (nemis. Verner Buchholz ), hash funktsiyalari bo'yicha keng qamrovli tadqiqotlar olib bordi. Keyingi bir necha yil ichida xeshlash keng tarqalgan bo'lib qo'llanildi, ammo muhim ish nashr etilmadi.
1967 yilda zamonaviy ma'noda xeshlash Gerbert Xellermanning "Raqamli hisoblash tizimlarining printsiplari" kitobida eslatib o'tilgan. 1968 yilda Robert Morris Robert Morris ) ACM Communications-da xeshlash bo'yicha katta sharhni chop etdi, bu ish ilmiy muomalaga xeshlash tushunchasini kirituvchi va ilgari faqat mutaxassislar jargonida ishlatilgan "xesh" atamasini tuzatuvchi asosiy nashr hisoblanadi.
1990-yillarning boshlariga qadar rus tilidagi adabiyotda Andrey Ershovning ishi tufayli xeshlash so'zi "hashing" atamasiga ekvivalent sifatida ishlatilgan. "tartibga solish", va to'qnashuvlar uchun "nizo" atamasi ishlatilgan (Ershov 1956 yildan beri "tartibga solish" dan foydalanmoqda; Wirthning 1989 yildagi "Algoritmlar va ma'lumotlar tuzilmalari" kitobining rus tilidagi nashrida ham "tartibga solish" atamasi qo'llaniladi). Usulni ruscha so'z bilan nomlash ham taklif qilindi "okroshka". Biroq, bu variantlardan hech biri ildiz otmagan va "hashing" atamasi asosan rus tilidagi adabiyotda qo'llaniladi.
Xesh funksiyalarning turlari
Yaxshi xesh funktsiyasi ikkita xususiyatga javob berishi kerak:
Tez hisoblang;
To'qnashuvlar sonini minimallashtiring
Aytaylik, aniqlik uchun kalitlar soni va xesh funksiyasi har xil qiymatlarga ega emas:
“Yomon” xesh-funksiyaga misol sifatida, sonning yigirma xonali kvadratining o‘rtasidan tanlangan uchta raqamga ega o‘n xonali natural songa mos keladigan funksiyani keltirishimiz mumkin. Ko'rinishidan, xesh-kod qiymatlari "000" va "999" o'rtasida teng taqsimlanishi kerak, ammo haqiqiy ma'lumotlar uchun bu usul faqat tugmachalarda chap yoki o'ngda ko'p sonli nol bo'lmasa mos keladi.
Biroq, ko'plab xesh-funksiyalar asoslangan bir nechta sodda va ishonchli usullar mavjud.
Bo'linishga asoslangan xesh funktsiyalari
Birinchi usul - biz xesh sifatida bo'linishning qolgan qismini ishlatamiz, bu erda barcha mumkin bo'lgan xeshlar soni:
Shu bilan birga, agar qiymat juft bo'lsa, funktsiyaning qiymati juft bo'ladi, agar u juft bo'lsa va toq bo'lsa - toq bo'lsa, bu fayllardagi ma'lumotlarning sezilarli siljishiga olib kelishi mumkin. Bundan tashqari, kompyuterni baza darajasi sifatida ishlatmang, chunki xesh kodi o'ng tomonda joylashgan raqamning faqat bir nechta raqamiga bog'liq bo'ladi, bu ko'p sonli to'qnashuvlarga olib keladi. Amalda, odatda, oddiy birini tanlaydi - ko'p hollarda bu tanlov juda qoniqarli.
Ikki polinom moduliga bo'linishga asoslangan xeshlash usuli haqida ham aytish kerak. Bu usulda u ham ikkining darajasi bo'lishi kerak va ikkilik kalitlar () ko'phadlar sifatida ifodalanadi. Bunday holda, oldindan tanlangan darajali polinomga bo'linishning qolgan qismi sifatida olingan polinom koeffitsientlarining qiymatlari xesh-kod sifatida qabul qilinadi:
To'g'ri tanlov bilan bu usul deyarli bir xil kalitlar o'rtasida to'qnashuvlar yo'qligini ta'minlaydi.
Multiplikativ xeshlash sxemasi
Ikkinchi usul esa bilan ba'zi bir butun son doimiy kopmasini tanlashdan iborat, bu erda mashina so'zi bilan ifodalangan qiymatlar soni (IBM PC kompyuterlarida). Keyin biz shaklning xesh funktsiyasini olamiz:
Bunday holda, ikkilik sanoq tizimiga ega kompyuterda ikkining kuchi va mahsulotning o'ng yarmining yuqori bitlaridan iborat bo'ladi.
Bu ikki usulning afzalliklari qatorida shuni ta'kidlash joizki, ular haqiqiy kalitlarning tasodifiy emasligidan foydalanadilar, masalan, agar kalitlar arifmetik progressiya bo'lsa (aytaylik, "NAME1", "NAME2" nomlari ketma-ketligi. , "NAME3"). Multiplikativ usul arifmetik progressiyani har xil xesh qiymatlarining taxminan arifmetik progressiyasiga ko'rsatadi, bu tasodifiy vaziyatga nisbatan to'qnashuvlar sonini kamaytiradi.
Ushbu usulning bir o'zgarishi oltin nisbatning xususiyatlariga asoslangan Fibonachchi xeshingidir. Bu erda eng yaqin butun son bilan ko'paytiriladi
O'zgaruvchan uzunlikdagi satrlarni xeshlash
Yuqoridagi usullar, agar biz bir nechta so'zlardan tashkil topgan kalitlarni yoki o'zgaruvchan uzunlikdagi kalitlarni hisobga olishimiz kerak bo'lsa ham qo'llaniladi. Misol uchun, modul qo'shish yoki XOR operatsiyasidan foydalanib, so'zlarni birlashtirishingiz mumkin. Ushbu printsip asosida ishlaydigan algoritmlardan biri Pearson xesh funktsiyasidir.
Universal xeshlash
Universal xeshlash universal xeshlash ) xeshlash deyiladi, bunda bitta maxsus xesh-funksiya ishlatilmaydi, lekin tasodifiy algoritm bo'yicha berilgan oiladan tanlov amalga oshiriladi. Umumjahon xeshlashdan foydalanish odatda kam sonli to'qnashuvlarga olib keladi. Universal xeshlash ko'plab ilovalarga ega, masalan, xesh-jadvallarni va kriptografiyani amalga oshirishda.
Faraz qilaylik, biz kalitlarni bo'sh joydan raqamlarga o'tkazmoqchimiz. Kirishda algoritm oldindan noma'lum bo'lgan o'lchamli ma'lum ma'lumotlar to'plamini oladi. Odatda, xeshlashning maqsadi eng kam sonli to'qnashuvlarni olishdir, bu har qanday maxsus xesh funktsiyasi yordamida erishish qiyin.
Bunday muammoning yechimi sifatida universal oila deb ataladigan ma'lum bir to'plamdan tasodifiy funktsiyani tanlash mumkin.
To'qnashuvlarni bartaraf etish usullari
Yuqorida aytib o'tilganidek, xesh-funktsiyaning to'qnashuvi (ba'zan to'qnashuv yoki to'qnashuv) bir xil xesh kodlarini beradigan ikkita kirish ma'lumotlar blokidir.
hash jadvallarida
Xeshlash haqidagi dastlabki yozmalarning aksariyati xesh-jadvallardagi to'qnashuvlarni bartaraf etish usullari haqida edi, chunki xesh funktsiyalari katta fayllarni qidirish uchun ishlatilgan. Xesh-jadvallarda ikkita asosiy usul qo'llaniladi:
Zanjir usuli (to'g'ridan-to'g'ri bog'lash usuli)
ochiq adreslash usuli
Birinchi usul - har bir xesh qiymati uchun bittadan bog'langan ro'yxatlarni saqlash. Ro'yxat bir xil xesh-kod qiymatini beradigan kalitlarni saqlaydi. Umuman olganda, agar bizda kalitlar va ro'yxatlar bo'lsa, ro'yxatning o'rtacha hajmi bo'ladi va xeshlash ketma-ket qidiruvga nisbatan o'rtacha ish hajmini taxminan bir omilga kamaytiradi.
Ikkinchi usul shundan iboratki, jadval massivi kalit-qiymat juftlarini saqlaydi. Shunday qilib, biz havolalardan butunlay voz kechamiz va kerakli kalit yoki bo'sh joyni topmagunimizcha, jadval yozuvlarini ko'rib chiqamiz. Jadval kataklarini skanerlash ketma-ketligi zondlar ketma-ketligi deb ataladi.
Kriptografik tuz
Parollar va imzolarni qalbakilashtirishdan himoya qilishning bir necha usullari mavjud, hatto kriptoanalitik foydalanilgan xesh funktsiyasi uchun to'qnashuvlarni qanday yaratishni bilsa ham ishlaydi. Bunday usullardan biri kirish ma'lumotlariga kriptografik tuzni (tasodifiy ma'lumotlar qatori) qo'shishdir (ba'zan xesh-kodga "tuz" qo'shiladi), natijada olingan xesh-jadvallarni tahlil qilishni ancha qiyinlashtiradi. Bu usul, masalan, UNIX-ga o'xshash operatsion tizimlarda parollarni saqlash uchun ishlatiladi.
Xesh funksiyalarini qo'llash
Kriptografik xesh funksiyalari
Mavjud ko'plab xesh-funksiyalar orasida kriptografiyada ishlatiladigan kriptografik himoyalanganlarini ajratib ko'rsatish odatiy holdir, chunki ularga qo'shimcha talablar qo'yiladi. Xesh-funksiya kriptografik jihatdan xavfsiz deb hisoblanishi uchun u kriptografiyadagi xesh-funksiyalarning aksariyat ilovalari asoslangan uchta asosiy talabga javob berishi kerak:
Ushbu talablar mustaqil emas:
Qaytariladigan funktsiya birinchi va ikkinchi turdagi to'qnashuvlarga chidamli emas.
Birinchi turdagi to'qnashuvlarga chidamli bo'lmagan funksiya ikkinchi turdagi to'qnashuvlarga chidamli emas; teskarisi to'g'ri emas.
Shuni ta'kidlash kerakki, qaytarilmas xesh-funksiyalarning mavjudligi, ular uchun berilgan xesh qiymatining har qanday preimagesini hisoblash nazariy jihatdan imkonsizdir. Odatda, o'zaro bog'liqlikni topish faqat hisoblash qiyin vazifadir.
Xeshlash ko'pincha raqamli imzo algoritmlarida qo'llaniladi, bu erda xabarning o'zi shifrlangan emas, balki uning xesh-kodi hisoblash vaqtini qisqartiradi va kriptografik quvvatni oshiradi. Bundan tashqari, aksariyat hollarda parollar o'rniga ularning xesh kodlari qiymatlari saqlanadi.
Tekshirish summalari
Oddiy, juda tez va amalga oshirish oson apparat algoritmlari tasodifiy buzilishlardan, shu jumladan apparat xatolaridan himoya qilish uchun ishlatiladi. Matematika nuqtai nazaridan, bu axborotni uzatish va saqlashdagi xatolarni aniqlash uchun ishlatiladigan boshqaruv kodini hisoblaydigan xesh funktsiyasi.
Hisoblash tezligi bo'yicha u kriptografik xesh-funksiyalarga qaraganda o'nlab va yuzlab marta tezroq va apparatni bajarishda ancha sodda.
Bunday yuqori tezlikning narxi kriptografik quvvatning yo'qligi - xabarni oldindan belgilangan miqdorga moslashtirishning oson imkoniyati. Shuningdek, nazorat summalari (odatiy raqam: 32 bit) kriptografik xeshlardan (odatiy raqamlar: 128, 160 va 256 bit) kichikroq bo'lishi odatiy holdir, ya'ni beixtiyor to'qnashuvlar sodir bo'lishi mumkin.
Bunday algoritmning eng oddiy holati xabarning 32 yoki 16 bitli so'zlarga bo'linishi va ularning yig'indisi bo'lib, u, masalan, TCP/IP da qo'llaniladi.
Qoida tariqasida, bunday algoritm odatdagi apparat xatolarini kuzatish uchun talab qilinadi, masalan, ma'lum bir uzunlikdagi bir nechta ketma-ket xato bitlar. Algoritmlar oilasi deb ataladi. "Tsiklik ortiqcha kodlar" ushbu talablarga javob beradi. Bularga, masalan, Ethernet qurilmalarida va ZIP ma'lumotlarini siqish formatida ishlatiladigan CRC32 kiradi.
Masalan, nazorat summasi asosiy matn bilan birga aloqa kanali orqali uzatilishi mumkin. Qabul qilish oxirida nazorat summasini qayta hisoblash va uzatilgan qiymat bilan solishtirish mumkin. Agar nomuvofiqlik aniqlansa, bu uzatish buzilganligini anglatadi va takrorlashni talab qilish mumkin.
Bunday holda, xeshlashning maishiy analogi, harakatlanayotganda, bagaj bo'laklari soni xotirada saqlangan texnika bo'lishi mumkin. Keyin, tekshirish uchun har bir chamadon haqida eslab qolishning hojati yo'q, lekin ularni hisoblash kifoya. Gugurt, birorta ham chamadon yo'qolmaganligini anglatadi. Ya'ni, bagaj qismlari soni uning xesh-kodidir. Ushbu usul uzatilgan ma'lumotni soxtalashtirishdan himoya qilish uchun osongina kengaytirilishi mumkin (MAC usuli). Bunday holda, xeshlash faqat xabarni jo'natuvchi va qabul qiluvchiga ma'lum bo'lgan maxfiy kalit bilan birlashtirilgan xabar ustidan kriptografik himoyalangan funktsiya tomonidan amalga oshiriladi. Shunday qilib, kriptoanalitik ushlangan xabardan kodni va xesh qiymatini tiklay olmaydi, ya'ni u xabarni soxtalashtirishga qodir bo'lmaydi (Taqlid himoyasiga qarang).
Geometrik xeshlash
geometrik xeshlash. Geometrik xeshlash) kompyuter grafikasi va hisoblash geometriyasida tekislikdagi yoki uch oʻlchamli fazodagi masalalarni yechish, masalan, nuqtalar toʻplamida eng yaqin juftlarni topish yoki bir xil tasvirlarni qidirish uchun keng qoʻllaniladigan usul. Ushbu usuldagi xesh funktsiyasi odatda ma'lum metrik bo'shliqni kiritish sifatida oladi va uni ajratadi va hujayralar panjarasini yaratadi. Bu holda jadval ikki yoki undan ortiq indeksli massiv bo'lib, grid fayli deb ataladi. grid fayli). Geometrik xeshlash ko'p o'lchovli signallar bilan ishlashda telekommunikatsiyalarda ham qo'llaniladi.
Ma'lumotlarni qidirishni tezlashtirish
Xesh-jadval - bu shakl juftlarini (kalit, xesh-kod) saqlashga imkon beruvchi va elementni qidirish, kiritish va o'chirish operatsiyalarini qo'llab-quvvatlaydigan ma'lumotlar tuzilmasi. Xesh-jadvallarning maqsadi qidirishni tezlashtirishdir, masalan, ma'lumotlar bazasida matn maydonlarini yozishda ularning xesh-kodi hisoblanishi va ma'lumotlarni ushbu xesh-kodga mos keladigan bo'limga joylashtirish mumkin. Keyin ma'lumotlarni qidirishda birinchi navbatda matnning xesh kodini hisoblash kerak bo'ladi va ularni qaysi bo'limda izlash kerakligi darhol ma'lum bo'ladi, ya'ni butun ma'lumotlar bazasini qidirish kerak bo'lmaydi, faqat uning bo'limlaridan biri (bu qidiruvni sezilarli darajada tezlashtiradi).
Bunday holda, xeshlashning uy analogi lug'atdagi so'zlarni alifbo tartibida joylashtirish bo'lishi mumkin. So'zning birinchi harfi uning xesh-kodi bo'lib, qidiruvda biz butun lug'atni emas, balki faqat kerakli harfni ko'rib chiqamiz.