Hash algoritmlari
- Axborot xavfsizligi
Men ishonganimdek, ko'pchilik 2007 yildan buyon AQSh Milliy Standartlar va Texnologiyalar Instituti (NIST) SHA-1 o'rnini bosuvchi xash algoritmini va SHA-2 oilaviy algoritmlarini ishlab chiqish bo'yicha tanlov o'tkazib kelayotganidan xabardor. Biroq, ushbu mavzu, ba'zi sabablarga ko'ra, saytda e'tibordan mahrum. Aslida bu meni oldingizga olib bordi. Men sizning e'tiboringizga hash algoritmlari bo'yicha bir qator maqolalarni taqdim etaman. Ushbu ketma-ketlikda biz xash funktsiyalarining asoslarini birgalikda o'rganamiz, eng mashxur xash algoritmlarini ko'rib chiqamiz, SHA-3 musobaqasi atmosferasiga kirib boramiz va unda g'olib bo'lishni da'vo qiladigan algoritmlarni ko'rib chiqamiz, albatta ularni sinab ko'ramiz. Shuningdek, iloji bo'lsa, rus tilidagi xeshlash standartlari ko'rib chiqiladi.
O'zim haqimda
Axborot xavfsizligi kafedrasi talabasi.Hashing haqida
Hozirda deyarli hech qanday kriptografik dastur xeshlashsiz to'liq bajarilmaydi.Hash funktsiyalari - bu o'zboshimchalik bilan xabar yoki ma'lumotlar majmuini, odatda ikkilik alifboda yozilgan, konvolusiya deb nomlangan ba'zi bir uzunlikdagi bit naqshiga "siqish" uchun mo'ljallangan funktsiyalar. Hash funktsiyalari statistik tajribalarda, mantiqiy qurilmalarni sinashda, tezkor qidiruv algoritmlarini tuzishda va ma'lumotlar bazalaridagi yozuvlarning yaxlitligini tekshirishda turli xil dasturlarga ega. Xash funktsiyalarining asosiy talabi argument qiymatlarini tasodifiy tanlash uchun ularning qiymatlarini taqsimlanishining bir xilligi.
Kriptografik xash funktsiyasi - bu kriptografik jihatdan kuchli bo'lgan, ya'ni kriptografik dasturlarga xos bo'lgan bir qator talablarni qondiradigan har qanday xash funktsiyasi. Kriptografiyada xash funktsiyalari quyidagi muammolarni hal qilish uchun ishlatiladi:
- ularni uzatish yoki saqlash paytida ma'lumotlar yaxlitligini boshqarish tizimlarini qurish,
- ma'lumotlar manbasini autentifikatsiya qilish.
Har qanday funktsiya xash funktsiya deb ataladi h: X -\u003e Y, har qanday xabar uchun osonlikcha hisoblash mumkin M qiymat h (M) \u003d H (konversiya) sobit bit uzunligiga ega. X - ko'plab xabarlar, Y - sobit uzunlikdagi ikkilik vektorlar to'plami.
Qoida tariqasida, xash funktsiyalari bir bosqichli siqishni funktsiyalari deb nomlanadi y \u003d f (x 1, x 2) ikkita o'zgaruvchi, qaerda x 1, x 2 va y - uzunlikning ikkilik vektorlari m, n va n navbati bilan va n konvulsiya uzunligi va m - xabarlar blokining uzunligi.
Qiymatni olish uchun h (M) xabar avval uzunlik bloklariga bo'linadi m (bu holda, agar xabar uzunligi ko'p bo'lmagan bo'lsa m keyin oxirgi blokni to'ldirish uchun qandaydir maxsus usul bilan to'ldiriladi), so'ngra hosil bo'lgan bloklarga M 1, M 2, .., M N Quyidagi ketma-ketlikni hisoblash tartibini qo'llang:
H o \u003d v,
H i \u003d f (M i, H i-1), i \u003d 1, .., N,
h (M) \u003d H N
Bu yerda v - ba'zi bir doimiy, ko'pincha boshlang'ich vektori deb nomlanadi. U tashqariga chiqadi
turli sabablarga ko'ra va maxfiy doimiy yoki tasodifiy ma'lumotlar to'plami bo'lishi mumkin (masalan, sana va vaqt namunasi).
Ushbu yondashuv bilan xash funktsiyasining xususiyatlari bir bosqichli qisqarish funktsiyasining xususiyatlari bilan to'liq aniqlanadi.
Kriptografik xash funktsiyalarining ikkita muhim turi mavjud - kalit va kalitsiz. Asosiy xash funktsiyalari xabarni tasdiqlash kodlari deb nomlanadi. Ular qo'shimcha vositalarsiz, bir-biriga ishonadigan foydalanuvchilar bilan ma'lumotlar manbalarining to'g'riligini va tizimlardagi ma'lumotlarning yaxlitligini kafolatlashga imkon beradi.
Kalitsiz xash funktsiyalari xatolarni aniqlash kodlari deb ataladi. Ular ma'lumotlarning yaxlitligini kafolatlash uchun qo'shimcha vositalar (masalan, shifrlash) yordamida imkon yaratadilar. Ushbu xesh funktsiyalari ishonchli va ishonchli foydalanuvchilarga ega tizimlarda ishlatilishi mumkin.
Statistik xususiyatlar va talablar to'g'risida
Yuqorida aytib o'tganimdek, xash funktsiyalari uchun asosiy talab - bu argument qiymatlarini tasodifiy tanlash uchun ularning qiymatlarini bir xil taqsimlash. Kriptografik xash funktsiyalari uchun argumentning ozgina o'zgarishi funktsiya qiymatini juda o'zgartirishi ham muhimdir. Bunga qor ko'chkisi ta'siri deyiladi.
Asosiy xashlash funktsiyalari quyidagi talablarga ega:
- uydirma mumkin emasligi,
- modifikatsiyaning mumkin emasligi.
Birinchi talab shuni anglatadiki, to'g'ri katlama qiymatiga ega xabarni topish juda qiyin. Ikkinchisi, ma'lum bir katlama qiymati bilan ma'lum bir xabarni to'g'ri katlama qiymati bilan mos keladigan yuqori murakkablik.
Kalitsiz funktsiyalarga quyidagi talablar qo'yiladi:
- bir tomonlama,
- to'qnashuvlarga qarshilik,
- ikkinchi oldingi rasmni topishga qarshilik.
Bir yo'nalishlilik - bu konvolyutsiyaning qiymati bo'yicha xabarni topishning yuqori murakkabligi deb tushuniladi. Shuni ta'kidlash kerakki, hozirda tasdiqlangan bir yo'nalishli foydalanilgan xash funktsiyalari mavjud emas.
To'qnashuv qarshiligi bir xil katlama qiymatlari bo'lgan bir juft xabarni topish qiyinligi sifatida tushuniladi. Odatda bu kriptoanalizatorlarning to'qnashuvlarni qurish usulini topishi algoritm eskirganligi va uni tez orada almashtirish zarurligi to'g'risida birinchi signal bo'lib xizmat qiladi.
Ikkinchi premajni topishga qarshilik ma'lum konvolyutsiya qiymatiga ega bo'lgan xabar uchun bir xil konvolusiya qiymatiga ega bo'lgan ikkinchi xabarni topishning murakkabligi sifatida tushuniladi.
Bu kelajakda biz uchun foydali bo'lgan nazariy qism edi ...
Mashhur xash algoritmlari haqida
Algoritmlar CRC16 / 32 - summa (kriptografik konversiya emas).
Algoritmlar MD2 / 4/5/6... Ular RSA algoritmi mualliflaridan biri Ron Rivestning yaratilishi.
MD5 algoritmi bir paytlar juda mashhur bo'lgan, ammo buzish uchun dastlabki shartlar to'qsoninchi yillarning oxirlarida paydo bo'lgan va endi uning mashhurligi tezda pasayib bormoqda.
MD6 algoritmi konstruktiv nuqtai nazardan juda qiziqarli algoritmdir. U SHA-3 tanloviga nomzod bo'lgan, ammo afsuski, mualliflar uni standart darajasiga etkazishga ulgurmagan va bu algoritm ikkinchi bosqichga o'tgan nomzodlar ro'yxatida yo'q.
Hukmdor algoritmlari SHA Hozirda keng qo'llanilayotgan algoritmlar. SHA-1 dan SHA-2 versiya standartlariga faol o'tish mavjud. SHA-2 - SHA224, SHA256, SHA384 va SHA512 algoritmlarining umumiy nomi. SHA224 va SHA384 asosan SHA256 va SHA512 analoglari, faqat konvolyutsiyani hisoblagandan so'ng undagi ba'zi ma'lumotlar bekor qilinadi. Ular faqat eski jihozlar bilan mosligini ta'minlash uchun ishlatilishi kerak.
Rossiya standarti - GOST 34.11-94.
Keyingi maqolada
MD algoritmlariga umumiy nuqtai (MD4, MD5, MD6).
Adabiyot
A.P. Alferov, Kriptografiya asoslari.
Bryus Shnayer, amaliy kriptografiya.
Katta ma'lumotlar orasidan kerakli elementni topish masalasini hal qilish uchun algoritm taklif qilingan hashing (hashing - aralashtirish), unda massiv ma'lumotlarini aniqlaydigan klavishlar yaratiladi va ular asosida ma'lumotlar jadvalga yoziladi xash jadvali ... Yozib olish tugmachalari funktsiya yordamida aniqlanadi i \u003d h(kalit) deb nomlangan xash funktsiyasi ... Xashlash algoritmi xesh-jadvalda kerakli elementning o'rnini xash funktsiyasi tomonidan olingan kalitning qiymati bo'yicha aniqlaydi.
Kontseptsiya xeshlash - bu ma'lumotlar elementlarining umumiy (asosiy) to'plamini ma'lum bir xususiyatga ega bo'linmagan to'plamlarga ajratish.
Masalan, lug'at yoki ensiklopediyani oling. Bunday holda, alifbo harflari qidirish tugmachalari sifatida qabul qilinishi mumkin, ya'ni. xeshlash algoritmining asosiy elementi hisoblanadi kalit (kalit). Ko'pgina dasturlarda kalit ma'lumotlarga bilvosita murojaat qilishni ta'minlaydi.
Aslida, xeshlash - kerakli ma'lumotlarni tezda topish uchun ma'lumotlarga murojaat qilishning maxsus usuli. tugmachalar orqali .
Agar asosiy to'plam tarkibida bo'lsa N elementlar, keyin uni 2 ga bo'lish mumkin N turli pastki to'plamlar.
Hash jadvali va xash funktsiyalari
Ma'lumot elementlarining kalitlarini butun sonlar to'plamiga (jadvaldagi indekslar -) ko'rsatadigan funktsiya xash jadvali ) deyiladi aralashtirish funktsiyasi , yoki xash funktsiyasi :
men = h(kalit);
qaerda kalit - konvertatsiya qilinadigan kalit, men - natijada olingan jadval ko'rsatkichi, ya'ni. butun sonlar to'plamiga kalit xaritalar ( xash manzillari ), keyinchalik ular ma'lumotlarga kirish uchun ishlatiladi.
Biroq, bir nechta asosiy qiymatlar uchun xash funktsiyasi bir xil pozitsiya qiymatini berishi mumkin men jadvalda. Ikki yoki undan ortiq kalit bir xil indeksni (xash-manzil) oladigan holat deyiladi to'qnashuv hashing paytida.
Yaxshi xash funktsiyasi bu to'qnashuvlarni minimallashtiradigan va butun jadval bo'yicha ma'lumotlarni teng ravishda taqsimlaydigan funktsiya va mukammal xash funktsiyalari to'qnashuvlarni keltirib chiqarmaydigan funktsiya:
Hash to'qnashuvlarni hal qilishning ikkita usuli mavjud:
- chiziqli tekshirish bilan ochiq adreslash usuli bilan;
- zanjirlar usuli bilan.
Hash stol
Xash jadvali odatiy massiv bo'lib, xash funktsiyasi tomonidan berilgan noodatiy manzilga ega.
Xash tuzilishi ma'lumotlarga indeks bo'yicha tezkor to'g'ridan-to'g'ri kirishni ta'minlaydigan massivni umumlashtirish deb hisoblanadi.
Yaxshi funktsiyani tanlashda farq qiluvchi ko'plab xeshlash sxemalari mavjud h(kalit) va nizolarni hal qilish algoritmi. Haqiqiy amaliy muammoni hal etish samaradorligi sezilarli darajada tanlangan strategiyaga bog'liq bo'ladi.
Xash funktsiyalariga misollar
Siz tanlagan xash funktsiyasini hisoblash va iloji boricha kamroq to'qnashuvlarni yaratish oson bo'lishi kerak, ya'ni. jadvaldagi mavjud ko'rsatkichlar bo'yicha kalitlarni teng ravishda taqsimlashi kerak. Albatta, ma'lum bir xesh funktsiyasi tugmachalarni oldindan taqsimlanmagan taqdirda, kalitlarni to'g'ri tarqatishini aniqlash mumkin emas. Biroq, xash funktsiyasini tanlashdan oldin kalitlarning o'zi kamdan-kam hollarda ma'lum bo'lsa-da, ularning tarqalishiga ta'sir ko'rsatadigan ushbu tugmachalarning ba'zi xususiyatlari odatda ma'lum. Xash funktsiyasini o'rnatishning eng keng tarqalgan usullarini ko'rib chiqamiz.
Bo'linish usuli... Dastlabki ma'lumotlar - ba'zi bir butun kalit kalit va stol kattaligi m... Ushbu funktsiya natijasi bu tugmachani jadval kattaligi bo'yicha bo'linishning qolgan qismidir. Funktsiyaning umumiy ko'rinishi:
int h (int kaliti, int m) {
qaytish kaliti% m; // Qiymatlar
Uchun m \u003d 10 xash funktsiyasi kalitning eng kichik raqamini qaytaradi.
Uchun m \u003d 100 xash funktsiyasi tugmachaning eng kichik ikkita raqamini qaytaradi.
Qo'shimcha usulbu erda kalit belgilar qatori. Xash funktsiyasida mag'lubiyat barcha belgilar va bo'linishning qolgan qismini yig'ish orqali butun songa aylantiriladi m(odatda jadval hajmi m= 256).
int h (char * tugmasi, int m) (
To'qnashuvlar, masalan, bir xil belgilar to'plamini o'z ichiga olgan satrlarda sodir bo'ladi abc va kabina.
Ushbu usul biroz o'zgartirilishi mumkin, natijada faqat kalit qatorning birinchi va oxirgi belgilarini yig'ish orqali natijaga erishiladi.
int h (char * tugmasi, int m) (
int len \u200b\u200b\u003d strlen (kalit), s \u003d 0;
agar (len< 2) // Если длина ключа равна 0 или 1,
s \u003d kalit; // qaytish kaliti
s \u003d key + key;
Bunday holda to'qnashuvlar faqat satrlarda bo'ladi, masalan abc va amc.
O'rtacha kvadrat usuli, unda kalit kvadrat shaklida (o'zi ko'paytiriladi) va natijada olingan qiymatning bir nechta o'rta raqamlari indeks sifatida ishlatiladi.
Masalan, kalit 32 bitli butun son bo'lib, xash funktsiyasi uning kvadratining o'rtadagi 10 bitini qaytaradi:
int h (int kaliti) {
kalit \u003e\u003e \u003d 11; // Eng kam ahamiyatli bo'lgan 11 bitni bekor qiling
qaytish kaliti% 1024; // Eng kichik 10 ta bitni qaytaring
Eksklyuziv OR usuli qator tugmachalari uchun (odatda jadval kattaligi m\u003d 256). Ushbu usul qo'shimchalar uslubiga o'xshaydi, ammo u o'xshash so'zlarni ajratib turadi. Usul shundan iboratki, "eksklyuziv OR" operatsiyasi satr elementlariga ketma-ket tatbiq etiladi.
IN multiplikativ usul qo'shimcha ravishda tasodifiy haqiqiy son ishlatiladi r intervaldan. Agar ushbu mahsulot jadval o'lchamiga ko'paytirilsa m, keyin hosil bo'lgan mahsulotning butun qismi 0 dan oralig'ida qiymat beradi m–1.
int h (int kaliti, int m) {
er-xotin r \u003d tugma * rnd ();
r \u003d r - (int) r; // Ajratilgan kasr qismi
Umumiy holda, katta qiymatlarda m xash funktsiyasi tomonidan yaratilgan indekslar juda katta farq qiladi. Bundan tashqari, matematik nazariya, agar taqsimot bir xil bo'lsa, deb da'vo qiladi m asosiy son.
Ko'rib chiqilgan misollarda xash funktsiyasi men = h(kalit) faqat kalit bilan yozuvni qidirish (yoki dastlab - jadvalga qo'yish) pozitsiyasini belgilaydi kalit... Shuning uchun, aralashtirish sxemasi o'z ichiga olishi kerak nizolarni hal qilish algoritmi pozitsiyasi bo'lsa harakatlar tartibini belgilash men = h(kalit) allaqachon boshqa yozuv bilan ishg'ol qilingan yozuv bo'lib chiqadi.
U xash "Hash funktsiyasi"
Ro'yxatda topilgan.
muammolarni C ++ da hal qilishda xeshlash.Ma'lumotlarni katta hajmdagi qidirish jarayoni ko'p sonli narsalarni ko'rish va qidirish kaliti bilan taqqoslash zarurati tufayli ko'p vaqt talab etadi. Ko'rish maydonini lokalizatsiya qilish orqali qidiruvni qisqartirish mumkin. Masalan, ma'lumotlarni qidiruv tugmachasi bo'yicha saralash, ba'zi bir guruh mezonlari bo'yicha bir-birining ustiga chiqmaydigan bloklarga ajratish yoki qidiruv protsedurasini soddalashtiradigan biron bir kodni haqiqiy ma'lumotlarga muvofiq yozish.
Hozirgi vaqtda tashqi xotirada saqlanadigan ma'lumotlarga tezkor kirishni ta'minlashning keng tarqalgan usuli qo'llanilmoqda - xashlash.
Hashing (yoki hashing, inglizcha hashingMa'lum bir turdagi va o'zboshimchalik uzunlikdagi kirish ma'lumotlari massivini sobit uzunlikdagi chiquvchi bit qatoriga aylantirishdir. Bunday transformatsiyalar ham deyiladi xash funktsiyalari yoki konvolyutsiya funktsiyalari va ularning natijalari deyiladi xash, xash kodi, xash jadvali yoki hazm qilish xabarlar (inglizcha) xabar hazm qilish).
Hash stol - bu ma'lumotlar tuzilishi, bu assotsiativ massiv interfeysini amalga oshiradi, ya'ni kalit-qiymat juftlarini saqlashga va uchta operatsiyani bajarishga imkon beradi: yangi juftlikni qo'shish, topish va juftlikni kalit yordamida o'chirish operatsiyasi. Xash jadvali - bu xash funktsiyasi tomonidan ma'lum bir tartibda hosil bo'lgan massiv.
- funktsiya hisoblashda sodda bo'lishi kerak;
- funktsiya xash jadvalidagi tugmachalarni iloji boricha bir tekis taqsimlashi kerak;
- funktsiya asosiy qiymatlar orasidagi bog'liqlikni manzil qiymatlari o'rtasidagi munosabat bilan taqqoslamasligi kerak;
- funktsiya to'qnashuvlar sonini minimallashtirishi kerak, ya'ni har xil tugmalar bir xil xash qiymatiga mos keladigan holatlar (bu holda tugmachalar chaqiriladi) sinonimlar).
Bunday holda, yaxshi xash funktsiyasining birinchi xususiyati kompyuterning xususiyatlariga, ikkinchisi ma'lumotlar qiymatlariga bog'liq.
Agar barcha ma'lumotlar tasodifiy bo'lsa, xash funktsiyalari juda sodda bo'lar edi (masalan, kalitning bir nechta bitlari). Biroq, amalda tasodifiy ma'lumotlar juda kam uchraydi va siz butun kalitga bog'liq bo'lgan funktsiyani yaratishingiz kerak. Agar xash funktsiyasi to'plamni tarqatsa mumkin bo'lgan kalitlar indekslar to'plami ustida bir tekis, keyin xesh tugmachalar to'plamini samarali ravishda ajratadi. Eng yomon holat - barcha kalitlarni bitta indeksga qo'shib qo'yishdir.
To'qnashuvlar bo'lsa, xash jadvalining bir xil katagiga da'vo qiladigan kalitlarni saqlash uchun yangi joyni topish kerak. Bundan tashqari, agar to'qnashuvlarga yo'l qo'yilsa, ularning soni minimallashtirilishi kerak. Ba'zi maxsus holatlarda to'qnashuvlarning oldini olish mumkin. Masalan, agar elementlarning barcha tugmachalari oldindan ma'lum bo'lsa (yoki juda kamdan-kam hollarda o'zgarib tursa), unda siz ular uchun to'qnashuvlarsiz ularni xash jadvali kataklari orasida taqsimlaydigan bir nechta in'ektsion xash funktsiyasini topishingiz mumkin. Shunga o'xshash xash funktsiyalaridan foydalangan holda xash-jadvallar to'qnashuvni echish mexanizmiga muhtoj emas va ular bilan xash jadvallar deb nomlanadi to'g'ridan-to'g'ri manzil.
Hash jadvallari quyidagilarga mos kelishi kerak xususiyatlari.
- Xash jadvalidagi amal keshdan xash funktsiyasini hisoblash bilan boshlanadi. Olingan xash qiymati asl massivdagi indeksdir.
- Xash funktsiyasining mumkin bo'lgan qiymatlari soniga bo'lingan saqlangan massiv elementlari soni deyiladi xash jadvalni to'ldirish koeffitsienti (yuk omili) va operatsiyalarning o'rtacha bajarilish vaqti bog'liq bo'lgan muhim parametrdir.
- Qidiruv, qo'shish va o'chirish operatsiyalari o'rtacha O (1) vaqt ichida bajarilishi kerak. Biroq, bu taxmin xash jadvali indeksini qayta tiklash uchun massivlar hajmining qiymatini oshirish va xesh jadvaliga yangi juftlikni qo'shish bilan bog'liq bo'lgan mumkin bo'lgan qo'shimcha xarajatlarni hisobga olmaydi.
- To'qnashuvni hal qilish har qanday xash jadvalining muhim qismidir.
Hashlash juda ko'p miqdordagi qadriyatlarni kichik hajmdagi xotirada saqlash kerak bo'lganda va tezkor, tasodifiy yaqin kirish usuli zarur bo'lganda foydalidir. Hash jadvallari ko'pincha ma'lumotlar bazalarida ishlatiladi va ayniqsa til protsessorlari kompilyatorlar va montajchilar kabi, bu erda ular ID jadvalini qayta ishlashni tezlashtiradi. Hashlashdan kundalik hayotda foydalanish sifatida kutubxonadagi kitoblarni tematik kataloglar bo'yicha tarqatish, lug'atlarda so'zlarning birinchi harflari bilan buyurtma qilish, universitetlardagi mutaxassisliklarni shifrlash va h.k.larga misollar keltirish mumkin.
To'qnashuvni hal qilish usullari
To'qnashuvlar xash jadvallardan foydalanishni murakkablashtiradi, chunki ular xash kodlari va ma'lumotlar o'rtasidagi aniq xatlarni buzadi. Biroq, yuzaga keladigan qiyinchiliklarni engib o'tish usullari mavjud:
- zanjirlash usuli (tashqi yoki ochiq xeshlash);
- ochiq adreslash usuli (yopiq xashlash).
Zanjirlash usuli... Elementlarni yopishtirish texnologiyasi shundan iborat to'plam elementlaribir xil xash qiymatiga mos keladigan ro'yxat sifatida zanjirlangan. Joylashuv raqami i asosiy xesh qiymati i ga teng bo'lgan elementlar ro'yxatining boshiga ko'rsatkichni o'z ichiga oladi; agar to'plamda bunday elementlar bo'lmasa, NULL i holatida yoziladi. Shakl. 38.1 to'qnashuvlarni hal qilish uchun zanjirli usulning amalga oshirilishini namoyish etadi. 002 kaliti chiziqli ro'yxat bo'yicha tartiblangan ikkita qiymat tomonidan talab qilinadi.
Shakl: 38.1.
Massivdagi har bir katak bir xil kalit xash qiymatiga mos keladigan kalit-qiymat juftlarining bog'langan ro'yxati (zanjiri) ko'rsatkichidir. To'qnashuvlar oddiygina uzunlikdagi bir nechta elementlarning zanjirlariga olib keladi.
Ma'lumotlarni topish yoki yo'q qilish, berilgan kalit bilan elementni topish uchun mos keladigan zanjirning barcha elementlarini bosib o'tishni talab qiladi. Ma'lumotlarni qo'shish uchun mos keladigan ro'yxatning oxiriga yoki boshiga element qo'shishingiz kerak, agar to'ldirish koeffitsienti juda katta bo'lsa, massiv hajmini oshiring va jadvalni qayta tiklang.
Har bir element jadvalning istalgan holatiga teng ehtimollik bilan borishi va boshqa har qanday element qaerga borganidan qat'i nazar, borishi mumkin deb faraz qilsak,
Yoki Xash funktsiyasi funktsiyasi, har qanday (odatda katta) hajmdagi kirish ma'lumotlarini sobit o'lchamdagi ma'lumotlarga aylantiradi. Hashing (ba'zan r yeshuvannya, uz. Hashing) - ixtiyoriy uzunlikdagi kirish ma'lumotlari massivini belgilangan uzunlikdagi chiquvchi bit qatoriga aylantirish. Bunday transformatsiyalar ham deyiladi xash funktsiyalari yoki konversiya funktsiyalari, va ularning natijalari xash deb nomlanadi, xash kodi, hash sum, yoki xabar hazm qilish (ing.) Xabar dayjeti).
Xash funktsiyasi, xususan, ma'lumotlar tuzilmalarida - xash jadvallarida qo'llaniladi, tezkor ma'lumot olish dasturiy ta'minotida keng qo'llaniladi. Hash funktsiyalari jadvallar va ma'lumotlar bazalarini optimallashtirish uchun bir xil yozuvlarda bir xil xash qiymatlariga ega bo'lish uchun ishlatiladi. Dublikatlarni topishning bunday yondashuvi katta hajmdagi fayllarda samarali bo'ladi. DNK sekanslaridagi o'xshash joylarni topishga misol. Kriptografik xash funktsiyasi ba'zi bir kirishlarning berilgan xash qiymatiga mos kelishini tekshirishni osonlashtiradi, ammo agar kirish noma'lum bo'lsa, saqlangan xash qiymatini bilib, kirish qiymatini (yoki unga teng keladigan alternativani) qayta tiklash qasddan qiyin bo'ladi. Bu uzatilgan ma'lumotlarning yaxlitligini ta'minlash uchun ishlatiladi va xabarlarni tasdiqlashni ta'minlaydigan HMAC-lar uchun qurilish blokidir.
Xash funktsiyalari yig'indilar, raqamlar, barmoq izlari, funktsiyalarni tasodifiylashtirish, kodlar, xatolarni tuzatish va shifrlar bilan bog'liq (va ko'pincha aralashtiriladi). Ushbu tushunchalar ma'lum darajada bir-biriga to'g'ri keladigan bo'lsa-da, ularning har biri o'z doirasi va talablariga ega va har xil yo'llar bilan ishlab chiqilgan va optimallashtirilgan.
Tarix
Donald Knut xashlash bo'yicha birinchi sistematik g'oyani 1953 yil yanvarida xashni taklif qilgan IBM xodimi Xans Piter Longa beradi.
1956 yilda Arnold Doom o'zining "Kompyuterlar va avtomatika" asarida birinchi bo'lib xeshlash tushunchasini joriy qildi, chunki bugungi kunda ko'pchilik dasturchilarga ma'lum. Doom xeshlashni "lug'at muammosi" ning echimi deb hisobladi va shuningdek, qoldiq sonni bo'linish sonini xash-manzil sifatida ishlatishni taklif qildi.
Katta hajmdagi fayllarni qidirish bilan bog'liq birinchi muhim ish Uesli Petersonning maqolasi edi IBM Journal of Research and Development 1957 yilda u ochiq manzilni aniqladi, shuningdek, o'chirishda ishlashning pasayishini ta'kidladi. Olti yil o'tib, Verner Buxoltsning xash funktsiyalarini asosan o'rganib chiqqan asarlari nashr etildi. Keyingi bir necha yil ichida xeshlash keng qo'llanildi, ammo muhim ish nashr etilmadi.
1967 yilda zamonaviy ma'noda xeshlash Herbert Hellermanning Raqamli hisoblash printsiplari kitobida keltirilgan. 1968 yilda Robert Morris nashr etilgan ACM aloqalari hashing haqida ajoyib ma'lumot. Ushbu asar xeshlash tushunchasini ilmiy muomalaga kiritadigan va nihoyat mutaxassislar orasida "xash" atamasini birlashtirgan nashr hisoblanadi.
1990-yillarning boshlarida Andrey Ershov asarlari tufayli "xeshlash" atamasining ekvivalenti "burjlar" (ruscha) so'zi bo'lib, to'qnashuvlar uchun "nizo" (ruscha) atamasi ishlatilgan (Ershov 1956 yildan beri "burjlar" dan foydalangan va shu bilan birga Niklaus Virtning "Algoritmlar va ma'lumotlar tuzilmalari" (1989) kitobining rus tilidagi nashrida ushbu atama ishlatilgan.) Ammo, bu variantlarning hech biri qo'lga kiritilmagan va adabiyotda asosan "xeshlash" atamasi ishlatilgan.
Tavsif
Hashlash assotsiativ massivlarni yaratish, ma'lumotlar to'plamining nusxalarini nusxalarini izlash, ma'lumotlar to'plamlari uchun noyob identifikatorlarni yaratish, saqlash yoki uzatish paytida tasodifiy yoki qasddan qilingan xatolarni aniqlash uchun summa, xavfsizlik tizimlarida parollarni saqlash uchun ishlatiladi (bu holda xotira maydoniga kirish " parollar joylashgan xotira, parolni tiklashga imkon bermaydi), elektron imzo yaratishda (amalda ko'pincha xabarning o'zi emas, balki uning xash tasviri imzolanadi).
Umumiy holatda, xash funktsiyalari qiymatlari soni kirish qatori qiymatlari variantlari sonidan kam bo'lganligi sababli, asl ma'lumotlar va xash kodlari o'rtasida birma-bir yozishmalar mavjud emas. Turli xil tarkibga ega bo'lgan ko'plab massivlar mavjud, ammo ular bir xil xash kodlarini beradi - to'qnashuvlar. To'qnashuvlar ehtimoli xash funktsiyalarining sifatini baholashda muhim rol o'ynaydi.
Turli xil xususiyatlarga ega bo'lgan juda ko'p hash algoritmlari mavjud (bit chuqurligi, hisoblash murakkabligi, kriptografik kuch va boshqalar). U yoki bu xash funktsiyasini tanlash hal qilinayotgan muammoning o'ziga xos xususiyatlari bilan belgilanadi. Xash funktsiyalarining eng oddiy misollari bu checksum yoki CRC.
Xash funktsiyalarining turlari
Yaxshi xash funktsiyasi ikkita xususiyatni qondirishi kerak:
- Tezda hisoblang;
- To'qnashuvlar sonini minimallashtirish
Aytaylik, aniqlik uchun tugmalar soni va xash funktsiyasi har xil qiymatlardan oshmaydi:
"Yomon" xash funktsiyasiga misol sifatida raqamning yigirma xonali kvadratining o'rtasidan tanlangan o'n xonali tabiiy songa uchta raqam bilan mos keladigan c funktsiyasi kiradi. Xash kodlari qiymati "000" va "999" o'rtasida teng taqsimlanishi kerakdek tuyuladi, ammo haqiqiy ma'lumotlar uchun ushbu usul faqat tugmachalarda chap yoki o'ngda juda ko'p sonli nolga ega bo'lmagan taqdirda mos keladi.
Shu bilan birga, ko'plab xash funktsiyalari asoslangan yana bir qancha sodda va ishonchli usullar mavjud.
Bo'limga asoslangan xash funktsiyalari
Birinchi usul bu biz xash sifatida ishlatadigan narsadir - bo'linishning qolgan qismi, bu erda barcha mumkin bo'lgan xeshlarning soni:
Shu bilan birga, juftlik bilan tejash rejimi juftlik bilan, juftlik bilan birlashtirilishi aniq. Va g'alati - g'alati bilan, bu fayllardagi ma'lumotlarning sezilarli o'zgarishiga olib kelishi mumkin. Bundan tashqari, siz kompyuterning raqamli tizimidan asos sifatida foydalanmasligingiz kerak, chunki xash o'ng tomonda joylashgan raqamning bir nechta raqamlariga bog'liq bo'ladi va bu juda ko'p to'qnashuvlarga olib keladi. Amalda, odatda oddiy tanlanadi - aksariyat hollarda bu tanlov juda qoniqarli.
Ikkala log moduli bilan bo'lishga asoslangan xeshlash usuli haqida ham aytish kerak. Ushbu usulda u ikkitadan kuchga ega bo'lishi kerak va ikkilik tugmalar () polinomlar shakliga ega. Bunday holda, bo'linishning qolgan qismi sifatida olingan polinom koeffitsientlarining qiymatlari oldindan tanlangan darajadagi polinom bilan xash kodi sifatida qabul qilinadi:
To'g'ri tanlov bilan ushbu usul deyarli bir xil kalitlar o'rtasida to'qnashuvlar bo'lmasligini kafolatlaydi.
Multiplikatsion xeshlash sxemasi
Ikkinchi usul nisbatan sodda bo'lgan bir necha butun sonni doimiy ravishda tanlashdan iborat bo'lib, bu erda kompyuter so'zi ko'rinishidagi qiymatlarning mumkin bo'lgan variantlari soni (IBM PC kompyuterlarida). Keyin biz shaklning xash funktsiyasini olishimiz mumkin:
Bunday holda, ikkilik sanoq tizimiga ega bo'lgan kompyuterda u ikkitaning kuchiga ega va mahsulotning o'ng yarmining eng muhim bitlaridan iborat.
Ushbu ikkita usulning afzalliklari qatorida ular haqiqiy kalitlarning tasodifiy emasligidan foydalanganliklarini ta'kidlash kerak. Masalan, tugmalar arifmetik progressiya bo'lgan taqdirda ("name1", "name2", "name3" nomlari ketma-ketligini aytaylik). Multiplikatsion usul tasodifiy vaziyat bilan taqqoslaganda to'qnashuvlar sonini kamaytirib, arifmetik progresiyani har xil xesh qiymatlarining taxminiy arifmetik progresiyasida aks ettiradi.
Ushbu usulning o'zgarishlaridan biri bu oltin nisbati xususiyatlariga asoslangan Fibonachchi xeshidir. Bu erda, biz coprime bilan eng yaqin bo'lgan butun sonni tanlaymiz
O'zgaruvchan uzunlik satrlarini xashlash
Yuqoridagi usullar, shuningdek, o'zgaruvchan uzunlikdagi bir nechta so'zlardan yoki tugmachalardan iborat kalitlarni ko'rib chiqish zarur bo'lganda ham qo'llaniladi. Masalan, siz modulli qo'shimchalar yoki 2-modulli qo'shimchalar yordamida so'zlarni birlashtira olasiz. Ushbu printsip asosida ishlaydigan algoritmlardan biri bu Pearson xash funktsiyasi.
Pearson hashing - bu Piter Pirson tomonidan taklif qilingan algoritm. Piter Pirson) 8 bitli registrlarga ega bo'lgan protsessorlar uchun, ularning vazifasi o'zboshimchalik uzunlikdagi satr uchun xash kodini tezda hisoblashdir. Funktsiya har biri 1 bayt hajmdagi belgilardan iborat so'zni qabul qiladi va 0 dan 255 gacha bo'lgan qiymatni qaytaradi. Xash kodining qiymati kiritilgan so'zning har bir belgisiga bog'liq.
Algoritmni quyidagi psevdokod bilan tavsiflash mumkin, u mag'lubiyatni kirish sifatida qabul qiladi va almashtirish jadvalidan foydalanadi.
h: \u003d 0 Har biriga v yilda V pastadir indeks: \u003d h xor ch: \u003d T Tugatish davri Qaytish h
Algoritmning afzalliklari orasida quyidagilarni ta'kidlash lozim:
- hisoblash qulayligi;
- to'qnashuv ehtimoli eng yuqori bo'lgan kirish ma'lumotlari yo'q;
- ideal xash funktsiyasiga o'zgartirish imkoniyati.
Belgilar () dan tashkil topgan kalitlarni xeshlashning muqobil usuli sifatida hisob-kitoblarni taklif qilish mumkin
Xash funktsiyalaridan foydalanish
Hash funktsiyalari kriptografiyada, shuningdek, hash jadvallari, Bloom filtrlari va dekart daraxtlari kabi ko'plab ma'lumotlar tuzilmalarida keng qo'llaniladi.
Kriptografik xash funktsiyalari
Ko'pgina xash funktsiyalari orasida kriptografiyada ishlatiladigan kriptografik jihatdan kuchli bo'lganlarni ajratish odatiy holdir, chunki ularga qo'shimcha talablar qo'yiladi. Xash funktsiyasi kriptografik jihatdan kuchli deb hisoblanishi uchun xash funktsiyalarining kriptografiyada ko'p ishlatilishiga asoslangan uchta asosiy talabni qondirishi kerak:
- Qaytarilmaslik: berilgan xash qiymati uchun m buning uchun ma'lumotlar blokini topish imkonsiz bo'lishi kerak.
- Barqarorlik birinchi turdagi to'qnashuvlar: berilgan xabar uchun M boshqasini olish hisoblash uchun imkonsiz bo'lishi kerak xabar Buning uchun N.
- Barqarorlik ga to'qnashuvlar ikkinchi tur: bir xil xashga ega bo'lgan bir juft xabarni topish imkonsiz bo'lishi kerak.
Ushbu talablar bir-biriga bog'liq:
- Teskari funktsiya birinchi va ikkinchi turdagi to'qnashuvlar uchun beqaror.
- Birinchi turdagi to'qnashuvlarga chidamli bo'lmagan, ikkinchi turdagi to'qnashuvlarga chidamli bo'lmagan funktsiya; buning aksi to'g'ri emas.
Shuni ta'kidlash kerakki, qaytarib bo'lmaydigan xash funktsiyalari mavjudligi isbotlanmagan, buning uchun berilgan xash qiymatining biron bir oldingi qismini hisoblash nazariy jihatdan mumkin emas. Odatda, o'zaro kelishuvni topish faqat hisoblash qiyin.
Tug'ilgan kunga qilingan hujum sizga uzunlik qiymatlari bilan xash funktsiyasi uchun to'qnashuvlarni topishga imkon beradi n taxminan xash hisoblash uchun o'rtacha. shuning uchun n - bit xash funktsiyasi, agar u uchun to'qnashuvlarni topishning hisoblash murakkabligi yaqin bo'lsa, sirli hisoblanadi.
Kriptografik xash funktsiyalari uchun argumentning eng kichik o'zgarishida funktsiya qiymati katta o'zgarishi ham muhim (ko'chki effekti). Xususan, xash qiymati, hattoki argumentning alohida bitlari haqida ham ma'lumot chiqarmasligi kerak. Ushbu talab kalitni olish uchun foydalanuvchi parolini yig'adigan xeshlash algoritmlarining kriptografik kuchining kafolati hisoblanadi.
Hash tez-tez raqamli imzo algoritmlarida qo'llaniladi, bu erda xabarning o'zi shifrlanmaydi, lekin uning xeshi hisoblash vaqtini qisqartiradi va kriptografik quvvatni oshiradi. Bundan tashqari, ko'p hollarda parollar o'rniga ularning xash kodlari qiymatlari saqlanadi.
Geometrik xeshlash
Geometrik xeshlash (ing.) Geometrik xeshlash) - tekislikda yoki uch o'lchovli kosmosda masalalarni echish uchun kompyuter grafikasi va hisoblash geometriyasida keng qo'llaniladigan usul, masalan, nuqtalar to'plamida eng yaqin juftlarni topish yoki bir xil tasvirlarni izlash. Ushbu usuldagi xash funktsiyasi odatda metrik bo'shliqni kiritishda oladi va uni ajratadi, hujayralar panjarasini yaratadi. Jadval bu holda ikki yoki undan ortiq indeksli massiv bo'lib, panjara fayli (ing.) Deb nomlanadi. Grid fayli). Geometrik xeshlash telekommunikatsiyalarda ko'p o'lchovli signallar bilan ishlashda ham qo'llaniladi.
Ma'lumotlarni qidirishni tezlashtirish
Xash jadvali - bu shaklning juftlarini (kalit, xash kodi) saqlashga imkon beradigan va elementlarni izlash, qo'shish va o'chirish operatsiyalarini qo'llab-quvvatlovchi ma'lumotlar tuzilishi. Xash jadvallarning vazifasi - qidiruvni tezlashtirish, masalan, ma'lumotlar bazasidagi matn maydonlaridagi yozuvlar bo'lsa, ularning xash kodini hisoblash va ma'lumotlarni ushbu xash kodga mos keladigan qismga joylashtirish mumkin. Keyinchalik, ma'lumotlarni qidirishda birinchi navbatda matnning xashini hisoblash kerak bo'ladi va qaysi bo'limda qidirish kerakligi darhol ma'lum bo'ladi, ya'ni butun ma'lumotlar bazasi bo'yicha qidirish kerak bo'lmaydi, lekin faqat uning bo'limlaridan biri (bu qidiruvni juda tezlashtiradi).
Bu holda xeshlashning kundalik analogi lug'atda so'zlarni alfavit bo'yicha joylashtirish bo'lishi mumkin. So'zning birinchi harfi uning xash kodidir va qidirishda biz butun lug'atni ko'rib chiqmaymiz, faqat kerakli harfni ko'rib chiqamiz.
